Hello,
I am finding it difficult to obtain information on how the ghosts in the pacman game are able to find their way through the maze towards pacman. The method I used before caused the ghosts to all gather up against a wall for example whereas in the actual game the ghosts move round a wall.
Does anyone have any information or links to information on this subject.

Thanks
Spcman

I assume that what your doing is checking the player's position
relative to the ghost (for each ghost) and then moving towards it,
and then getting stuck against walls. You need to add some primitive AI,
so that if the ghost hits a wall, it goes in a different direction,
until it can go in the direction it wants.

  # #
  # ###
  #   G
### ###
    #
### #
  # #

G is the ghost, and it "wants" to go left, so it will head left and get
stuck against the wall

  # #
  # ###
  #G  
### ###
    #
### #
  # #

Then the AI kicks in. It chooses which direction to go in. This could
either be randomly, or, slightly more intelligent, depending again on
the position of the player, as they are not likely to be directly to
the left. However you choose, say it decides to go down:

  # #
  # ###
  #   
###G###
    #
### #
  # #

So it does. It still remembers that it wants to go left, but it can't,
so it goes down again:

  # #
  # ###
  #   
### ###
   G#
### #
  # #

Now it CAN go left, so it does, and continues on its way

  # #
  # ###
  #   
### ###
G   #
### #
  # #

a smarter way to do it is to build a graph, and to write the code so it finds the shortest way from node A to node B. or if you don't want to use a graph, you can try the wall-bouncing method explained earlyer, but you should make the code able to memorise the location already tryed and proven blocked, so it won't need to go all over again, and so, it will build step by step the map of the maze. if i come to think of it, you will still need to use graphs after memorising the map. graphs, that is the idea. learn graphs.

Hello rufio
Thanks for the advice concerning ghost-pacman maze navigation.
I was wondering what you meant by 'using a graph'
is the graph a table in memory or something to do with the screen?

thanks
Ed

: Hello rufio
: Thanks for the advice concerning ghost-pacman maze navigation.
: I was wondering what you meant by 'using a graph'
: is the graph a table in memory or something to do with the screen?
:
: thanks
: Ed
:
well, a graph is actually a bunch of points which are related to each other by roads. let,s say you have points a,b,c,d. from a you can go to b and c directly, but you can,t go to d, and from d you can go to c only. got the picture? so you can go from a to d travelling by c, and from b you can go to d travelling by a, b, c. the theory of graphs calculates the shortest way to go from one point to another. your maze is a bunch of points connected to each other. the points which are on different sides of a wall are not directly connected to each other, by you can get from one to another by passing through the other points. the problem for you is to write an algorithm which will calculate the shortest way from one point to another, considering that the roads in the maze are consecutive points related to each other and the walls are "non-relations", which means that you cannot go from one point ot another by passing through a wall. take a math book and search for graphs, and you will find some algorithms also for calculating the shortest way through a graph. hope that helped. don't hesitate to ask.

A graph is a mathematical structure. Its based in the SET THEORY.
A graph is defined as nodes and paths (directed or undirected).
This structure is often used for the representation of mazes, air traffic systems, network maps, etc.

There are many ways of actually implementing a graph as a Data Structure or Abstract Data Type. The approach you take will affect the final implementation of the algorithms for shortest-path calculation too. I would advice you to read a good book with information about Data Structures and algorithm analysis. Because if you want to be a good game developer you should use good software development techniques and not single-minded brute-force algorithms for the AI of your computer characters.

One book that might be a very good introduction is Data Structures and Algorithm Analysis in C++ (2nd Edition) by Mark Allen Weiss.
I used that as a textbook a couple of years ago.

Going back to your actual necessity, I'd say that you should go either for the linked-list or adjacency-matrix implementations for the graph.
And then use the DIJKSTRA algorithm for the calculation of the shortest-path from your "pac-man" to your "ghost".

You'll probably find a lot of source code already written that you can use. But it will be of great help for you if you actually know the theory behind these algorithms.

I hope this message is helpful,
Good luck.
G.L.

This message was edited by Nerd at 2003-1-31 4:45:41

---

Legend says that in original pacman game ghosts had different AIs. For example one turned always left, one always right then one randomly and the last one using some sort of "guided movement". Those were only examples.
But what I'm trying to say is that an easy way to do a pacman ghost movement is giving ghosts easy instructions, maybe always same on based on random numbers. So if the ghosts would choose their way randomly the player would eventually run on them. And if not then you could always add more ghosts: it's a hell to avoid 20 ghosts on a small map ;)

This was only my opinion about the easy way to do it. Other ways are probably much better but this is at least easy.

To know where the ghosts can 'walk' you could set up an array of boolean. true if there is a way, false if not. When your ghost walks against a wall you could just change the direction by random until the way is free again.