Поиск ближайшей точки на сетке с препятствиями

Question

У меня есть игра, в которой вам нужно передвигаться по карте, собирающей золото, а затем перейдите к выходу. В настоящее время я пытаюсь написать AI, который будет играть в эту игру, но я хочу знать, какой алгоритм я должен использовать для поиска ближайшего экземпляра объекта. Например, ближайший кусок золота или ближайший неизвестный квадрат карты. Проблема в том, что есть стены, которые игрок не может перемещать, поэтому вместо того, чтобы просто найти ближайший объект, мне нужно найти тот, на котором есть самый короткий маршрут. Есть ли алгоритм, который может это сделать?

Answer 1

Алгоритм, который вы ищете, называется алгоритмом поиска *. Это самый лучший алгоритм поиска, который работает, начиная с начальной точки и создавая ряд возможных путей (за исключением прохождения препятствий, поскольку это не возможные пути), а затем забирая эти пути, чтобы найти наименьшую стоимость. В вашем случае вам нужно настроить счет, уменьшив стоимость на основе объектов вдоль пути и увеличив стоимость по расстоянию.

Там какая-то информация, которая поможет вам с ней здесь:

Там есть отличная интерактивная демо здесь (код также на GitHub): http://qiao.github.io/PathFinding.js/visual/

Другие ресурсы:

• https://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/
• https://en.wikipedia.org/wiki/A*_search_algorithm
• What is a good 2D grid-based path-finding algorithm?