|
3D-программирование Вопросы, касающиеся программирования 3D мира |
01.05.2009, 13:54
|
#1
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Поиск кратчайшего пути
Юзал поиск, ничего толкового не нашёл.
Существуют ли в природе примеры нахождения пути ботами, находящимися в весьма запутанных образованях этих путей?
К примеру таких:
пишут же люди шутеры на блице, неужели до сих нет ии нормального))
всё что я находил по словам "вейпоинты", "waypoints" было обычно тупым катанием по вейпоинтам по кругу.
A* мне удалось заставить работать в 3д но это оказалось оччень непрактично...т.е. либо выходит что делаешь сетку из таких крупных ячеек что маленькие лазы не отмечаются, либо из таких мелких, что их перебор занимает слишком много времени.
|
(Offline)
|
|
01.05.2009, 14:16
|
#2
|
|
Ответ: Поиск кратчайшего пути
Mr_F_
для шутеров используй area awareness system (aas)
http://www.kbs.twi.tudelft.nl/docs/M...van/thesis.pdf с 34 страницы
имхо идинственая нормальный способ поиска пути для шутеров
|
|
|
Сообщение было полезно следующим пользователям:
|
|
01.05.2009, 14:26
|
#3
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Ответ: Поиск кратчайшего пути
может май инглиш из нот вери велл, но по ходу все равно остаётся проблема нахождения пути, если боту надо перейти с одной выпуклой формы на другую при условии что между ними ещё куча разных форм.
|
(Offline)
|
|
01.05.2009, 14:30
|
#4
|
|
Ответ: Поиск кратчайшего пути
Mr_F_
какая проблема ? AAS это тупо обьем в котором бот может физически находится на карте (просчитываются варианты что он куда-то прыгнет и тд и тп), как я понимаю этот обьем задается параллелепипедами (возможно и другие реализации), вот и ищешь путь по параллелепипедам, а потом просто смотришь каким способом ты можешь между ними проходить (прыгнуть, присесть и тд)
и никаких вейпоинтов не надо алгоритм универсален идинственое что AAS надо просчитать для карты заранее
|
|
|
01.05.2009, 15:57
|
#5
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Ответ: Поиск кратчайшего пути
ну как бот поймёт куда ему идти:
|
(Offline)
|
|
01.05.2009, 17:21
|
#6
|
|
Ответ: Поиск кратчайшего пути
на рисунке два этапа : 1 и 2 - полученый обьем и его графовое представление, 3 - переход от областей к графу связей
вот только задача как определять растояние между одной связью и другой ? есть идея брать минимальное среди между двумя отрезками
|
|
|
Эти 2 пользователя(ей) сказали Спасибо за это полезное сообщение:
|
|
01.05.2009, 18:01
|
#7
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Ответ: Поиск кратчайшего пути
хм я нашёл неплохой пример юзанья алгоритма Дейкстры.
вот сделал им вейпоинты.
связи между поинтами можно будет переделать в выпуклые формы в принципе.
|
(Offline)
|
|
01.05.2009, 18:17
|
#8
|
ПроЭктировщик
Регистрация: 11.11.2008
Адрес: Тольятти
Сообщений: 153
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Поиск кратчайшего пути
Mr_F_ а можешь показать етот пример?
jimon а есть эта книга на русском языке?
|
(Offline)
|
|
01.05.2009, 18:20
|
#9
|
|
Ответ: Поиск кратчайшего пути
Sashka007
нету её на русском языке, зачем ? кому очень надо выучат английский
Mr_F_
так тебе приходится раставлять вейпоинты, а AAS само за тебя всё делает, в прочем решать тебе
|
|
|
01.05.2009, 18:43
|
#10
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Ответ: Поиск кратчайшего пути
так тебе приходится раставлять вейпоинты
|
да мне так надёжнее.
Mr_F_ а можешь показать етот пример?
|
прицепляю к посту
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо Mr_F_ за это полезное сообщение:
|
|
07.05.2009, 14:17
|
#11
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: Поиск кратчайшего пути
так тебе приходится раставлять вейпоинты, а AAS само за тебя всё делает, в прочем решать тебе
|
jimon, мож раскажеш вкратце как оно само расставляет ??
Mr_F_ , в 2д разделе, там тема про волновой, я опписовал алгоритм Дейкстры !! но там сам принцип !! на основе его есть у меня исходник в 3Д !! завтра, если незбуду, принесу, скину !!
хотя твой пример "Dijkstra.zip" тож ниче !! я бы сказал даже круче, т.к. есть уже готовые функции для постороения готовой системи вейпоинтов !!
|
(Offline)
|
|
07.05.2009, 20:11
|
#12
|
|
Ответ: Поиск кратчайшего пути
IGR
строится пустое пространство уровня (берется всё пространство и из него вычитаются обьемы стенок уровня), от этого пространства отсекаются зоны когда игрок не может попасть (по-сути почти брутфорс, на уровне задается несколько стартовых точек, имеем плоскость, просчитываются все варианты - запрыгнуть куда-то, перепрыгнуть и тд и тп), получаем пространство в котором может находится игрок, разбиваем его на выпуклые многоугольники между которыми ставим связь как можно попасать из одного в другой, вот и всё
операция ресурсоёмкая, потому просчёт делается заранее
|
|
|
Эти 2 пользователя(ей) сказали Спасибо за это полезное сообщение:
|
|
07.05.2009, 20:50
|
#13
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: Поиск кратчайшего пути
ясн !!
берется всё пространство и из него вычитаются обьемы стенок уровня
|
вот это самое интересно !! что именно подразумивается под словом "берется" ?? матиматически это как ?? как кодом ?? какие существуют методы "взять" ??
|
(Offline)
|
|
07.05.2009, 20:59
|
#14
|
|
Ответ: Поиск кратчайшего пути
IGR
обычно FPS игры имеют довольно компактные уровни, всё пространство для уровня это некий параллелепипед который можно задать в редакторе или посчитать самому исходя из крайних точек уровня
как отнимаются ? тут много вариантов, можно исходить из такой операции - отнимание от выпуклых многоугольников выпуклый многоугольник и разбивать результат на выпуклые многоугольники
первоначально будет только один параллелепипед и потом от него будем отнимать по очереди все выпуклые многоугольники которые представляют уровень
|
|
|
07.05.2009, 21:05
|
#15
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: Поиск кратчайшего пути
ясно !!
кста, есть библиотека, правда для с++ !! там короче демка мне понравилась как машина по трасе сама едит, типо путь ищет !!
http://sourceforge.net/projects/opensteer/
(нада несколько раз <таб> что б включить ту демку !!)
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 21:49.
|