Faire correspondre les représentations (logique et visuelle) de sa carte

[Sephi-Chan]

Je dispose d'une carte représentée par un graphe ainsi que d'une image pour représenter visuellement cette carte.

Lorsqu'une entité est sur une arrête, je définis sa position en stockant l'arrête sur lequel il se trouve ainsi que son pourcentage de progression sur l'arrête. Exemple : l'entité E est à 80% du chemin AB (du nœud A vers le nœud B).

Mon but est de faire le lien entre la représentation logique et la représentation visuelle de ma carte.


Positionner les nœuds (représentés par des cercles) est assez simple : il suffit d'indiquer pour chaque nœud les coordonnées de sa représentation visuelle.

Positionner les routes me paraît en revanche est plus délicat.

Pour rappel, les nœuds de ma carte sont soit des points stratégiques (représentés par les ronds de couleur) ou des carrefours entre les routes (représentées par les intersections du tracé vert). Chaque fragment du tracé vert situé entre deux nœuds est une arrête de mon graphe.




Je pense stocker pour chaque arrête une liste de coordonnées : les points de passage visuels, sur lesquels positionner mes entités en mouvement. Il faut également que je conserve un angle, pour que la flèche des entités pointe vers le sens de la marche.


J'aimerais avoir vos avis sur mon approche et/ou — encore mieux — des alternatives.

[Myrina]

J'ai une démarche similaire avec ma représentation des flottes en mouvement dans une galaxie.
J'ai un avantage sur toi pour le rendu visuel par rapport à tes données (origine, arrivée, % de parcours effectué): mes flottes vont en ligne droite; du coup le calcul est simple.
D'après ton image, tes chemins sont courbes donc une représentation en ligne droite ne positionnera pas le curseur sur le chemin.
Au mieux tu peux associer une courbe de Bézier à chacun de tes tronçons pour obtenir le point exact. Si ta carte est figée, tu peux codifier chaque tronçon sans trop de difficulté mais si ta carte est générée dynamiquement, il faudra trouver le moyen d'associer une représentation visuel du chemin à une équation.

Nota: Avec le SVG, il est facile de positionner un élément à X% d'une droite (droite ou associé à un chemin défini ou associé à une courbe)

PS: le sujet initial est trop long pour faire apparaitre RE: devant iffle:

[Xenos]

Oui, si tu veux des axes un peu plus lissés, jette un oeil sur les courbes de Bézier (à 3 ou à N points, il me semble que celles à N points peuvent se décomposer en u n ensemble de courbes à 3 points), qui normalement sont prises en charge en SVG.

En plus, l'avantage des courbes de Bézier est de disposer quasi-directement directement de l'abscisse curviligne de la courbe, ce qui permet de savoir facilement où se place le point qui est à P% du chemin entre deux noeuds du graph. Je ne sais plus exactement comment elle se calcule, mais google te le diras surement. Ah, et les Bézier résistent très bien aux rotations, donc la carte pourra se tourner sans soucis si besoin.

[Sephi-Chan]

Je pensais effectivement partir sur du SVG pour définir les tracés, tout en gardant du bitmap pour l'image à proprement parler.

J'ai bel et bien utilisé les courbe de Bézier pour tracer l'ensemble de ma carte d'exemple via l'outil plume de Photoshop, mais je ne peux pas en récupérer la formule.

Un processus qui me conviendrait serait d'utiliser mon image comme guide afin — pour chaque portion de route — de dessiner la courbe de Bézier correspondante reliant le nœud de départ au nœud d'arrivée (avec plusieurs points d'inflexion intermédiaires, si nécessaire). Est-ce qu'un outil existant me permettrait de dessiner ça puis de récupérer l'équation de cette courbe de manière à pouvoir déterminer les coordonnées du point qui correspond à une progression de N% sur la courbe ?

[Myrina]

Tu ne peux pas faire l'inverse? :
- Déterminer les points de l'équation de la courbe de Bézier (http://www.liafa.jussieu.fr/~carton/Ense...index.html)
- Appliquer la courbe pour générer le rendu du chemin sur l'image (soit coté serveur, soit surimpression d'image coté client)
- Utiliser les points générés comme chemin support pour positionner ton curseur à X% du chemin

[Sephi-Chan]

Je n'ai pas la courbe de Bézier de chaque portion de route.

[Sephi-Chan]

Pour rester dans le domaine du simple bitmap, j'ai dans l'idée de créer une image définissant les tracés à suivre pour les mouvements.



Bien sûr, cette image ne serait pas affichée : elle serait uniquement utilisé par un script pour générer les coordonnées de passage de chaque fragment de route.

L'algorithme serait a priori simple :

• Chaque nœud de la carte est représenté par un petit amas (5*5) de pixels d'une couleur unique, les coordonnées de leur centre sont stockés ;
  
• Pour chaque nœud de la carte, on regarde les pixels colorés voisins (les transparents sont ignorés) ;
  
• Pour chaque pixel de couleur trouvé, on suit le chemin de cette couleur jusqu'au bout (qui mène à un autre nœud), ce qui permet de dresser une liste de pixels qui constitue le chemin visuel du nœud D de départ au nœud A d'arrivée (donc l'arrête DA du graphe) ;
  

Si le chemin visuel de l'arrête DA contient 10 pixel et que l'entité qui se déplace sur cette arrête est à 80% du chemin, je dessine l'entité sur le huitième pixel de la liste.

Ainsi, je peux générer le graphe (la représentation logique) d'une carte très facilement (ce serait fastidieux de le faire à la main) à partir d'une telle image de description et faire correspondre les progression (en %) à des coordonnées.


Je vais essayer d'implémenter ça. Je reste à l'écoute si vous avez des solutions.

[Xenos]

Si tu as le format PSD de l'image, il existe un outil en ligne "PSD2SVG". Tu pourras alors récupérer le code de la sourbe de Bézier utilisé:

http://www.online-convert.com/ (plus précisément: http://image.online-convert.com/fr/convertir-en-svg )

Qui me donne un résultat SVG pour une "patate" en Bézier via l'outil plume:

Code :

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN"
"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg version="1.0" xmlns="http://www.w3.org/2000/svg"
width="784.000000pt" height="721.000000pt" viewBox="0 0 784.000000 721.000000"
preserveAspectRatio="xMidYMid meet">
<metadata>
Created by potrace 1.10, written by Peter Selinger 2001-2011
</metadata>
<g transform="translate(0.000000,721.000000) scale(0.100000,-0.100000)"
fill="#000000" stroke="none">
<path d="M2150 4570 c-566 -68 -1065 -316 -1489 -740 -324 -324 -306 -519 69
-740 63 -37 176 -100 250 -140 285 -153 408 -251 520 -416 91 -134 170 -217
284 -303 170 -127 339 -212 548 -275 233 -70 423 -97 689 -97 288 0 402 19
904 146 395 100 509 136 619 193 272 142 333 414 270 1202 -50 632 -150 852
-419 925 -46 13 -139 19 -395 25 -414 11 -496 22 -799 110 -311 89 -453 111
-746 115 -126 2 -264 0 -305 -5z"/>
</g>
</svg>

Soit http://www.online-convert.com/result/963...1c6cf056e3

[Sephi-Chan]

J'ai bossé sur mes scripts d'extraction. Ils sont disponibles sur GitHub.

Voici les 2 images qui décrivent la représentation visuelle de ma carte : celle des nœuds et celle des chemins.




Le script récupère d'abord les positions occupées par chaque nœud (4*4 pixels), puis suit les chemins partant de chaque nœud (jusqu'à leur fin sur un autre nœud) afin de dresser la liste de tous les pixels qui forment un chemin.

[Myrina]

Donc comme cela, tu obtiens un tableau des différents points traçant tes chemins et il est aisé de récupérer le point à X%.

Question: ta carte est figée où elle peut évoluer? (donc nécessité de regénérer tes tableaux)