pacman game

I once used a matrix approach to solve the path problem :

Look at the points where the tunnels intersect.

The distance from point a to point b is the length of the tunnel segment that connects them if there is one.

Use the length of the direct connections to calculate the length of the shortest routes between the points which are not directly connected.

Find the point z you would first pass on the shortest route from point x to point y. Save this point in a matrix : nextPoint[x][y] = z;

( Is this an implementation of the A* algorithm ? I've read that's an algorithm used for pathfinding ... )

Every time a ghost reaches one of the points, he can look up the shortest route to the point where you are or to the two end points of the tunnel segment you are in. The advantage of this approach is that it looks at all existing paths and doesn't drop any for simplification.

Zyphrusa at 2007-7-9 18:47:05 >

ah, thanks. So my approach was not an implementation of A*. If there is a limited number of forking points for the path, my "list of optimal paths" will be faster. I think something like that was used in Dungeon Keeper, and modern RTS games precalculate possible paths along the line of "if units want to get from region A to region B, they have to pass through this canyon".

Zyphrusa at 2007-7-9 18:47:06 >

> I once used a matrix approach to solve the path

> problem :

> ...

quite interesting idea.

i was once studing methods how to creat good othello AI, and i came across a implementation where there was edgegame precalculated...

here may similar thing be done:

for certain playfield, you create twodimentional array, width wuould hold all possible places where creature can be, and heigth would hold all possible places you can go to.

now you'll runn a program that ests 'all possible routs' from A to B, and then remember the shortest, and just record int your matrix the first move.

i hope everyone gets what i mean by 'all possible routs'

but when calculating those best next moves, you could start from the short distances, for example start with squares next to each other,and then you can later, reuse values calculated before.

and idea i just had:

at the runtime, you could 'chek all routes' again by starting from point A inall directions, but do that only untill half way, and start with the same thing from location B, this way you'd stop searching when covered ares start overlaping

also there you may dedect dead-ends that don't lead you to desired square, then you may mark some moves as BAD moves, so when you'd need to deside on runtime where to go, but don't have time to wait for correct answer, then you could random齳 deside among these that aren't marked too bad.

VaskoLa at 2007-7-9 18:47:06 >