Post
by PF » Tue 01 Aug 2017, 23:04
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 !