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

[Mr_F_]

Юзал поиск, ничего толкового не нашёл.

Существуют ли в природе примеры нахождения пути ботами, находящимися в весьма запутанных образованях этих путей?

К примеру таких:


пишут же люди шутеры на блице, неужели до сих нет ии нормального))

всё что я находил по словам "вейпоинты", "waypoints" было обычно тупым катанием по вейпоинтам по кругу.

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

Mr_F_
для шутеров используй area awareness system (aas)
http://www.kbs.twi.tudelft.nl/docs/M...van/thesis.pdf с 34 страницы

имхо идинственая нормальный способ поиска пути для шутеров

[Mr_F_]

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

Mr_F_
какая проблема ? AAS это тупо обьем в котором бот может физически находится на карте (просчитываются варианты что он куда-то прыгнет и тд и тп), как я понимаю этот обьем задается параллелепипедами (возможно и другие реализации), вот и ищешь путь по параллелепипедам, а потом просто смотришь каким способом ты можешь между ними проходить (прыгнуть, присесть и тд)
и никаких вейпоинтов не надо алгоритм универсален идинственое что AAS надо просчитать для карты заранее

[Mr_F_]

ну как бот поймёт куда ему идти:

на рисунке два этапа : 1 и 2 - полученый обьем и его графовое представление, 3 - переход от областей к графу связей
вот только задача как определять растояние между одной связью и другой ? есть идея брать минимальное среди между двумя отрезками

[Mr_F_]

хм я нашёл неплохой пример юзанья алгоритма Дейкстры.

вот сделал им вейпоинты.

связи между поинтами можно будет переделать в выпуклые формы в принципе.

[Sashka007]

Mr_F_ а можешь показать етот пример?

jimon а есть эта книга на русском языке?

Sashka007
нету её на русском языке, зачем ? кому очень надо выучат английский

Mr_F_
так тебе приходится раставлять вейпоинты, а AAS само за тебя всё делает, в прочем решать тебе

[Mr_F_]

так тебе приходится раставлять вейпоинты

да мне так надёжнее.

Mr_F_ а можешь показать етот пример?

прицепляю к посту

[IGR]

так тебе приходится раставлять вейпоинты, а AAS само за тебя всё делает, в прочем решать тебе

jimon, мож раскажеш вкратце как оно само расставляет ??

Mr_F_ , в 2д разделе, там тема про волновой, я опписовал алгоритм Дейкстры !! но там сам принцип !! на основе его есть у меня исходник в 3Д !! завтра, если незбуду, принесу, скину !!
хотя твой пример "Dijkstra.zip" тож ниче !! я бы сказал даже круче, т.к. есть уже готовые функции для постороения готовой системи вейпоинтов !!

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

[IGR]

ясн !!

берется всё пространство и из него вычитаются обьемы стенок уровня

вот это самое интересно !! что именно подразумивается под словом "берется" ?? матиматически это как ?? как кодом ?? какие существуют методы "взять" ??

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

[IGR]

ясно !!
кста, есть библиотека, правда для с++ !! там короче демка мне понравилась как машина по трасе сама едит, типо путь ищет !!
http://sourceforge.net/projects/opensteer/
(нада несколько раз <таб> что б включить ту демку !!)