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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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