Рейтинг темы:
  • Голосов: 0 - Средняя оценка: 0. Если голосов меньше 5 оценка не показывается.
  • 1
  • 2
  • 3
  • 4
  • 5
Поиск оптимального пути
#1
Игра написана на Куспе
В игре для боя строится карта 9х9 клеток из тайловых картинок.
Координаты каждой клетки задаются числом от 11 до 99, где десятки - это х координата а единицы это у.
На карте есть гг с координатами "Текущие_координаты_игрока"
На карте есть противник с координатами "Текущие_координаты_противника_1"
Двигаться можно только по горизонтали или по вертикали (т.е. не на искосок) и всего на одну клетку, но нужно, чтоб монстр не забредал в тупики и там не застревал
Проходимые клетки только те, где параметр Тайл_клетки_тип['<<Координаты>>'] = 1, в остальных случаях требуется найти обход. До понимания, как адаптировать к куспу алгоритмы типа A* или Дейкстра я видимо еще не дорос, а потому прошу помощи в написании данного модуля у уважаемого сообщества. Если не сложно, то с максимально подробной инструкцией.

 
Ответить
#2
Алгоритм волновой трассировки, как мне кажется, не должен вызвать больших сложностей в реализации:
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B8

Там есть псевдокод. Статья на Хабре (там для C#, но в общем максимально просто описывают)
https://habr.com/ru/post/264189/

 
1
Ответить
#3
@7ee35192, Спасибо. Алгоритм Ли оказался для понимания проще всего.

 
Ответить
#4
@9382efe0, ты уже создавал подобную тему https://albedo.pw/thread-4997.html
Используя то решение с небольшими модификациями и твоя задача решена.

 
Ответить
#5
(03.12.2019, 14:04)7c78cee3 писал(а): @9382efe0, ты уже создавал подобную тему https://albedo.pw/thread-4997.html
Используя то решение с небольшими модификациями и твоя задача решена.

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

 
Ответить
#6
Может кому пригодится:
http://qiao.github.io/PathFinding.js/visual/
http://github.com/qiao/PathFinding.js
Редактор 2д сетки где можно посмотреть как работает тот или иной алгоритм поиска путей в той или иной конфигурации.

 
Ответить


Переход:


Просматривают эту тему: 1 Гость(ей)