Calculer la meilleure map de collision à partir d'une collection d'obstacles ?

[Argorate]

Bonjour,

je voulais savoir si quelqu'un connait un algo/programme/scipt qui permet de calculer la map de collision optimal à partir d'une liste d'objet en 2d?

Exemple : sur la pièce jointe, on peut dire qu'on a une collection d'arbres qui on leur coordonnée en jaune, et il faudrait que l’outil minimise au mieux toutes les zones de collisions en regroupant tout ce qui peut l'etre pour qu'il y ait le moins de test à faire une fois en jeu (sur l'exemple en rouge, on est passé de 5 paires de coordonnées à tester à seulement 2 !)

Merci.

[Xenos]

Salut,

la définition de "optimale" est toujours à préciser, car l'optimum peut prendre plein de formes: est-ce qu'on veut minimiser l'aire totale où des éléments se chevauchent (= si 4 éléments de surface 1 unité se superposent, alors la somme est 1 unité)? Est-ce qu'on veut minimiser la somme des aires de chevauchement de chaque élément (= si 4 éléments de surface 1 unité se superposent, alors la somme est 4 unités)? Ou le carré de chaque somme (= si 2 éléments se superposent à moitié, la somme est de 0.5²+0.5² = 0.5)?

En plus, en lisant l'exemple, j'ai l'impression que la solution rouge n'est pas du tout celle du problème initial posé. J'ai plutôt l'impression que tu as une surface composée de rectangles qui se chevauchent, et tu cherches à créer un ensemble d'autres rectangles, couvrant l'exacte même surface, mais de sorte que ce nouvel ensemble ait le moins de rectangles possibles, c'est ça?

(Perso, je trouve que cela sent le recodage d'une optimisation de moteur de collisions 2D et que tu perds inutilement du temps dessus si tu comptes mettre le jeu en prod derrière)

[Argorate]

L'optimal c'est qu'il y ait le moins de test possible, donc c'est le nombre de "rectangle" qui compte.

Le quadtree est une bonne méthode, mais elle fini tjs par un maillage minimal qui demande donc le parcours de tous les éléments présents dans le carré final, pour testé s'il y a collision avec un projectile par exemple.

Donc on retombe bien sur ce problème, moins il y a de série d'aire (x1;y1 à x2;y2) à vérifier, mieux c'est...

[Xenos]

Le moins de tests possibles par rapport à quoi? Que testes-tu? Le déplacement d'un joueur? Dans ce cas, je ne pense pas que les centaines (voire milliers) de gens qui ont bossé sur ce problème se soient trompés en utilisant des arbres binaires...

Car si tu cherches à savoir si un point est dans un arbre (ou autre élément solide), l'arbre binaire sera vite parcouru (voire la variante "on descend l'arbre jusqu'à tomber sur un noeud marqué "pas obstacle", ou "obstacle"; s'il est marqué "mélange", on descend encore"). Pour un segment, tu auras à peu près le même principe (tu vas simplement te retrouver avec plusieurs segments lorsque tu descendra assez bas dans l'arbre).

Après, d'un point de vue pratique (pour la curiosité, c'est bien, mais je sais que tu vas vouloir en faire un jeu en prod derrière):
- T'as vraiment besoin de cette optimisation avant même de sortir l'alpha de TMI?
- Pourquoi ne pas prendre un FW qui gèrera ton canvas plutôt que de réinventer des trucs et devoir implanter du code système en boucle au lieu de te concentrer sur le coeur de jeu?
- Qu'est ce qui te fait dire que juste limiter le nombre de rectangles soit le plus optimal? Une machine traite très bien une grande quantité de données simples, du même type, et très mal les petites quantités de données complexes et spécifiques.
- Si t'en as la possibilité, il existe des fonctions géométriques en MySQL qui font ce genre de calcul, et très vite même sur de grandes quantités de data (mais je crois que t'es en canvas coté client là, donc pas sûr que ce soit utilisable, mais il existe surement ce genre de FW de calcul en JS)

[Argorate]

Je comprends pas que tu ne comprennes pas ce que je dis, je parle chinois? ^^

https://openclassrooms.com/courses/theor...tionnement

Le principe c'est de découper la map en zone, puis quand c'est fait tu te retrouves avec une listes d’éléments de cette zone à comparer à celle de ton sujet (joueur, projectile, véhicule...etc)

Donc il y aura un nombre de test de coordonnée autant que le nombre d'éléments dans les listes lié à ce bout de map, au sens du plus mauvais cas. Donc le but est de réduire le nombre d’éléments de la liste. right?


PS : ce n'est pas pour TMI

[Xenos]

Si tu découpes ta map en "pixels", chacun étant "obstacle" ou "pas obstacle", tu sauras immédiatement qui est dans un mur. Même si tu as 100x100 pixels à tester, il te suffit de regarder le statut du "pixel" i;j. Si tu fais des "fusions" en transformant cette map de pixels simples en une map avec moins de rectangles mais des plus gros, alors ton calcul sera certainement bien plus bordélique.

Si je regarde à nouveau ta screen, j'y vois des petits carrés en pointillés. Il te suffit donc de donner un statut "Obstacle" ou "pas obstacle" à chaque carré, à partir de la position de chaque rectangle, et basta, tu as instantanément la réponse à "est-ce que le joueur en X;Y est dans un mur?" (en fait, l'instantané vient de comment JS est codé pour accéder à l'élément d'un tableau). Pour les déplacements, ce sera le même principe: tu vas "pixeliser" le déplacement de X;Y à U;V en listant les carrés qui sont concernés par ce déplacement, et carré par carré, tu regardes si c'est un obstacle (et tu t'arrêtes au 1er carré obstacle trouvé).

--------

Sinon, sur le plan mathématique, la question d'un algo permettant de couvrir une surface pixellisée donnée avec le moins de rectangles possibles est intéressante. J'essayerai de voir ce qui existe, mais je ne pense pas que cela te serve de toute façon face à la grille pixellisée de base (et même si tu passes de 6 à 2 rectangles, je doute de l'intérêt d'un tel calcul préalable).
D'autant qu'il y a certainement des cas à plusieurs réponses (un carré avec un trou carré au milieu, tu peux le paver de 2 façons avec 3 rectangles: horizontalement ou verticalement).

-------
& Ce que tu montres pour le partitionnement, c'est différent: c'est un espace 2D "continu" (pour autant qu'on puisse le faire en informatique), qui ne peut donc pas se baser sur ce schéma de pixels. C'est un champ vaste exploité déjà depuis des années par les moteurs de jeux bruts, donc autant aller voir comme est fait Ogre ou Unity. Pour ma part, les méthodes que je connais pour optimiser ces calculs sont:
• Clipbox: on considère l'objet compliqué comme "non-solide", et on lui crée un modèle invisible plus simple servant aux collisions
• Bouding box: L'objet est englobé dans un pavé et on ignore tout ce qui est au dehors (partitionnement)
• Assemblage de shapes de base: on remplace l'objet complexe par un assemblage imbriqué de formes prédéfinies et faciles à calculer: sphères, cubes, etc (c'est différent de la clipbox, qui permet de faire ce qu'on veut comme forme, sans superposition)

[Xenos]

Bon, je me doutais que la complexité de la chose ne serait pas à la mesure des apports espéré: c'est un problème NP. Mais tu peux regarder les variantes proposées sur l'article Wiki, qui doivent approximer pas trop mal les choses dans ton cas.

Après, vu que la question du minimum n'est pas capitale pour le résultat final, tu peux te servir de cet algo tout simple, et éventuellement en faire quelques variantes (ie: l'exécuter en partant de différents points, au hasard par exemple, et ne garder que le résultat avec le moins de rectangles).

[Argorate]

J'ai pris une image au pif sur google image, là il y a des cases, mais pour l'idée que j'ai en tête il n'y en a justement pas^^

merci pour le lien c'est tjs intéressant comme algo.

La technique que tu décris par case c'est justement celle que j'ai sur TMI, j'ai donc pas de soucis pour savoir quelle case est obstacle ou pas.

[Xenos]

Donc en fait, ton cas est différent de l'image trouvé: tu es dans un espace 2D continue, c'est ça?

Car si tu as des rectangles dont les coordonnées sont toutes entières (ou multiples d'une valeur donnée) de sorte que la zone qui t'intéresse ne soit pas "trop grande", alors tu peux appliquer le même alog. Sinon, tu crées une grille supplémentaire de finesse quelconque (avec des carrés de 0.1 ou de 1 unité ou plus) et tu t'en sert pour la physique (et pas pour le reste). Tu pourras faire du quadtree d'ailleurs pour éviter de stocker trop en mémoire.
(mais bon, le mieux, c'est d'aller prendre les docs techniques d'unity et de voir comment tout cela fonctionne si tu veux t'instruire; et si tu veux produire, prendre juste Unity)

[Argorate]

Oui le problème c'est pour les espace continues.

Que penses-tu de la technique du BSP? https://openclassrooms.com/courses/theor.../r-1375723
Comment on calcule l'arbre équilibré qui en découle c'est ça le hic^^