Обход препятсвия

← →
nordford (2010-07-26 16:23) [0]

Здравствуйте!
Пишу небольшую игру, есть необходимость перемещения игрока из одной точки в другую на плоскости. Игроки, как и препятствия, представляют собой круги (коорд и радиус). Так как особого поиска пути мне не нужно, обход препятсвия решил делать след образом: игрок идет к цели, если впереди препятствие, то изменяем угол в одну сторону, если там тоже препятствие, то в другую.
На рисунке это выглядит так:
http://i054.radikal.ru/1007/fe/a5e3992f0361.jpg
Вот часть кода:
function collision(k:integer):boolean; var i:integer; begin collision:=false; for i:=1 to 10 do if (sqrt(sqr(objects[i].x1-player[k].x)+sqr(objects[i].y1-player[k].y))<15+objects[i].r)then collision:=true; end; //в цикле, когда идем к цели //ygol- ф-я просчета угла ygl:=ygol(player[i].x,player[i].y,player[i].action.x,player[i].action.y); player[i].x:=player[i].x+player[i].speed*cos(ygl); player[i].y:=player[i].y+player[i].speed*sin(ygl); //proverka na collision if collision(i) then begin //если вошли в препятствие, то отходим назад ygl:=ygl-pi; player[i].x:=player[i].x+player[i].speed*cos(ygl); player[i].y:=player[i].y+player[i].speed*sin(ygl); //изменяется угол коэффициентом k*pi //k изменяется 0.7 -0.7 0.5 -0.5 k:=0.7; repeat ygl:=ygl+pi*k; player[i].x:=player[i].x+player[i].speed*cos(ygl); player[i].y:=player[i].y+player[i].speed*sin(ygl); flag:=false; if collision(i) then begin flag:=true; ygl:=ygl-pi*k; player[i].x:=player[i].x+player[i].speed*cos(ygl); player[i].y:=player[i].y+player[i].speed*sin(ygl); if (k<0) then k:=-k-0.2 else k:=-k; end; until (not flag)or(k=0.3);
В итоге правильно ходит только в одну сторону (по часовой стрелке) в другую просто стоит. Можно поменять в условии 0.7 на -0.7, тогда пойдет в другую сторону. Как бы сделать чтоб работало в обе стороны. Вроде все правильно и в теории и в коде. Единственное до чего я додумался, так это то, что программа прост не успевает записывать новые координаты игрока и правильно просчитывать коллизии. Пытался напихать application.processmessages но не помагает.
Когда-то давно была потребность в точно таком же действии, решил жутким способом, хотелось бы так, как задумано..

← →
Сергей М. © (2010-07-26 16:27) [1]

> если впереди препятствие, то изменяем угол в одну сторону, если там тоже препятствие, то в другую

.. и вновь упираемся рогом в первое ?)

← →
nordford (2010-07-26 16:32) [2]

> .. и вновь упираемся рогом в первое ?)

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

← →
Сергей М. © (2010-07-26 16:38) [3]

> если препятствий несколько, то .. будем просто стоять на месте

Стоя на месте переместиться из одной точки в другую никак не удастся))

← →
nordford (2010-07-26 16:45) [4]

> Стоя на месте переместиться из одной точки в другую никак
> не удастся))

вы заостряете свое внимание не на той проблеме.. как я уже сказал, поиск пути мне особо не нужен, если впереди сплошная стена, пусть герой упрется в нее и будет стоять, не суть важно.. однако если препятствие-это небольшой круг, то почему бы его плавно не обойти по контуру? чем плох предложенный мной алгоритм?

← →
Сергей М. © (2010-07-26 16:59) [5]

> почему бы его плавно не обойти по контуру?

Для этого нужно знать насколько он "небольшой". Т.е. знать его радиус или диаметр.

← →
nordford (2010-07-26 17:09) [6]

> Для этого нужно знать насколько он "небольшой". Т.е. знать
> его радиус или диаметр.

Для этого я в самом начале и написал:

> Игроки, как и препятствия, представляют собой круги (коорд
> и радиус).

У меня характеристики препятствий хранятся в objects[i].x1 objects[i].y1 objects[i].r
Или вам надо точное значение? Ну возьмите радиус игрока 15, а препятствия 30. Впрочем невижу никакой раздницы..

← →
Сергей М. © (2010-07-26 17:25) [7]

Когда твой "игрок" столкнулся с одним из препятствий, коих более одного и с разными радиусами, то как ты намерен выяснять с препятствием какого конкретно радиуса он столкнулся ?

← →
nordford (2010-07-26 17:33) [8]

> Когда твой "игрок" столкнулся с одним из препятствий, коих
> более одного и с разными радиусами, то как ты намерен выяснять
> с препятствием какого конкретно радиуса он столкнулся ?

эм.. никак, а смысл в этом? или я не понял вопроса..
в ф-ии коллизии в цикле просматриваем все препятствия на предмет пересечения с игроком.. если произошло пересечение, то отходим назад и ищем новый путь в сторонке.. впринципе в цикле то мы и узнаем с каким конкретно препятствием произошло столкновения, но мне это ни к чему..

> for i:=1 to 10 do
> if (sqrt(sqr(objects[i].x1-player[k].x)+sqr(objects[i].y1-
> player[k].y))<15+objects[i].r)then collision:=true;

← →
Сергей М. © (2010-07-26 17:57) [9]

Вот граф.иллютрация примера коллизии:

http://slil.ru/29501979

Куда двигаться объекту ? По какому "контуру" ?

← →
nordford (2010-07-26 18:11) [10]

> Куда двигаться объекту ? По какому "контуру" ?

вот на этой картинке действительно двигаться некуда, но я и хочу до вас донести, что поиск пути как таковой, мне не нужен.. т.е. идем вперед, залезаем на препятствие, отходим, идем влево, отходим, идем вправо, отходим.. все, стоим..
но что нам мешает обойти препятствие вот так:
http://s46.radikal.ru/i114/1007/d5/fc5f720ed25f.jpg
идем вперед, отходим, идем влево, отходим, идем вправо и в итоге придем..

← →
Сергей М. © (2010-07-26 18:17) [11]

> на этой картинке действительно двигаться некуда

Как это некуда ?
Цель-то достижима)
Я к тому чтобы ты опредилился с алгоритмом обработки множественной коллизии.

← →
nordford (2010-07-26 18:39) [12]

да не нужен мне "алгоритм обработки множественной коллизии" )) если впереди, слева и справа находятся препятствия, то герой просто стоит на месте и все.. искать оптимальный путь, учитывая все объекты, это слишком долго..

на счет своего алгоритма я уверен на 95% и проблема, считаю, не в нем самом, а в том, как он воспроизводится, т.е. программа просто не успевает запомнить изменившуюся координату и вбить ее в функцию.. по крайней мере я так думаю, и спрашиваю у вас совета, так ли это и можно ли это исправить...

← →
MonoLife © (2010-07-26 18:48) [13]

> Как бы сделать чтоб работало в обе стороны
random()? 0.7 or -0.7

← →
nordford (2010-07-26 18:53) [14]

> random()? 0.7 or -0.7

нет, рендом тут не прокатит.. в цикле значение меняется
0.7 -0.7 0.5 -0.5
должно работать в обе стороны, но косячит походу второй вызов функции collision (это который в цикле)

← →
12 © (2010-07-27 09:41) [15]

k:=0.7;
repeat
ygl:=ygl+pi*k;
player[i].x:=player[i].x+player[i].speed*cos(ygl);
player[i].y:=player[i].y+player[i].speed*sin(ygl);
flag:=false;
if collision(i) then
begin
flag:=true;
ygl:=ygl-2*pi*k;
player[i].x:=player[i].x+player[i].speed*cos(ygl);
player[i].y:=player[i].y+player[i].speed*sin(ygl);
if (k<0) then
k:=-k-0.2
else k:=-k;
end;
until (not flag)or(k=0.3);
так если?

← →
12 © (2010-07-27 09:44) [16]

т.е. ошибка имхо такова:
Вы прибавили угол обхода, если не получилось - надо в др. сторону попробовать.
Но отнимать надо не угол, а два угла - один чтоб вернуть угол как был, а потом второй раз, чтоб считать

← →
nordford (2010-07-27 18:13) [17]

мыслите правильно, но не совсем) переведу мой код на русский:
k:=0.7;
НАЧАЛО ЦИКЛА
Изменяем угол в одну сторону
Идем туда
Флаг=нет
Если зашли на препятствие, то
Флаг=да
угол меняем обратно, как было
идем обратно, как было
изменяем коэф k чтоб в другую сторону
конец условия
КОНЕЦ ЦИКЛА (выходим если нету флага или к мало)

Т.е. идем куда-нибудь. если препятствие, то отходим обратно и идем в другую сторону..

← →
12 © (2010-07-28 13:20) [18]

блин, надо переписать
player[i].x:=player[i].x+player[i].speed*cos(ygl);
player[i].y:=player[i].y+player[i].speed*sin(ygl);

procedure Move(nPl:integer; Angl:double);
begin
player[nPl].x:=player[nPl].x+player[nPl].speed*cos(Angl);
player[nPl].y:=player[nPl].y+player[nPl].speed*sin(Angl);
end;

Function TrueMove(nPl:integer; Angl:double):boolean;
var
Angl2: double;
begin
Result := true;
Move(nPl, Angl);
if collision(nPl) then
begin
Angl2 := Angl - Pi;
Result := false;
Move(nPl, Angl2);
end;
end;

ygl:=ygol(player[i].x,player[i].y,player[i].action.x,player[i].action.y);
if not(TrueMove(i,ygl)) then
begin
//изменяется угол коэффициентом k*pi
//k изменяется 0.7 -0.7 0.5 -0.5
k:=0.7;
repeat
ygl:=ygl+pi*k;
if (k<0) then
k:=-k-0.2
else k:=-k;
until (TrueMove(i, ygl)) or (k=0.3);
end;

вроде правильно все..
Не работает? (не проверял сам, прямо тут пишу)

Чего-то я не понял, зачем гадать в какую сторону идти?
В данном случае, строим касательную в точке пересечение траектории движения с препятствием. Далее сравниваем два угла - где меньше, туда и поворачиваем. Или я тему не догнал?

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

все правильно, но это надо еще формулы/считать
по простому же если - алгоритм вполне себе ничего

Вот еще вариант, тут совсем все просто, и по-челочески понятно

procedure Move(nPl:integer; Angl:double);
begin
player[nPl].x:=player[nPl].x+player[nPl].speed*cos(Angl);
player[nPl].y:=player[nPl].y+player[nPl].speed*sin(Angl);
end;

Function TrueMove(nPl:integer; Angl:double):boolean;
var
Angl2: double;
begin
Result := true;
Move(nPl, Angl);
if collision(nPl) then
begin
Angl2 := Angl - Pi;
Result := false;
Move(nPl, Angl2);
end;
end;

ygl:=ygol(player[i].x,player[i].y,player[i].action.x,player[i].action.y);
if not(TrueMove(i,ygl)) then
repeat
dAngle := dAngle + 0.1;
until TrueMove(i, ygl + dAngle) or TrueMove(i, ygl - dAngle) or (dAngle > 1);

> надо еще формулы/считать

да там одна формула-то, движение по окружности... что может быть проще?

> а там одна формула-то, движение по окружности... что может
> быть проще?

в этом случае - да, sin|cos и вперед
но чем мне этот алгоритм понравился - препятствие может быть любым, не только круглым

← →
nordford (2010-07-29 13:25) [24]

извините, вчера не смог написать..

> 12

спасибо, действительно помогло разбиение этого кода на отдельные процедуру и функцию.. единственно немного поправил код:
until TrueMove(i, ygl + dAngle) or TrueMove(i, ygl - dAngle)
если написать так, то при возможном движении как влево, так и вправо, объект будет просто стоять в ступоре..
вообщем, спасибо, все вышло как нельзя лучше!..

> строим касательную в точке пересечение траектории движения
> с препятствием. Далее сравниваем два угла - где меньше,
> туда и поворачиваем.

что-то подобное я делал прошлый раз, но это не всегда удобно..
и, да, действительно:

> чем мне этот алгоритм понравился - препятствие может быть
> любым, не только круглым

главное знать, что мы вошли в препятствие, а какова ее форма значения не имеет.. хотя, извиняюсь, т.к. в самом начале условия я говорил лишь о кругах, думал так будет проще..

> спасибо, действительно помогло разбиение этого кода на отдельные
> процедуру и функцию.. единственно немного поправил код:
> until TrueMove(i, ygl + dAngle) or TrueMove(i, ygl - dAngle)

надо ставить "не вычислять полностью булевы операции", тогда будет и быстрее считать и не будет

> при возможном движении как влево, так и вправо,
> просто стоять в ступоре..

← →
nordford (2010-07-29 13:53) [26]

> не вычислять полностью булевы операции

действительно.. чет я не подумал..

Обход препятсвия Найти похожие ветки