Рассчитайте количество шагов, чтобы добраться до другого квадрата из квадрата в сетке и используйте его для стоимости h в алгоритме A *

Question

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

Что-то вроде этого (ps просто игнорировать синее пятно):

Редактировать: хорошие значенияза ч стоимость в алгоритме A *?

Answer 1

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

Answer 2

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

Эмуляция графа довольно проста - вершина A, B существует, если квадраты являются примыкающими, и ни один из них не является препятствием.Перечислить вершины, связанные с точкой (x, y), просто - проверьте границы для (x-1, y), (x + 1, y), (x, y-1), (x, y + 1) и проверьте,они не являются препятствиями.

Итак, если у вас нет весов, вы можете использовать упомянутый поиск в ширину https://en.wikipedia.org/wiki/Breadth-first_search

Также вы можете использовать алгоритм Дейкстры, хотя он немного медленнее: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm или A * алгоритм: https://en.wikipedia.org/wiki/A*_search_algorithm

Наконец, вы можете использовать алгоритм Беллмана-Форда: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm