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

Psycho Tiger · 27.03.2009, 21:51

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

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

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

VVall · 27.03.2009, 22:11

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

Mnilionic · 27.03.2009, 22:23

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

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

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

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

Psycho Tiger · 27.03.2009, 22:52

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

Mnilionic · 27.03.2009, 23:22

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

nOobCrafter · 27.03.2009, 23:26

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

Stargazer · 27.03.2009, 23:28

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

gloomyBrain · 28.03.2009, 00:23

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

Psycho Tiger · 28.03.2009, 00:45

Цитата:

Сообщение от gloomyBrain

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

Черт, офигенная идея! Как я сам не допер до неё. Мегаспасибо.

Цитата:

Сообщение от Stargazer

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

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

Цитата:

Сообщение от Mnilionic

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

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

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

Котяра · 28.03.2009, 00:59

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

см.A*

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