Matrix based game: path finding

Hi,

I'm writing a simple PacMan clone, in which the monsters form some kind of neural network. When a monster spots PacMan, it sends PacMan's coordinates to the other monsters, which then move to that location. When there is no target set, the monsters alway return to their home base, where the current location of PacMan is alway available.

Anyway, I want to let the monsters move the shortest path from their current location to the target location. Suppose I have the following simple map (matrix bases):

1,1,1,1,1,1,1,1,1,1

1,0,0,0,0,0,0,0,0,1

1,0,1,1,1,0,1,1,B,1

1,0,1,0,0,0,0,1,*,1

1,0,1,1,1,1,*,*,*,1

1,*,*,*,1,0,*,1,0,1

1,A,1,*,*,*,*,1,0,1

1,0,1,1,0,1,1,1,0,1

1,0,0,0,0,0,0,0,0,1

1,1,1,1,1,1,1,1,1,1

The path (drawn by *) is the shortest path from A to B. Which algorithm should be used to solve this problem? How should it be implemented?

Thanks,

Jeroen

[962 byte] By [j_oosterlaar] at [2007-9-27 21:43:32]