>>306915 (OP)
Либо делай полноценный граф, либо храни в матрице куда можно идти из текущей клетки.

>>306918
Но ведь, по сути, ты советуешь одно и то же. Предположим я создам сущность node у которой будет массив ссылок на другие node. У меня проблема начинается в момент просчёта кратчайшего пути, а именно в сам момент просчёта расстояния до конечной точки. Т.к. по описанному выше принципу я не имею возможности оценить расстояние пока не пропрыгаю все ссылки, получается я потрачу много итераций для повторного "пропгрыивания" по ссылкам. А добавляя костыли в виде флагов "я здесь был, выход не здесь" алгоритм превращается в какую то непонятную кашу. Нехотеть

>>306919
Маня, почитай еще раз как работает алгоритм поиска на графе.
1) Если ты в качестве представления графа используешь матрицу (двумерный массив), то расстояние между узлами можно вычислить по теореме пифагора. А в качестве эвристики использовать дистанцию по чебышеву.
2) Если ты используешь граф, то есть строишь структуру из узлов со ссылками на соседние ноды, то в каждой ноде тебе надо хранить расстояние до соседей и идти по узлам, для расчета дистанции.

>>306919
А что касается твоей сложности, то ты в каждом узле хранишь g, которое является стоимостью маршрута от точки старта, до текущего узла. Значит ты можешь посчитать для всех узлов в которые тебе можно дальше идти стоимость, элементатарно прибавив стоимость до соседнего узла к g

>>306915 (OP)
В общем на, читай.
http://tatrix.org/public/games/dull-of-war/astar.js
http://tatrix.org/public/games/dull-of-war/

>>306922
>>306921
>>306920
В целом, я понял. Мне казалось что получится слишком много итераций пока найдётся нужная нода, но я прикинул кол-во нод и понял что зря волновался. Спасибо.

>>306920
Волнами грамотнее, потому что тогда к карте не создаётся лишних сущностей. И с изменениями карты не надо будет сразу перестраивать все пути.
Не говоря уже о куда большей функциональности. Ведь путь можно строить будет не до точки, а из зоны (заражения/видимости).

>>306929
Во первых он более тупой, ибо не используют эвристику. Во вторых он точно так же основан на графе, который ты один хуй должен построить для работы алгоритма. Заодно поясни что ты понимаешь под "лишними сущностями"

>>307055

> ехал граф через граф

Нинужно.

>>307056

> Во первых он более тупой, ибо не используют эвристику.

Тебе алгоритм или эвристику, технодебил? Ебясь с эвристикой, что получит ОП? Анально ресурсоёмкий некомпактный алгоритм, не позволяющий просто так перестраивать карту. Который из-за некомпактности, после ещё более технодебильной оптимизации, будет, периодически запихивать мобов в изменившиеся участки карты, а потом пытаться вытягивать их на старый путь. Если бы это была статистическая модель с хотя бы несколькими тысячами сущностей, это бы имело смысл, потому что в статистике всегда есть погрешность. В интерактивных форматах это ненужное говно.

И если даже очень нужно эвристику, то надо просто сделать слой карты (возможно даже свой для разных фракций, так как животные идут по одним целям, а людишки по другим), на котором отмечать вес фрагментов, по которым все ходят (вплоть до разбивания дороги, по которой слишком много ходят, но всё равно все будут ходить именно по ней, кроме ёбнутых дебилов, которые пытаются прохождением по ебеням показать какие они умные эвристы). И считать вес остальных участков исключительно в дальностях от этих "тропинок". И считать путь до цели исключительно от дороги. И считать полный путь исключительно когда дорога наебнулась.

Или подрочить графопарашу и запретить любые изменения в мире. Это же 2007+ год, пора даунгрейдить всё, до чего можешь дотянуться. Что? Ресурсы комплюхтера позволяют моделить в тысячу раз более сложные ИИ? Зачем? Лучше я сделаю овертесселяцию. Это будет умно.

> он точно так же основан на графе

Это привлечение лишней сущности. Рассматривать двухмерную карту из квадратов как граф, лишь бы выглядеть умно, на самом деле просто архитупо.

> Заодно поясни что ты понимаешь под "лишними сущностями"

Всё то, что ты пытаешься выдать за свой ум, хотя ОПу не надо знать что ты умный (он и не сможет этого узнать, потому что это 'ложь'), ему надо просто алгоритм поиска пути.

>>307087
Маня, граф это очень простая хуйня. Для работы твоего волнового алгоритма тоже нужен граф. Вот тебе цитата из википедии:

> Алгоритм волновой трассировки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе.

Вот "планарный граф" это умно. Пойди почитай определение.
Пойди посмотри визуализацию волнового алгоритма и поймешь, зачем нужна эвристика.

Далее. Если карта поменялась, то тепловую карту НАДО перестравить. И в этом он ничем не отличается от производных алгоритма дейсктры.

Ресурсы комплюхтера по прежнему не позволяют сделать приемлемый поиск пути за приемлемое время, увы. Тот факт что ты считаешь что иначе говорит лишь о том, что ты сферический кукаретик в вакууме.

> Рассматривать двухмерную карту из квадратов как граф

Ебать ты дибил.

>>307087
http://qiao.github.io/PathFinding.js/visual/
Твой волновой алгоритм основан на BFS. Посмотри как он работает. И сравни с а-старом.

>>307092

> граф просто, мам смотри я умный

Мы тебя все уже поняли.

>>307094

> основан на BFS

Всё что угодно в мире можно свести к ебле.

>>307097
>>307098
Ебать ты тупой. Даже у опа на пике есть граф. Это настолько простая хуита, что даже проще чем пиздец.

Йобаный в рот:

> The Lee algorithm is one possible solution for maze routing problems based on Breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory.

>>307100

> Даже у опа на пике есть граф.

Для говноедов повторяю: Всё что угодно в мире можно свести к ебле.