
27.03.2009, 21:51
|
|
блогер
Регистрация: Jun 2005
Адрес: Toronto
Сообщений: 6,601
|
Сетка из прямых: поиск пути и движение по этим прямым
Всем привет.
Для начала опишу задачу словами:
Есть машинка, есть дороги. Я должен кликнуть куда нибудь - машина должна по этим дорогам проехать к этой точке. Все дороги - отрезки.
По сути, мы имеем несколько опорных точек, которые соединяются прямыми с другими точками (я решил дать точкам гордое имя waypoint).
Причем не обязательно вейпоинт соединяет 2 отрезка, например дороги могут быть в форме буквы Т (точка в середине соединяет 3 отрезка), или + (все 4).
Давайте разберемся пока с простыми формами, вроде буквы Г или квадрата.
По сути я не могу сформулировать даже алгоритм, по которому это возможно сделать. Пока написал класс, который элементарно смотрит все вейпоинты и расстояния до них, берет 2 кратчайших и смотрит, какой из них ближе к цели, и движется к нему. Работает на ура, но анализировать при прихода в вейпоинт снова все точки (оптимизация вроде не смотреть старые точки, по которым уже прошлись не в счет) - вовсе не айс.
Буду рад любым подсказкам, тычкам в статью и тому подобному. Спасибо.
|