amélioration warning box

Bonjour à tous, je suis actuellement en train de travailler sur la génération de séquence de pas d'un robot censé éviter les obstacles. pour l'instant, le robot évite bien les obstacle, mais il n'est pas optimal. le programme "encadre" l'obstacle (tout est en 2D) dans une warning box (hitbox) et le robot évite cette box. Cela ne me suffit pas, ça me fait perdre beaucoup trop d'espace ou les pieds du robot pourrait se poser! (par exemple pour un obstacle en forme de C, je voudrais pouvoir le faire poser son pieds au centre du C.)
Ca m’énerve de perdre du temps la dessus, alors que ce n'est qu'une étapes avant de commencer le vrai travaille!
J'avais penser utiliser des warning box carré, puis découper celle ci en quatre autres carrés (11,12,13,et 14), que je repartis dans deux différentes listes : "vide" et "pleine", selon si l'obstacle est présent ou non dans cette case. Ensuite je recommençais a découper les élément de "pleine" (ex: 111, 112, 113, et 114) que je redistribue dans "vide" et "pleine"... etc...
Avec un nombre d'itération suffisant, j'obtiens une forme assez fidèle. Le problème est le temps de calcul... C'est très long... J'ai besoin de quelques chose de très rapide!

Est ce que quelqu'un aurait des idées pour optimiser l'espace disponible pour que le robot y pose ses pieds?

Cordialement,

Lestate

Hello,

tu connais la forme des pieds de ton robot.
L'objectif est de savoir donc si le pied de ton robot peut se fourrer dans l'espace vide d'un obstacle visionné dans ta hitbox.
Tu peux t'orienter vers un algorithme "diviser pour régner" afin de réaliser ton découpage matriciel et déterminer les pleins (bits à 1) et vides (bits à 0) sur une profondeur récursive de X (X que tu détermineras et qui t'offre la précision que tu recherches).

De manière récursive c'est comme si tu parcourais un arbre découpé en 4 puis chaque partie en 4 etc...

Après bien entendu, il faut de la reconnaissance de forme pour déterminer si à une position (x, y) de ta matrice pleins / vides, tu peux insérer la forme de ton pied de robot.