M.A.X.    Вы вошли как гость
Российский Клуб игроков M.A.X.
 
[Новости]   [Новичку]   [Энциклопедия]   [Документы]   [Файлы]   [Игроки]   [Архивы]   [Архив форума]  
[Новый сайт]   [M.A.X. Gold]   [Партии]  

 
 
 
Архив форума  МаксГолд
[Основной форум] [Голосования] [МаксГолд] [Off-Topic]
 


Выложил в буффер демку 012а  -  Barloggg,  26.11.2003  9:14:33

Вчера неожиданно рано пришел домой и решил сходить по маленькому в свою демку...
Так, по мелочам покликал... подрисовал фонты, поменял спрайтики кнопочек...поставил парочку if`ов кое-где
вывод статичной картинки стал пошустрее, поприятнее стал режим отображения проходабельности территории для юнитов

и вдруг среди этого благоденствия обнаруживаю что мой алгоритм поиска пути не идеален! :O
я то блин думал что все, закончил и уже хвастаться начал что вот мол, сынки, учитесь... тому же ArtLaw`у например

ну, начал я это дело править...
и знаете что? подправил так быстро и элегантно, что решил немедленно известить всех об этом.
В общем качайте и заценивайте


а теперь собственно в чем произошло изменение:
алгоритм поиска пути в ширину предусматривает просмотр всех возможных вариантов.
и реализуется это так:
из начальной точки во все стороны расходится волна до тех пор пока не дойдет то конечной

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


а изменение я внес следующее:
при просмотре клеток рассматриваются ТОЛЬКО те клетки, расстояние от которых до искомой точки наименьшее!
то есть те клетки которые идут назад в общем то не рассматриваются.

Но все не так примитивно :)
клетка с минимальным расстоянием вполне может оказаться сзади...
хе-хе
минимальное расстояние считается так: путь пройденный до данной клетки + путь до конечной точки по дорогам по прямой.

понятно?


Качните демку, кликните кнопки Все пути и Цена пути, потом выделите юнит, желательно амфибию для наглядности, крутаните колесо вниз чтобы уменьшить масштаб, и пошлите юнит куда-нибудь
и увидите как работает этот алгоритм

хорошо работает

ВСЕ, объявляю алгоритм поиска пути в ширину законченным.

всем спасибо, наслаждайтесь :)


SVS, будь добр грохни в буффере файлы MaxEXE012.zip и MaxSrc012.zip
они только зря лишних 500 кб отнимают
а заодно 010 и 009 ...