Нахождение пути в лабиринте

[whiteRed]

столкнулся с такой задачей: есть лабиринт, точнее сказать поле с препятствиями, заданное 2-хцветный битмапом. нужно быстро находить в нем пути обхода препятствий. наткнулся вот на такую статью: http://algolist.manual.ru/games/smartmove.php#c_space
в общем, мне нужно найти на карте точки видимости (рис 11с)...
кто-нибудь знает, где почитать как они строятся? не знаю, по каким словам гуглить...

вот мои соображения:

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

2. просто натыкать случайным образом на карте очень много точек, а потом удалять по одной бесполезные

полезность точки я собираюсь определять таким образом:
А - подозреваемая точка, В и С - видимые из нее. чем больше отношение количества пар, в которых есть дуга ВС, к количеству пар, где такой дуги нету, тем точка бесполезнее (блин, непонятно написал. короче, чем больше путей потеряется в случае удалении точки А, тем она полезнее)

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

прошу критиковать / высказывать ваши идеи

п.с. реализовывать буду на С++, так что производительность не так критична

[whiteRed]

мда...

[wvxvw]

Честно? я думаю, что с битмапом умаешься... с векторами все-таки проще.
На что поискать? - Алгоритм Дийкстры (вроде так прально пишеться). Но ты и так нашел то что надо... Или "поиск путей", "метод чернильных пятен\клякс" как-нть так... (метод с точками видимости хорош если цена прохода может быть либо "проходимый", либо "нет", а вот если на карте существуют "полупроходимые" препядствия, и нужно выбрать самый быстрый, а не самый короткий путь, то тогда начнутся траблы...

ЗЫ. Ну и еще такой момент, что важнее, скорость, или точность?.. Хотя, вобщем-то, чего это я =) там уже итак все описано =)

[whiteRed]

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