Часто бывает, что интересные открытия совершаются случайно, во время работ по совершенно другой тематике.
И вот сейчас, изучая статьи по генеративному дизайну зданий, в одной из них (Spatial configuration: Semi-automatic methods for layout generation in practice) я наткнулся на сразу зацепившую мой взгляд картинку. Вот эту:
Сама статья посвящена алгоритму размещения помещений внутри здания и казалось бы не имеет прямого отношения к теме данного блога. Но в ней авторы походя изложили очень интересную идею для просчета пешеходных потоков.
Авторам статьи понадобился алгоритм, который будет просчитывать пути посетителей или жителей внутри здания, чтобы затем использовать полученные пути для оптимального размещения помещений и коридоров. И они предложили идею использовать физическое моделирование системы частиц.
Иллюстрация из статьи, полученные пути используются для генерации объемов здания вокруг них
Алгоритм в целом таков:
- Строятся прямые линии (кратчайшие пути) меду точками притяжения
- Эти пути представляются в виде частиц, соединенных пружинками
- Между частицами, находящимися на разных путях, настраивается сила притяжения, эквивалентная гравитации
- Запускается физическая симуляция
В итоге соседние пути-частицы притягивают друг друга, стараясь слипнуться вместе. При этом гибкость самих путей-пружинок позволяет им растягиваться до какой-то степени.
Регулируя параметры физической симуляции (веса частиц, жесткость пружин, силу притяжения), можно настраивать, насколько далеко пути могут отклоняться от прямых чтобы «слипнуться» друг с другом.
Идея показалась интересной, так что я быстро накидал демку. И да, действительно, результат очень хороший. На примере с пятью точками притяжения из статьи алгоритм сгенерировал очень хорошую пешеходную сеть. Убрав избыточные дорожки, слив воедино многие маршруты.
На анимации ниже цветные прямоугольники — точки притяжения. Красные пунктиры — «пружины», красные точки — частицы из которых состоят маршруты.
Тут еще можно играться с настройками и подкручивать кривизну дорожек, чтобы она попадала в 30-градусные зоны, описанные в работах Ромма, но в целом подход перспективный. Возможно, когда у нас тут появится свободное время — добавим этот алгоритм в АРП
Илья
Интересно, насколько отличаются результаты этого алгоритма от нынешнего вашего?
smirnovegorv
Сложно проверить, пока я только быструю демку накидал, и она не умеет обрабатывать препятствия, произвольную форму участка, существующие дорожки. В целом мне понравилось как оно реализует слипание близких дорожек, но очень много глюков лезет, физическую модель еще долго настраивать надо