Соединяю города дорогами

В одном обсуждении однажды поднялся вопрос о соединении некоторого числа городов дорогами оптимальным образом. Ну я и решил немного поэкспериментировать, да попрограммировать😃

Идем в лоб по каждому городу, находим для него ближайший и строим дорогу по кратчайшему пути. Затем проделываем то же самое со всеми остальными - это первый круг. На втором круге дорогу рисуем уже не к ближайшему, а ко второму по расстоянию. И так далее, пока не переберем все пары городов по 2 раза. Почему по 2? Смотрите, обзовем два города А и Б. В какой-то момент работы алгоритма мы окажемся в А и будем искать путь до Б - проведем дорогу. В какой-то другой момент мы будем уже в Б и будем искать дорогу до А - и проведем ее еще раз. И вот в этом моменте различается работа однопроходного и двупроходного режимов.

В One pass мы сразу рисуем полную дорогу из А в Б.

В Two pass мы сначала рисуем половинную дорогу и А в Б, а когда пойдем обратно - дорисуем до полной. Веса меняются таким образом: 6 заменяется на 4,5 при первом проходе, а при втором 4,5 - на 3.Как видите, разница между режимами незначительная, да я и не рассчитывал на нее, появилась идея - решил попробовать.

Идею этого алгоритма я также почерпнул в одном из видео ТехноШамана. Суть простая: у нас есть несколько муравьев (красные круги 😄). Каждый выбирает себе случайный город в качестве цели и идет туда кратчайшим путем, на каждом шаге он "протаптывает тропинку", уменьшая вес на величину Weight change. Также для разнообразия я добавил ему шанс случайно свернуть на другую клетку на каждом шаге, шанс задан параметром Rotate chance. Тропинка не вечная - если по ней не пройдет ни один муравей в течение Life turns ходов, она начнет "зарастать", то есть ее вес будет увеличиваться на Weight change, пока не достигнет значения бездорожья 😉

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

Моя программа не запрещает указать вес дороги больше обычного, но в таком случае вас ждет хаос из дорог! 😁 Ведь каждый новый маршрут для новой дороги будет пытаться избежать уже проложенных путей 😁

#programming