[Truc] Carte, Hexagones et Coordonnées

[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