Créer et mémoriser une liste de chemins "les plus courts"Résolu

Question

Bonjour !

Pour l'un de mes projets de fin d'année notre groupe se doit de coder Pacman en Java. Nous avons bien avancé et sommes capables de coder des fantômes et pacman automatiques qui se suivent ou se fuient dès qu'ils voient un ennemi.

Nous souhaiterions maintenant créer des IA plus intelligentes. Les fantômes (ou pacman) seraient avertis quand l'un de leurs congénères voit un ennemi. Les pacman s'éloigneraient de cette position, et les fantômes s'en rapprocheraient (sauf quand les fantômes sont vulnérables, c'est alors l'exacte inverse).

Toutefois, cela semble extrêmement coûteux. Soit, à chaque tour de jeu, les personnages testent tous les chemins qui leur sont offerts et déterminent lequel est le moins long... Soit, une seule fois, en début de partie, nous créons un tableau dont les colonnes et les lignes sont des numéros de case, et nous le remplissons avec la distance qui sépare deux cases.

Nous supposons que la seconde solution est, de loin, plus efficace, mais nous hésitons à la mettre en place. Avez-vous des idées, des suggestions, des solutions ?

Merci d'avance !

PS : actuellement, nous utilisons une solution très simple mais qui risque de faire faire beaucoup de détours à nos personnages : si l'ennemi qu'ils ont détecté est en haut à droite, ils prennent un chemin qui les mène vers le haut ou vers la droite s'ils chassent, l'inverse s'ils fuient.

jordane45 · Answer

Bonjour,

Il faut coder un petit algo qui calcule la distance la plus courte pour accéder à la case voulue..
Un truc se basant sur ça devrait être pas trop mal je pense :
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

ou encore mieux : (c'est en C#.... mais il est possible, une fois qu'on a compris le mécanisme...de le re coder en JAVA )
http://codes-sources.commentcamarche.net/source/41235-algorithme-de-pathfinding-a-star-a

jordane45 · Answer

Tu peux aussi regarder ces liens :
http://theory.stanford.edu/~amitp/GameProgramming/

http://fr.openclassrooms.com/informatique/cours/le-pathfinding-avec-dijkstra

.

Créer et mémoriser une liste de chemins "les plus courts"

2 réponses

Votre réponse

Discussions similaires