Быстрый геопоиск, где взять? Из геймдева!
Временами возвращаюсь к вопросу реализации алгоритма быстрого геопоиска для мессенджера. Стандартные серверные алгоритмы PostgreSQL меня не устроили. Дело в том, что существует плагин PostGIS. И плагин вроде как отлично справляется с задачей поиска в радиусе.
И правда, чего не хватает? Есть основные функции, котрые хотел бы добавить в мессенджер:
- оповещение подписчиков при приближении человека
- оповещение при входе человека в область сложной формы
- возможно еще что-то подобное, связаное с геооповещением
Функции удобные, полезные, бесплатные. Если включить режим "семья", то вообще отлично. Матери будут видеть своих детей на карте :)
Конечно, можно решить как-то данные задачи и с помощью PostreSQL. Например сделать кучу точек в пространстве и сканировать рассточяние из них. Так мы узнаем попал ли человек в указанную область. А оповещение можно сделать путем постоянного опроса и проверки. Если сервисом пользуется 1000 человек и каждый и из них примерно 1000 якорей за которыми производится мониторинг, то это сильно ударит по производительности сервиса. В общем невооруженным взглядом понятно, что тут нужно придумывать что-то другое или покупать бесконечную серверную мощь для решения пустяковой задачи 😂.
И вот, недавно пришла идея алгоритма, который позволит решить подобную задачу: октри. А если точнее, то его 2D-брат по имени "квадродерево". К счастью это уже реализовано в предыдущем продукте, который разрабатывал с коллегой: https://store.steampowered.com/app/2412090/Total_Reload/
Как говорится, просто бери и используй.
В общем-то так я и делаю, но... Но система была написана с учетом одного инстанса, то есть для игрового компьютера. А мне нужно чтобы оно работало на нескольких компьютерах, стейтлесс нужен.
В общем, пока думаю как перенести это все дело на свой сервер с учетом стейтлес подхода к обработке данных. Может кто-то знает готовые решения и ткнет в них? По идее Яндекс такси должен иметь что-то подобное, но что они используют найти не удалось.
Кому интересно, можете подписаться куда-нибудь на меня, попробуете мессенджер в числе первых.
Постепенно буду продолжать делиться успехами :)












