Définition table pour pathfinding

[gizmo3845]

Bonjour,

Depuis longtemps je me pose la question: Comment les équipes font pour définir leur table et obstacles pour faire le pathfinding.
En effet, quand on fait un calcul de Pathfinding on a besoin de définir une grille ou graphe qui va définir virtuellemnt notre table de jeux.
Chez Alpobot, nous définissons, grosso modo, jusqu'à présent (les choses peuvent toujours s'améliorer !) les éléments comme suit:

• La table est définie avec une résolution de 30000x20000 afin de garantir une bonne précision

• Les obstacles sont définis en terme de coordonnées (Circulaire: Centre + rayon, Rectangulaire: points des sommets, Composés: mixe circulaire,Rectangulaire)

• Un graphe de points définis les positions possibles du robot (prenant en compte son encombrement), définis humainement de façon à les placer judicieusement

• Pathfinding basé sur Dijkstra se servant des 3 points précédents

Qu'utilisez-vous pour définir ces concepts ?
Découpage de la table sous forme de grille ? Autre ?

Merci pour vos retours.

[wix]

De notre côté quand on veut définir une solution simple, on défini des points de référence sur la table à la main (genre une dizaine par demi table) et on en fait un graphe. Pour se déplacer on va vers le point le plus proche (en espérant que ça passe), on trouve un chemin vers le point le plus proche de destination (avec un A* tout con), puis on va du graphe au point de destination en faisant attention à ne pas se payer un mur.

Quand un adversaire est présent on invalide des branches du graphe et on recalcule.

Ca casse pas 3 pattes à un canard mais en pratique, y'a peut de robot qui sont au cm près de déplacement pour gagner du temps, et on aime bien voir des robots qui passent toujours aux même endroits, ça rassure. Du coup ça suffit.

Ca peut aussi être une façon de construire une heuristique pour un chemin qui est ensuite optimisé pour limiter les manœuvres, l'idée étant de donner au robot une idée de la structure de la table. Si en plus tes points de passages sont des objets tu peux te débrouiller pour ramasser ce qui traine sur la table "par chance".

[PF]

Au club INTech, ça varie selon les années mais le plus souvent ce sont des points de passage définis à la main. Quand on détecte un ennemi, on invalide les arcs qui sont bloqués et on rajoute des points autour de l'adversaire (qu'on suppose être circulaire avec un rayon assez grand) afin de pouvoir le contourner.

Je pense qu'un A* avec des points de passages définis à la main est généralement suffisant. Parmi les améliorations possibles, il y a :

- le lissage du trajet. Si le pathfinding te donne le trajet "A, B, C" et qu'en fait tu peux aller directement de A à C, alors autant supprimer B. Selon comment tu relies tes points de passages, le lissage peut être utile ou pas. Si tu relies tous les nœuds qui sont accessibles l'un à partir de l'autre (un graphe de visibilité), alors le lissage est inutile (le trajet est déjà lissé). Si par contre tu limites le nombre de voisins qu'à un nœud dans le graphe, là le lissage pourra améliorer la trajectoire. On peut aussi lisser le chemin pendant la recherche en utilisant l'algorithme Theta*.

- prendre en compte non pas la longueur de la trajectoire mais sa durée de parcours. Par exemple, tu peux considérer que le coût d'un trajet entre A et B est "distance(A,B) + constante". Cette constante prendra en compte le fait que le robot doit accélérer et ralentir pour faire ce parcours A-B. Ainsi, entre un trajet court (en terme de distance totale) avec 8 points et un trajet plus long (en terme de distance totale) avec 4 points, ce dernier pourra peut-être être plus rapide.

Enfin, une piste d'amélioration de temps de calcul peut être l'heuristique. L'heuristique classique est la distance à vol d'oiseau. Si ton pathfinding est trop lent, tu peux utiliser la distance octile (max(x, y) + (0.414)*min(x, y)) comme heuristique, qui est une très bonne approximation de la distance à vol d'oiseau sans avoir à calculer de racine carré. Mais attention à l'optimisation précoce !

J'espère avoir été assez clair !

[gizmo3845]

On fait donc peu ou prou la même chose ( Graphe manuel + A*, Disjkstra, etc.. ) avec des heuristiques ou des pré-calculs.
Où cela se complique c'est que maintenant on veut faire des trajectoires en courbes de Bézier. Or, un graphe avec des points manuels n'est plus tellement indiqué, on partirait plutôt sur une solution de calcul de zones "libres" afin de pouvoir y placer nos points de contrôles.
Quelqu'un a-t-il déjà expérimenté ?
@PF: J'ai lu ton document sur les trajectoires courbes à base de clothoïdes mais il nous semble qu'une solution basée sur des courbes de Bézier serait plus appropriée (comme tu semblais l'évoqué dans ton échange avec arno). Comment aviez-vous placé les points de controles ?

[PF]

Une courbe de Bézier est définie par ses points de contrôle, mais on peut aussi définir une courbe en imposant des contraintes, comme la position d'arrivée, l'orientation à l'arrivée, etc., et en déduire ensuite les points de contrôle qui donnent une courbe qui respecte ces contraintes (il suffit de savoir dériver un polynôme). Le problème c'est que la courbe de Bézier qui arrive là où tu veux avec la bonne orientation peut parfaitement passer par un obstacle. Donc chercher une seule courbe de Bézier pour arriver directement à destination est assez illusoire.

Une autre idée sur laquelle je vais travailler pour ma librairie de pathfinding est d'avoir des points de passage posés manuellement, et de faire un A* particulier. Au lieu de faire un A* avec une ligne brisée, on fait un A* avec des courbes de Bézier, où chaque courbe entre deux points est une courbe de Bézier (et pas juste un segment). Pour calculer ces courbes, on peut utiliser une méthode comme celle ci-dessus (pour avoir une courbure continue et éviter des discontinuités, tu peux aussi imposer des contraintes supplémentaires sur la courbe).

Ainsi, tu ne spécifies jamais les points de contrôle : ils sont déduits des contraintes sur la (les) courbe(s) de Bézier.