Поиск путей в C ++ с помощью a-star, оптимизация

Question

Мне интересно, могу ли я немного оптимизировать свой код поиска пути, давайте посмотрим на эту карту:

+ - wall, . - free, S - start, F - finish
.S.............
...............
..........+++..
..........+F+..
..........+++..
...............

Человек посмотрит на нее и скажет, что это невозможно, потому что конец окружен ... Но А-звезда ДОЛЖНА проверить все поля, чтобы удостовериться, что дороги нет.Ну, это не проблема с маленькими картами.Но когда у меня есть карта 256x265, проверка всех точек занимает много времени.Я думаю, что я могу прекратить поиск, пока вокруг финиша есть закрытые узлы, я имею в виду:

+ - wall, . - free, S - start, F - finish, X - closed node
.S.............
.........XXXXX.
.........X+++X.
.........X+F+X.
.........X+++X.
.........XXXXX.

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

Спасибо за любые ответы.

Answer 1

Если карта не меняется, вы можете предварительно обработать ее, разделив ее на подключенных компонентов .Это можно сделать с помощью быстрой непересекающейся структуры данных набора .Затем перед запуском A * вы в постоянное время проверяете, что источник и пункт назначения принадлежат одному и тому же компоненту.Если нет - пути не существует, в противном случае вы запускаете A *, чтобы найти путь.

Недостатком является то, что вам потребуются дополнительные n-биты на ячейку, где n = ceil (log C), где C - это числоподключенные компоненты.Если у вас достаточно памяти и вы можете себе это позволить, тогда все в порядке.

Редактировать: если вы исправляете n как маленький (например, один байт) и имеете больше этого количества компонентов (например, более 256 для 8-битногоn) затем вы можете назначить один и тот же номер нескольким компонентам.Для достижения наилучших результатов убедитесь, что каждому компоненту-идентификатору присвоено примерно одинаковое количество ячеек.

Answer 2

Прежде всего эту проблему лучше решить с помощью поиска в ширину , но я предполагаю, что у вас есть веская причина использовать вместо него звездочку.Однако я все же рекомендую сначала проверить связь между S и F с помощью какого-либо поиска (поиск в ширину или поиск в глубину).Это решит нашу проблему.