Qu'est-ce qu'un bon algorithme de recherche de chemin basé sur une grille en 2D?
Je suis en train d'écrire un jeu en 2D en Javascript en utilisant le HTML5 <canvas> élément. Ça se passe très bien, mais j'ai couru dans un problème.
Le level design pour mon niveau de jeu est une grille (donc coût de chemin de déplacer d'une cellule vers le nord/sud/est/ouest de la cellule est de 1) à divers obstacles occupant divers endroits dans le réseau, un peu comme un labyrinthe, mais avec beaucoup plus de marge de manœuvre. Chaque niveau est de l'ordre de 400 × 200 cellules.
Je suis en train de mettre en œuvre un ennemi qui va chercher le joueur n'importe où qu'ils soient, mais je vais avoir du mal à essayer de traduire dans l'une des différentes chemin de trouver des algorithmes pour l'adapter à ma situation. La plupart de ceux que j'ai rencontré (comme Un* et Dijkstra) semblent être les mieux adaptés à la 3D ou beaucoup plus compliqué 2D situations. Je me demandais si il est possible de simplifier considérablement ces algorithmes afin de mieux répondre à mes fins, ou si quelque chose comme la profondeur d'abord de recherche serait une alternative plus efficace, étant donné le niveau de la taille.
source d'informationauteur creXALBO
Vous devez vous connecter pour publier un commentaire.
A* est un très commun 2D algorithme de pathfinding. Il pourrait prendre un peu de temps pour envelopper votre tête autour de ce qui se passe si le pathfinding n'est pas familier, mais il n'est pas très complexe. Vous peut-être simplement en regardant quelqu'un d'autre exemple de code qui a été développé pour une application plus complexe que vous le souhaitez. Il y a un bon tutoriel pour comprendre l'algorithme ici.
Vérifier cela https://github.com/qiao/PathFinding.js Il a beaucoup de démos et de découverte de parcours algothms.
EasyStar.js est une jolie bibliothèque qui semble faire ce que vous voulez. Je n'ai pas utilisé moi-même, mais la documentation sur le projet github page semble assez bon, et c'est probablement ce que je choisirais dans votre position.