|
•Описание алгоритма (для интересующихся) - Geo, 18.05.2003 15:45:45 |
|
|
В реализации алгоритма имеются две основных сущности: список, задаваемый классом TFrontier и массив PathMap. Класс TFrontier -- это список тех самых юнитов, которые едут по карте. Название такое потому, что юниты образуют как бы фронт волны. Массив PathMap -- это массив, соответствующий по резмеру карте, в котором для каждолй клетки заносится информация о том, проезжали ли здесь уже или еще нет. Еще есть такое поняти как направление. Оно задается числами от 0 до 7 включительно. 0 -- вертикально вверх. Каждое добавление единички означает приращение на 45 градусов по часовой стрелке. Для направления есть функции, которые переводят его в приращения координат для смещения в соответствующем направлении на единицу.
У элементов списка TFrontier есть четыре важных элемента: координаты X и Y клетки, к которой он движется, направление, в котором он движется и сколько единиц движения нужно потратить, чтобы доехать до этой клетки. В главном цикле пробегается списрк юнитов. При этом измененное состояние заносится во второй список. После завершения шага цикла списки меняются местами и все начинается сначала. На каждом шаге главного цикла для каждого элемента списка из стоимости доезда до клетки (это поле элемента списка называется cost) вычитается единичка. Если значение остается больше нуля, то измененный элемент заносится во второй список и выполняется переход к следующему элементу списка. Если значение cost оказалось равным нулю, то считается, что юнит доехал. При этом проверяем не проехал ли кто-нибудь по этому полю раньше. Для этого смотрится поле PathLen соответствующего элемента массива PathMap. Если его значение больше нуля, то значит здесь уже кто-то проехал раньше, а число обозначает порядковый номер этой клетки в маршруте того, кто проехал.В этом случае ничего не делаем и переходим к следующему элементу списка. Если значение равно нулю, то заносим порядковый номер этой клетки в нашем маршруте и направление, с которого мы сюда приехали. А дальше тестируем соседние клетки. В идеале тестировать надо семь из восьми (кроме той, с которой приехали), но в этой задаче достаточно пяти: направдение, по которому приезали плюс-минус два. Я думаю, что это понятно. Расшифровывать не буду. Так вот, каждую из этих пяти клеток тестируем на то, может ли юнит туда пойти и не проехал ли там уже кто-нибудь. Для каждой клетки, в которую можно пойти и по которой еще никто не проехал создается елемент во втором списке с указанием координат этой новой клетки, направлением, по которому мы в нее приезжаем и стоимостью перемещения. Все.
Условия завершения поиска. Если юнит доехал до клетки, которая является конечной точкой, то цикл завершается успешно. Восстановить путь по массиву PathMap не составит труда. Если же за какой-то шаг главного цикла во второй список не было добавлено ни одного элемента (все юниты сняты), то значит такого пути не существует.
В описании у меня написано, что на каждом шаге цикла из значения поля cost каждого юнита вычитается единица. На самом деле, а программе вычитается не единица, а минимальное значение, при котором зануляется поле cost хотя бы у одного элемента списка. Это производится, чтобы избежать нудных циклов, в которых ничего не происходит кроме уменьшения значений поля cost для всех элементов списка. Соответствующее значение естественно должно быть вычислено на предыдущем шаге главного цикла.
Вроде все описал. Если будут вопросы, или вспомню еще что-нибудь, то будет дополнение. А вообще то, чертовски тяжело описывать алгоритм словами разговорного языка ;-) |
|
| |