La longue histoire du guide - comment j'ai écrit un service pour des sentiers de randonnée intelligents pendant 5 ans

Beaucoup ont un ou plusieurs de leurs projets à domicile. Ce sont de petits utilitaires, des pièces expérimentales, des échantillons de nouvelles technologies, des «tueurs» Facebook et bien plus encore. De manière moins fréquente, de tels projets sont engagés depuis longtemps.

Dans l'article, je partagerai mon expérience et vous dirai comment pendant 5 ans j'ai travaillé occasionnellement sur le développement d'un guide intelligent pour Saint-Pétersbourg, comment j'ai réussi à ne pas abandonner cette entreprise, comment l'attitude envers le projet a changé et ce qui s'est finalement produit.

De nombreuses solutions techniques et vélos douteux sont décrits ci-dessous, mais ne soyez pas surpris - presque tous sont justifiés par les objectifs et les ressources disponibles à ce moment (= généralement mes connaissances et mon temps)

Idée

Dans toute grande ville touristique, il y a des centaines de guides, bons et pas très bons, où les itinéraires principaux sont peints, les principaux points et un tas d'autres informations utiles sont indiqués.
Mais les itinéraires y sont constants et limités, et les sites touristiques ne sont généralement que les plus importants, comme "que voir en 3 jours".

Par conséquent, l'idée est venue de construire des itinéraires intelligents. L'utilisateur sélectionne les points A et B et ne reçoit pas l'itinéraire le plus court classique, mais quelque chose à proximité, mais en passant par les attractions à proximité.

Le public d'un tel guide n'est pas seulement des touristes, mais aussi des résidents locaux qui souhaitent diversifier leurs itinéraires typiques vers la maison / le travail / le magasin (et il y avait de telles critiques dans l'application!) Ou tout simplement mieux connaître la ville.

TL; DR
L'essentiel est l'application Android Wander , qui ne fonctionne désormais que pour Saint-Pétersbourg.

Acte 1: Prototype

L'idée est revenue à l'université en 2014, je ne suis même pas sûr que l'idée était à l'origine de moi, sur un certain cours, il était nécessaire de se diviser en groupes, de proposer des projets et de les terminer en tant que document de fin d'études. Ils se sont écrasés et ont généré l'idée du projet, puis le nom TravelPath commencé.

C'était censé être un service Web, je connaissais un peu PHP, alors j'ai choisi PHP.
Il fallait résoudre plusieurs problèmes:

1. Base d'attractions
Ici, nous avons rencontré OpenStreetMap , il s'est avéré que c'est le projet le plus cool qui nous convient parfaitement. OSM est un projet de carte communautaire communautaire à but non lucratif. Comme Wikipedia, uniquement sur les cartes.
Téléchargez la carte au format xml de Saint-Pétersbourg - il y a une liste de ressources où vous pouvez le faire.
À cette époque, je me souviens, les fichiers cartographiques pesaient plus de 1 Go, donc un analyseur en streaming est écrit qui sélectionne des objets de catégories présélectionnées - monuments, parcs, églises, musées.
OSM possède une documentation complète sur les balises, les attributs et tout ce dont vous avez besoin ici , grâce à cela, il ne sera pas difficile de comprendre comment obtenir les données dont vous avez besoin à partir des cartes.

Les données cartographiques sont créées par des passionnés, donc pas partout et pas toujours les objets ont les balises nécessaires, certains endroits ont des erreurs, des problèmes. Mais pour les grandes villes, les données sont de très bonne qualité.

Si j'ai mis à jour correctement mon ancien code, j'ai utilisé les balises suivantes pour récupérer des objets:

• building signifiant cathedral , chapel , church est devenue une catégorie d' church
• amenity avec des valeurs de fountain tombe en monument
• tourism avec des valeurs d' artwork d' artwork et de viewpoint va au monument , au zoo et au museum au museum et au park à theme_park au park
• historic avec boundary_stone , castle , memorial , les valeurs des monument vont à la catégorie des monument
• leisure avec une valeur dans le park finissent naturellement dans le park

Nous mettons tous les objets reçus dans une base de données avec coordonnées et réjouissons-nous! Plus de 1 200 points ont été débloqués à Saint-Pétersbourg.

2. Construire un itinéraire
Il n'était pas destiné à implémenter des systèmes complexes dans le cadre du cours, et les connaissances techniques à l'époque étaient rares, nous avons donc décidé de diviser l'itinéraire en deux parties: le choix des objets dans l'itinéraire et l'itinéraire lui-même. En partie, cela a déterminé le sort de l'avenir, car plus tard, je ne voulais pas changer ce schéma.

La construction d'un itinéraire entre les points sélectionnés a été donnée par l'API Google Maps, qui a assez bien construit les itinéraires en voiture, mais à l'époque ne savait pas marcher, du moins en Russie.

Le choix des objets devait être réalisé par vous-même. Il s'est avéré le schéma suivant de la demande:

Le principal inconvénient de l'approche est la sélection de points sur l'itinéraire sans tenir compte de la carte, uniquement sur la base des coordonnées GPS. Et dans l'ensemble, cela fonctionne assez bien, surtout lorsqu'il y a un réseau routier fréquent. Des problèmes rares sont perceptibles le long des rivières avec des ponts rares, par exemple.

Ensuite, nous arrivons à un algorithme pour sélectionner des points dans l'itinéraire. D'une part, il faut que l'itinéraire ne dévie pas beaucoup sur le côté, mais d'autre part il sélectionne quand même quelques points dans les quartiers donnés.

Pas un énoncé très clair du problème, le même algorithme est sorti, quelque chose de similaire à A * ( wiki ): on pense que de chaque point il y a des transitions à chacun. De plus, dans A *, le prix pour aller au sommet n lors de la recherche de la route AB est généralement exprimé comme suit: f(n) = g(An) + h(nB) , où g(x,y) est la longueur du chemin de x à y, et h(x,y) est une estimation heuristique de la distance de x à y. Mon prix est le même - f(n) = h(x,n) + h(n,y) * q , où q est une constante inférieure à 1. En modifiant la valeur de q, vous pouvez affecter le nombre de points dans l'itinéraire.

Nous implémentons l'algorithme et, cheers, tout fonctionne, fixons l'interface, achetons un domaine, le téléchargeons sur l'hébergement, rédigeons des rapports et autres formalités administratives et réjouissons-nous! Cela ressemblait à quelque chose comme ça (et n'a pas beaucoup changé après):

Total: j'ai eu un prototype d'une idée sympa, j'ai fait connaissance avec OSM, Google API, travaillé en équipe, obtenu un crédit à l'université, et c'était aussi intéressant.

Acte 2: Première version Web complète

J'ai vraiment aimé l'idée et j'ai décidé de la développer davantage, mais déjà une. Et il était clair tout de suite ce qu'il fallait d'abord: à cette époque, Google Maps n'était pas encore en mesure de construire des itinéraires pédestres, seuls des automobiles étaient en cours de construction. Et l'idée de l'application est principalement axée sur la marche, ce qui signifie que vous devez pouvoir créer des itinéraires le long des ruelles ombragées des parcs, des passerelles piétonnes, des ponts et bien plus encore.

C'était en 2015, et j'ai continué à travailler sur TravelPath, j'ai pris la correction de cette faille fatale - j'ai commencé à construire des moyens par moi-même.

Je n'ai pas changé la technologie, PHP + MySQL . Bien sûr, j'ai immédiatement réalisé que ce n'était pas la meilleure pile technique pour une telle tâche (construire des routes en PHP? Sérieusement?).
Mais j'étais limité dans le temps et je n'étais pas prêt à passer à une pile plus raisonnable, et deuxièmement, jusqu'à présent, le projet était écrit "sur la table" - je voudrais utiliser une telle application à partir d'un appareil mobile, et à l'époque, cela ne signifiait que le développement natif. Autrement dit, son inapplicabilité sous la forme d'une version Web était évidente, même en dépit de certaines tentatives pour créer une interface adaptative.

Les tâches suivantes sont survenues:

1. Obtention d'un graphe de ville
Ici, le même OSM nous sauve. Encore une fois, téléchargez le graphique au format xml, analysez-le, en sélectionnant uniquement les types de routes nécessaires et émerveillez-vous de la quantité de données - à cette époque, plus de 3 millions de sommets et 500k bords sont sortis. La première idée est que le graphique peut ne pas être lié.
Les cours, les territoires fermés, les choses incompréhensibles ne sont pas très intéressants pour construire un itinéraire, donc nous sélectionnons un point, en parcourons tout le graphique, en marquant les sommets passés et en obtenant la partie connectée du graphique.
Au total, plus de 600k crêtes et 150k bords sont sortis.
Enregistré le reçu dans la base de données et laissé jusqu'à des temps meilleurs.

2. Construire un itinéraire
Il y a des données, tout est laissé au petit: créez des routes dessus. Nous n'avons pas eu à inventer quelque chose de nouveau - rappelez-vous le cours des algorithmes, lisez attentivement les articles sur l'utilisation des graphiques, prenez l'algorithme A *, implémentez-le en PHP et réjouis-toi frustré par la lenteur avec laquelle tout fonctionne.

Il y a beaucoup de données, par conséquent, lors de la construction du graphique, nous n'utilisons pas le graphique complet, mais nous n'en lisons qu'une partie - tout ce qui tombe dans le rectangle obtenu à partir de tous les points sélectionnés de l'itinéraire.

(cadre rouge = ~ un tel graphique a été lu pour construire le chemin)

Il en va de même pour les points candidats pour l'itinéraire - nous ne prenons pas en compte tout, mais seulement ceux entre le début et la fin + une petite valeur.
Après avoir sélectionné la taille de ce rectangle (la constante par laquelle nous l'agrandissons), nous essayons de garantir que nous lisons la taille de données minimale requise.
Il y avait aussi l'idée de diviser la ville en carrés, de construire d'abord l'itinéraire par des carrés, puis de lire le graphique à l'intérieur de ces carrés et de chercher un chemin uniquement le long de celle-ci. Et vous pouvez pré-calculer les chemins entre tous les carrés voisins. Ou encore plus - pour calculer et enregistrer le chemin entre tous les sites. À la volée, il ne reste plus qu'à construire les chemins de l'initiale au premier objet, et du dernier objet à la ligne d'arrivée.
Mais les mains n'ont pas atteint la réalisation de tels vélos.

3. Acheminement dans un délai raisonnable
Il est immédiatement devenu clair que le goulot d'étranglement est le stockage et le travail avec les données - l'algorithme de recherche lui-même n'est pas particulièrement accéléré. Et des repères sur le genou confirment que la plupart du temps est consacré à la lecture de la base de données et à des manipulations similaires.
Que faut-il faire dans de tels cas? Ne stockez pas ce graphique. Mais j'ai une façon spéciale, MySQL et rien de plus, mais le problème doit être résolu.

1. Le tout premier - les données ont été normalisées, ce qui était pratique lors de l'analyse, mais la lecture de dizaines de milliers d'enregistrements et même de deux tableaux est pénible. La solution évidente est de créer l'un des deux tableaux (pour les sommets et les arêtes), uniquement pour les arêtes, dans lesquels dans chaque enregistrement les coordonnées des deux sommets et leur id.
2. Nous comptons à l'avance les sommets les plus proches du graphe des vues, et ne le faisons pas à la volée à chaque fois.
3. Un temps considérable est consacré à la recherche du point du graphique le plus proche de l'utilisateur donné. Pour accélérer cela, j'ai divisé le graphique entier en petits secteurs, en utilisant la formule de coordonnées, vous pouvez instantanément obtenir l'ID du secteur, puis sélectionner le sommet uniquement à l'intérieur du secteur, et non dans le graphique entier, ce qui est beaucoup plus rapide.

Après toutes les manipulations, nous obtenons la construction de tout itinéraire de marche raisonnable à Saint-Pétersbourg en 2 secondes, ce qui sonne bien - c'est un temps d'attente acceptable pour les utilisateurs.
Le schéma final est sorti comme ceci:

Total: Je me suis encore mieux familiarisé avec les données OSM, en pratique j'ai résolu des problèmes de graphes (le cas où les algorithmes de graphes étaient enfin utiles), j'ai écrit mes premiers benchmarks.

Acte 3: La première version Web normale

Voici les premières réflexions sur le projet en tant que produit qui peut être utile à quelqu'un, et non sur l'artisanat sur la table.
Vous devez donc résoudre les deux problèmes les plus importants:

1. Il était immédiatement évident que la construction d'itinéraires comme je l'ai fait dans le dernier paragraphe est erronée.
2. Un guide dans le navigateur peut ne pas être pratique pour personne - vous voulez vous promener dans la ville, chercher une application pratique où vous pouvez lire ce qui est spécial et ainsi de suite. En bref, au moins - vous avez besoin d'une interface adaptative sympa, et dans le bon sens d'une application mobile.

Mais à ce stade, j'ai décidé de ne traiter que le premier point. Nous étudions Internet sur ce sujet et là encore OSM aide, ou plutôt le projet qui est né grâce à eux - OSRM .
Sur la base des données cartographiques d'OSM, l'Open Source Routing Machine peut créer une variété d'itinéraires en temps utile. Oui, et un projet open source avec une bonne documentation que vous pouvez installer sur votre serveur et utiliser.
En prime, il dispose également d'une API assez pratique.
Et antaresm a déjà écrit sur OSRM sur un habr qui m'a aidé à l'époque. Certes, beaucoup d'eau a coulé et l'article est obsolète. Mais merci beaucoup à l'auteur! La documentation réelle et assez bonne est ici .
Après une installation réussie, nous jetons, presque sans regret, tout notre code sur les routes et commençons à suivre les routes dans l'API OSRM, et le diagramme final se présente comme suit:

Nous ne touchons même pas la partie client - de son côté, l'API de notre service ne change en rien.

Total : J'ai pensé à l'utilisation réelle de l'application par d'autres, il s'est avéré que c'était une architecture normale et de bons itinéraires. La version Web est toujours disponible, bien qu'elle n'ait pas changé depuis lors. https://travelpath.ru/

Acte 4: application Android

Malgré la solution à un problème passé, il est toujours clair que le projet est toujours inutile pour tout le monde sauf moi. Parce que vous avez besoin d'une interface normale et, surtout, d'une application mobile, pas d'une version de navigateur. Maintenant, la technologie a progressé et, peut-être, il sera déjà possible de faire une application de navigateur de ce type qui fonctionne bien pour les clients mobiles, mais pas en 2015-2016. Ce qui signifiait une possibilité très étroite d'utiliser le projet sous la forme d'une version Web - pour s'asseoir à la maison, sélectionner à l'avance des endroits intéressants à visiter. Par conséquent, si nous parlons d'un produit normal, vous avez besoin d'une application mobile avec une bonne interface.

Puis en 2016, j'ai commencé à écrire en Java (mais le backend) et j'ai pensé que sous Android, ils écrivaient aussi en Java. Pourquoi ne pas essayer le développement d'applications, cela devrait être une expérience intéressante.
Le deuxième problème est que je ne sais pas concevoir et je ne ferai pas moi-même une bonne interface. Je suis venu visiter mon premier lieu de travail (un petit studio Le-Dantu) et j'ai invité mon collègue burovk à participer au projet. Curieusement, il a accepté, pour lequel merci beaucoup :)

Les premiers schémas et prototypes
Tout d'abord, nous essayons de trouver un nouveau nom, car TravelPath n'est pas une abréviation très parlante. Et donc grâce aux efforts de Cyril apparaît «Wander» avec un drôle de logo:

Je l'ai fortement associé à un homme moustachu, mais en général je l'aime bien.

Ensuite, les premières dispositions de la future application apparaissent:

Nous pensons également, discutons, que la deuxième option apparaît, qui devient la première version de l'application:

Du côté du développement, j'ai délibérément décidé de ne pas utiliser toutes sortes de frameworks à la mode qui font une magie différente - car il y a de gros risques à les utiliser sans comprendre le travail, et étudier les bases et eux prend trop de temps. Google, nous lisons les quais officiels, les articles éducatifs et nous surmontons les difficultés.

Des problèmes et des tâches dont on se souvient:

• Pour Android, il existe ProGuard - un utilitaire qui compresse le code source lors de l'assemblage, supprime les inutilisés, modifie les noms et plus encore. Il est raisonnable qu'il existe, mais lorsque vous vous lancez dans le développement et que vous le faites vous-même - il n'est pas évident qu'il existe des champs de renommage et cela peut affecter le comportement. Et que tout se passe uniquement dans l'assemblage prod. À la suite de la sortie, tout est cool, mais pour une raison quelconque, il n'y a pas de statistiques. Vous commencez à débiter du backend - et le client envoie un non-sens, au lieu des noms de champs normaux - a, b, c , etc. Béquilles pour que l'API soit capable d'analyser habilement cela, puis vous découvrez que ProGuard a essayé et vous devez spécifier les classes nécessaires comme exception dans sa configuration. Rien d'inhabituel en général, mais l'horloge de débogage s'est envolée.
• Une tâche intéressante consistait à mettre à jour les données de l'application. La base de données principale est livrée avec un fichier apk et je le mets à jour avant chaque version. Mais vous devez également prendre en charge la mise à jour sur le réseau afin que les clients disposent toujours de nouvelles données en cas de changement.
  Dans la première version, j'ai décidé de me concentrer uniquement sur l'heure de la dernière mise à jour. L'application stocke l'heure de l'objet le plus récent, à chaque démarrage, elle demande au backend avec cette heure si quelque chose de nouveau est apparu. Des mises à jour lui sont envoyées, le client se souvient à nouveau de l'heure du plus récent des objets reçus (mais pas de l'heure de la mise à jour elle-même, c'est important).
  Il s'est avéré que j'avais mal pensé - car un an plus tard, une cinquième catégorie est apparue - les bâtiments. Et lors de la mise à niveau de l'ancienne vers la nouvelle version, un problème se pose. J'ai dû changer un peu et le client envoie du temps pour chaque catégorie, pas celle générale. Mais le schéma n'est toujours pas parfait - lors de l'ajout de nouveaux champs aux objets, des problèmes surviennent qui ne peuvent pas être résolus comme ça. Il y a des idées sur la façon de faire mieux, mais les mains n'ont pas atteint et en général la tâche n'est pas très prioritaire. Moralité - il vaut la peine d'aborder soigneusement ces questions et de réfléchir un peu à l'avance.

Et je veux également dire ce que tout le monde sait déjà - Stack Overflow est incroyablement cool et cela est particulièrement visible lorsque vous vous lancez dans le développement de quelque chose d'extérieur comme je l'ai fait - écrivez immédiatement l'application, et pas en douceur à partir des cours, des guides, des exemples de démonstration . Et quand il n'y a personne à demander à un ami. Mais à côté de lui, les discussions sur le développement Android ont également aidé - vous pouvez y poser des questions plus abstraites et demander des conseils sur la meilleure façon de faire quelque chose.

5 décembre 2016, l'application arrive sur Google Play
Il n'avait que des fonctions de base - tracer un itinéraire, afficher des informations sur les points. Mais même cela semblait un succès! Le succès, bien sûr, seulement à leurs propres yeux. Il était entendu que l'application est encore brute et doit être améliorée.

La première version complète et les médias
Par conséquent, je considère la prochaine version comme une version complète et un premier lancement.
Tout d'abord, nous avons examiné à la fois le design et le logo - maintenant, il est devenu comme ceci:

Et ils ont ajouté des fonctionnalités importantes pour le guide - favoris, points de vue sur la carte elle-même, une liste d'attractions avec une recherche. L'application mise à jour ressemblait à ceci:

Une autre idée est venue: contacter la Nuit des Musées et créer un mode séparé pour l'événement à Saint-Pétersbourg.
La Nuit des musées est une fête internationale annuelle où les musées sont ouverts la nuit, souvent avec des programmes spéciaux. Un seul billet est valable et beaucoup essaient de se déplacer dans de nombreux musées à la fois. En même temps, il n'y a pas de navigateur / carte pour mobile - seulement quelques fonctionnalités sur le site officiel de l'événement.
On dirait qu'il correspond parfaitement à l'idée de Wander et est également en demande. J'ai contacté les organisateurs de l'événement, mais malheureusement, l'idée n'a pas été appréciée et elle est restée dans mon esprit jusqu'à des temps meilleurs.

En fin de compte, cela s'est avéré cool et, enfin, l'application a pu être pleinement utilisée. Le 2 juin 2018, une version est sortie et nous avons décidé d'essayer de la montrer au monde - nous avons acheté de la publicité sur VKontakte et Instagram. Mais surtout, ils ont écrit à quelques médias. Le journal a écrit une note sur le lancement de l'application, après qu'un certain nombre de publications de Pétersbourg - The Village, Dog et autres - ont été écrites ou réimprimées avec un fan. Et enfin il y avait du trafic! Les installations se sont précipitées avec un pic, des graphiques d'activité à l'intérieur de l'application aussi. Bien sûr, nous n'avons pas eu à nous réjouir longtemps - mais nous avons eu les premiers utilisateurs, un retour utile et en général c'était très motivant. Le même été, le trafic provenant de la recherche Google Play était visible, ce qui était très agréable, mais plus tard, le résultat n'a pas pu être reproduit.
Dans l'ensemble, cela a donné une motivation assez forte et a aidé à continuer à travailler sur l'application.

Que faire ensuite? Nuit des musées, Google maléfique, itinéraires circulaires

La saison est passée, l'activité dans l'application a chuté de façon spectaculaire et il était clair que les fonctionnalités de sciage ne sont pas très utiles - personne ne les verra, il n'y a pas de budget pour le marketing. Il fallait trouver quelque chose, puis nous sommes revenus à l'idée repoussée avec la Nuit des musées.
Mais encore une fois, il n'a pas été possible de s'entendre sur un partenariat, mais cette fois, nous avons décidé de ne pas repousser l'idée, mais de tout faire par nous-mêmes. Il s'est avéré un certain nombre de fonctionnalités utiles dans un mode de guide séparé: musées sur la carte, itinéraires uniquement pour les participants, brèves informations, favoris.

En plus de ce mode, même à partir de l'arriéré, nous avons obtenu la préservation de l'itinéraire et, surtout, la fonctionnalité sur les itinéraires circulaires.

Les itinéraires circulaires étaient toujours plus importants que les itinéraires AB, mais ils étaient obstinément ignorés. Pourtant, les gens se promènent souvent dans le métro / la maison / le travail / l'hôtel que de A à B. Finalement, ils ont atteint leurs mains et j'ai trouvé une simple heuristique:
Nous obtenons tous les points à l'intérieur du rayon donné. Le rayon est le limiteur de la longueur de l'itinéraire. Nous sélectionnons d'abord un point (conditionnellement aléatoire). Tous les autres sont triés par ordre croissant de l'angle entre lui, le centre et le point donné. / , .

, .

, , :

, , , , , . — , , .

Kotlin , , Wander. , . , . , java — .

, , , . — The Village. - 1000 , 1400 . , Wander , , , . .

Google . — 2018 , API. — 2018- Places API . API, - — . .

— Places API , . , . , — Google Maps, . .

: android Google Play, . burovk , Wander , .

, , , — . , , , — . , — , . , , .

• — git tag v1.0.5 .
• , , , .
• - , .
• — , //etc .

Android . , , , .

— , .

! , . , , , , , .
:

1. — ? - ?
2. . , — .
3. IOS

. , IOS , .

— . Google Play .

Conclusions

• , — . , . . , .
• — , . backend , , android Kotlin, , , . , .
• — . - , . - . , — .

. IOS ( ) — !

PS
— https://habr.com/post/414433/ . . , ( -!), .