10-01-2017, 04:53 PM
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)
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)