Add support for A* pathfinding algorithm

[parasyte]

http://en.wikipedia.org/wiki/A*_search_algorithm

Pathfinding is usually a desirable feature in games, especially for "smarter" AI. The algorithm implemented should be configurable to:

1. specify the heuristic function
2. specify the maximum number of steps taken to find a path
3. specify whether the algorithm is reentrant (i.e. the algorithm can be paused when it hits the maximum number of steps, and will pick up where it left off the next time it is called.)

This will provide melonJS with an algorithm that can be tailored to the type of game being made:

The default heuristic function will focus on finding the optimal path, and will be considerably slower than a heuristic function that prefers searching through fewer possible paths.

The maximum number of steps can be used in cases where there are a very large number of objects doing pathfinding, like in an RTS. The goal is keeping the AI from causing dropped frames.

And finally, the pathfinding function can be made reentrant so that previous attempts at the pathfinding can be continued in cases where an object must find a suitable path, no matter how long it takes.

Here are some ideas for an API:

• The function can be called me.Path.find(), where me.Path is a new namespace for pathfinding in melonJS.
• me.Path will be implemented in /src/math/path.js
• Accepts five arguments: me.Path.find(start, end, h, maxSteps, reentrant)
  • start: a me.Vector2d that indicates the start point.
  • end: a me.Vector2d that indicates the end point.
  • h: [Optional] heuristic function for determining the cost estimate.
  • maxSteps: [Optional] number indicating the maximum number of steps (1 step = 1 tile) the algorithm will try. Default is Infinity.
  • reentrant [Optional] pass <previous return value from me.Path.find()> to continue a previous search.
• Return value is an object which specifies the algorithm results:

{
    "path"  : [ ... ],
    "state" : ...
}

The values of the properties depends on the value of maxSteps: When the algorithm completes before maxSteps has been reached, the path property is an array of me.Vector2ds which gives the complete path found, and state === undefined.

In the case that maxSteps has been reached, path will be an incomplete array of me.Vector2ds for the path found so far, and state will be set to the internal state of the algorithm.

This return value can be passed back into the algorithm (e.g. the next time the object's update method is called) in the reentrant argument, where both path and state will be used to continue the search.

[parasyte]

Also look into Jump Point Search to get the most out of A*. JPS has a few limitations:

1. Diagonal paths are required
2. Weighted nodes need to be treated as "forced neighbors", according to the algorithm.

A "weighted node" is a piece of terrain that has a higher or lower acceleration or velocity cost. Quicksand is an example of terrain with a higher velocity cost, because objects will move slower when walking through it. Ice has lower acceleration and friction costs.

A* will work great for overhead maps (RPG, RTS, ...) but will not work so well on side-scrollers, where the cost of gravity must be figured into the algorithm.

[melonjs]

http://buildnewgames.com/astar/ :)

[ghost]

Hi,

I've created a plugin integrating Brian Grinstead's JS A* implementation. (see: https://github.com/bgrins/javascript-astar)

Repo is here: https://github.com/swmuron/melonjs-astar

Spaghetti code warning. I hacked this together one day while experimenting with Melon. I have a list of improvements in mind for it, but I'll save the essay for the mailing list.

Hope this helps.

[obiot]

Tagging this one as candidate for 0.9.9 as we might have an official plugin for it :)

[obiot]

do we close this one, now that there is existing plugin for it ?

I will also probably put a copy of swmuron (with a link to the original repo) to make sure we keep track of it :P

[obiot]

https://github.com/melonjs/plugins/commit/da7cd967530dff2e1c78fa8c6b4d65f75e1b1d3c

[rmarku]

Hi, I was using this plugin with melon 1.x, but now with the new collision system, it doesn't work. Do you know if are there some other solution?

[ldd]

You can always make your own plugin! I sort of made one, since I don't use the collision layer at all, but I have not talked about it since I was trying to wait for 2.1.x to be done (webGL is really great) For the time being, you can see a broken 'sneak' peak at https://github.com/ldd/melonjs-pathfinding (the pathing is done in another thread so performance is fairly good)

You can go from there, and include updates/changes in the collision system. (melonJS is fairly easy to extend)

[parasyte]

@ldd That's very cool :) Looks like the user just needs to partition the collision layer into a grid (size of their choosing) and send it to the worker with the setWalkableNodes message. I like it!

@rmarku To partition the collision layer into a grid, you should search the QuadTree using the grid cell boundaries as the lookup rectangle; Iterate over an imaginary grid with nested for-loops, setting the pos.x, pos.y, width and height properties of a rectangle to the boundary of each cell as you iterate. Pass that rectangle to me.collision.quadTree.retrieve() and it will return all shapes that intersect with that cell. You can then determine if any of the shapes are solid by inspecting its properties. Use that to build the node list for @ldd's plugin.

• If you are using collision shapes aligned to the tile grid, create your imaginary grid using the same size as the tiles.
• For arbitrary collision shapes, a smaller grid will provide better granularity at the cost of more CPU time to compute a path.

As another example of an algorithm that works well with the collision layer, @aaschmitz wrote a line-of-sight / ray-casting / occlusion plugin recently: https://github.com/aaschmitz/melonjs-improved-platformer/blob/3c65faaf35b29d41fae0d65e7c421dbe49563a53/js/entities/entities.js#L416-L440 Again, it's just a clever use of the collision detection (QuadTree) that we already have.