Discussion :

[TheBearTedd]

Bonjour à tous

Dans le cadre de mon projet d'informatique en Terminale, mon groupe et et moi développons un jeux : pacman en langage C.
Le problème etant que mes connaissances en C sont moindres et j'ai besoin de développer un un algorithme pour faire déplacer les fantomes simplement. J'aimerais donc avoir votre aide et avis sur la question.

Merci beaucoup !

[Bktero]

Il y a deux choses :

• Progresser en langage C : pour cela, il faut lire des cours et tutoriels pour apprendre la programmation C, faire des exercices, comprendre.
• écrire un algorithme pour les fantômes : pour cela, il faut prendre un papier un crayon et écrire en français (ou pseudo-code) le comportement souhaité.

Quand ces 2 étapes seront faites, tu pourras traduire ton algorithme en C. Il y a du travail. Malheureusement on ne pourra pas faire le premier point pour toi ; Google devrait t'aider pour le deuxième point, mais on peut te filer un coup de main. Quand tu arrives au point 3, alors cette discussion aura vraiment lieu d'être. Pour le moment, ta question est tellement vaste qu'il n'y a pas de réponses à part faire le travail à ta place (et celle de ton groupe).

Quand j'étais étudiant, un groupe avait fait un Pacman. De mémoire, il y avait 3 niveaux de difficulté donc 3 algorithmes pour le déplacement des fantômes :

1. Déplacement complètement aléatoire : à chaque tic, chaque fantôme allait aléatoire dans une direction de manière équiprobable.
2. Déplacement presque aléatoire : à chaque tic, chaque fantôme soit se rapproche du Pacman soit va dans une direction aléatoire.
3. Déplacement intelligent : à chaque tic, chaque fantôme se déplace vers le Pacman.

Tu peux déjà commencer par l’algorithme 1

[TheBearTedd]

Humm je vois merci de ta réponse.
J'ai par ailleurs suivie des cours et tutoriel complet pour apprendre le langage de programmation C mais j'avous être un peu perdu quand il s'agit de créer mon propre algo ...
Notre pacman par contre ne sera pas si "complexe", j'ai juste pour objectif de faire déplacer les fantomes sur des coordonnées données (de telle case à telle case). Je ne sais pas si je me suis bien fait comprendre

[Bktero]

Un algorithme, c'est (presque) indépendant du langage que tu utilises. C'est un raisonnement mathématique et logique. Tu peux l'écrire en français, comme tu pourras écrire une relation pour une suite en mathématiques. Par exemple :

• Pour chaque fantôme:
• --> tirer une direction aléatoire
• --> si la direction est possible (ie: pas de mur dans cette direction), déplacer le fantôme
• --> sinon, tirer une nouvelle direction

Après vient la traduction en C. Mais seulement après.

[TheBearTedd]

Ah d'accord ! Le problème c'est que j'ai l'algo sur papier mais c'est pour le reproduire en code que je ne sais pas comment faire. Si vous pourriez me guider se serait sympa s'il vous plait

[AdmChiMay]

Coucou !

Bon, donc tu nous montres ce que tu as écris, histoire que ça motive les troupes des "répondeurs potentiels" (je ne parle pas forcément de moi). Et tant qu'à faire, en ajoutant comment tu penses pouvoir l'écrire en C (disons, le premier jet).

[TheBearTedd]

D'accord !

Bon voila se que j'ai écrit très brièvement : le fantôme va a gauche -> S'il y a un mur -> Si pacman est en coordonné "y" -> y aller vers le haut, sinon aller vers le bas. De même pour les autres directions.
Je sais pas si c'est suffisant :/
En ce qui concerne le code "1er jet" je ne l'ai pas, tout est au lycée malheureusement et je n'ai pas Code::Blocks sur mon pc

[BufferBob]

salut,

c'est vrai que ça risque d'être probablement la partie la plus technique de ton jeu en l'occurrence

un algorithme très simple pourrait consister à "se rapprocher" de pacman en permanence, de manière assez simple, si x_pacman > x_fantome, alors x_fantome + 1 pour aller dans la direction de pacman en gros, en oubliant pas de vérifier effectivement s'il y a des obstacles
le problème de cette technique c'est que s'il y a un obstacle entre le fantôme et pacman, le fantôme peut rester bloqué jusqu'à ce que pacman se déplace ailleurs et que le fantôme puisse se rapprocher, un autre problème est que ça laisse peu de marge d'erreur au joueur, il a intérêt à ramasser très vite des pacgums sinon il va très vite se retrouver encerclé par tous les fantômes et il est mort

une méthode plus aboutie consistera à implémenter un algorithme comme A* ("A-star") qui permet de trouver un chemin, même quand il y a un obstacle, le principe est assez simple intellectuellement parlant; on test tous les chemins jusqu'à atteindre la destination (en gros), reste qu'à implémenter ça peut être vite compliqué si tu n'as pas l'habitude de programmer
qui plus est, on a toujours le problème de la horde de fantômes qui bloqueront pacman dans un coin un moment donné, inévitablement, en revanche les murs ne poseront plus de souci

on pourrait alors ensuite affiner un peu encore, en imaginant quelque chose du genre "si pacman est trop loin, on le laisse courrir, et on se deplace plus ou moins aléatoirement, sinon on enclenche la recherche de chemin avec A*"
ça permettrait donc d'éviter la nuée de fantômes en mode berserk, à ce stade le seul problème que j'envisage, c'est qu'en faisant du pur aléatoire on pourrait avoir un fantôme qui fait des mouvements erratiques gauche-droite-gauche-droite-droite-gauche-droite-gauche-haut-droite-gauche-etc., mais d'ici que tu en sois à ce stade trouver une façon de contourner ce problème mineur sera probablement devenu plus facile

ps: note que quand pacman mange un fantome, ces derniers retournent à leur point de départ, où qu'ils soient, là encore A* est un bon candidat pour les faire aller dans ce sens

[AdmChiMay]

Je pense qu'à environ deux semaines de rendre votre projet, vous entrez "un peu" dans le mode panique.
Il fallait commencer un peu (sérieusement) plus tôt…
Faire un algorithme, c'est :

• savoir dans sa tête ce qui doit se passer,
• pouvoir jouer manuellement ce qui doit se passer (avec crayon & papier, blocs de Lego à manipuler, etc),
• le formuler en clair, façon je cause comme d'habitude,
• le reformuler de façon plus structurée.

Dans votre cas, dessinez une grille de pacman sur papier, et prenez quelque chose pour figurer les pièces (le pacman, les fantômes). Vous allez déplacer les pièces à la main (et ne pas commencer à vous dire que c'est gnan-gnan). En déplaçant une pièce, formulez à voix haute ce qui se passe (quelle déplacement) et pourquoi (quelles raisons pour le faire et pas autre chose, et si c'est juste une histoire de choix alors les raisons du choix car le hasard n'existe pas ici).
Le premier jet peut ressembler à ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
on essaye de se déplacer vers le pacman
  - d'abord à l'horizontale si c'est possible
  - puis à la verticale (et encore, si c'est possible, on ne sait jamais, on peut être bloqué)

J'ai divisé en horizontal/vertical, mais tu peux de ton côté choisir d'emblée 4 cas : droite/gauche/haut/bas : à toi d'adapter.
Vous pouvez passer à une deuxième étape, car en informatique, on va d'abord vérifier si c'est possible avant de le faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
si pacman et fantôme n'ont pas le même x
  alors tenter de se déplacer selon axe des x
  sinon se pencher sur le déplacement en y

Le alors est à décomposer, et le sinon aussi : on avait un gros problème, maintenant on a deux sous-problèmes, plus petits, et indépendants. Pour le premier cas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
si x_fantome < x_pacman
  alors x_fantome = x_fantome + 1
  sinon x_fantome = x_fantome - 1

Et on relit ce qu'on vient d'écrire. Peut-il y avoir un problème ? Ben oui : peut-on aller en +1 ou en -1 ? la case est-elle libre ? Il faut faire un choix si ce n'est pas possible : est-ce qu'on ne fait rien (on reste sur place) ou bien est-ce qu'on tente l'autre sens ?
Vous allez donc avoir pas mal de si-alors-sinon. S'il y en a trop, à vous de voir s'il faut reformuler l'ordre des tests ou pas. Mais là, cela dépend de votre manière de voir les choses, pas de moi ou d'un autre.

Bref, pour un algorithme de déplacement "simple", il y a déjà à utiliser un peu le crayon. Essayez déjà de faire fonctionner une méthode simple, car je crains que vous lancer dans le A* à quelques jours de la fin vous n'êtes pas sorti de l'auberge (mais sait-on jamais ?). De toutes façons, regardez quand même comment le A* fonctionne, car on risque fort de vous demander "mais pourquoi n'avoir pas mis en œuvre le A* ?", et là il faudra savoir répondre un peu.

Sinon, à défaut de n'avoir pas d'algo à cette date, vous avez pu avancer le côté graphique ?

[BufferBob]

Je pense qu'à environ deux semaines de rendre votre projet, vous entrez "un peu" dans le mode panique.

ah effectivement vu sous cet angle...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
on essaye de se déplacer vers le pacman
(...)
si x_fantome < x_pacman
  alors x_fantome = x_fantome + 1
  sinon x_fantome = x_fantome - 1

(...) regardez quand même comment le A* fonctionne

bonnes idées

[Sve@r]

Bonjour

Avec du temps, l'algo de BufferBob est le meilleur. Trouver l'ensemble des chemins qui vont du fantome jusqu'à pacman et choisir le chemin le plus court. Mais cela nécessite de maitriser la récursivité.

Sinon il y a une solution plus rapide: demander aux fantomes de suivre la ligne de points. En effet, pacman est obligé de la suivre aussi s'il veut les manger. Donc fatalement à un moment donné, la rencontre se fera...

[LittleWhite]

Bonjour,

Sinon il y a une solution plus rapide: demander aux fantomes de suivre la ligne de points. En effet, pacman est obligé de la suivre aussi s'il veut les manger. Donc fatalement à un moment donné, la rencontre se fera...

Oui mais non. Car en fin de partie, il ne reste pas assez de points pour trouver un chemin.

[TheBearTedd]

Merci beaucoup a tous pour vos réponses et conseils !

Oui j'avoue mon projet est à rendre sous peu et c'est la panique de mon côté car je ne suis pas à l'aise avec la programmation pour l'instant ... Il ne reste néanmoins que ma partie (oui je sais je suis très en retard) x) Tout est fait sinon, je me suis de plus occupé du coté graphique en créant l'écran d'accueil, celui de fin (game over) et celui quand la partie est gagné. J'ai aussi fait le pacman dans les 4 directions possibles, fait les "points" qu'ils ramassent, la cerise qui apparaît aléatoirement sur la carte et qui nous fait simplement gagné des points supplémentaire et j'ai fait les 4 fantômes.

[Sve@r]

Je me souviens d'une fois, un type jouait à pacman. Et il connaissait tous les déplacements des fantomes par coeur. Il fonçait vers le fantome qui au dernier moment tournait à droite (alors qu'il lui suffisait d'avancer pour manger pacman). Bref il ne jouait plus, il suivait un schéma.
Ce qui me fait penser que peut-être les déplacements des fantomes sont programmés de façon figée et que tu peux faire de même. Ou bien nstaller des "waypoints" et que le fantôme doit alors aller d'un waypoint à un autre (un peu comme les drones qui survolent Paris). Et ensuite rajouter un cas particulier if (pacman proche) then aller ver lui...

[chrtophe]

Algorithme des fantômes de Pacman :

- Inky : s'enfuit dès que Pacman approche une pastille qui lui permet de manger les fantômes
- Clyde : Il se promène de façon aléatoire
- Pinky : est informé de la position de Pacman par les autres fantômes qui le voient
- Blinky : connait en permanence la position de Pacman et s'y dirige

Exception à la règle :Un fantôme voyant Pacman se dirige dans sa direction.
le fait de manger une super-pastille rend les fantômes fuyards, et ils deviennent les proies.

[TheBearTedd]

Oui je savais que chaque fantomes avaient un déplacement différent merci
Mais par simplicité nous avons préféré rendre le déplacement des fantomes moins complexe

[BufferBob]

- Inky : s'enfuit dès que Pacman approche une pastille qui lui permet de manger les fantômes
- Clyde : Il se promène de façon aléatoire
- Pinky : est informé de la position de Pacman par les autres fantômes qui le voient
- Blinky : connait en permanence la position de Pacman et s'y dirige

bien vu t'as trouvé ça où ?

[chrtophe]

Je ne sais plus, je ne peux donc citer ma source

[chrtophe]

J"ai retrouvé
http://poukie8.free.fr/ESIL/3%E8me%2...an_rapport.pdf

[theodorandaipieds]

Merci beaucoup a tous pour vos réponses et conseils !

Oui j'avoue mon projet est à rendre sous peu et c'est la panique de mon côté car je ne suis pas à l'aise avec la programmation pour l'instant ... Il ne reste néanmoins que ma partie (oui je sais je suis très en retard) x) Tout est fait sinon, je me suis de plus occupé du coté graphique en créant l'écran d'accueil, celui de fin (game over) et celui quand la partie est gagné. J'ai aussi fait le pacman dans les 4 directions possibles, fait les "points" qu'ils ramassent, la cerise qui apparaît aléatoirement sur la carte et qui nous fait simplement gagné des points supplémentaire et j'ai fait les 4 fantômes.

Ok j allais te suggérer de voir un algo de génération de nombres aléatoires, mais bon ce sera peut-être partie remise