[Truc] Carte, Hexagones et Coordonnées

[Meraxes]

Tiens je déterre ce sujet (désolé), mais il y a un site que j'adore pour expliquer le calcul des distances de Manhattan de la méthode 3D : redblobgames (en)

Et il y a pleins d'autre articles intéressants comme : les parcours A*, les algorithmes de visibilité sur un plan 2D, des probas sur les jets de dés, etc.

C'est vraiment un site génial avec, en plus, plein de petits effets sympas pour visualiser et comprendre tous les algos et calculs présentés.

[Meraxes]

[Xenos]

Ta distance de Manhattan, c'est juste la distance entre les tuiles selon les axes d'angle (Pi / 6)

Code :

const d = Math.sqrt((du * du + dv * dv) / 2.25) * Math.cos((Math.atan2(dv, du) + 2 * Math.PI) % (Math.PI / 3) - (Math.PI / 6));

Je n'ai pas encore cherché la simplification de la formule, je mettrai ça en ligne après manger.
Je maintiens que rajouter des dimensions, c'est (comme quand on rajoute des dépendances), amener de la complexité inutile.

Je ne sais pas où tu as vu qu'on appelait ça des "coordonnées axiales"; à part dans cet (obscur) article, ce terme n'est pas approprié. On parle tout simplement de redondance. D'ailleurs, pourquoi vouloir conserver ce "z" à toute force, plutôt que de juste le remplacer par sa valeur (x;y)?!

Puis bon, niveau utilisation des index, on est quand même mal barrés...
T'es loin de m'avoir convaincu...

(tu peux me nommer, perso, je préfère, je déteste l'approche du "y'en a qui disent que/qui devrait/qui ceci cela" sans nommer. Ca ne fait pas avancer le schmilblik. Bon, là, ok, c'est obvious, mais perso, je préfère largement le nominatif explicite au nominatif caché)

PS: si ton modèle est un graph, c'est à dire une liste de tuiles (qu'importe la forme) avec les liens entre elles, la distance de manhattan se calcul trivialement en partant de la tile de départ, puis en ajoutant +1 à chacun de ses enfant et en réitérant, sans revenir en arrière. C'est le modèle le plus bateau et efficace quand t'as la carte en mémoire

[Meraxes]

Mmm "Axial Coordinates" c'est le nom anglais ; en français je ne suis pas sûr...

Pour le coup, non, il n' y a aucune redondance ici puisqu'on a seulement deux éléments pour sa coordonnée (c'est justement un système où on supprime la redondance de la coordonnée cubique).

Attention, on ne parle pas de graphe ici ; la structure choisie pour le problème c'est un tableau en gros (on peut tout à fait modéliser son jeu avec un graphe en définissant des sommets et des arcs mais c'est un autre sujet & d'autres algos ; ça n'a rien à voir avec les données du problème qui est posé ici).

Pour ta formule je ne saurais pas dire si elle est correcte (il faudrait que je teste sur l'exemple) mais attention c'est un problème de maths discrètes (je ne suis pas sûr que ce soit la bonne approche de voir ça comme un problème de trigonométrie, mais à tester pourquoi pas) ; là on parle d'une définition abstraite d'une map (peu importe la distance choisie entre les cases ou leur taille par exemple).

EDIT 1 : après tu peut ajouter des index ou utiliser des types géometriques si tu préfères mais ce n'est pas le fond du problème
EDIT 2 : bon j'essaie de tester ta formule mais pour le moment ça ne passe pas : il faut créer une fonction à double précision pour le modulo, sinon ça m'envoie balader...bon les fonction trigo aussi...j'abandonne...

J'ai essayé :

SELECT x, y
FROM CaseTest
WHERE fmod((sqrt(((x-3) * (x-3) + (y-4) * (y-4)) / 2.25) * cos((atan2((y-4), (x-3)) + 2 * pi()),(pi() / 3) - (pi() / 6)))) < 2;

EDIT 3 : non justement, une distance de Manhattan, ce n'est pas la même chose qu'une distance euclidienne

[Xenos]

Je n'ai jamais dis que la distance euclidienne était la distance de manhattan. J'ai juste dit que c'était la distance de parcours du graph de la carte, noeud à noeud (sans revenir en arrière). Ca permet de faire des cartes plus originales que les sempiternelles tuiles hexa.

Je te laisse t'amuser avec cette petit "démo": https://xenos.reinom.com/jeuweb/hexamap/hexamap.svg Vous vous amuserez à simplifier les calculs si nécessaire, une rotation de PI/6 devrait d'ailleurs faciliter pas mal de choses, et une échelle x2 aussi. Mais le sujet ne m'intéresse plus.

Je vais voir les étoiles, et j'ai pas envie de tourner en rond 15 ans sur ce sujet, donc, je vous laisse choisir les méthodes que vous voulez, moi, je m'arrête là, le sujet ne m'intéressant plus.

[Meraxes]

Oui, après moi non plus je ne veux pas y passer ma soirée.

Juste :
- oui c'est le résultat d'un BFS si tu vois le tablier comme un graphe
- non, je ne pense pas que c'est "la distance entre les tuiles selon les axes d'angle (Pi / 6)"
- j'ai déjà dis dans mon 1er post que l'intérêt d'une coordonnée cubique n'est pas l'affichage (donc inutile de me montrer un programme d'affichage) mais pour travailler sur les distances (en nombre de cases/noeuds donc) entre deux noeuds/cases

Mais bon, je ne veux pas te chercher à te convaincre à tout prix.

[Xenos]

Au passage, comme la distance de Manhattan correspond à la distance aux 6 axes à Pi/3 (ou à PI/6 + n * Pi/3 comme sur le SVG d'exemple, suivant l'orientation des hexagones), alors l'ensemble des hexagones à une distance de Manhattan inférieure à D de l'hexagone A correspond à l'ensemble des hexagones à l'intérieur de l'hexagone de diagonale (ou hauteur, faut vérifier) D tourné de 90° par rapport aux hexagones de la grille.

Dommage, j'ai pas pensé à uploader la maj de mon SVG: avec des couleurs rouge/verte/bleues (cf Discord), c'était franchement flagrant. Et cela permet alors d'utiliser une colonne de type GEOMETRY si on est en SQL, de construire le polygone de cet hexagone (tourné de 90°, de diagonale D, à un facteur scalaire près dépendant de la taille des hexagones dans la carte) et de getter tous les centres d'hexagones (les centres de tuiles) à l'intérieur de cet hexagone (forme englobante). Avec un index, c'est probablement instantané.

Edit:

DROP TABLE IF EXISTS geo;



CREATE TABLE geo (

	cx INT NOT NULL,

	cy INT NOT NULL,

	pt POINT NOT NULL,

	PRIMARY KEY (cx, cy),

	SPATIAL INDEX (pt)

) ENGINE=INNODB;



INSERT INTO geo (cx, cy, pt) VALUES (0, 0, POINT(0, 0));

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 1, POINT(cx, cy + 1) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 2, POINT(cx, cy + 2) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 4, POINT(cx, cy + 4) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 8, POINT(cx, cy + 8) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 16, POINT(cx, cy + 16) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 32, POINT(cx, cy + 32) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 64, POINT(cx, cy + 64) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 128, POINT(cx, cy + 128) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 256, POINT(cx, cy + 256) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 512, POINT(cx, cy + 512) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx, cy + 1024, POINT(cx, cy + 1024) FROM geo);



INSERT INTO geo (cx, cy, pt) (SELECT cx + 1, cy, POINT(cx, cy + 1) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 2, cy, POINT(cx, cy + 2) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 4, cy, POINT(cx, cy + 4) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 8, cy, POINT(cx, cy + 8) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 16, cy, POINT(cx, cy + 16) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 32, cy, POINT(cx, cy + 32) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 64, cy, POINT(cx, cy + 64) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 128, cy, POINT(cx, cy + 128) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 256, cy, POINT(cx, cy + 256) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 512, cy, POINT(cx, cy + 512) FROM geo);

INSERT INTO geo (cx, cy, pt) (SELECT cx + 1024, cy, POINT(cx, cy + 1024) FROM geo);



SELECT cx, cy, ST_ASTEXT(pt)

FROM geo

WHERE ST_CONTAINS(ST_GEOMFROMTEXT('POLYGON((60 60,115 120,10 90,60 60))'), pt);



SELECT cx, cy, ST_ASTEXT(pt)

FROM geo

WHERE ABS(cx - 60) <= 18 AND ABS(cy - 60) <= 18

;

La première requête de SELECT utilise bel et bien l'index SPATIAL de manière hyper-effiace (query + network = 0.000 + 0.016s). Un EXPLAIN montre d'ailleurs bien que l'index "pt" est utilisé, et qu'il filtre sur 12630 rows (sur les 4.194.304 rows au total d'après un SELECT COUNT(*) FROM geo). Cela doit correspondre au bouding rectangle du triangle utilisé (j'ai eu la flemme de faire un hexagone). 1448 rows sont retournées sur ces 12630. Avec un hexagone, le ratio devrait même être plus élevé (un hexagone rempli mieux le rectangle qui lui est circonscrit)

La 2e requête en revanche passe à côté des index (comme EXPLAIN le montrera) et les 4.000.000 et quelques de lignes sont testées une à une... Outre le lock dément que cela devrait induire, la perf s'en ressent clairement (0.079s + 2.968s). Le network correspond semble-t-il au fait que toutes les lignes de la DB sont lues (donc, il faut les transférer du disque à la mémoire, en gros, et HeidiSQL compte ça dans "network" au sens large)

Donc bon, 0s vs 3s de query quand on modélise la carte hexagonale en "flat"... Je ne suis même plus "pas convaincu que la 3D sert à qqc", je suis carrément "convaincu que c'est un énorme frein".

Note que l'ensemble des tuiles à une distance de manhattan D d'une autre tuile devrait pouvoir se calculer de manière similaire pour une map faite d'autres polygones (ie: triangles équilatéraux par exemple); la forme dans le ST_CONTAINS sera juste différente

[Meraxes]

Oui effectivement, seulement je pense que c'est vrai pour une représentation donnée de ta carte hexagonale sur le plan euclidien, mais pas dans le cas général.

Par exemple si tu avais voulu une représentation de ta carte hexagonale tout en largeur pour que chaque case ressemble à une sorte d' "d'hexagone aplati", alors c'est toujours la même carte hexagonale mais ce n'est plus tout à fait la même formule (les angles vont changer et, comme tu l'as remarqué, il faudra adapter la formule initiale ou bien appliquer une transformation).

C'est toujours intéressant à voir du point de vue géométrie mais pour résoudre un problème de distance de Manhattan entre deux cases d'un tablier orthogonale (ou entre deux nœuds dans un graphe) tu n'as pas besoin de faire de la trigonométrie normalement (même si c'est possible de faire comme ça).

[Xenos]

C'est une méthode adaptée à tout pavage hexagonal régulier du plan, qu'importe l'orientation des tuiles (pas sûr que t'arrives à te représenter un pavage tourné de 30°, 45° ou 90° dans ta modélisation 3D)

Hexagones aplatis => Oui, tu fais une transfo initiale pour retomber sur un hexagone régulier et c'est terminé (ou tu transforme le POLYGON dans la query ci-dessus en appliquant un facteur sur X et sur Y, niveau changement, ça va, j'attends de voir les changements dans le modèle X/Y/Z). Ca vaut pour toutes les représentations d'ailleurs, et toutes les transformations linéaires (suffit d'en inverser la matrice pour retomber sur du régulier, ou de l'appliquer au POLYGON). D'ailleurs, l'hexagone aplatit peut l'être dans un plan toujours euclidien, et je ne suis pas certain que tu arrives à te représenter correctement la transformation 3D associées, sachant qu'on partait de ce sujet et qu'elle est (de mémoire) uniquement adaptée aux hexagones réguliers

Représentation en graphe => Oui, tu fais juste un parcours du graph, quelque soit le pavage, y'a pas à discuter là, et y'a pas de représentation 3D/pas 3D qui tienne. C'est, IMO, le meilleur système d'ailleurs puisque très souple et adaptable à un paquet de types de tuiles/pavages plus originaux (c'est l'approche d'ECLERD d'ailleurs). Avec les WINDOW FUNCTIONS de mysql 8, je pense même que c'est performant

Pas besoin de faire de la trigo => Y'a pas de trigo dans mon dernier exemple, et mis à part ça, je trouve l'argument très mal venu. Quand la trigo est un outil adapté, on s'en sert, je maintiens que si un "dev" informatique ne sait pas faire de la trigo, c'est clairement pas un ingénieur. Puis bon, à ce compte-là, tu fais aussi de la trigo avec une représentation 3D (c'est de la trigo dans l'espace d'ailleurs)

Là, j'ai l'impression de partir dans le débat stérile où le postulat "la représentation 3D proposée dans l'article est top pour connaitre les tuiles à une distance de manhattan donnée d'une autre tuile, puisque c'est dans un article" sera de toute façon inébranlable (par définition du postulat, ou parce que "ah, ouais, je me suis peut-être gourré" est trop difficile à dire), donc bon, même si ce ne sera pas hyper-diplomatique comme formule, je dis: quand tu trouveras un argument plus percutant (meilleures perfs SQL? une "applicabilité" à plus de cas/plus de types de tuiles/d'agencements de tuiles?) en faveur de cette représentation 3D, je reviendrai répondre avec plaisir. Si c'est pour se cantonner à "ouais mais non, ton truc est moins bien", je passe mon tour. Chacun modélisera comme il veut son jeu, j'espérai juste éviter qu'il ne faille 3s/page à cause d'un mauvais algo implémenté en SQL.

[Meraxes]

Mais là tu dis juste qu'utiliser des index B-trees ce sera plus rapide que de faire un FULL SCAN..

Après, très bien, tu utilises GEOMETRY et tu raisonnes sur des représentations concrètes mais, comme on l'a déjà dit, ce n'est pas le problème de départ ,tel que je l'avais posé, qui était de raisonner sur des représentations abstraites de la carte hexagonale dans un tablier, donc indépendamment de la façon dont tu la représente sur le plan, et surtout de simplifier une approche (mais, bon, si tu en choisis une autre, tant mieux pour toi ; mais c'est un autre sujet pour moi).

Et oui tu feras comme tu veux : et si ce que j’écris ne t’intéresse pas, ne me lis pas.

EDIT : du coup, pour utiliser les index (x,y,z) faire :
" where x between xpa and xpb and y between ypa and ypb and z between zpa and zpb "
Avec xpa = xp - D ; xpb = xp +D , etc.