Comment faire face à des objets de différentes tailles dans une situation pathfinding (A *, A-star)

Question

Je travaille sur un jeu qui utilise A-star (A *) pour la recherche de chemin mais je suis arrivé à un point où par J'ai quelques objets qui sont plus grands qu'un seul carré de grille.

Je cours sur une grille de 16 * 16px. les segments de mur sont en 16 * 16 et font donc un seul carré impraticable. Certains de mes méchants sont 32 * 32 et ils ont donc besoin de vérifier que l'écart est d'au moins 2 carrés de la grille afin de pouvoir passer à travers.

Je ne peux pas simplement faire la grille 32 * 32 car la conception nécessite des parois minces (à 16px) et il y a quelques méchants plus petits qui ne prennent qu'un seul carré 16 * 16.

Comment implémenter cet environnement multi-résolution? Une étoile est-elle toujours l'outil approprié?

Answer 1

http://aigamedev.com/open/article/clearance-based-pathfinding/

Answer 2

Pour une solution relativement simple, je collerait au même algorithme A * que pour 16x16 objets de taille, mais avec une manière légèrement différente pour évaluer si un carré est accessible à pied ou non.

• Un objet de taille 16x16 peut marcher sur un carré si ce carré est praticable.
• Un objet de taille 32x32 peut marcher sur un carré si ce carré et ses voisins sont accessibles à pied.