whiteRed
17.10.2006, 10:53
столкнулся с такой задачей: есть лабиринт, точнее сказать поле с препятствиями, заданное 2-хцветный битмапом. нужно быстро находить в нем пути обхода препятствий. наткнулся вот на такую статью: http://algolist.manual.ru/games/smartmove.php#c_space
в общем, мне нужно найти на карте точки видимости (рис 11с)...
кто-нибудь знает, где почитать как они строятся? не знаю, по каким словам гуглить...
вот мои соображения:
1. метод муравьиных колоний - если запускать муравьев искать маршрут из одной случайной точки в другую, то по моему предположению точки видимости будут посещаться муравьями чаще всего
2. просто натыкать случайным образом на карте очень много точек, а потом удалять по одной бесполезные
полезность точки я собираюсь определять таким образом:
А - подозреваемая точка, В и С - видимые из нее. чем больше отношение количества пар, в которых есть дуга ВС, к количеству пар, где такой дуги нету, тем точка бесполезнее (блин, непонятно написал.:confused: короче, чем больше путей потеряется в случае удалении точки А, тем она полезнее)
3. нейросети или генетические алгоритмы. тут я еще не думал, но мне кажется они неплохо могут справиться. вечером подумаю :away:
прошу критиковать / высказывать ваши идеи
п.с. реализовывать буду на С++, так что производительность не так критична:cool:
в общем, мне нужно найти на карте точки видимости (рис 11с)...
кто-нибудь знает, где почитать как они строятся? не знаю, по каким словам гуглить...
вот мои соображения:
1. метод муравьиных колоний - если запускать муравьев искать маршрут из одной случайной точки в другую, то по моему предположению точки видимости будут посещаться муравьями чаще всего
2. просто натыкать случайным образом на карте очень много точек, а потом удалять по одной бесполезные
полезность точки я собираюсь определять таким образом:
А - подозреваемая точка, В и С - видимые из нее. чем больше отношение количества пар, в которых есть дуга ВС, к количеству пар, где такой дуги нету, тем точка бесполезнее (блин, непонятно написал.:confused: короче, чем больше путей потеряется в случае удалении точки А, тем она полезнее)
3. нейросети или генетические алгоритмы. тут я еще не думал, но мне кажется они неплохо могут справиться. вечером подумаю :away:
прошу критиковать / высказывать ваши идеи
п.с. реализовывать буду на С++, так что производительность не так критична:cool: