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

Signaler
Messages postés
4
Date d'inscription
lundi 26 août 2013
Statut
Membre
Dernière intervention
17 juin 2014
-
Messages postés
32944
Date d'inscription
mercredi 22 octobre 2003
Statut
Modérateur
Dernière intervention
12 juin 2021
-
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.

2 réponses

Messages postés
32944
Date d'inscription
mercredi 22 octobre 2003
Statut
Modérateur
Dernière intervention
12 juin 2021
351
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
Messages postés
32944
Date d'inscription
mercredi 22 octobre 2003
Statut
Modérateur
Dernière intervention
12 juin 2021
351