Вы в разделе: Мне

Маршрутизация для игры

.from "Sk"
.to "all"
.subj "маршрутизация"
.date "09.04.2001"
.time "15:44"

Навигация ботов.

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

Он конечно надёжный но Оочень медленный. Конечно, если вы пишете лайнс одно дело,
а если надо направлять пару десятков (сотен) обьектов в реалтайме.
Незнаю, незнаю. К томуже он заточен под однотипный фиксированный лабиринт вида:

xxxxxx
x.xx.x
x.x..xx
x.xx...
x....xx
xxxxxx

т.е. расстояние между стенками относительно маленькое оптимизировать движение
в свободном пространтве не надо вот и перебирается всё подряд.
А теперь представим по настоящему больщой лабиринт. ~1000x1000!
Притом он постоянно меняется. Не полностью, но всётаки (теже боты не одни же мы).
А нам надо попасть из одного конца в другой. Ндаааа.
Так и самый мощныйпень тормознуть недолго.

Натолкнул меня на эти мысли скринсэйвер под линуксом в котором ищется путь в дово-
льно большом (в зависимости от разрешения) лабиринте.
Притом ищет он его довольно хитро и интелектуально.

Например если при движении (довольно случайном) он отсекает какуюто часть (отмечена точками)
он потом на развилке туда просто не поворачивает т.е. он высчитывает и запоминает
места из которых достижение конечной точки принципиально не возможено!


xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xA-| x
x..|---------| x
x............| x
x............| x
x............---| x
x...............| x
x...............> Bx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Вот такая фенька. Довольно полезная.