Navigation sur les maillages de navigation (en polygones)

Question

Je travaille sur un jeu d'aventure Point and Click en JavaScript et j'ai besoin d'aide pour l'ensemble du mouvement. D'après ce que j'ai compris à propos du sujet, il semble y avoir deux sujets principaux: les maillages de navigation et l'algorithme A * Pathfinding. Cependant, pour la vie de moi, je ne pouvais pas trouver une mise en œuvre JS de ceux combinés.

Toutes les implémentations A * que j'ai trouvées sont basées sur une grille. Ce que je cherche, fondamentalement, est un moyen de naviguer à l'intérieur d'un grand polygone.

J'espère que j'ai fait un peu de sens, je ne suis pas sûr de l'avoir compris complètement moi-même.

Answer 1

Un * fonctionne sur une grille. Vraiment un nœud-chemin.

S'il n'y a qu'un seul noeud, alors A * ne va pas beaucoup aider, car il n'y a qu'un seul noeud. Vous devrez soit décomposer votre grand polygone en plus petits polygones, pour un déplacement de nœud correct, ou simplement faire quelque chose de simple comme déplacer votre personnage jusqu'à ce que ses pieds se rencontrent là où vous avez cliqué (et garder le polygone vraiment simple carré, sans rien sur le chemin). Fondamentalement, si vous voulez faire la recherche de chemin autour des objets, alors vous aurez besoin de casser votre chemin dans les noeuds, en quelque sorte. Que ce soit fait en subdivisant votre zone en carrés plus petits, ou en faisant quelque chose comme lancer des rayons vers votre cible, et créer de nouveaux rayons dans différentes directions pendant les collisions (fixant récursivement le chemin que vous allez - ai-je mentionné que cette est une mauvaise idée?) ...