№27 :: Поиск пути

:: №27 (05.08.2006) Просмотров: 4043

Автор: Александр Синяков / SAM style.

Номер: №27 (05.08.2006).

Поиск пути

При создании некоторых программ может возникнуть задача поиска пути из точки 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 
stack   DS 4*(DX_MAP+DY_MAP)

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    ;адрес - 
                ;переходим 
                ;к следующему 
                ;шагу