Sign in to follow this  
fryedrycestyle

Pathfinding in Lua

Recommended Posts

fryedrycestyle    100
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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,64

for r=1,rows do
map[r]={}
for c=1, columns do
map[r][c]={}
end
end




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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this