Элементарный поиск пути

← →
Ricks © (2005-10-20 00:43) [0]

Как в трехмерном пространстве (ландшафт + объекты) найти путь, по которому лучше всего добраться до заданной точки, учитывая что на пути могут встречаться препятствия и объезжая их?

← →
_111_ (2005-10-20 01:25) [1]

http://delphigfx.mastak.ru/samples.htm

там пара рабочих есть

← →
_111_ (2005-10-20 02:18) [2]

http://algolist.manual.ru/games/wavealg.php

еще нашел (в старых темах копаюсь)

← →
XProger © (2005-10-20 02:34) [3]

Ricks, а воспользоваться функцией поиска по форуму гордость не позволяет?

← →
Signate © (2005-10-20 09:33) [4]

Используй волновой метод, ищи кратчайший путь только на видемом куске карты

← →
TButton © (2005-10-20 17:29) [5]

> Элементарный поиск пути

кратчайшее асстояние от точки А до точки Б - прямая
берем направление на точку Б и шагаем вперед
встречаем препятствие - обходим
(пробовали в FPS бежать уперевшись в стену под неуоторым углом?)
достигаем точки Б - останавливаемся.

← →
Signate © (2005-10-20 17:40) [6]

> TButton © (20.10.05 17:29) [5]

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

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

если не найдете статью - могу куда нибудь ее залить

← →
Loginov Dmitry © (2005-10-20 18:00) [7]

В кладовке есть реальная прога, которая ищет кратчайщий путь волновым методом (раздел - студентам, автор Loginov)

← →
Signate © (2005-10-20 18:12) [8]

http://delphigfx.mastak.ru/samples/samp2.rar

прямая ссылка на реализацию... имхо не самая лучшая, но все же

← →
Ricks © (2005-10-20 20:40) [9]

То есть, если пользоваться указанными алгоритмами мне придется разбивать всю карту на участки проходимости (если карта 128*128, то проходимости примерно 256*256), заполнять их соответственно и искать пути?

← →
Loginov Dmitry © (2005-10-20 20:55) [10]

> Ricks © (20.10.05 20:40) [9]

А ты как думал?

← →
Signate © (2005-10-20 21:01) [11]

> Ricks © (20.10.05 20:40) [9]

У тебя должен быть массив проходимостей такого же размера как и массив карты и еще должен быть вспомогательный массив в котором будет считаться твой путь. Вспомогательный массив стоит делать размером с видимую часть карты... 16х16 например...

← →
TButton © (2005-10-21 01:18) [12]

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

а я и не спорю, ты просил элементарный поиск пути
а не универсальный
для простейшего AI такой метод архи подходящий

← →
JUS (2005-10-21 02:29) [13]

А ещё не забудь сделать, чтобы после каждого шага твой объект который должен дойти то точки назначения просчитывал путь заново (это для того случая, если ты направил свой объект на противника который имеет свойство перемещаться).
Представь к примеру что твой объект к примеру танк1, ему надо добраться и уничтожить танк2, ты направляеш танк1 на танк2 и пока твой танк1 доберётся до танка2(тот путь по которому направился танк1), то в это время танк2 куда нибудь срулит или вообще его уничтожат(в последнем случаее танк1 должен остановиться).

← →
Loginov Dmitry © (2005-10-21 08:44) [14]

Вы мой вариант не рассматривали?

http://kladovka.net.ru/download.cgi?id=239

Не знаю насчет универсальности метода. Алгоритм такой: есть 2 точки - начальная и конечная. Если они в зоне прямой видимости, то кратчайшее расстояние - прямая, в противном случае от обеих точек одновременно распространяются волны (причем распространение волн сначала идет по диагональным элементам, а затем - во вертикальным и горизонтальным). Как только эти волны встретились - точка из встречи отмечается как ключевая точка. Короче находится несколько ключевых точек, проверяется, лежат ли они в зоне видимости...
На 99 % ищется именно кратчайший путь.

> А ещё не забудь сделать, чтобы после каждого шага твой объект
> который должен дойти то точки назначения просчитывал путь
> заново

да да. я это подразумевал =)
по сути получается самонаводящийся... объект =)

> Loginov Dmitry © (21.10.05 08:44) [14]

есть у меня алгоритм, который пляшет от прямой
с огибанием препятствий, ограниченых некоторой окружностью
на выходе даёт список path nod"ов

задумывался на тот случай
когда используется не ячеечная
а непрерывная карта
на которой просто есть объекты заданые положением
и радиусом bounding окружности

> задумывался на тот случай
> когда используется не ячеечная
> а непрерывная карта
> на которой просто есть объекты заданые положением
> и радиусом bounding окружности

Вот-вот, у меня как раз такая карта пока что. TButton, можешь привести этот алгоритм?

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

и такая ботва на каждом шагу

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

кроме того можно сделать оценку проходимости местности
т.е. для карты 1км*1км
можно сделать байтовую карту 100*100 проходимости
и просто интерполируя рассчитывать проходимость любой точки

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

*******
* о *

А
бот затупит на смерть

резюме:
path nod"ов никто не отменял
и имхо, это наиболее подходящий вариант для premade карт

Но у меня игра не пошаговая, а типа real-time :)
Такие вычисления на каждом шаге каждого юнита... вобщем капец будет!

я в принципе на скорость не тестировал
но не думаю что будет слишком тормозно

http://dev.dtf.ru/articles/read.php?id=46
http://dev.dtf.ru/articles/read.php?id=36

http://gamedev.ru/articles/?id=70121

Элементарный поиск пути Найти похожие ветки