Поиск путиПри создании некоторых программ может возникнуть задача поиска пути из точки A в точку B по карте, состоящей из проходимых и непроходимых элементов. Программа должна быть как можно быстрее (а для Спектрума это один из важнейших факторов), а построеный путь по возможности оптимален. В процессе создания подобной программы, используя три алгоритма поиска, я пришел к нескольким интересным выводам, чем и собираюсь поделиться с читателем. Возможно, приведенная информация будет полезна разработчикам игр, в которых ставится задача поиска пути. С разными результатами были опробованы три алгоритма: 1. Обход препятствий по периметру; 2. Метод волн; 3. Алгоритм A* (или это я только думаю, что реализовал его). Начнем с самого первого - обход препятствий по периметру. Алгоритм достаточно простой: 1. Определяем направление на цель. 2. Смотрим, есть ли возможность в этом направлении двигаться. 2.1 Если такая возможность есть, делаем шаг в выбраном направлении. - если цель еще не достигнута, то к п. 1; - если мы дошли до цели, то выход. 2.2 Если на пути у нас препятствие, мы: a) осматриваем его по периметру; b) определяем положение ближайшей к цели точки при осмотре; c) определяем, с какой стороны надо обходить препятствие, чтобы быстрее в этой точке оказаться; d) обходим препятствие в выбраном направлении; e) к п. 1. Для меня самой сложной частью стал обзор препятствия. Важно обходить именно тот массив непроходимых элементов, в который мы уперлись на пути к цели, и не перескакивать на соседние препятствия. Мы можем осматривать препятствие двумя методами - <держась> за него левой или правой рукой. В первом случае осмотр клеток вокруг текущей надо выполнять по часовой стрелке, а во втором - против. Для того, чтобы определить, с какой стороны сейчас находится обходимое нами препятствие, надо знать, куда мы двигались на предыдущем шаге. Поэтому осмотр соседних клеток на первом шаге будет отличаться от остальных. Рассмотрим на примере. Допустим, препятствие мешает нам сделать шаг наверх и осмотр мы будем делать против часовой стрелки. Начиная с клетки выше героя [Г] (потому что препятствие сверху от нас) по часовой стрелке, т.е. в порядке вверх, вправо-вверх, вправо, вправо-вниз ит.д., осматриваем окрестные клетки и замечаем первую проходимую клетку. На нее и будет сделан шаг. Пусть эта клетка находится справа-снизу (см. рис.). Потому как мы осматривем непрерывную цепочку клеток, то клетка, с которой мы начинали обзор и последняя замеченая нами непроходимая клетка принадлежат одному препятствию (соседние клетки являются частью одного целого, если одна их координата совпадает, а второй они отличаются на 1). Итак, из точки [Г] мы переместились в точку [1], двигаясь вправо-вниз. Теперь возникает вопрос, с какой точки нам сейчас начинать обзор, чтобы эта точка оказалась точкой препятствия. В нашем случае точка справа от [Г] точно являлась точкой препятствия, и она же находится сверху от [1]. Значит, обзор надо начинать с верхней от [1] точки. Легче пользоваться следующей таблицей соответствия направления предыдущего шага и положения начальной точки осмотра. Обзор необходимо заканчивать, если точка вернулась в начальную [Г] или в первую точку обзора [1]. В ходе обзора мы вычисляем расстояние от текущей точки до цели и сравниваем его с минимальным. Также надо считать шаги - общее их число и число шагов до ближайшей к цели точки на препятствии. Если обозначить A=общее число шагов при обходе, B=число шагов до ближайшей точки в направлении обхода препятствия, то C=A-B это число шагов до этой точки в обратном направлении. Сравнивая B и C мы выбираем направление обхода и делаем нужное число шагов по периметру препятствия, после чего снова выбираем направление на цель и пытаемся в этом направлении двигаться. Если в ходе обзора ближайшая к препятствию точка на периметре препятствия оказалась не ближе к нему чем начальная, то это означает, что цель недоступна, и мы сейчас находимся в максимально близкой к цели точке. В этом случае построение пути надо заканчивать. Плюсом этого метода является его скорость, а минусом - очень глупый и иногда смешной маршрут движения. Особенно если карта представляет собой лабиринт из тоннелей. Вариантом этого метода является движение в направлении обхода только на один шаг, после чего вновь происходила проверка на возможность движения в направлении цели. Этот вариант дает более умный путь, но в некоторых вариантах просто зацикливается, а поэтому его применение под вопросом. Второй метод поиска пути - волновой. Суть метода - заполнение карты так называемыми волнами. А если проще - записывание в каждую проходимую ячейку числа, которое по сути является примерной длиной пути от начальной клетки до данной, а потом по этим значениям строится путь. Кратко алгоритм выглядит так: 1. Записываем в начальную клетку 1 (первая волна) и запоминаем ее. 2. Во все проходимые клетки в заданых направлениях от запомненых записываем число, на 1 большее чем число в текущей клетке и попутно запоминаем их. 3. Если цель не достигнута и еще есть куда распространять волну, то переходим к п. 2, иначе выход. Варианты волнового метода заключаются в разных критериях осмотра клеток вокруг текущей в п. 2 алгоритма. Самый точный путь дает обзор клеток только в 4 направлениях - вверх, вниз, влево и вправо от текущей, однако у этого варианта есть недостаток: т.к. волна не распространяется по диагонали, она не сможет проникнуть в область, в которую попасть можно только по диагональному проходу. Волна, распространяемая во все 8 сторон дает более высокое проникновение , но путь, построеный по этой волне не отличается оптимальностью. Третьим вариантом распространение волны является смешаное избирательное направление. Например, если невозможно распространение волны вверх и вправо, мы пробуем распространить ее вверх-вправо, т.е между этими направлениями. Проникающая способность такой волны высокая, а путь получается ненамного хуже чем при распространении волны в 4 стороны. В ходе заливки карты волнами нам необходимо определить ближайшую к цели точку, которую <накрыло> волнами, а потом строить путь от этой точки к начальной (получается такое <хождение задом> - встаём в конечную точку и строим путь в начальную). Так охватываются оба варианта - и когда цель недоступна, и когда к ней есть проход. При построении пути мы начинаем от определенной нами ранее ближайшей к цели точки. Если цель доступна, то эта точка совпадет с ней. Клетка, на которую мы делаем шаг, имеет минимальный номер из всех, что окружают текущую. Путь заканчивается на начальной точке. Метод волн всегда дает нужный путь, всегда подходит к недоступной цели на минимальное расстояние, но он довольно медленый. Алгоритм A*. Насколько я понял, этот алгоритм похож на волновой, но волна выпускается не из всех точек предыдущей волны, а только из той, что ближе всего к цели. Остальные точки волны в отличие от предыдущего алгоритма с наблюднния не снимаются. Плюсом является более высокая скорость работы при доступной цели, но при недоступной начинаются проблемы, столкнувшись с которыми я забросил проработку этого алгоритма и на базе волнового метода разработал следующую вариацию. Вариация волнового алгоритма. Несколько измененный волновой алгоритм - волна пускается не из всех точек предыдущей волны, а лишь из тех, которые отстоят от определенной ближайшей к цели точки на волне не более чем на заданое расстояние. Варьируя данный критерий можно значительно ускорить алгоритм, добившись требуемого результата. В отличие от алгоритма A* точки предыдущей волны снимаются с наблюдения. Волновой метод и алгоритм A* могут быть интересны тем, что с их помощью можно составлять пути не только на однородной карте, но и на карте, где у разных клеток разная <стоимость> прохода по ним. Скажем, по песку скорость движения ниже чем по траве. В этом случае в каждую осматриваемую клетку записываем число, равное значению в текущей клетке плюс стоимость осматриваемой клетки. В заключение, предлагаю исходник поиска пути волновым методом в моей вариации. ;-- переменные --
DX_MAP EQU 64 ;размер карты
;по горизонтали
DY_MAP EQU 64 ;размер карты
;по вертикали
MAXWAVE EQU 100 ;эта переменная
;определяет
;максимальное
;число распро-
;страняемых
;волн
MAXDIST EQU 5 ;а эта -
;радиус
;активности
;волны
;относительно
;ближайшей
;к цели точки
;(см.выше)
;-- направления --
DIR_DR EQU 0 ;вниз-вправо
DIR_R EQU 1 ;вправо
DIR_UR EQU 2 ;вверх-вправо
DIR_D EQU 3 ;вниз
DIR_U EQU 4 ;вверх
DIR_DL EQU 5 ;вниз-влево
DIR_L EQU 6 ;влево
DIR_UL EQU 7 ;вверх-влево
; вх. H=X, L=Y начальной точки
; D=X, E=Y цели
WAVE LD (XY_bgn),HL ;начальные
;координаты
LD (XY_end),DE ;конечные
;координаты
CALL FILLMAP ;заливаем
;карту волнами
LD DE,0 ;путь строим
;досюда...
XY_bgn EQU $-2
CALL MAP_ADR
PUSH HL
LD DE,0 ;...отсюда -
;от ближайшей
;к цели точки
XY_cur EQU $-2
CALL MAP_ADR ;DE - адрес
;цели
;(нач.точка)
POP DE ;HL - адрес
;текущей
;точки
EXX
LD HL,stack ;HL' -
;указатель
;адреса
;в буфере
LD (HL),#FF ;#FF - конец
;пути
INC HL
;Делаем шаг на клетку с мин.номером
Steps EXX
AND A
SBC HL,DE
JR Z,stp_2 ;HL=DE - мы
;достигли цели
ADD HL,DE
stp_1 CALL STEPIN ;иначе делаем
;следующий шаг
EXX ;и записываем
;направление
;в буфер
LD (HL),A
INC HL
JR Steps
stp_2 EXX
PUSH HL
LD HL,MASSIVE ;Восстанавли-
;ваем карту
;после заливки
LD BC,#1000 ;длина карты
wav_1 LD A,(HL)
CP 2
JR C,wav_2
LD (HL),0
wav_2 INC HL
DEC C
JR NZ,wav_1
DJNZ wav_1
POP HL
DEC HL
RET
;шаг на клетку с минимальным номером
; вх. HL = адрес текущей клетки
; вых. HL = адрес клетки,
где мы оказываемся после шага
; А = направление, в котором происходит движение от вых.HL к вх.HL
STEPIN
LD C,255 ;минимальный
;номер
;в клетках
;вокруг HL.
;Для начала =
;255
LD (mxxz18+1),HL
DEC HL ;смотрим
;влево, если
LD A,(HL) ;там 0 или 1
;нам это не
;надо (это
;исходная
;клетка карты,
;там волны не
;было)
CP 2
JR C,mxxz11
CP C ;если в клетке
;число,
;большее или
;равное
;минимальному,
;то она нам
;тоже не
;подходит
JR NC,mxxz11
LD (mxxz18+1),HL ;а иначе -
;запоминаем
;адрес этой
;клетки
LD C,(HL) ;и переписы-
;ваем мини-
;мальный
;номер
LD B,DIR_R ;в B -
;направление,
;обратное
;текущему,
;потому как
;путь строится
;в обратном
;направлении
mxxz11 LD A,L ;влево вниз
ADD A,DX_MAP
LD L,A
ADC A,H
SUB L
LD H,A
LD A,(HL)
CP 2
JR C,mxxz12
CP C
JR NC,mxxz12
LD (mxxz18+1),HL
LD C,(HL)
LD B,DIR_UR
mxxz12 INC HL ;вниз
LD A,(HL)
CP 2
JR C,mxxz13
CP C
JR NC,mxxz13
LD (mxxz18+1),HL
LD C,(HL)
LD B,DIR_U
mxxz13 INC HL ;вправо-вниз
LD A,(HL)
CP 2
JR C,mxxz14
CP C
JR NC,mxxz14
LD (mxxz18+1),HL
LD C,(HL)
LD B,DIR_UL
mxxz14 LD A,L ;вправо
SUB DX_MAP
LD L,A
SBC A,L
ADD A,H
LD H,A
LD A,(HL)
CP 2
JR C,mxxz15
CP C
JR NC,mxxz15
LD (mxxz18+1),HL
LD C,(HL)
LD B,DIR_L
mxxz15 LD A,L ;вправо-вверх
SUB DX_MAP
LD L,A
SBC A,L
ADD A,H
LD H,A
LD A,(HL)
CP 2
JR C,mxxz16
CP C
JR NC,mxxz16
LD (mxxz18+1),HL
LD C,(HL)
LD B,DIR_DL
mxxz16 DEC HL ;вверх
LD A,(HL)
CP 2
JR C,mxxz17
CP C
JR NC,mxxz17
LD (mxxz18+1),HL
LD C,(HL)
LD B,DIR_D
mxxz17 DEC HL ;влево-вверх
LD A,(HL)
CP 2
JR C,mxxz18
CP C
LD A,DIR_DR
RET C
mxxz18 LD HL,0
LD A,B
RET
; заливка карты волнами
FILLMAP
LD DE,(XY_end) ;определяем
;адрес
;конечной
;точки
CALL MAP_ADR
LD (WaveEnd+1),HL
;на стеке у нас находится список ;адресов клеток, из которых надо ;пускать волну. список заканчивается ;адресом 0
LD HL,0 ;строим
;первый
;список
;из одной
;начальной
;точки
PUSH HL
LD DE,(XY_bgn)
CALL MAP_ADR
PUSH HL
LD A,255 ;это
;минимальная
;оценка
;расстояния
;от точки
;волны до цели
LD (Distan),A
LD A,2 ;волны
;начинаем
;считать
;с номера 2
Next LD (WaveNr),A
XOR A ;это длина
LD (WaveLen),A ;текущей волны
LD HL,stack ;а это -
;указатель
;адреса в
;буфере, где
;мы делаем
;список точек
;новой волны
LD (SP_reg),HL
Loop POP DE ;во все
;адреса
;списка
;заносим
;номер волны.
LD A,D ;DE = текущий
;адрес
OR E
JR Z,WaveEnd
LD A,0
WaveNr EQU $-1
LD (DE),A
PUSH DE ;оцениваем
;расстояние
;до цели
LD HL,-MASSIVE
ADD HL,DE
LD A,L ;!!! ТУТ
;ЗАТОЧКА ПОД
;DX_MAP=64
AND 63
LD B,A
ADD HL,HL
ADD HL,HL
LD A,H
AND 63
LD C,A ;B,C = X,Y
;тек.точки
LD DE,0 ;D,E = X,Y
;цели
XY_end EQU $-2
LD A,B
SUB D
JR NC,clu_1
NEG
clu_1 LD D,A
LD A,C
SUB E
JR NC,clu_2
NEG
clu_2 ADD A,D ;A = тек.
;расстояние
CP 0 ;сравниваем
;его
;с минимальным
Distan EQU $-1
JR NC,clu_3
LD (Distan),A
LD (zistan+1),A
LD (XY_cur),BC
clu_3
zistan SUB 0 ;проверка,
;попала ли
;точка
;в активный
;радиус
CP MAXDIST
POP DE
CALL C,AROUND ;если попала
;из нее
;пускаем новую
;волну
JR Loop
WaveEnd
LD A,(0) ;начальная
INC A ;точка
CP 3 ;достигнута
RET NC
LD A,(WaveNr)
CP MAXWAVE ;число волн
;перевалило
;за заданое
;в EQU
RET NC
LD A,(WaveLen) ;волна не
;распро-
;страняется
AND A
RET Z
LD B,A ;все адреса
LD HL,0 ;из нового
PUSH HL ;списка
LD HL,stack ;переносим
wend_1 LD D,(HL) ;на стек
INC HL ;т.е делаем
LD E,(HL) ;новый список
INC HL ;текущим
PUSH DE
DJNZ wend_1
LD A,(WaveNr) ;следующая
INC A ;волна
JR Next
; осмотр клеток вокруг текущей
; вх. DE = адрес текущей клетки
; вых. - нужные клетки помечены и их адреса занесены в буфер
AROUND LD HL,0 ;помечаем
;и запоминаем
;свободных
;соседей
;вокруг D,E
SP_reg EQU $-2
LD BC,0 ;C = длина
;текущей волны
WaveLen EQU $-2
DEC DE ;слева
LD A,(DE) ;нам нужны
;только
;свободные
;клетки -
;в которых 0
SUB 1
JR NC,mzzz1A
LD (DE),A ;в них
;заносим 255,
;чтобы не
;проверять ее
;повторно
LD (HL),D ;их адрес
INC HL ;записываем
LD (HL),E ;в буфер
INC HL
INC C
SET 2,B ;увеличиваем
;длину волны
;это - для
;последующей
;проверки
mzzz1A LD A,E ;вверх
SUB DX_MAP-1
LD E,A
SBC A,E
ADD A,D
LD D,A
LD A,(DE)
SUB 1
JR NC,mzzz1B
LD (DE),A
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
SET 1,B
mzzz1B LD A,E ;вправо
ADD A,DX_MAP+1
LD E,A
ADC A,D
SUB E
LD D,A
LD A,(DE)
SUB 1
JR NC,mzzz1C
LD (DE),A
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
SET 0,B
mzzz1C LD A,E ;вниз
ADD A,DX_MAP-1
LD E,A
ADC A,D
SUB E
LD D,A
LD A,(DE)
SUB 1
JR NC,mzzz1D
LD (DE),A
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
SET 3,B
mzzz1D DEC DE ;если вниз
LD A,B ;и влево
AND %1100 ;клетки
JR NZ,mzzz1E ;не свободны
LD A,(DE) ;то пробуем
SUB 1 ;клетку
JR NC,mzzz1E ;влево-вниз
LD (DE),A ;от текущей
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
mzzz1E INC DE ;то же
INC DE ;вправо-вниз
LD A,B
AND %1001
JR NZ,mzzz1F
LD A,(DE)
SUB 1
JR NC,mzzz1F
LD (DE),A
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
mzzz1F LD A,E ;вправо-
SUB DX_MAP ;вверх
LD E,A
SBC A,E
ADD A,D
LD D,A
LD A,E
SUB DX_MAP
LD E,A
SBC A,E
ADD A,D
LD D,A
LD A,B
AND %0011
JR NZ,mzzz1G
LD A,(DE)
SUB 1
JR NC,mzzz1G
LD (DE),A
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
mzzz1G DEC DE ;и влево-
DEC DE ;вверх
LD A,B
AND %0110
JR NZ,aro_EX
LD A,(DE)
SUB 1
JR NC,aro_EX
LD (DE),A
LD (HL),D
INC HL
LD (HL),E
INC HL
INC C
aro_EX LD (SP_reg),HL
LD A,C
LD (WaveLen),A
RET
MAP_ADR
LD L,0 ;!!! ЗАТОЧЕНО
LD H,E ;ПОД DX_MAP=64
LD E,D ;из D=X, E=Y
LD D,L ;делается
AND A ;HL = адрес
RR H ;в массиве
RR L
RR H
RR L
ADD HL,DE
LD DE,MASSIVE
ADD HL,DE
RET
MASSIVE
INCBIN MASSIVE - это наш массив, состоящий из элементов 0 и 1. 0 значит, что клетка проходима, 1 - непроходима. Для корректной работы необходимо, чтобы размер карты по горизонтали был не более 254. Размер по вертикали значения не имеет. Карта со всех четырех сторон должна быть окружена непроходимой границей. К тому же номер волны не может превышать 255, т.е. должно быть выпущено не более 253 волн. Этот алгоритм имеет только один изъян - если волна затечет в достаточно большую <коробку>, то выйти оттуда уже не сможет. Если на карте такие места имеются, необходимо увеличить MAXDIST, но это замедлит процедуру. На выходе мы получаем в буфере (метка stack) цепочку байт - это направления, в которых надо двигаться на пути к цели. В HL имеем адрес первого направления, но следует помнить, что цепочка построена в обратную сторону, т.е. процесс движения по ней будет выглядеть так: label LD A,(HL) ;берем
CP 255 ;направление
RET Z ;255 - конец
;цепочки
PUSH HL
CALL MOVE ;двигаемся
;в этом
;направлении
POP HL
DEC HL ;уменьшаем
JR label ;адрес -
;переходим
;к следующему
;шагу |