Pathfinding in Lua

Recommended Posts

Hi, I'm currently using an engine that's running off of Lua (designed by my professor). I was wondering how exactly I could do some 'basic' Pac-Man style pathfinding in Lua as I'm trying to make a Pac-Man clone for a game design class I'm currently in. Even if it's just pseudo code, any help would be appreciated. I'll try and post with more info later if any more is needed. - Cian

Share on other sites
Katie    2244

Well, Pac-man's path finding isn't actually as complex as it looks.

Every time pacman enters a square, he puts down a marker, and all previous markers are decremented by one down to zero. All other squares have a marker of zero.

The ghosts simply move into the neighbouring square with the highest marker, or pick a direction at random if none are marked. {The maze is designed so the ghosts don't get stuck}

They don't "pathfind" around the maze, they just follow the trail of pacman's drying footprints, each time looking for the wetter footprint.

When you eat a powerpill, they invert the algorithm and run away from Pac.

Hence you can implement this using the same array as you use for the map itself -- you have a value for WALL, one for DOT, one for POWER-PILL, one for PACMAN-10 (most recently here), PAC-MAN-9... down to EMPTY. This is possible because any square which has a pill on it MUST be considered empty because pac can never have been in it, etc. In fact, Pac's marking the square erases the dot as you eat it.. :-)

Marker algorithms like this can be used to do things like solve mazes as well; they're how you can store arbitrary "backtracking" markers. They're very simple to implement, and can be *very* effective.

Share on other sites
Katie    2244
Oh yeah; if it's a class project, you could have a mode which *displays* pac's footprints, fading out to black as they age. Then you can show the ghosts running along the path as they find it...

Share on other sites
ddn3    1610
Lua is a dynamic language which supports tables so you can easily create the playing field which looks similar to a 2d array in C like so.

local map={}local row, columns = 64,64for r=1,rows do  map[r]={}   for c=1, columns do      map[r][c]={}  endend

now you can fill out the map like so.

map[1][2]={cost=1}

fill our all the nodes which exist and then u can use the standard A* algorithm found in any text book or web site.

Good Luck!

-ddn