Trouver des mouvements possibles pour une entité dans un jeu en mosaïque 2D

Je rencontre des problèmes avec un terme de recherche spécifique pour cela, mais comment trouver les mouvements possibles dans un jeu de stratégie au tour par tour 2D (par exemple FF: Tactics, Fire Emblem, Advance Wars).

Je ne pense pas tellement au terrain (ou même à la collision) à ce stade. Je me demande simplement quel algorithme je peux utiliser pour comprendre que l'entité X peut déplacer 5 tuiles et attaquer 2 tuiles plus loin que cela.

Je sais que je peux utiliser quelque chose comme Dijkstra pour trouver la distance entre deux points. Une implémentation possible est de commencer à l'emplacement des joueurs, puis de bifurquer à partir de là jusqu'à ce que la distance renvoyée par Dijkstra soit supérieure au nombre de coups.

Je me demandais simplement si quelqu'un pouvait m'orienter dans la bonne direction (c.-à-d. Nom des algorithmes, technique, articles, etc.).

Je pense qu'un Dijkstra délimité est précisément ce que vous voulez utiliser. La façon dont Dijkstra trouve la distance entre deux points est de tracer la distance à chaque nœud à partir d'un nœud d'origine, puis de «sélectionner» le chemin le plus court à partir de cette carte de distance. Vous voulez faire pratiquement la même chose, sauf que vous voulez que le graphe de nœuds de distance qu'il crée en tant que sortie, plutôt qu'un chemin vers un point particulier.

La seule modification que vous voudrez faire est de sauter le calcul de la distance des nœuds qui ont déjà dépassé votre plage de mouvement maximale. Ensuite, vous aurez un graphique des nœuds de tous les nœuds vers lesquels l'unité peut se déplacer, plus une bordure, alors découpez simplement les nœuds qui ont une distance supérieure à la tolérance de mouvement.

Alto.

En d'autres termes, à peu près ce que vous avez décrit dans votre question est ce que vous devez faire. Il a également l'avantage de pouvoir utiliser la sortie pour effectuer la recherche de chemin, sans avoir à effectuer d'autres calculs.

L'approche la plus simple (et probablement la plus naïve) à laquelle je puisse penser en ce moment:

• Commencez par votre personnage et marquez tous les champs environnants comme steps - 1.
• Itérer sur tous les champs nouvellement marqués et marquer une fois de plus leurs champs environnants comme steps - 1où stepsserait le numéro d'étape du champ actuel, sauf si le nouveau champ a un numéro déjà plus élevé.
• Répétez la dernière étape jusqu'à ce que vous manquiez d'étapes.

Je pense que ce que vous cherchez pourrait être Manhattan Distance . En supposant qu'il n'y ait pas d'obstacles, vous pouvez dire qu'un carré est accessible simplement si:

| toX-fromX | + | toY-fromY | <maxMoveDistance

Cet algorithme peut ne pas être la bonne direction à suivre si vous rencontrez des obstacles plus tard; une façon possible de l'adapter pourrait consister à faire projeter des ombres par des obstacles et à réévaluer à partir du point le plus proche.

EDIT (parce que j'ai un peu plus de temps libre maintenant):

Par «ombres», je veux dire quelque chose comme ceci, si 0 est un carré accessible, C est le caractère et X est un obstacle:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Puisque (5, 2) est un obstacle, vous commencez par supposer que vous ne pouvez rien faire avec x> = 5 ET y <= 2. Vous pouvez ensuite recalculer à partir d'un autre carré; si vous voulez aller à (5, 1), vous pouvez calculer la distance manhattan de (4, 1) et voir si cette distance + du personnage à (4, 1) est inférieure à la distance de mouvement du joueur.

Ceci est un exemple assez banal, mais si vous avez plusieurs obstacles et / ou une plage de mouvement un peu plus longue, il devrait être capable de gérer la complexité.

Que ce soit en fait mieux que le simple remplissage, que ce soit en termes de complexité de programmation ou d'efficacité d'exécution, je n'ai aucune idée. Cela semblait être un moyen plus intéressant de résoudre le problème.