Sélectionner les cases cotières d'une carte

[Xenos]

Salut à tous!

J'ouvre tellement peu les sujets que je n'ai même pas le réflexe de poster ici quand j'ai un problème >.>

J'ai une table MySQL contenant les cases de la carte du jeu, structurée comme ceci:

x INT SIGNED
y INT SIGNED
altitude SMALLINT SIGNED
mer BIT(1)

x,y PRIMARY KEY

Je cherche à sélectionner toutes les cases côtières de la carte, d'altitude négative ou nulle. Donc, je cherche toutes les cases (x,y) telles que mer=0 (case terrestre) et altitude<=0 (sous le niveau de la mer), et telles que l'une de ses voisines (x-1,y-1) ou (x-1,y+1) ou (x+1,y-1) ou (x+1,y+1) soit maritime (mer=1).
Le but est de pouvoir inonder ces cases côtières dont l'altitude est négative (logique: une case terrestre voisine de la mer et en-dessous de celle-ci ne reste pas terrestre très longtemps!): la sélection SELECT sera transformée en un UPDATE.

Pour l'instant, j'ai cette requête:

SELECT `case0`.`x`, `case0`.`y`

FROM `cases` `case0`, `cases` `case1`

WHERE `case0`.`mer`=0 AND `case1`.`mer`=1 AND `case0`.`altitude`<=0 AND (

(`case1`.`x`-1=`case0`.`x` AND `case1`.`y`-1=`case0`.`y`) OR 

(`case1`.`x`+1=`case0`.`x` AND `case1`.`y`-1=`case0`.`y`) OR 

(`case1`.`x`-1=`case0`.`x` AND `case1`.`y`+1=`case0`.`y`) OR 

(`case1`.`x`+1=`case0`.`x` AND `case1`.`y`+1=`case0`.`y`))

Où je sélectionne les données de la case cotière (case0), ainsi que celles de la case maritime voisine (case1).

La requête s'exécute en 10secondes. Auriez-vous une requête plus véloce, sachant que la table des cases contient 516k cases actuellement (ce nombre ne changera pas)?

[Xenos]

Et si vous avez une solution pour sélectionner toutes les cases côtières, quelque soit leur altitude (donc les cases ayant au moins une voisine maritime), plus rapide que celle ci-dessous qui dure des plombes (pour 500k cases dont les 2/3 sont de la mer), je suis preneur:

SELECT

	`case0`.`x`, `case0`.`y`

FROM

	`cases` `case0`, `cases` `case1`

WHERE

	`case0`.`mer`=0

	AND `case1`.`mer`=1 

	AND (

		(`case1`.`x`-1=`case0`.`x` AND `case1`.`y`-1=`case0`.`y`)

		OR (`case1`.`x`+1=`case0`.`x` AND `case1`.`y`-1=`case0`.`y`) 

		OR (`case1`.`x`-1=`case0`.`x` AND `case1`.`y`+1=`case0`.`y`)

		OR (`case1`.`x`+1=`case0`.`x` AND `case1`.`y`+1=`case0`.`y`)

	)

[niahoo]

Pfff t'es vraiment obligé de mettre toutes ces quotes ? ça me fait bugger les yeux.

Bref, donc déjà tu utilises les notations x/y et altitude, pourquoi ne pas plutôt mettre 'latitude', 'longitude', et 'z' ? :p

Ensuite c'est pas logique que des cases aient une altitude négative par rapport à la mer et soient côtières. à moins que tu simules l'avancée des eaux. Dans tous les cas pourquoi ne pas simplement calculer tout ça à l'avance et le garder au chaud ?

---

Oui je sais ça aide pas trop.

[Ter Rowan]

de la même manière que tu stockes mer, lorsque tu créés/modifies une case, ajouter l'attribut côte ?

après je me pose la question si une case < 0 est à côté d'une case < 0 qui est elle même à côté d'une case mer, est ce qu'elle aussi ne devrait pas être inondée ?

[Akhyra]

Hello

Est ce que ta carte est grande ?
Est ce que l’inondation est réalisé par un cron/script ou en temps à l'affichage ?

Si c'est réalisé par un cron, je serai passer par un traitement serveur (PHP), traitement plus long selon la grandeur de la carte mais qui te permet de mettre en place un algo d’inondation plus élaboré et modifiable par la suite.
Je pense notamment à des cas ou tu ne voudrai pas inonder des cases adjacentes avec une certaine altitude, un certains type ou contenu.

[niahoo]

La carte fait 516k cases.

[Xenos]

@niahoo: Latitude/Longitude impliquent une carte sphérique, ce qui ne sera pas forcément le cas, d'où X/Y et altitude (et non Z car deux cases ne se superposent pas: l'altitude est une propriété de la case en XY plus qu'une coordonnée de la case).
Le générateur de carte travaillant à partir d'une image PNG, le résultat n'est pas parfaitement exact, et des cases terrestres se retrouvent sous le niveau de la mer, en étant voisine de celle-ci :\

---

@Ter Rowan: Oui, dans le cas d'une case sous le niveau de la mer, voisine d'une case également sous le niveau de la mer, voisine elle-même d'une case maritime, les deux cases sous le niveau de la mer seront inondées. Cela se fera très bien par réccurence: noyer les cases cotières sous le niveau de la mer, ce qui crée de nouvelles cases maritimes, modifier la liste des cases cotières sachant lesquelles viennent d'être noyées, puis noyer les cases cotières sous le niveau de la mer voisine d'une case qui vient d'être noyée.
Cette récurrence est en place, mais chaque "passage" (chaque tour de boucle) prend une dizaine de secondes, et comme le nombre de boucles peut monter à quelques centaines, cela fait vite très très long!
Oui, j'ai tenté de stocker un autre attribut indiquant qu'une case est cotière, mais la requête pour générer cet attribut est interminable (cf 2nd post, requête sans le "case0.altitude <=0).

---

@Akhyra: La carte contient environ 500k cases, dont 200k sont terrestres et 300k sont maritimes. Pour l'instant, l'inondation est réalisée uniquement au démarrage du jeu, pour l'initialiser.
J'ai eu la même idée en me levant, passer par un PHP avec un tableau 2D de booléens "mer" pour créer un autre tableau de booléens 2D "estCotiere". Je viens de tester, et le résultat est assez satisfaisant. Je vais essayer de faire le même procédé en SQL.

Pour information, en voici le code:

$r = $mysqli->query('SELECT `x`, `y`, `altitude`, `mer` FROM `cases`');



// Initialiser un tableau d'entiers type "flag", dont le premier bit indique s'il s'agit d'une case maritime (0x01)

// Le second bit (0x02) indique s'il s'agit d'une case cotière

$data = array_fill(0, 720, array_fill(0, 1440, 0));



// Insérer les données SQL dans ce tableau

foreach ($r as $c)

	$data[(int)$c['y']][(int)$c['x']] = (int)$c['mer'];



foreach ($data as $j=>&$row)

{

	foreach ($row as $i=>&$case) // Pour chaque case du tableau

	{

		// On teste si la case est terrestre et si l'un de ses voisins est maritime

		// Effectivement, comme souligné par Akhyra, on pourra ajouter des traitements supplémentaires

		// Comme le fait que la carte "boucle", exemple: les cases en X=0 sont voisines de celles en X=Xmax

		// X=0 ($i==0) sont les cases du bord gauche, X=1439 ($i==1439) sont celles du bord droit

		// Y=0 ($j==0) sont les cases du bord haut, Y=719 ($j==719) sont celles du bord bas

		// Dans ce test, la carte ne boucle pas (pas encore!)

		if ($case == 0

			and (

				($j > 0		and $i > 0	and $data[$j-1][$i-1] & 0x01)

				or ($j > 0	and $i < 1439	and $data[$j-1][$i+1] & 0x01)

				or ($j < 719	and $i > 0	and $data[$j+1][$i-1] & 0x01)

				or ($j < 719	and $i < 1439	and $data[$j+1][$i+1] & 0x01)

			)

		)

			$case |= 0x02; // Case cotière

	}

}

// ($data[y][x] & 0x01) indique si la case est maritime

// ($data[y][x] & 0x02) indique si la case est cotière

Temps (500k cases dont 24k cases côtières): 5secondes
Mémoire (carte 1440*720 contenant 500k cases): 165Mo

Merci du coup de main

[niahoo]

Genre un carré de 718 cases de côté (mais je suppose que c'est plutôt un rectangle dans le cas présent).

[Akhyra]

Retour rapide, pourquoi stocker seulement une valeur 1 ou 0 dans les coordonnées de la case ?

J'ai pas fait de test, mais stocker la ligne SQL sous format array me parait pas délirant sur les ressources, ca te permettra si besoin par la suite d'avoir toutes les infos de la case pour modifier l'algo.

[Xenos]

Parce que pour la détection des côtes, je n'ai pas besoin de plus. Je suis déjà à 165Mo en mémoire (ah, la terrible optimisation de la mémoire en PHP :p), si je rajoute d'autres données, (en remplaçant la valeur entière par un tableau correspondant aux données de la ligne SQL) je dépasserai facilement le giga...

Finalement, j'ai opté pour:

• Ajouter un identifiant unique "id" à chaque case (au lieu d'utiliser le couple (x,y) comme clef primaire)
  
• Ajouter 4 colonnes IdVoisin1, IdVoisin2, IdVoisin3, IdVoisin4 à la table des cases
  
• Insérer, dans ces colonnes IdVoisinN, l'identifiant des voisins de la case (donc, la case Id=1 en (x=1,y=1) se voit associer IdVoisin1=721 correspondant à la case (x=0,y=2))
  
• Utiliser les jointures dans la requête SQL suivante:
  

  
  
  	UPDATE `cases` `case0`
  
  	LEFT JOIN `cases` `case1` ON (`case1`.`id`=`case0`.`idVoisin1`)
  
  	LEFT JOIN `cases` `case2` ON (`case2`.`id`=`case0`.`idVoisin2`)
  
  	LEFT JOIN `cases` `case3` ON (`case3`.`id`=`case0`.`idVoisin3`)
  
  	LEFT JOIN `cases` `case4` ON (`case4`.`id`=`case0`.`idVoisin4`)
  
  	SET `case0`.`mer`=1
  
  	WHERE
  
  	`case0`.`mer`=0
  
  	AND `case0`.`altitude`<=0
  
  	AND (
  
  		`case1`.`mer`=1
  
  		OR `case2`.`mer`=1
  
  		OR `case3`.`mer`=1
  
  		OR `case4`.`mer`=1
  
  	)
  
  

Le résultat est rapide (quelques secondes), sans exploser la taille en mémoire pour le PHP.

J'aurai pu insérer les "IdVoisinN" dans une table séparée (type "IdCase1", "IdCase2", symbolisant deux cases voisines) mais étant donné que je n'ai que 4 voisins pour chaque case, une table supplémentaire aurait été plus lourd à gérer.

En pratique, le goulot d'étranglement qui fait exploser la durée du traitement vient de l'indexation (x,y) (ou (y,x) dans mon cas): l'utilisation de deux arbres binaires (BTREE) comme le fait MySQL n'est absolument pas optimisé pour la recherche des voisins d'une case.
Par curiosité, je vais tenter d'utiliser le format spatial de MySQL. Je vous rapporterai les résultats