С приходом весны и дождей на улице в глаза все чаще бросается одна проблема. Вот эта:



Думаю знакомая всем жителям наших городов. Вечно вытоптанные газоны, превращающиеся в грязевое болото после каждого дождика, через которое самоотверженно продолжают пробираться пешеходы. Пачкая при этом одежду и вынося грязевую кашу на асфальт.

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

Шел я как-то по дорожке и вяло размышлял на тему того, что опять придется или тащиться в обход, или пачкать обувь. С возмущения типа «вот же дураки это проектируют» мысль плавно перетекла на слышанную когда-то байку про некий наукоград, где дорожки во дворах сперва не сделали вовсе, а потом просто заасфальтировали протоптанные людьми тропинки, получив сеть удобных жителям маршрутов. А оттуда мысль перекочевала к идее «а почему бы не сделать то же самое, но на компьютере?». Разработать программу, которая по заданной карте предскажет, где люди будут топтать газоны и где неплохо бы сделать асфальтовое покрытие?

Под катом — описание алгоритма и пара примеров его работы для реальных питерских дворов.


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

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



Вариант второй: признать ошибку и исправить
Да, так тоже бывает. В этом плане мне нравятся дворы вокруг Московского проспекта — там тропинки превратили в нормальные дорожки, и по газонам больше никто не ходит — в этом просто нет нужды. Однако тут все зависит от энтузиазма местных властей — кто-то делает, кто-то пишет отписки, обещает сделать лет через 5 когда будут деньги, а чаще всего пытаются бороться по первому методу.



Ну и вариант третий: предусмотреть и исправить проблемы еще на стадии проектирования
Честно скажу, понятия не имею что для этого предпринимают проектировщики и застройщики. Судя по увиденным мной схемам — ничего, лепят все руководствуясь исключительно эстетическими соображениями. Буду рад если в комментариях кто-нибудь с опытом в этой области сможет что-то рассказать.
Этим вариантом мы и займемся.

Постановка задачи
Итак, что у нас есть? А есть у нас карта местности, на которой присутствуют:

• Участки с разной степенью проходимости и привлекательности для пешеходов (дорожки, газоны)
• Препятствия (дома, заборы)
• Места между которыми пешеходы передвигаются — подъезды, ларьки, лавочки — все что угодно. Их будем называть генераторами пешеходов

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

Сразу отметим два краевых случая, которые обычно первыми приходят в голову в качестве решения. Первый — это полный граф, то есть мы просто возьмем и соединим каждый генератор с каждым, проложив дороги по прямой. На словах просто, пешеходам будет, разумеется, удобно, однако в итоге весь двор окажется закатанным в асфальт, что дорого и неэстетично. Второй случай — это минимальное остовное дерево графа, вершинами в котором будут генераторы. К сожалению, люди все-таки не роботы и не ходят по минимальным остовным деревьям, что было показано исследователями работе «Modelling the Evolution of Human Trail Systems» (D. Helbing, J. Keltsch, P. Molnar.) Иллюстрацией к данному утверждению может послужить следующее изображение:

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

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

Алгоритм

Подготовка.
Карта рассматриваемого участка территории представляется в формате GeoJSON. На ней вручную размечаются генераторы пешеходов и проходимость участков ландшафта.

Инициализация. На основе карты строится навигационный граф G(V, E). Вершины графа V – это множество точек местности. В данной работе выбран наиболее простой метод построения этого множества: на карту накладывается прямоугольная сетка, ее узлы становятся вершинами графа. Если между двумя соседними узлами сетки может пройти человек, такие узлы соединяются ребрами, составляющими множество E. Исходный вес каждого ребра e представлен в виде разности двух компонент: фиксированной Wconst(e), определяемой типом местности, и изменяемой Wvar(e), которую в дальнейшем будем называть вытоптанностью. Изначально она равна нулю. У некоторых типов ландшафта (дорожек с жестким покрытием) изменяемой компоненты может не быть.
Вытоптанность ограничена снизу нулем (нетронутый газон), а сверху числом Wmax, подобранным таким образом, чтобы даже максимально вытоптанная тропинка все-таки была чуть менее привлекательна, чем аналогичная дорожка.
Помимо этого, для каждого пешехода p вводится коэффициент порядочности k(p). Этот коэффициент используется для симуляции различных категорий пешеходов – как «порядочных», предпочитающих всегда ходить только по дорожкам, даже если итоговое расстояние будет значительно больше, так и любителей ходить всегда напрямик. Формула для вычисления веса W(e, p) ребра e для пешехода p имеет вид:

В таком случае при значении k(p) > 1 короткие спрямленные тропинки для данного пешехода будут иметь большую привлекательность, так как роль компоненты Wvar в формуле будет выше. При k < 1 получается «порядочный» пешеход, который будет стараться чаще ходить по дорожкам.

Симуляция.
P пешеходов равномерно распределяются по генераторам. Цели для них выбираются случайным образом из списка остальных генераторов. Коэффициент порядочности k(p) выбирается следующим образом:

Здесь Kbad – обязательная доля непорядочных пешеходов (для ускорения сходимости алгоритма предположим, что в обществе всегда есть определенная доля любителей передвигаться максимально прямыми и короткими путями), N – нормальное распределение. Значения коэффициентов подобраны эмпирическим путем, для Kbad выбрано значение 0.1.

На каждом шаге симуляции выполняются следующие действия:
1) пешеходы проходят определенное расстояние, зависящее от заданной скорости движения;
2) вытоптанность пройденных пешеходами ребер графа увеличивается на фиксированную величину ?Wped за каждого прошедшего по ним пешехода;
3) дошедшие до своей цели пешеходы заменяются на новых;
4) вытоптанность всех ребер графа уменьшается на фиксированную величину ?Wtime (зарастание со временем).
Таким образом, общее изменение вытоптанности для ребра е после шага симуляции i выглядит как:

Здесь Pcount(e, i) – число пешеходов, прошедших на i шаге по ребру e.
Пешеходы прокладывают маршрут с помощью алгоритма A* c эвристикой для спрямления путей (изначально я использовал банального Дейкстру, но на прямоугольных сетках он любит генерировать довольно неестественно выглядящие пути). Симуляция продолжается либо до сходимости, пока карта тропинок не перестанет изменяться, либо заданное число шагов. После завершения симуляции карта с распределением вытоптанности демонстрирует участки, на которых пешеходы чаще всего сходят с дорожек на землю, и которые стоит замостить твердым покрытием.

Пример работы

В качестве примера работы приведу тот самый двор, который и сподвиг меня на создание данной программы. Это окрестности жилого дома на проспекте Гагарина в Санкт-Петербурге, в котором я раньше жил и где регулярно чертыхаясь ходил. Собственно фото моего подъезда есть выше, там где забор перевязан ленточкой, так что знакомство с головотяпством планировщиков и архитекторов у меня начиналось прямо с выхода на улицу.

Вот так этот дом выглядит со спутника. Сам дом посередине, слева и справа от него — панельные пятиэтажки. Справа находится размеченная карта местности с указанием очертаний домов и препятствий.



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

В результате симуляции после нескольких сотен итераций нарисовалась вот такая картина. Черным отмечены предсказанные программой места вытаптывания газонов:



Для сравнения, фото из реальности, соответствующие пронумерованным участкам:

1 тропка по диагонали к углу дома


2 — тропа вдоль всего дома


3 — фото из начала статьи, тропы от подъезда


В целом можно видеть что предсказания программы довольно точны.

Пример 2

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

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

Итак, предсказание программы:



И реальный спутниковый снимок (разумеется несчастный газон нетерпеливые граждане истоптали так, что видно стало даже из космоса):



Конечно на этом снимке не видно более мелких троп, но они там есть (на самом деле их даже больше чем предсказала программа, но в целом конфигурация очень схожа, фотографий у меня их хватает, но тут уже выкладывать их я не буду, и так пожалуй перебор). Определенное несоответствие опять таки обусловлено неточностью карты — на момент написания исходной статьи, которая так и не была опубликована, во всяких картографических сервисах еще не было новой карты парка после реконструкции, приходилось рисовать ее по памяти и зарисовкам.

Выводы

А выводы очень простые. Если бы как-то удалось внедрить подобное средство туда, где занимаются проектированием дворов — жить стало бы лучше и трава стала бы зеленее. Я вот сам недавно переехал в «Балтийскую жемчужину» — новый и современный микрорайон СПб — и просто за голову хватаюсь когда вижу как там сделаны дворовые проходы. Со спутника наверное красиво выглядит, но абсолютно нефункционально. Первое фото в статье как раз оттуда. Отправка обращений в органы местной власти не помогает — официально тот район еще не передан городу, и никто за него не отвечает. Надо было с самого начала делать правильно.

Но поскольку я люблю писать код и не очень люблю его потом кому-то навязывать — я понятия не имею можно ли что-то с этой ситуацией сделать, а если можно — то как именно. Может кто-то из хабражителей подскажет?

UPD: в комментариях спрашивают про код и возможность запустить на своих данных. Пока реализация скорее некий proof-of-concept, с не очень дружественным интерфейсом. Раз уж эта тема вызвала интерес — доделаю ее в каком-нибудь более человеческом виде и выложу чуть позже.