Bonjour à tous,

je suis en train de développer un jeu de stratégie, et pour générer les zones d'influences des factions, j'utilise la Triangulation de Delaunay.

Ça fait maintenant environ une semaine que je bloque sur un problème, et je ne trouve personne sur le net qui a le même problème que moi, et impossible de trouver la solution, en ayant relu et réécris le code plusieurs fois et tenter des modifications au niveau algorithmique. Ce problème apparaît uniquement lorsque le nombre de point à relier est conséquent, donc pas facile de faire des tests...
Quand je suis par exemple à une centaine de points ou moins : aucun problème. Tout est nickel.
Quand je suis à 1000-2000 points, par moment, le problème arrive.

En voyant l'image vous pouvez facilement deviner le problème... Des lignes verticales apparaissent aléatoirement, alors que le reste est correct. Je précise, les points des lignes erronées ne sont pas alignés verticalement.

J'utilise l'algorithme "diviser pour régner" : http://www.geom.uiuc.edu/~samuelp/del_project.html

J'ai déjà testé de générer les triangles de gauche à droite et non plus récursivement pour voir si l'algorithme posait problème : même problème.

Je ne poste pas le code au cas où quelqu'un aurait une idée rien qu'en voyant la nature du bug ou si c'est déjà arrivé à quelqu'un, sait-on jamais. Par contre, si vous voulez le code je peux l'envoyer sans problème.
Même si vous avez une piste je suis preneur car là je suis complètement largué !

Merci beaucoup.

Tu ecris le code en quel langage ?

C# sur Unity

les grosses lignes verticales que l'on voit, c'est une seule ligne, ou c'est une dizaine de lignes superposees?

J'ai fais plusieurs zoom pour bien montrer la chose.
Par moment ça peut être une ligne qui va de A à B qui passent à travers tous les triangles mais qui les perturbent pas, ou sinon c'est complètement l'inverse il y a une ligne imaginaire qui va de A à B qui passent à travers tous les triangles et qui les perturbent (comme sur les screen ici).
Au final tous les points sont reliés soit à A ou à B - au lieu d'être reliés au point juste à côté d'eux - ce qui forment ces grandes lignes verticales.
Du coup pour te répondre : c'est plusieurs lignes superposées.

Je vois.
Du coup on dirait que ca ressemble a un probleme dans la construction des "non-delaunay triangles".

Ce que je ferais c'est que je hackerai le code pour avoid plus d'information. En particulier, je dumperai des etats intermediaire de la triangulation.
Aussi, je ferais un mode "debug" qui verifie a chaque ajout d'une arete dans la triangulation si tu as deux aretes qui se croisent et qui pond un message d'erreur quand ca arrive. Du fait ca va te permettre de mettre un breakpoint sur cette condition et de pouvoir regarder ce qu'il se passe dans le code au moment de l'ajout de la premiere arete non valide.

Ok merci Godrik, je vais essayer de trouver un seed qui me donne cette erreur avec un nombre de point minimal et voir si ça détecte quand 2 segments se croisent, je mettrai à jour pour dire ce qu'il en est !

Je pense aussi qu'il va falloir "instrumenter" l'algo pour verifier chaque etape et tester les sorties dans des conditions precises pour s'assurer de la logique. Sur qqch de cette complexite, il est difficile d'intuiter la cause exacte, meme si on peut avoir des intuitions.

Essaye p-e d'implementer des unit tests pour verifier que les resultats sont bien ceux escomptés pour chacun des cas pris en compte par l'algorithme.

Ou alors trouver un "trigger" qui puisse servir de condition logique a un breakpoint, e.g. "si deux points distants de plus de x unites sont reliés, c'est surement un bug", etc.

Merci Refeuh de ta réponse, je pense avoir trouvé l'origine du bug.

J'ai décrémenté le nombre de points, et j'ai réussi à en générer 20 qui reproduisent le bug, beaucoup plus facile pour tester ,donc finalement ce que je pensais depuis le début - que ça pouvait se produire seulement quand il y en avait beaucoup - était faux !

J'ai isolé les points qui déconnaient et je me suis rendu compte que ça clochait juste au début, la première étape qui consiste à relier le set de points gauche au set de points droit par le segment le plus bas possible. Par moment, en l’occurrence là où il y avait le bug, la ligne qui était censée relier était carrément pas à la bonne place, du coup ça faisait foirer tout le truc car tout part de là.

Me reste plus qu'à trouver l'algo pour trouver la bonne liaison car du coup l'autre est pas bon, et ça devrait fonctionner !

Je vous confirmerai ça.

Cool.
Souvent identifier une instance simple du probleme qui ne marche pas est la moitie du travail.

J'ai ré-écris la fonction qui permettait de trouver le segment le plus bas possible et cette fonction fonctionne maintenant.

Je n'ai plus aucun bug quand le nombre de systèmes est bas maintenant mais ça reste toujours présent quand il y en a plusieurs milliers, même si mon jeu n'aura jamais autant de systèmes, ce bug me dérange un peu.

Entre temps j'ai également remarqué que j'oubliais de supprimer des connexions par moment mais le problème ne venait pas de là au final.
J'ai aussi pensé que ça pouvait être une erreur de précisions des float, du coup j'ai remplacé les coordonnées par des integer, ce qui n'a absolument rien changé.
Pour être sûr que ça ne venait pas d'un problème de coordonnée, aucun point ne pouvait avoir le même X.

Malgré le fait que le bug reste présent, les fix que j'ai apporté ont permis de régler les problèmes quand le nombre n'est pas important.

Du coup vu que ça marche pour ce que je veux faire je vais laisser ça comme ça.

Si tu veux pousser sur la question, je ferais ce que j'ai ecrit plus haut. Faire en sorte que ton code detecte au moment ou tu rajoute une arete qui en croise une autre. Ca devrait te permettre de detecter l'etape precise qui declenche le probleme.

Me revoilà.

Bon, j'ai fais en sorte de détecter quand un segment en croise un autre et de pouvoir revenir à ce moment pour voir ce qu'il s'est passé avant. Et bien d'après ce que j'ai vu, c'est une sorte de cascade qui entraîne par la suite ces lignes verticales. Un point ne peut pas en relier un autre alors qu'il devrait ce qui fait que le segment créer est complètement mauvais etc etc et ça s'enchaîne. Mais c'est impossible de remonter à la source tellement qu'avec tous ces points c'est le bordel total.

J'ai aussi trouvé 2 autres problèmes que j'ai pu réglé avec une seule solution :
Je générai les polygones de 4 et 5 côtés avec un algorithme à part, mais je me fiais à la distance et donc par moment je ne respectais pas la condition des triangles de Delaunay (les cercles devant être vide).
J'ai aussi pu supprimer quelques lignes verticales en remplaçant un ">=" par un ">", mais bon.

Un autre problème qui n'en est pas vraiment au final : les lignes verticales n'apparaissent plus du tout quand il n y a pas énormément de points (<500), donc pour tester c'est peu la galère. Pour en être sûr j'ai fais une boucle infinie qui génère des triangulations de Delaunay avec des points aléatoires, et quand une triangulation est foireuse, le programme plante (vu que je génère des meshes avec). Et avec plusieurs dizaines de milliers de générations, aucune erreur.

Du coup, pour régler ce problème de lignes, je me suis dis qu'elles étaient verticales car je lie les points seulement de gauche à droite, je devrais donc peut-être alterner, une fois de gauche à droite, une fois de bas en haut. Vu que sur les lignes verticales, les points sont souvent distancés d'une hauteur de 1000-2000 unités alors qu'ils sont distancés d'une largeur de quelques unités seulement, les angles sont vraiment petits, et les erreurs de précisions font peut-être que...

Problème résolu.

J'ai fais comme j'avais dit, j'ai alterné, je sépare en premier de droite à gauche, ensuite de haut en bas, et ainsi de suite... Le résultat est que les triangles générés sur de grand espace ne sont plus étirés (tellement étirés qu'ils ressemblaient à des droites) mais ressemble à des triangles lambda. Du coup ensuite pour les connexions tout est nickel...

J'ai fais plusieurs test avec 10000 points : OK.

Donc si quelqu'un a le même problème que moi, cette méthode d'alternance fonctionne à merveille.
Sinon pour le problème initial, c'est sûrement un problème de précision d'une de mes fonctions qui calcules les angles ou que sais-je.

2 petits screenshots qui montrent la triangulation de Delaunay ainsi que son Diagramme de Voronoï qui va avec !
Je vais pouvoir enfin continuer sereinement à bosser sur le reste du jeu, enfin !

Merci pour l'aide !