Le contexte
Les jeux d'aventure graphique de type pointer-cliquer de Old Lucas Arts (ère ScummVM) utilisaient la recherche de chemin précalculée. Voici un aperçu approximatif de la technique.
Étape 1
Le sol de chaque pièce était divisé en ce qu'ils appelaient des «boîtes de promenade», qui étaient à peu près équivalentes à des nœuds dans un maillage de navigation, mais limitées à des formes trapézoïdales. Par exemple:
______ _____ _________ _____
\ A | B | C | D \
\_____| | |_______\
|_____| |
|_________|
Étape 2
Un algorithme hors ligne (par exemple Dijkstra ou A *) calculerait le chemin le plus court entre chaque paire de nœuds et stockerait la première étape du chemin dans une matrice 2D, indexée dans chaque dimension par le nœud de début et de fin utilisé. Par exemple, en utilisant les boîtes de promenade ci-dessus:
___ ___ ___ ___
| A | B | C | D | <- Start Node
___|___|___|___|___|
| A | A | A | B | C | ---
|___|___|___|___|___| |
| B | B | B | B | C | |
|___|___|___|___|___| |-- Next node in shortest path
| C | B | C | C | C | | from Start to End
|___|___|___|___|___| |
| D | B | C | D | D | ---
|___|___|___|___|___|
^
|
End Node
Comme vous pouvez le deviner, les besoins en mémoire augmentent rapidement à mesure que le nombre de nœuds augmente (N ^ 2). Puisqu'un short serait généralement assez grand pour stocker chaque entrée dans la matrice, avec une carte complexe de 300 nœuds qui entraînerait le stockage d'un extra:
300^2 * sizeof(short) = 176 kilobytesÉtape 3
D'un autre côté, le calcul du chemin le plus court entre deux nœuds était extrêmement rapide et trivial, juste une série de recherches dans la matrice. Quelque chose comme:
// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
Current = LookUp[Current, End]
Path.Add(Current)
ENDWHILE
L'application de cet algorithme simple pour trouver le chemin le plus court de C à A renvoie:
1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit
Question
Je soupçonne qu'avec le matériel puissant d'aujourd'hui, couplé aux besoins en mémoire de faire cela pour chaque niveau, tous les avantages de cette technique ont été surpondérés en exécutant simplement un A * au moment de l'exécution.
J'ai également entendu dire que de nos jours, les recherches de mémoire peuvent même être plus lentes que le calcul général, c'est pourquoi la création de tables de recherche sinus et cosinus n'est plus aussi populaire.
Mais je dois admettre que je ne suis pas encore trop bien informé sur ces questions d'efficacité matérielle de bas niveau, donc je profite de cette occasion pour demander l'avis de ceux qui connaissent mieux le sujet.
Sur mon moteur, j'avais également besoin de pouvoir ajouter et supprimer dynamiquement des nœuds au graphique au moment de l'exécution ( voir ceci ), donc l'itinéraire précalculé n'a fait que compliquer les choses, alors je l'ai mis au rebut (sans oublier que ma solution d'exécution A * fonctionnait déjà parfaitement ). Pourtant, je me demandais ...
En fin de compte, cette technique est-elle toujours pertinente de nos jours dans n'importe quel scénario?
la source
Réponses:
Je ne vois aucun avantage à utiliser une telle technique.
Je n'ai pas la flexibilité d'un graphique (vous pouvez avoir différents niveaux de détail, ils ne doivent pas nécessairement avoir de forme spécifique, etc.). De plus, tout utilisateur de votre moteur saura ce qu'est un graphique et comment l'utiliser. Donc, s'ils veulent ajouter des fonctionnalités supplémentaires, ils devront apprendre à implémenter leur extension en utilisant une situation complètement nouvelle pour eux.
Comme vous l'avez mentionné, il semble que cela évoluerait horriblement. Il est également intéressant de noter que si un graphique correspond à la trésorerie et que vous exécutez toutes les conclusions de votre chemin dos à dos, cela réduit vraiment le temps d'E / S. Il semble que votre implémentation deviendrait bientôt trop volumineuse pour tenir dans n'importe quel cache.
À moins que vous ne puissiez adapter tout votre programme et sa mémoire nécessaire dans le cache, vous allez mettre le goulot d'étranglement en tirant les choses dans et hors de la mémoire avant de mettre le processeur en bouteille.
Sachez également que de nombreux jeux ont des boucles distinctes pour mettre à jour l'IA. Je pense que la façon dont mon projet est mis en place est qu'il y a une boucle de mise à jour pour l'entrée utilisateur à 60 Hz, l'IA n'est que de 20 Hz et les jeux s'approchent le plus rapidement possible.
De plus, j'ai fait de la programmation GBA juste pour le plaisir et rien du tout n'est transféré à l'aide d'un appareil moderne. Pour la GBA, tout consistait à minimiser la charge de travail du processeur (car c'était pathétique). Vous devez également réaliser que la plupart des langages de haut niveau C # et Java (pas tellement C ++ ou C) font des tonnes d'optimisations pour vous. Quant à l'optimisation de votre code, il n'y a pas grand-chose d'autre à faire que d'accéder à la mémoire aussi peu que possible et lorsque vous exécutez autant de calculs que possible avant d'apporter une nouvelle mémoire qui la fera sortir du cache et vous assurera que vous êtes ne faire les choses qu'une seule fois.
Edit: Aussi pour répondre à votre titre oui c'est le cas. Le précalcul des chemins fréquemment utilisés est une excellente idée et peut être fait avec A * n'importe où en dehors de votre boucle de jeu. Par exemple, de votre base vers une ressource dans un RTS afin que les regroupements n'aient pas à recalculer chaque fois qu'ils veulent partir ou revenir.
la source