At the moment, I''m knocking up a basic game with some similarities to Pacman: tile-based map, no scrolling, 1 player, several enemies that kill the player upon contact. Due to the maps utilising some open spaces, there are 8 degrees of freedom corresponding to the compass points. Now, I think it''s just because I''ve not been getting enough sleep recently, but I''m having trouble coming up with a decent algorithm that will make an enemy chase the player effectively. Obviously something like A* or DFS would work, but that seems like overkill for this project. I just need something that heads more or less in the direction of the player, but won''t get trapped if there is an interposing wall. I''m also interested in variations on such an algorithm, or alternatives, so that the numerous opponents on the map won''t eventually all end up in the same place pursuing the same path. Links to examples of this would be appreciated, as would algorithms and pseudocode (actual code not necessary, unless you find it easier to express things that way).

Well, for part of your question about all the enemies ending up in the same place, I know that each of the original Pacman''s ghosts had different ''personalities.''

For example, one of the ghosts is aggressive and always tries to get to where the player is by the most direct route. Another ghost tries to avoid the player by moving generally away. One of the ghosts moves randomly and the last ghost ''guards'' the wraparound points on the sides of the screen. (Keep in mind, this is just my own version of the personalities. A couple of these are probably different from Pacman) Anyway, these different personalities will help keep your enemies from all clumping together and rushing the player at once.

There''s the "turn left" maze solution, which essentially says to turn left at every turn (at a dead-end this should result in an about-face). It fails if you have a "left loop", where a series of left turns take you through the same path over and over.

Selecting a path can be done as a pure vector function: where is the player? What''s the direction from me (evil opponent) to him (goody 2-shoes)? What paths are available in that general direction? Turn left, or to the leftmost one.

jaxson''s right about Pac; the ghosts did have different personalities, which you can use too. One enemy can go straight for the player (probably resulting in early demise - above algorithm works perfectly); another can try to sneak up behind the player (you''d need to find "probable" non-intersecting paths to a spot behind the player), and so on. Since this game is tile-based and overhead, there''s no point in a "hide in wait" algorithm.

Dead-ends are a question of checking if the next tile''s attributes say "passable" or "no-go".

So, am I to take it that nobody has an algorithm a little more detailed than "move towards the opponent"? Quick searches online show that most sites only deal with more complicated graph theory algorithms like A* etc. But I'm sure the original Pacman didn't use anything nearly so complex.

Edit: I found some limited information on how the ghosts work. In an interview with the original author, it was said that 1 pursues the player directly, one pursues a point in front of the player, one moves randomly without backing up on itself, and one evades you until you get too close, at which point it pursues you. However, the exact details of the pursuit algorithm (which I assume can simply be reversed for evasion) still elude me. Through looking at other people's Pacman clones, it seems like a lot of people have simply opted for random movement, ie. "when we hit an intersection, pick a random valid direction".

Edited by - Kylotan on July 9, 2001 1:54:11 AM

Well, you could come up with a complex algorithm of your own based on personality (statistical distribution of tendency to respond so), but it seems like overkill for such a simple game (no offence). I used one such alogorithm in open-court pathfinding and teamwork in a basketball AI demo (which I''d have to re-derive and re-code to show you).

Avoiding getting trapped by dead-ends is a question of the tile attributes. If the opponent wishes to move onto a tile, it should query the tile for whether it is passable (or whether it is slippery, rough, sticky, etc). If the tile isn''t passable, the opponent should go back and mark that path as a dead-end. It could even inform the other opponents of the dead-end so they don''t waste time exploring it - limiting the player''s options. Of course, if the player attempted to hide down a dea-end path, the opponents should gang up at the entrance and charge him!

This can be achieved by numbering the tiles and maintaining a "knowledge base" - a linear array - in which the properties of each tile are mapped. This makes the opponents seem like they''re learning the layout over time, which is cool.

Better now?