Сетка из прямых: поиск пути и движение по этим прямым

[Psycho Tiger]

Всем привет.
Для начала опишу задачу словами:
Есть машинка, есть дороги. Я должен кликнуть куда нибудь - машина должна по этим дорогам проехать к этой точке. Все дороги - отрезки.

По сути, мы имеем несколько опорных точек, которые соединяются прямыми с другими точками (я решил дать точкам гордое имя waypoint).
Причем не обязательно вейпоинт соединяет 2 отрезка, например дороги могут быть в форме буквы Т (точка в середине соединяет 3 отрезка), или + (все 4).
Давайте разберемся пока с простыми формами, вроде буквы Г или квадрата.

По сути я не могу сформулировать даже алгоритм, по которому это возможно сделать. Пока написал класс, который элементарно смотрит все вейпоинты и расстояния до них, берет 2 кратчайших и смотрит, какой из них ближе к цели, и движется к нему. Работает на ура, но анализировать при прихода в вейпоинт снова все точки (оптимизация вроде не смотреть старые точки, по которым уже прошлись не в счет) - вовсе не айс.
Буду рад любым подсказкам, тычкам в статью и тому подобному. Спасибо.

[VVall]

Поищите про алгоритм Дейкстры.

[Mnilionic]

как вариант:
каждая точка является объектом
каждый объект имеет ссылку на своязаный с ним объект.

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

кол-во итераций цыкла будет равно кол-ву точек максимум.

как исбежать повторных обходов:
в начале цыкла создаётся линейный массив точек. после посещения точки ссылка из массива удаляется.

[Psycho Tiger]

2VVall: спасибо, сейчас поищу.
2Mnilionic: дык это уже как раз и реализованно. На фрейм уходит до 1 мс расчетного времени на моей машине, а таких машинок может быть до 3 - это неприемлимо много.

[Mnilionic]

а сколько точек?

[nOobCrafter]

мм не знаю насколько подойдет, но http://demiart.ru/forum/index.php?showtopic=46096

[Stargazer]

Одна тысячная секунды - это неприемлимо долго?

[gloomyBrain]

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

[Psycho Tiger]

Можно посчитать таблицу кратчайших расстояний один раз, и затем ей пользоваться (если точки неподвижны)
Кстати это называется метод потенциалов
Черт, офигенная идея! Как я сам не допер до неё. Мегаспасибо.


Одна тысячная секунды - это неприемлимо долго?
Это на моей мегамашине. На компьютерах пользователей это 2-3 мс. Машин 3 - это 9 мс каждый фрейм. Фпс 30, то есть у меня есть на просчете только 30. Одна треть уже занята. Да, это много.

а сколько точек?
В моем варианте чтобы описать почти безглючный квадрат понадобилось около 15.

2nOobCrafter: регистрация нужна, сейчас зарегистрируюсь и посмотрю, спасибо.

[Котяра]

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

см.A*

Предрасчет всех путей тоже неплохо, если полей мало. простовстречал варианты.. где для 9 локаций нуна 2Г памяти... а если 300 -500, хранить в базе тоже не айс.. траблы с запросами.. в общем очень прикольный вопрос.

[Psycho Tiger]

Да, почитал про Дейкстру, это то что надо!
Но, к сожалению я едва понимаю этот алгоритм на примерах, не говоря уже о том, чтобы его написать/переписать с другого языка =\
Может, у кого есть наработки или здесь есть мастера графов? Помогите, работа встала :(

[iflamberg]

у меня сейчас похожая задача.
досадно, что мощности компьютера огромны, а приходится изгаляться и придумывать методы обхода как будто перед тобой 286ой.
пока додумался только до следующих упрощений:
1) делать пересчет пути не на каждом шаге, а раз в 10 ходов. Соотвественно разгрузить моменты пересчета разных юнитов так, чтобы на ход было как можно меньше пересчетов. (20 юнитов - 2 пересчета на ход). Между пересчетами двигаться в запланированном направлении.
2) Считать не весь путь, а n-переходов, потом выбрать путь приближающий к цели как можно ближе.
3) идти к цели по прямой, только при обнаружении препяствия возвращаться на шаг назад и начинать искать альтернативные пути (рекурсивно, естественно. Т.е. если альтернативные пути из этой точки не найдены все равно - вернуться еще на шаг назад и искать альтернативные пути).
4) если двигаться надо к конечной неподвижной точке - то считать путь делая в кадр n шагов, пока не будет найдено решение, а только затем начать движение.

[Psycho Tiger]

У тебя не совсем то. У меня нет препятсвий, у меня контрольные точки (графы). =\

[iflamberg]

было бы очень интересно узнать о решении, если ты его найдешь

[WRC_S]

сходи сюда http://flash.tutsite.net/g3/g3.html моя разработка ! там какраз чё надо!