WIP: Panda Pathfinding

[Wolfsbane]

Hiya guys and girls,

Overview

One of the more useful features to have in a game engine is path finding. Think games from Pac-man to Age of Empires to Tower Defenses. have some kind of rudimentary path finding. And these days with game tablets and phones, players want to simply tap some place on the screen, and watch their player scurry over there.

So I thought I'd take a shot at creating a template/example on how you'd implement it. I'm not finding much time to work on it, so I thought I'd post what I had as a WIP:

API

So far: We have

Quote

PathGrid

 init: function(left, top, hcells, vcells, cellwidth, cellheight, diagonals, debug) 

Create a grid at position left/top, with hcells number of cells horizontally, and vcells number vertically. Set diagonals to true if you want to be able to move across grids diagonally, and set debug to true to see the grid in debug mode.

addCollisionGroup: function(world, groupNum) 

Add a CollisionGroup to the grid. When this is called, the grid will check to see if there are any Panda Physics.Bodies that are inside our path grid. If they are, all the grid cells that overlap with the Body will be marked as blocked.

 search: function(start, end) 

This is an A* algorithm based on the code here. The parameters are a starting Cell square and an ending cell square, and it will return a list of Cell objects to form the path.

heuristic: function(pos0, pos1) 

This one is interesting. This helps determine how accurate your path is. Check this link for further reading. 

For now, you can play with these two values:

this.D = 0.1;
this.G = 10;

I.e. if you set them both to 1, you'll see(from debug mode) that it'll find a path quickest, but the path is not the most optimal. 

Example screenshots: Debug mode and no debug mode.

 

 

So: All you have to do is

1. Create a grid over a playing area.
2. Add a collision group of objects to be avoided. and
3. return the path. Done!

Links and resources

I'm basing the design on the old GM mp_grid movement API (Docs). It's a really simple, straightforward pathing implementation, that's pretty flexible for most games.

The A* Algorithm is based on this page by Brian Grinstead. Code is just tweaked a bit to suit Panda. Code isn't optimized, and probably well get changed as per progress.

I think EasyStar.js is probably the de facto way to do pathing in html5 games. The smart dev would just take it and adapt it to Panda. (But I never claimed to be smart, and where's the fun in just using someone else's code)

Attachment

pathfinding_02.zip

[enpu]

Great work again @Wolfsbane!