La recherche de chemin précalculée est-elle toujours pertinente?

12

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?

David Gouveia
la source
2
Je pense que c'est toujours pertinent si vous avez un budget CPU serré. Mais une fois que vous voulez des chemins dynamiques, ce n'est plus utile. Btw J'ai regardé d'où vous tiriez votre algorithme A * et vous pouvez l'optimiser encore plus en utilisant un minheap et quelques autres astuces. J'ai fait quelques itérations pour améliorer A * en C # que vous pouvez voir ici: roy-t.nl/index.php/2011/09/24/… pourrait être utile.
Roy T.
1
Merci, je l'ai mis en signet et je l'examinerai lorsque je commencerai à optimiser mon application. J'ai pratiquement utilisé la solution d'Eric Lippert avec quelques modifications mineures car elle était si propre et facile à suivre ... Et pour tous mes cas de test, elle a fonctionné "instantanément", donc je n'ai même pas pris la peine de l'optimiser.
David Gouveia
1
BTW si vous décidez de poursuivre le précalcul, vous voudrez peut-être regarder l'algorithme Floyd-Warshall . Il construit la matrice «étape suivante» plus efficacement que plusieurs fois en utilisant Dijkstra / A *.
2011
@amitp Merci pour le conseil, il est toujours bon de connaître ces alternatives! Bien que, dans la plupart des cas, le précalcul se fasse hors ligne, il n'y aurait pas grand-chose à gagner à le rendre plus efficace. Sauf si vous êtes vraiment impatient. :-)
David Gouveia
D'accord, bien que Floyd-Warshall soit également beaucoup plus simple à implémenter que l'algorithme de Dijkstra, donc si vous n'avez pas déjà implémenté Dijkstra, ça vaut le coup d'oeil :)
amitp

Réponses:

3

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?

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.

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.

À 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.

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

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.

ClassicThunder
la source
À propos de votre montage, je ne parlais pas vraiment de précalcul des chemins fréquemment utilisés, mais strictement de la technique décrite pour le précalcul de chaque chemin possible . Je suis également un peu confus quant à la façon dont la plupart de vos réponses étaient contre l'utilisation de la recherche de chemin précalculée, mais à la fin, vous avez dit que ce serait une excellente idée. Alors, serait-il utile sur un environnement restreint CPU tel que le GBA?
David Gouveia
1
Mon mauvais J'essayais de souligner que la réponse à votre titre pris hors contexte est oui. Bien que la réponse relative à l'algorithme spécifique décrit dans votre question soit non. Bref, le précalcul de tous les chemins possibles est une mauvaise idée, mais le précalcul de quelques chemins très fréquemment utilisés peut être une bonne idée.
ClassicThunder
2
@ClassicThunder: Cette technique de pré-calcul de tous les chemins à partir de quelques points de repère est souvent appelée ALT : étoile A avec repères et inégalité triangulaire
Pieter Geerkens