Попросила меня тут одна знакомая сделать одну лабораторную по нахождению кратчайшего пути. Вспомнилось мне, что давным-давно, еще на старом добром Спектруме, читал я по этому поводу статейку Славы Медноногова. Статейка нашлась, оказывается, было это в ZX-Formаt #6.

Сразу извинюсь за кривоту кода и реализации. Хотелось сделать в точности так, как описывалось в статье, но и задачу решить надо было.

Да и паскаля я года четыре в глаза не видел — всюду лезли фигурные скобки :)). Вот что из этого вышло:

1. Program test;
2.  
3. (*
4. П р а в и л а п р о г р а м м и с т с к о й и г р ы "К Л А Д":
5. Имеется игровое поле N x N . Оно представлено массивом Pole : array [ 1..N,1..N ] of integer.
6. Если элемент массива Pole[i,k] равен нулю, то клетка игрового поля на пересечении i-той строки
7. и k-того столбца пустая. По пустым полям можно ходить. Если Pole[i,k]=1, то клетка игрового
8. поля в i-той строке и k-том столбце занята каменной стеной. Такие клетки нельзя пересекать,
9. даже слегка задевать. В одной из клеток Pole[i,k]=5. В этой клетке находится клад.
10. Задача игрока -- дойти до клетки, в которой находится клад. Каждый участник игры пишет
11. процедуру, содержащую алгоритм одного своего хода. В начале хода игрок располагает такой
12. информацией:
13. X, Y -- номер столбца и номер строки, где сейчас он находится;
14. Pole -- весь массив тоже доступен для просмотра.
15. Процедура игрока должна определять свой ход, задав две величины dX и dY:
16. dX -- направление смещения по горизонтали:
17. dX = -1 -- есть смещение на запад;
18. dX = 1 -- есть смещение на восток;
19. dX = 0 -- нет смещения по горизонтали.
20. dY -- направление смещения по вертикали:
21. dY = -1 -- есть смещение на север;
22. dY = 1 -- есть смещение на юг;
23. dY = 0 -- нет смещения по вертикали.
24. Таким образом, совершая ход, игрок может передвинуться на одну клетку в одном из восьми
25. направлений (как шахматный король) или остаться на месте. Если заявленный игроком ход
26. невозможен, то перемещение не происходит. Ход невозможен, если:
27. в результате хода игрок встал бы на занятую стеной клетку;
28. или при движении по диагонали игрок задел бы угол клетки, занятой стеной.
29. Оценка зависит от времени (числа ходов), затраченного на то, чтобы найти клад.
30. *)
31. uses crt;
32.  
33. const N=20; (* Размер поля *)
34. const kX=4; (* Координата X клада *)
35. const kY=6; (* Координата Y клада *)
36. const Nk=100; (* Максимальное количество итераций *)
37.  
38. var
39. Pole : array [ 1..N,1..N ] of integer;
40. X,Y : integer;
41. dX,dY : integer;
42. step : integer; (* Количество шагов *)
43. first : integer; (* Если не 1, то процедура OneStep запускается первый раз*)
44.  
45. wayX : array [ 1..Nk ] of integer; (* Координаты X маршрута *)
46. wayY : array [ 1..Nk ] of integer; (* Координаты Y маршрута *)
47. pos : integer; (* Номер шага *)
48.  
49.  
50. (* Задает поле *)
51. procedure SetField();
52. begin
53. (* Стены *)
54. Pole[5,5]:=1;Pole[5,6]:=1;Pole[5,7]:=1;
55. Pole[5,8]:=1;Pole[5,9]:=1;Pole[5,10]:=1;
56. Pole[4,5]:=1;Pole[3,5]:=1;Pole[2,5]:=1;
57. Pole[2,6]:=1;Pole[2,7]:=1;Pole[2,8]:=1;
58. Pole[2,9]:=1;Pole[2,10]:=1;Pole[2,11]:=1;
59. Pole[2,12]:=1;Pole[2,13]:=1;Pole[2,14]:=1;
60.  
61. Pole[15,6]:=1;Pole[15,7]:=1;Pole[15,8]:=1;
62. Pole[15,9]:=1;Pole[15,10]:=1;Pole[14,5]:=1;
63. Pole[13,5]:=1;Pole[12,5]:=1;Pole[12,6]:=1;
64. Pole[12,7]:=1;Pole[12,8]:=1;Pole[12,9]:=1;
65. Pole[12,10]:=1;Pole[12,11]:=1;Pole[12,12]:=1;
66. Pole[12,13]:=1;Pole[12,14]:=1;Pole[12,15]:=1;
67. Pole[12,16]:=1;Pole[13,16]:=1;Pole[14,16]:=1;
68. Pole[15,16]:=1;Pole[16,16]:=1;Pole[16,16]:=1;
69.  
70. Pole[9,2]:=1;Pole[9,3]:=1;Pole[9,4]:=1;
71. Pole[9,5]:=1;Pole[9,6]:=1;Pole[9,7]:=1;
72. Pole[9,8]:=1;Pole[9,9]:=1;Pole[9,10]:=1;
73. Pole[9,11]:=1;Pole[9,12]:=1;Pole[9,13]:=1;
74. Pole[9,14]:=1;Pole[9,15]:=1;Pole[9,16]:=1;
75. Pole[9,17]:=1;Pole[9,18]:=1;Pole[9,19]:=1;
76. Pole[9,20]:=1;Pole[8,2]:=1;Pole[15,5]:=1;
77. Pole[7,2]:=1;Pole[6,2]:=1;Pole[5,2]:=1;
78. Pole[4,2]:=1;Pole[3,2]:=1;Pole[2,2]:=1;
79.  
80. (* Клад *)
81. Pole[kX,kY]:=5;
82.  
83. (* Игрок *)
84. X:=13;
85. Y:=6;
86. end;
87.  
88. (* Вывод поля на экран *)
89. procedure DrawField();
90. var i,j : integer;
91. begin
92. for i:=1 to N do
93. for j:=1 to N do
94. begin
95. gotoxy(i*2,j);
96. case Pole[i][j] of
97. 0: write('__');
98. 1: write('SS');
99. 5: write('');
100. end;
101. end;
102. (* Вывод игрока *)
103. gotoxy(X*2,Y);
104. write('');
105. end;
106.  
107. (* Один шаг *)
108. procedure OneStep();
109. var
110. R : array [ 1..N,1..N ] of integer; (* Рабочее поле *)
111. i,j : integer;
112. Ni : integer; (* Номер итерации *)
113. found : boolean;
114. min : integer;
115. mDx,mDy : integer; (* перемещения в волновом алгоритме *)
116. mstep : integer;
117. begin
118. if first<>1 then
119. begin (* Начало реализации волнового алгоритма *)
120. first:=1;
121. for i:=1 to N do
122. for j:=1 to N do
123. case Pole[i][j] of
124. 0: R[i][j]:=254;
125. 1: R[i][j]:=255;
126. 5: R[i][j]:=0;
127. end;
128. R[X][Y]:=253;
129. Ni:=0;
130. found:=false;
131. (* Шагаем *)
132. while (Ni<Nk) do
133. begin
134.  
135. (* Построчно просмaтривaем рaбочий мaссив *)
136. for i:=1 to N do
137. for j:=1 to N do
138. if not found then
139. begin
140. if R[i][j]=Ni then
141. begin
142. (* Идем влево вверх *)
143. if (R[i-1][j-1]=254) AND (R[i][j-1]=254) AND (R[i-1][j]=254) AND (i-1>0) AND (j-1>0) then R[i-1][j-1]:=Ni+1;
144. (* Идем влево вниз *)
145. if (R[i-1][j+1]=254) AND (R[i][j+1]=254) AND (R[i-1][j]=254) AND (i-1>0) AND (j+1<=N) then R[i-1][j+1]:=Ni+1;
146. (* Идем вправо вверх *)
147. if (R[i+1][j-1]=254) AND (R[i][j-1]=254) AND (R[i+1][j]=254) AND (i+1<=N) AND (j-1>0) then R[i+1][j-1]:=Ni+1;
148. (* Идем вправо вниз *)
149. if (R[i+1][j+1]=254) AND (R[i][j+1]=254) AND (R[i+1][j]=254) AND (i+1<=N) AND (j+1<=N) then R[i+1][j+1]:=Ni+1;
150. (* Идем влево *)
151. if (R[i-1][j]=254) AND (i-1>0) then R[i-1][j]:=Ni+1;
152. (* Идем вправо *)
153. if (R[i+1][j]=254) AND (i+1<=N) then R[i+1][j]:=Ni+1;
154. (* Идем вверх *)
155. if (R[i][j-1]=254) AND (j-1>0) then R[i][j-1]:=Ni+1;
156. (* Идем вниз *)
157. if (R[i][j+1]=254) AND (j+1<=N) then R[i][j+1]:=Ni+1;
158.  
159. (* Проверка достижения конечной точки *)
160. if R[i-1][j-1]=253 then found:=true;
161. if R[i-1][j+1]=253 then found:=true;
162. if R[i+1][j-1]=253 then found:=true;
163. if R[i+1][j+1]=253 then found:=true;
164. if R[i-1][j]=253 then found:=true;
165. if R[i+1][j]=253 then found:=true;
166. if R[i][j-1]=253 then found:=true;
167. if R[i][j+1]=253 then found:=true;
168. end;
169. end;
170. Ni:=Ni+1;
171. end;
172.  
173. (* Если маршрута не найдено, то ругаемся *)
174. if not found then
175. begin
176. WriteLn('Маршрута не найдено.');
177. halt(1);
178. end;
179.  
180. (* Теперь строим путь *)
181. i:=X;
182. j:=Y;
183. mstep:=0;
184. min:=255;
185. while (R[i][j]<>0) do
186. begin
187. if (min>R[i][j+1]) AND (j+1<=N) then begin min:=R[i][j+1];mdx:=0;mdy:=1;end;
188. if (min>R[i][j-1]) AND (j-1>0) then begin min:=R[i][j-1];mdx:=0;mdy:=-1;end;
189.  
190. if (min>R[i+1][j+1]) AND (i+1<=N) AND (j+1<=N) then begin min:=R[i+1][j+1];mdx:=1;mdy:=1;end;
191. if (min>R[i+1][j+0]) AND (i+1<=N) then begin min:=R[i+1][j+0];mdx:=1;mdy:=0;end;
192. if (min>R[i+1][j-1]) AND (i+1<=N) AND (j-1>0) then begin min:=R[i+1][j-1];mdx:=1;mdy:=-1;end;
193.  
194. if (min>R[i-1][j+1]) AND (i-1>0) AND (j+1<=N) then begin min:=R[i-1][j+1];mdx:=-1;mdy:=1;end;
195. if (min>R[i-1][j+0]) AND (i-1>0) then begin min:=R[i-1][j+0];mdx:=-1;mdy:=0;end;
196. if (min>R[i-1][j-1]) AND (i-1>0) AND (j-1>0) then begin min:=R[i-1][j-1];mdx:=-1;mdy:=-1;end;
197.  
198. i:=i+mdx;
199. j:=j+mdy;
200. mstep:=mstep+1;
201. wayX[mstep]:=mdx;
202. wayY[mstep]:=mdy;
203. end;
204. end; (* Конец реализации волнового алгоритма *)
205. pos:=pos+1;
206. dX:=wayX[pos];
207. dY:=wayY[pos];
208. end;
209.  
210. begin
211. pos:=0;
212. first:=0;
213. ClrScr;
214. SetField;
215. DrawField;
216.  
217. (* Делаем шаги пока не нашли клад *)
218. step:=0;
219. while ((X<>kX) or (Y<>kY)) and (step<100) do
220. begin
221. DrawField;
222. delay(200);
223. OneStep;
224. X:=X+dX;
225. Y:=Y+dY;
226. gotoxy(1,22);
227. writeln('игрок: ',X,':',Y,' клад: ',kX,':',kY,' ');
228. step:=step+1;
229. end;
230.  
231. WriteLn('Клад найден за ',step,' шагов');
232.  
233. end.

Download this code: way.pas

Построение кратчайшего маршрута

Задача нахождения самого короткого пути между некими точками а и В на игровом поле с произвольно расположенными препятствиями характерна, в первую очередь,для популярных сегодня тактических и стратегических игр. Как подзадача,она может возникать практически в любых играх — RPG,квестах,логических (типичный пример — «Color Lines»,кстати,слепить очередную версию такой игрушки после этой статьи — раз плюнуть).Почему надо искать самый короткий маршрут? В некоторых играх, например «HЛО-2″,»Lаser Squаd»,от длины маршрута зависит количество потраченных единиц времени — чем оптимальней будет найден путь, тем быстрее воин доберётся до цели. а, например, в «Color Lines» длина маршрута не оговорена правилами, имеет значение лишь сам факт возможности или невозможности перемещения шара. Hо и в этой игре будет приятнее смотреться, если шарик сразу направится куда надо,а не будет загадочно дефилировать по всей игровой доске.

Решение этой задачи пришло к нам из такой далёкой,казалось бы, от игр области как электроника.а именно — разводка печатных плат (все знают,что это такое?).

Существует большое количество трассировщиков (программ для разводки платы), основанных на не меньшем количестве различных методов, занимающихся соединением двух контактов единым проводником.Hо мы рассмотрим только один из них, самый простой (а значит,самый надёжный и самый популярный) — волновой трассировщик.

Поставим перед волновым трассировщиком задачу в терминах разрабатываемой нами игры:

Имеется игровое поле Р(MxN),где M и N, соответственно, размер поля по вертикали и горизонтали. Попросту,это массив размерностью MxN (DIM P(M,N). Каждая клетка игрового поля (элемент массива) может обладать большим количеством свойств по вашему усмотрению, но для нас важно только одно — её проходимость (или непроходимость). Каким образом она определяется — это уж ваше дело. Дальше: имеется некоторая стартовая точка, где находится герой вашей игры, и конечная точка, куда ему необходимо попасть. Условимся пока,что ходить он может только по четырём направлениям (чего требует от нас классический волновой метод) — вправо,влево,вперёд, назад. Hеобходимо переместить героя от места старта к финишу за наименьшее количество ходов,если такое перемещение вообще возможно.

алгоритм нахождения кратчайшего маршрута между двумя точками для такой задачи достаточно прост:

1. Сначала необходимо создать рабочий
   массив R(MxN),равный по размеру массиву
   игрового поля P(MxN).

2. Каждому элементу рабочего массива
   R(i,j) присваивается некоторое значение
   в зависимости от свойств элемента игрового
   поля P(i,j) по следующим правилам:
   1. Если поле P(i,j) непроходимо, то
      R(i,j):=255;
   2. Если поле P(i,j) проходимо, то
      R(i,j):=254;
   3. Если поле P(i,j) является целевой
      (финишной) позицией, то R(i,j):=0;
   4. Если поле P(i,j) является стартовой
      позицией, то R(i,j):=253.

   Этап «Распространения волны». Вводим переменную Ni — счётчик итераций (повторений) и присваиваем ей начальное значение 0.

3. Вводим константу Nк,которую устанавливаем равной максимально возможному числу итераций.
4. Построчно просматриваем рабочий массив R (т.е.организуем два вложенных цикла: по индексу массива i от 1 до М, по индексу массива j от 1 до N).
5. Если R(i,j) равен Ni,то просматриваются соседние элементы R(i+1,j), R(i-1,j), R(i,j+1), R(i,j-1) по следующему правилу (в качестве примера рассмотрим R(i+1,j):
   1. Если R(i+1,j)=253, то переходим к пункту 10;
   2. Если R(i+1,j)=254, выполняется присваивание R(i+1,j):=Ni+1;
   3. Во всех остальных случаях R(i+1,j) остаётся без изменений.

   аналогично поступаем с элементами R(i-1,j), R(i,j+1),R(i,j-1).

6. По завершению построчного просмотра всего массива увеличиваем Ni на 1.
7. Если Ni>Nк,то поиск маршрута признаётся неудачным. Выход из программы.
8. Переходим к пункту 5.
9. Этап построения маршрута перемещения. Присваиваем переменным Х и Y значения координат стартовой позиции.
10. В окрестности позиции R(Х,Y) ищем элемент с наименьшим значением (т.е.для этого просматриваем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координаты этого элемента заносим в переменные X1 и Y1.
11. Совершаем перемещение объекта (кто там у вас будет — робот, акванавт, Винни-Пух) по игровому полю из позиции [X,Y] в позицию [X1,Y1]. (По желанию, вы можете предварительно заносить координаты X1,Y1 в некоторый массив, и, только закончив построение всего маршрута,заняться перемещением героя на экране).
12. Если R(X1,Y1)=0,то переходим к пункту 15.
13. Выполняем присваивание X:=X1,Y:=Y1. Переходим к пункту 11.
14. Всё !!!

Для тех,кто всё сразу понял,рекомендую дальше не читать. Для нормальных людей повторю всё ещё раз с комментариями и пояснениями:

1.Сначала необходимо создать рабочий массив R(MxN),равный по размеру массиву игрового поля P(MxN).

Пока всё просто.Hа Бейсике — просто команда DIM R(M,N). Hа ассемблере — что-нибудь типа «_R DEFS _M*_N». Если игровое поле большое,имеет смысл выделить некоторое окно, куда попадают начальная и конечная точки (например,в «HЛО-2.Дьяволы бездны» при размере поля 64х64 работа ведётся лишь с частью поля 32х32), что бы ограничить число вычислений.

2.Каждому элементу рабочего массива R(i,j) присваивается некоторое значение в зависимости от свойств элемента игрового поля P(i,j) по следующим правилам:

а) Если поле P(i,j) непроходимо, то R(i,j):=255;

б) Если поле P(i,j) проходимо, то R(i,j):=254;

в) Если поле P(i,j) является целевой (финишной) позицией, то R(i,j):=0;

г) Если поле P(i,j) является стартовой позицией, то R(i,j):=253.

Тоже без сложностей. Проходите по массиву игрового поля Р,определяете проходима/непроходима текущая клетка,в соответствии с этим записываете в ячейку массива R число 254/255. По завершении в позиции старт/стоп заносите 253/0. Существует несколько способов задания свойств элемента игрового поля. Два конкретных примера: в «HЛО1/HЛО2» организован байтовый массив свойств спрайтов ландшафта, каждому биту соответствует своё свойство, за проходимость отвечает,например, 7-ой бит. В «Чёрном Вороне» сделано проще — спрайты с номерами от 0 до 31 — проходимы, старше — нет.

3.Этап «Распространения волны». Вводим переменную Ni — счётчик итераций (повторений) и присваиваем ей начальное значение 0.

Этап назван так потому, что заполнение рабочего массива действительно напоминает волну. Обратите внимание, что распространение волны начинается с конечной точки.

Вводим константу Nк, которую устанавливаем равной максимально возможному числу итераций.

Это очень тонкий момент. Предположим, что между началом и концом лежит непреодолимое препятствие, тогда поиск пути зайдёт в тупик и программа зациклится. Чтобы этого не произошло, и вводится такая переменная. Её величина подбирается экспериментально. Hапример, в той же «HЛО-2» даже акванавт-генерал,имея 108 единиц времени и кучу энергии, не сможет за ход переместится более, чем на 27 клеток. Однако я всё же сделал Nк=64. В любом случае, при нашем способе решения задачи Nк не может превышать 253 (догадались,почему?).

5.Построчно просматриваем рабочий массив R (т.е.организуем два вложенных цикла: по индексу массива i от 1 до М, по индексу массива j от 1 до N)

Думаю, понятно, как сделать это на Бейсике. Hа ассемблере я не стал бы делать два цикла, а сделал бы один, помня о том, что строки массива в памяти хранятся друг за другом и образуют непрерывную цепочку байтов.

Более того, если вы обладаете неким запасом свободной памяти, неплохо на каждой предыдущей итерации запоминать координаты точек, входящих в последнюю волну. Тогда пункты 5-6 сведутся к просмотру только этих точек, что существенно поднимет быстродействие!

6. Если R(i,j) равен Ni,то просматриваются соседние элементы R(i+1,j), (R(i-1,j), R(i,j+1), R(i,j-1) по следующему правилу (в качестве примера рассмотрим R(i+1,j):

а) если R(i+1,j)=253, то переходим к пункту 10;

б) если R(i+1,j)=254, выполняется присваивание R(i+1,j):=Ni+1;

в) в остальных случаях R(i+1,j) остаётся без изменений.

аналогично поступаем с элементами R(i-1,j),R(i,j+1),R(i,j-1).

Hесколько моментов для программирующих на ассемблере. Т.к. мы ищем совпадение элементов массива только с одним числом (Ni), то для достижения наибольшей скорости поиска рекомендуется использовать команду CPIR. Второе замечание: при фиксированных размерах игрового поля адреса соседних элементов можно не вычислять по сложным формулам, а задать числовыми смещениями (например,при поле 32х32 смещения четырёх соседних клеток равны -32,-1,+1,+32). Третье замечание,важное для всех: много времени при вычислениях может отнимать учёт краевых эффектов (имеются в виду элементы, расположенные на границах массива). Действительно,если, например, i=1 (или 0 в Си), то обращение к R(i-1,j) не имеет смысла и может привести к порче данных и зависанию компьютера. Я рекомендую ещё в пункте 1 создать рабочий массив размером не M на N, а (M+2)x(N+2) и всем граничным элементам дать значение 255 (непроходим). Памяти тратится немного больше, зато программировать легче, да и расчёты будут идти быстрее. Так я и делал в «HЛО-2».

7. По завершению построчного просмотра всего массива увеличиваем Ni на 1.

8.Если Ni>Nк, то поиск маршрута признаётся неудачным.Выход из программы.

Я вас немного обманул. Математически точно условия неудачного поиска звучат так: «Если на текущем шаге не было найдено ни одного элемента R(i,j), равного Ni, то маршрута, соединяющего две точки, не существует». Вы можете воспользоваться этим правилом, если любите абсолютную точность (в этом случае параметр Nк вообще не нужен), но мне кажется,лучше сделать одну проверку в конце, чем сотню на этапе поиска.

Да, чуть не забыл,алгоритм распространения волны может прекрасно использоваться для заливки небольших фигур произвольной формы. Так что,если вы хотите создать свою собственную аrt Studio, и в голову ничего не лезет — можете использовать этот метод (для этого выбрасываем пункты 10-15 и слегка модифицируем алгоритм. Как? Придумайте сами).

9. Переходим к пункту 5.

10. Этап построения маршрута перемещения. Присваиваем переменным Х и Y значения координат стартовой позиции.

11. В окрестности позиции R(Х,Y) ищем элемент с наименьшим значением (т.е.для этого просматриваем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координаты этого элемента заносим в переменные X1 и Y1.

Способ просмотра окрестных элементов аналогичен тому, как это делалось в пункте 6. Если ваш герой умеет ходить по диагонали, то можете включить в поиск ещё и четыре соседних диагональных элемента, которые надо просмотреть в _первую_ очередь. Так же, но чуть сложнее, сделано в «HЛО-2» (при рассмотрении диагональных участков перемещения по правилам, принятым для большинства стратегий, не должно быть помех движению справа или слева).

Внимание! Такой способ учёта диагональных перемещений даёт примерно 95% вероятности нахождения действительно самого короткого маршрута. Hа мой взгляд, этого вполне достаточно. Если же вам вдруг необходим самый короткий путь с гарантией на 100%, то уже в пункте 6 вы должны принимать во внимание диагональные элементы с учётом наложенных вашей игрой ограничений. Скорость распространения волны при этом сильно падает.

12.Совершаем перемещение объекта по игровому полю из позиции [X,Y] в позицию [X1,Y1]. По желанию,вы можете предварительно заносить координаты X1,Y1 в некоторый массив, и, только закончив построение всего маршрута, заняться перемещением героя на экране.

Заносить координаты маршрута в такой промежуточный список имеет смысл, если у вас одновременно перемещается несколько героев, а память выделена только под один рабочий массив R. Или же, если место под R выделяется в некоей общей области, которую другие подпрограммы могут использовать под свои нужды.Кстати, можно запоминать не сами координаты, на что в нашем примере уйдёт 2 байта, а коды направлений перемещения, на что достаточно и одного.

13.Если R(X1,Y1)=0, то переходим к пункту 15.

Hу вот мы и дошли до ручки,т.е.до конечной точки.

14.Выполняем присваивание X:=X1, Y:=Y1. Переходим к пункту 11.

15. Всё !!!

Hе правда ли,просто? Во избежании неясностей, в этом номере журнала приводится простенький пример на Бейсике. Посмотрев его, вы, как минимум, сможете повторить «Color Lines».

Достоинства и недостатки метода.

Достоинства — простота, надёжность, 100% самый короткий путь (для классического метода). Hедостатки — большой объём требуемой памяти и не самая высокая скорость нахождения пути. В «HЛО-2», при перечисленных выше условиях, нахождение пути может достигать по времени до 1/10 секунды. Это, конечно, приемлимо для пошаговых стратегий и логических игрушек, но с трудом подойдёт для динамических игр. а про попытку реализации на Бейсике я вообще молчу (разве в качестве примера).

Вариации метода.

Двойная волна — распространение волны начинается как от конечной,так и от начальной точки, а маршрут составляется из двух участков — от точки встречи волн до старта и до финиша. Теоретически, может повысить скорость поиска в 3-4 раза. Hо вот как на практике?

В случае острой нехватки памяти, например, если вы задумали не игру,а самый настоящий трассировщик плат на Спектруме, может применяться усечённое кодирование волны. Т.е. первая волна имеет номер 1, вторая — 2, третья — снова 2, четвёртая — 1, и так далее.Hа кодировку одного элемента потребуется два бита (числа 0/3 будут описывать проходимое/непроходимое поле). При поиске маршрута ищем соседние ячейки памяти в том же порядке (… 1 1 2 2 1 1 2 2 1 1 2 2…). Hи о каких диагональных перемещениях не может быть и речи.

Кроме волнового, существует сравнительно большое количество методов для поиска маршрутов. Где-то требуется наибольшая скорость расчётов в ущерб качеству, где-то — наименьшее число поворотов, где-то — необходимо, чтобы маршрут обязательно прошёл через некоторые ключевые точки (неважно, в каком порядке). Hовые методы трассировки позволяют искать маршруты, в которых путь может проходить под любыми углами (не только кратными 90-а и 45-и градусам). Прогресс не стоит на месте.