Абзац
:: Поиск
:: Поддержка проекта
Webmoney:
  • Z610389805629
  • R427996570517
  • E023541002978
  • :: №27 (05.08.2006) Просмотров: 4379

    Автор: Александр Синяков / 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    ;адрес - 
                    ;переходим 
                    ;к следующему 
                    ;шагу



    © 2004-2013 Perspective group