|
18.01.2014, 20:45
|
#1
|
Оператор ЭВМ
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
|
Алгоритм обхода препятствий
Я расматривал два алгоритма, Волновой(алгоритм Ли) и А*. Для меня проще волновой, но он требует много памяти для исполнения, не у каждого телефона будет достаточно памяти чтобы подсчитывать путь для 50 юнитов(+ еще 50 у противника). А* оптимальнее, но я не знаю как это реализовать на паскале, может кто-нибудь написать хотябы псевдокод
|
(Offline)
|
|
29.01.2014, 23:22
|
#2
|
Оператор ЭВМ
Регистрация: 09.02.2013
Сообщений: 46
Написано 6 полезных сообщений (для 13 пользователей)
|
Ответ: Алгоритм обхода препятствий
Легко, правда моя рекурсия не корректно строила пути.
Var
Cx:array[0..3]of integer; // 0, 1 , 0, -1
Cy:array[0..3]of integer; // -1, 0 , 1, 0
Карта мира
m:array[0..9,0..9]of integer;
Карта ботов
b:array[0..9,0..9]of integer;
Массив M, игровой мир, допустим 0-свободная клетка, 1 препятсвие
Получения карты B для юнита.
Стоим карту массива B из массива M, я делал так.
for i:=0 to 9 do
for j:=0 to 9 do
if B[j,i]=0 then B[j,i]:=-1; Проходимым участкам присваивал -1, для того что бы поиск пути был более комфортный,
if B[j,i]=1 then B[j,i]:=-2; Непроходимые участки -2
Делал прежде всего бота, который искал ближайшую приоритетную цель, но если вам нужно сделать, просто движение к указанной точке то все проще.
В этом массиве B, координате юнита присваивал значение 0, -3 допустим наша цель, после запускал рекурсию.
Us:boolean -глобальная переменная, для остановки рекурсии если цель найдена.
Процедура Поиск цели(x,y:integer; );
Переменные z:integer;
Начало
If us=false then
for z:=0 to 3 do {Используем константы, и проверяем 4-е направления}
if b[ x+Cx[z] ,y+Cy[z] ]=-1 then
begin
b[ x+Cx[z] ,y+Cy[z] ] := b[x,y];{Пристваиваем соседним ячейкам значение на 1-цу больше, поэтому стартовую точка и имела значение 0 для удобства}
Поиск(x+Cx[z] ,y+Cy[z] );{Заново запускаем рекурсию}
end;
Конец
В этом же коде вставляем проверку на цель. Если находим цель, останавливаем рекурсию . Сохраняем точку цели, я потом уже от этой точки запускаем рекурсию еще раз, но точкой цели будет уже наш юнит.
После заполнения Массива Карты B,
сдвигаем юнита на ячейку с меньшим значением. Вот и все.
Так двигался мой бот.
На ранних этапах проект работал корректно, но после поиск стал идти кругами, что и логично в общем.
Поэтому интересно услышать что нибудь по-поводу рекурсии поиска, и что собственно не так.
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо Ahsoka_Tano за это полезное сообщение:
|
|
29.01.2014, 23:32
|
#3
|
Оператор ЭВМ
Регистрация: 09.02.2013
Сообщений: 46
Написано 6 полезных сообщений (для 13 пользователей)
|
Ответ: Алгоритм обхода препятствий
Бот бегает по карте и собирает квадратики.
Вот версия того что описано выше, но без рекурсии( зы. Раньше ни как не получалось ее сделать), здесь зациклен поиска пути, но это не эффективно в плане быстродействия.
|
(Offline)
|
|
12.02.2014, 01:17
|
#4
|
Оператор ЭВМ
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
|
Ответ: Алгоритм обхода препятствий
Спасибо, я примерно таким же способом хотел, но это сильно ударит по памяти( размер мира массив[0..55,0..60] это максимальный размер). Может для экономии памяти просто сделать так: если точка слева от юнита уменьшать Х если на пути препятствие, то сменить направление вверх(тогда точка слева внизу) и приблежать юнита к точке, если опять препятствие, то снова сменить направление.
|
(Offline)
|
|
06.03.2014, 00:13
|
#5
|
AnyKey`щик
Регистрация: 06.03.2014
Сообщений: 1
Написано 0 полезных сообщений (для 0 пользователей)
|
Ответ: Алгоритм обхода препятствий
Тоже мучаюсь с этой проблемой, недавно наткнулся на ссылку алгоритмы поиска пути и заинтересовался методом Best-First Search, на мой взгляд он самый оптимальный, но не как не получается написать код на паскале, то кругами идёт, то стоит, кто-нибудь помогите.
|
(Offline)
|
|
06.03.2014, 22:04
|
#6
|
Оператор ЭВМ
Регистрация: 09.02.2013
Сообщений: 46
Написано 6 полезных сообщений (для 13 пользователей)
|
Ответ: Алгоритм обхода препятствий
Знакомо. Скоро придется вернуться к программированию Ботов. Держите в курсе дела, если разберетесь. Постараюсь скорее приступить.
__________________
superomnis
|
(Offline)
|
|
07.03.2014, 01:21
|
#7
|
Оператор ЭВМ
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
|
Ответ: Алгоритм обхода препятствий
Сообщение от Ahsoka_Tano
Знакомо. Скоро придется вернуться к программированию Ботов. Держите в курсе дела, если разберетесь. Постараюсь скорее приступить.
|
Я решил сделать так:
Если точка слева вверху от юнита, то просто идём к ней, если на пути встречается препятствие
смотрим на лево и на право в радиусе двух клеток. Самую ближайшую свободную клетку назначаем временной точкой. После назначения юнит подходит к временной точке, вр. точка :=0; Идём к основной точке, если опять препятствие, то повторяем процедуру и так пока не доберётся до неё.
Сейчас компьютер не рядом, завтра кину код.
|
(Offline)
|
|
11.03.2014, 18:04
|
#8
|
ПроЭктировщик
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений (для 91 пользователей)
|
Ответ: Алгоритм обхода препятствий
Если мир динамичный, то следует взять тот же астарс. Но расчет вести не от юнита к цели, а наоборот. В этом случае не придется вносить в память стоимость пути и родительские клетки. Получается что мы расчитываем не полностью короткий путь, а последовательно с каждым циклом находим клетку куда он должен идти. В последствии пройдет ровно такой же путь как и астарс, плюс спокойная реакция на изменения на карте
|
(Offline)
|
|
17.03.2014, 22:17
|
#9
|
Оператор ЭВМ
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
|
Ответ: Алгоритм обхода препятствий
Вот алгоритм:
1.Движемся к точке.
2.Если препятсвтие, то...
3.Сканиреуем мир в радиусе двух клеток от юнита на препятствия.
4.Затем, среди каждого проходимого блока ищем точку наимение удалённую от координат дома.(с этим проблем нет)
5. Координаты полученные в п.4 запоминаем и передвигаем юнита к этой точке
6. Продолжаемся двигаться к точке, указанной в п.1, если опять препятсвие повторяем.
Проблема в том, что могут возникнуть препятсвие даже между этой временной точкой. Я присваивал блоку в п.4 значения не проходимого блока и опять запускал процедуру уже не расматривая этот блок, но юнит то стоит на месте, то идет вообще непонятно куда.
type SoldierType = record x,y,wx,wy,ptx,pty,psx,psy,px,py,dir,r,anim,anim_timer,ta,speed: integer;//dir-direction,ta-time attack,wx-world x sel: boolean;//isg-is going end;
var ftp: array[0..26] of integer;// f,g,h,fw: integer;// soldier: array [0..10] of SoldierType; world_sold: array [0..52,0..57] of integer; world: array [0..52,0..57] of integer;
j:=-2; for i:=1 to 25 do begin k[i]:=j; j:=j+1; if j>2 then j:=-2;
if i<5 then l[i]:=-2;else if i<10 then l[i]:=-1;else if i<15 then l[i]:= 0;else if i<20 then l[i]:= 1;else if i<25 then l[i]:= 2; end;//
procedure across(x,y,x1,y1,i: integer;);// begin
for f:=1 to 25 do begin ftp[f]:=abs(x1-x+y1-y); end;
h:=52*57;// Растояние максимальное for f:=1 to 25 do begin if (ftp[f]<=h) and (world_sold[x+k[f],y+l[f]]=-1) then // если находится точка ближе чем предыдущая begin h:=ftp[f];// новое расстояние g:=f;// запоминаем номер end;//ftp<h end;// for f:=1 .....
end;//proc
procedure findway(x,y,x1,y1,i: integer;);//x1=put x, i=№ soldier begin
for f:=1 to 56 do for g:=1 to 51 do begin world_sold[g,f]:=-3;//чистим мир// Думаю это стоит вызывать через определённое время, а не каждый раз, иначе в этом нет смысла end;
if (x>2) and (x<51) and (y>2) and (y<56) then begin for f:=(y-2) to (y+2) do for g:=(x-2) to (x+2) do begin if (world[g,f]>2) and (world[g,f]<7) then world_sold[g,f]:=-2;else//-2 neprohodimuy block world_sold[g,f]:=-1;//-1 prohodimuy end;//for end;//if (x>2) and (x<51) and (y>2) and (y<56)
world_sold[x,y]:=i;// we was here world_sold[x1,y1]:=0;// target
across(x,y,x1,y1,i); // Далее если между выбранной временной точкой и юнитом нет препятсвия то назначаем её, иначе помечаем назначенный блок как непроходимый и запускаем процедуру ещё раз if ((x>x+k[g]) and (y>y+l[g]) and (world_sold[x+k[7], y+l[7]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//1 if ((x=x+k[g]) and (y>y+l[g]) and (world_sold[x+k[8], y+l[8]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//2 if ((x<x+k[g]) and (y>y+l[g]) and (world_sold[x+k[9], y+l[9]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//3 if ((x<x+k[g]) and (y=y+l[g]) and (world_sold[x+k[12],y+l[12]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//4 if ((x>x+k[g]) and (y=y+l[g]) and (world_sold[x+k[14],y+l[14]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//6 if ((x>x+k[g]) and (y<y+l[g]) and (world_sold[x+k[17],y+l[17]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//7 if ((x=x+k[g]) and (y<y+l[g]) and (world_sold[x+k[18],y+l[18]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//8 if ((x<x+k[g]) and (y<y+l[g]) and (world_sold[x+k[19],y+l[19]]=-1)) then begin soldier[i].ptx:=(x+k[g]); soldier[i].pty:=(y+l[g]);end;else begin world_sold[x+k[g],y+k[g]]:=1; across(x,y,x1,y1,i); end;//9
DrawText('Searching...',100,100);
end;//procedure
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 13:51.
|