Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для мобильных телефонов > MidletPascal

Ответ
 
Опции темы
Старый 18.01.2014, 20:45   #1
.:MaSe:.
Оператор ЭВМ
 
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
Алгоритм обхода препятствий

Я расматривал два алгоритма, Волновой(алгоритм Ли) и А*. Для меня проще волновой, но он требует много памяти для исполнения, не у каждого телефона будет достаточно памяти чтобы подсчитывать путь для 50 юнитов(+ еще 50 у противника). А* оптимальнее, но я не знаю как это реализовать на паскале, может кто-нибудь написать хотябы псевдокод
(Offline)
 
Ответить с цитированием
Старый 29.01.2014, 23:22   #2
Ahsoka_Tano
Оператор ЭВМ
 
Аватар для Ahsoka_Tano
 
Регистрация: 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 за это полезное сообщение:
.:MaSe:. (17.02.2014), Dark Dragon (02.02.2014), rumed (06.03.2014)
Старый 29.01.2014, 23:32   #3
Ahsoka_Tano
Оператор ЭВМ
 
Аватар для Ahsoka_Tano
 
Регистрация: 09.02.2013
Сообщений: 46
Написано 6 полезных сообщений
(для 13 пользователей)
Ответ: Алгоритм обхода препятствий

Бот бегает по карте и собирает квадратики.
Вот версия того что описано выше, но без рекурсии( зы. Раньше ни как не получалось ее сделать), здесь зациклен поиска пути, но это не эффективно в плане быстродействия.
Вложения
Тип файла: rar PixWorld.rar (6.8 Кб, 875 просмотров)
(Offline)
 
Ответить с цитированием
Старый 12.02.2014, 01:17   #4
.:MaSe:.
Оператор ЭВМ
 
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
Ответ: Алгоритм обхода препятствий

Спасибо, я примерно таким же способом хотел, но это сильно ударит по памяти( размер мира массив[0..55,0..60] это максимальный размер). Может для экономии памяти просто сделать так: если точка слева от юнита уменьшать Х если на пути препятствие, то сменить направление вверх(тогда точка слева внизу) и приблежать юнита к точке, если опять препятствие, то снова сменить направление.
(Offline)
 
Ответить с цитированием
Старый 06.03.2014, 00:13   #5
rumed
AnyKey`щик
 
Регистрация: 06.03.2014
Сообщений: 1
Написано 0 полезных сообщений
(для 0 пользователей)
Ответ: Алгоритм обхода препятствий

Тоже мучаюсь с этой проблемой, недавно наткнулся на ссылку алгоритмы поиска пути и заинтересовался методом Best-First Search, на мой взгляд он самый оптимальный, но не как не получается написать код на паскале, то кругами идёт, то стоит, кто-нибудь помогите.
(Offline)
 
Ответить с цитированием
Старый 06.03.2014, 22:04   #6
Ahsoka_Tano
Оператор ЭВМ
 
Аватар для Ahsoka_Tano
 
Регистрация: 09.02.2013
Сообщений: 46
Написано 6 полезных сообщений
(для 13 пользователей)
Ответ: Алгоритм обхода препятствий

...то кругами идёт
Знакомо. Скоро придется вернуться к программированию Ботов. Держите в курсе дела, если разберетесь. Постараюсь скорее приступить.
__________________
superomnis
(Offline)
 
Ответить с цитированием
Старый 07.03.2014, 01:21   #7
.:MaSe:.
Оператор ЭВМ
 
Регистрация: 14.08.2013
Сообщений: 27
Написано одно полезное сообщение
Ответ: Алгоритм обхода препятствий

Сообщение от Ahsoka_Tano Посмотреть сообщение
Знакомо. Скоро придется вернуться к программированию Ботов. Держите в курсе дела, если разберетесь. Постараюсь скорее приступить.
Я решил сделать так:
Если точка слева вверху от юнита, то просто идём к ней, если на пути встречается препятствие
смотрим на лево и на право в радиусе двух клеток. Самую ближайшую свободную клетку назначаем временной точкой. После назначения юнит подходит к временной точке, вр. точка :=0; Идём к основной точке, если опять препятствие, то повторяем процедуру и так пока не доберётся до неё.
Сейчас компьютер не рядом, завтра кину код.
(Offline)
 
Ответить с цитированием
Старый 11.03.2014, 18:04   #8
Izunad
ПроЭктировщик
 
Аватар для Izunad
 
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений
(для 91 пользователей)
Ответ: Алгоритм обхода препятствий

Если мир динамичный, то следует взять тот же астарс. Но расчет вести не от юнита к цели, а наоборот. В этом случае не придется вносить в память стоимость пути и родительские клетки. Получается что мы расчитываем не полностью короткий путь, а последовательно с каждым циклом находим клетку куда он должен идти. В последствии пройдет ровно такой же путь как и астарс, плюс спокойная реакция на изменения на карте
(Offline)
 
Ответить с цитированием
Старый 17.03.2014, 22:17   #9
.:MaSe:.
Оператор ЭВМ
 
Регистрация: 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,speedinteger;//dir-direction,ta-time attack,wx-world x
selboolean;//isg-is going
  
end;

var
ftp: array[0..26of integer;// 
f,g,h,fwinteger;// 
soldier: array [0..10of SoldierType;
world_sold: array [0..52,0..57of integer;
world: array [0..52,0..57of 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,iinteger;);// 
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]]=-1then // если находится точка ближе чем предыдущая
begin 
h
:=ftp[f];// новое расстояние
g:=f;// запоминаем номер
end;//ftp<h
end;// for f:=1 .....

end;//proc

procedure findway(x,y,x1,y1,iinteger;);//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<56then
begin
for f:=(y-2to (y+2) do
for 
g:=(x-2to (x+2) do
begin
if (world[g,f]>2) and (world[g,f]<7then 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]]:=1across(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]]:=1across(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]]:=1across(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]]:=1across(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]]:=1across(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]]:=1across(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]]:=1across(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]]:=1across(x,y,x1,y1,i); end;//9

DrawText('Searching...',100,100);

end;//procedure 
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 08:57.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com