![]() |
:: СОДЕРЖАНИЕ НОМЕРА
:: Газетные рубрики
:: АВТОРЫ
:: Поиск
:: Поддержка проекта
Webmoney:
|
:: №27 (05.08.2006) Просмотров: 3918
![]() Автор: Александр Синяков / 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 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 ;адрес - ;переходим ;к следующему ;шагу |