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