Ищу информацию о поиске пути на изометрических картах

Question

Я работаю над игровым движком Engine1 (логотип - большой паровоз).Я был очень успешным с анимацией движения, спрайтовой анимацией и манипуляциями с элементами.Я могу очень быстро создавать / уничтожать / анимировать элементы (примерно ~ 1000 элементов каждые 1/40 секунды).

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

Я также планирую выпустить свой движок с открытым исходным кодом после того, как я сначала выпущу свою собственную игру с ним (доказательствоконцепции).Если вы заинтересованы в получении ранней сборки, сообщите мне.

Answer 1

Основной алгоритм поиска путей к сетке очень прост:

• Возьми свою начальную клетку, рекурсивно порази каждую соседнюю возможную клетку
  • игнорировать недействительные ячейки, например, стены / и т.д.
• всякий раз, когда вы попадаете в ячейку, только продолжается, если вы находитесь на самом низком шаге для этой ячейки. e.g.:

• Умирают, когда вы находитесь дальше, чем лучшая дистанция на данный момент

  A B C
  D E F
  G H I
  

У вас есть несколько путей из A-I (в случайном порядке):

• A-B (1) -C (2) -F (3) -E (4) -Н (5) -I (6)
• A-D (1) -E (2) -B (3) - умереть, потому что B (3)> B (1)
• A-D (1) -E (2) -F (3) -I (4) * 1 029 *
• A-B (1) -E (2) -D (3) - умереть, потому что D (3)> D (1)