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