- Выполните 8-сторонний алгоритм заполнения ковша, чтобы найти мертвых.
Чтобы минимизировать количество мертвых объектов, добавьте сначала кардиналов в очередь, а затем первичные межкардиналы (диагонали).Также следите за последней мертвой областью, и если вы обнаружите новую мертвую область слишком близко к последней, вы удалите последнюю и сохраните новую найденную.На больших картах вы также можете рассчитать расстояние Манхэттена от тупика до центра карты, и если оно слишком короткое, вы просто не добавляете тупик.
Теперь просто A * каждая точка в любой другой точке.
Поскольку вы проверяете каждый путь дважды (от p1 до p2, затем от p2 до p1), как только вы проверяете от p1 до p2, вы также можете зарегистрировать p2 до p1 на летучей мыши с тем же расстоянием, чтобы вдвое сократить количество раз.вам нужно сделать поиск A *.Время, необходимое для выполнения поиска A *, можно рассчитать как number of deadends * (number of deadends - 1) / 2.