Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
В своей предыдущей статье про интерактивную карту метро Москвы я описывал процесс создания векторной карты на svg-движке, сравнивая с канвасным отображением.
Спустя время я решил вернуться к своей карте и добавил в неё возможность вывода маршрута кратчайшего пути между выбранными станциями по алгоритму BFS, обхода графа в ширину.
Сама задача поиска по графу потребовалась по работе для визуализации блок-схем в формате UML, DTD для предоставления заказчику. Алгоритм позволит "оживить" их, превратив в подобие задачи с известными решениями.
Я вспомнил про свою карту метро, представляющую готовый сложный, неориентированный граф, и решил апробировать алгоритм на ней.
Алгоритм состоящий из трёх небольших функций я адаптировал для использования массива с координатами станций, добавив условия:
Переходы по вершинам (станциям) назад и вперёд возможны только по линиям одного типа
Переходы с линии на линию возможны если у них есть общие станции, являющиеся пересадками (массив inches)
Размер массива координат станций пересадок настраивается выбором фильтра всех пересадок (тип inch): прямые, кольцевые, строящиеся, мцк. В дальнейшем добавлю в отдельный фильтр также пересадки Большого кольца и Монорельса.
Эта часть доработки оказалась самой простой, на пару часов. Получив список станций по заданному маршруту, сразу подумал, как отобразить его, на карте, и вот здесь пришлось уже изрядно повозиться.
Во-первых, выяснилось, что карта сильно устарела с момента её создания в 2013 году и пришлось синхронизировать её с текущим вариантом из Википедии.
Во-вторых, для правильного определения точек внутри отрезка пришлось перерисовать плавные отрезки некоторых линий, нарисованных функцией кривой Безье и командой Q в координатах, чтобы координаты кривой были между станциями, иначе кривая становилась ломаной. Определяется это только методом "тыка", так что ошибки возможны, проверял избирательно.
В-третьих, кратчайший путь не всегда соответствовал кратчайшему пути по сути. Для этого пришлось профильтровать массив линий с координатами станций пересадок (тип inch) на прямые, кольцевые и мцк, как уже писал выше. Иначе, если в алгоритм подать полный массив пересадок, то он не прокладывал путь по кольцу, кроме случаев, когда одна из станций находилась на кольце. Потому что по алгоритм дойдя до пересадки на кольцо, уходил вглубь по другим линиям, пересекающимся с кольцом, и по самому кольцу не двигался. Вообще алгоритм поиска должен бы ещё учитывать веса вершин и расстояния между ними (или время в пути). Но я рассматриваю только возможность управления поиском без существенного усложнения алгоритма поиска.
В-четвертых, исходный алгоритм поиска был написан по стандарту ECMA2015 с использованием конструкций let, const, Set, которые не позволяли мне посмотреть карту на стареньком iPad 3G. Пришлось переделать на старый формат с var, function.
Надеюсь, статья поможет тем, кто интересуется созданием изображений svg, оффлайн-картами с возможностью редактирования и использования в своих проектах.
Отдельные ссылки на карту метро и проект в github.
