Войти
ПрограммированиеФорумИгровая логика и ИИ

Хоббит, туда и обратно. Поиск пути. Поиск нескольких путей до цели.

#0
9:48, 10 авг. 2009

Задача:
есть связанный граф. количество узлов небольшое - около сотни, может чуть больше. НЕ СЕТКА (в связи с этим чет придумать не могу эвристику)
- АИ должен определить в нем целевые узлы куда он МОЖЕТ попасть (то бишь не конкретная цель, а ему "все равно", алгоритм выбора есть) - готово и не сложно
- Должен построить по нескольку путей к каждой цели (основная сложность, чтоб не было "петель" и т.п., пути должны быть разными, но не сильно) - тут только мысль про два прохода строить кратчайшие пути до каждой цели и потом задавая максимальную стоимость пути, основываясь на стоимости кратчайшего, делать второй проход и искать все возможные пути попадающие в указанную стоимость. ИМХО муторно, возможно неправильно
- Должен после этого выбрать из этого всего добра один путь - просто рандом, катит
- Добравшись до целевого узла, он должен идти обратно в исходный узел по другому пути, максимально отличающемся от того, каким пришел. - тут пока мыслей нет

В общем, муторности больше, чем сложности. Гуру, подсобите ;)


#1
10:27, 10 авг. 2009

Не совсем понятно, какими свойствами должны обладать найденые пути: должны ли все они быть близки к минимальному либо пойдут просто случайные? Что значит "разными, но не сильно" (разными на всём протяжении или можно только в конце)?

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

#2
10:35, 10 авг. 2009

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

Поясняю задачу: это граф симуляции. Разные пути нужны, чтоб неписи, которые идут к одному и тому же узлу (в данном случае это лагеря, квестовые места и проч.) не были "клонами" и не шли одинаково. Глупо выглядит. Вот это я и понимаю под "разные, но не сильно".

#3
10:55, 10 авг. 2009

сходу можно предложить два варианта:
1. искать самый короткий путь, затем убирать из него несколько коротких участков и пробовать перестроить.
2. может легче изначально пускать неписей по одному пути, а потом уже потихоньку корректировать? Например, если они идут в один узел графа, то пробовать для одного перестроить часть пути так, что бы он пошёл в обход?

#4
12:06, 10 авг. 2009

xStream
Можно в оценку пути добавлять NPC, которъе идут по ребрам графа, т.е. они какбъ мешают. Таким образом NPC будут старатся обходить участки где проходят другие NPC.

#5
13:24, 10 авг. 2009

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

#6
15:28, 10 авг. 2009

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

Z
это мысль, только задолбусь хранить, если честно, наверное. но попробовать стоит.

sildc
поясни пожалуйста, немного не понял мысль

ЗЫ все это добро на ЛУА, пишу на скриптах сталкеровских, там аи очень удобно управлять.

#7
18:34, 10 авг. 2009

xStream
Если узлов сотня - эвристика не нужна, быстрее просто волной.

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

#8
18:49, 10 авг. 2009

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

А про эвристику заикнулся, думал а-стар делать, потом сообразил, что нецелесообразно :)

К сожалению, это не помогает решить проблему.

#9
19:13, 10 авг. 2009

Если есть цена узлов - можно найти путь и временно повышсить цену у на этом пути. Найти другой, добавить цены на нем, и тд, пока не получится нужный результат.
Только если инфы о взаимном расположении нет - невозможно судить о
> максимально отличающемся от того, каким пришел

Или достаточно, чтобы в путях совпадало минимальное количество узлов? Даже если пути идут параллельно на минимальном расстоянии?

#10
19:42, 10 авг. 2009

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

вот карта, нарисованная дизайнером карта хоббитов | Хоббит, туда и обратно. Поиск пути. Поиск нескольких путей до цели.

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

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

Путь то я могу найти, но мне надо не один, а несколько - пучок.

#11
19:52, 10 авг. 2009

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

#12
19:57, 10 авг. 2009

Тут у меня соображалка не работает просто-напросто
кратчайший найду, а все - чет "моск" не работает.

Вроде мысли прояснились. Осталось только сделать это на ЛУА, вылазит stack overflow, но это уже проблемы алгоритма, нежели игры.

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

#13
0:34, 11 авг. 2009

xStream
Если добавть цены у узлов, то все просто - нпися хранит сколько-то последних посещенных точек и при поиске пути им назначается повышенная стоимость. И вообще последние посещенные полезно хранить, много для чего.
Хотя бы для того, чтобы целевой не выбирать только что посещенную точку :)

#14
1:18, 11 авг. 2009

Тут другая проблема, технического характера, для хранения доступно ооооочень маленькое количество информации. Ограничение двига, к сожалению. И используется оно и для других целей, как то: характеры неписей, информация, накопленная за жизнь, слухи/новости и т.п. Хранить можно только в самих объектах - доступа к двигу нет. Свое сделаю, ессно буду все как нужно мне делать.

В принципе проблему решил. Спасибо всем.

ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.