|
•Выложил в буффер демку 012а - Barloggg, 26.11.2003 9:14:33 |
|
|
Вчера неожиданно рано пришел домой и решил сходить по маленькому в свою демку...
Так, по мелочам покликал... подрисовал фонты, поменял спрайтики кнопочек...поставил парочку if`ов кое-где
вывод статичной картинки стал пошустрее, поприятнее стал режим отображения проходабельности территории для юнитов
и вдруг среди этого благоденствия обнаруживаю что мой алгоритм поиска пути не идеален! :O
я то блин думал что все, закончил и уже хвастаться начал что вот мол, сынки, учитесь... тому же ArtLaw`у например
ну, начал я это дело править...
и знаете что? подправил так быстро и элегантно, что решил немедленно известить всех об этом.
В общем качайте и заценивайте
а теперь собственно в чем произошло изменение:
алгоритм поиска пути в ширину предусматривает просмотр всех возможных вариантов.
и реализуется это так:
из начальной точки во все стороны расходится волна до тех пор пока не дойдет то конечной
Geo реализовал это расползающимися юнитами
Я реализовал это списком клеток предназначеннных к просмотру на следующий такт
то есть каждая клетка осматривается и если есть куда шагнуть ставит ту клетку в список проверяемых завтра
Я использовал дополнительную переменную в которой записывал пройденное расстояние, чтобы не наслаиваться на клетки где уже прошли
Но я не стал задействовать ожидание... и получалось что путь искался с минимальным количеством клеток но не с минимальным количеством ходов для их преодоления
а изменение я внес следующее:
при просмотре клеток рассматриваются ТОЛЬКО те клетки, расстояние от которых до искомой точки наименьшее!
то есть те клетки которые идут назад в общем то не рассматриваются.
Но все не так примитивно :)
клетка с минимальным расстоянием вполне может оказаться сзади...
хе-хе
минимальное расстояние считается так: путь пройденный до данной клетки + путь до конечной точки по дорогам по прямой.
понятно?
Качните демку, кликните кнопки Все пути и Цена пути, потом выделите юнит, желательно амфибию для наглядности, крутаните колесо вниз чтобы уменьшить масштаб, и пошлите юнит куда-нибудь
и увидите как работает этот алгоритм
хорошо работает
ВСЕ, объявляю алгоритм поиска пути в ширину законченным.
всем спасибо, наслаждайтесь :)
SVS, будь добр грохни в буффере файлы MaxEXE012.zip и MaxSrc012.zip
они только зря лишних 500 кб отнимают
а заодно 010 и 009 ...
|
|
ответы :
-
Замечания - Geo, 26.11.2003 20:58:40
-
хм... - Barloggg, 27.11.2003 9:50:31
|
| |