Sign in to follow this  
resle

[Pathfinding] Beyond A*

Recommended Posts

Hi, I am currently using a multithreaded implementation of A* in my engine. It's working fine, but it begins to show its age. As you know A* is "discrete", as it needs a block/pass boolean map to work. I'd like to know what would you suggest to move beyond this. If there's some well documented pathfinding algorithm which works in a generic 3d space and takes into account the size of the pathfinding entity. Thanks a.

Share this post


Link to post
Share on other sites
A* is indeed discrete, but it only requires a weighted graph with a heuristic function. These can be extracted fairly easily from a continuous 3D world with an entity that has a fixed size, so A* still applies.

Either way, you might find this interesting.

Share this post


Link to post
Share on other sites
Yes, you're right. I was thinking of modifying my A* library like this:

Currently for every onscreen object, I "project" it's base on the A* boolean map, by literally drawing "polygons of boolean values". This gives me a certain precision, depending on how thick the grid is.

Instead of this I could remove the boolean map concept, and just create a dynamic list of (X,Y,Passability) elements which is built depending on the onscreen objects. Of course every single simple access to a [x,y] array becomes a lookup into a list that may quickly become huge..

Share this post


Link to post
Share on other sites
Quote:
Original post by resle
Yes, you're right. I was thinking of modifying my A* library like this:

Currently for every onscreen object, I "project" it's base on the A* boolean map, by literally drawing "polygons of boolean values". This gives me a certain precision, depending on how thick the grid is.
Yep, that's the problem. Don't. Use. A. Grid. Depending on what your polygon map looks like, it's quite possible that Voronoi regions and/or a visibility graph would be a heapload faster than a grid-based approach

Quote:
Instead of this I could remove the boolean map concept, and just create a dynamic list of (X,Y,Passability) elements which is built depending on the onscreen objects. Of course every single simple access to a [x,y] array becomes a lookup into a list that may quickly become huge..
All you need is a graph structure where each vantage point links to all the vantage point it "sees" (of course, obstacles are assumed to obstruct visibility). This keeps the same algorithmic performance, but improves overall performance by reducing the graph size.

Share this post


Link to post
Share on other sites
Quote:
Original post by resle
Well actually I don't think there can be something faster than a grid based approach. The point is that it has some major limits, plus a heavy memory usage.


A visibility graph could be built from a grid (you'd just coalese adjacent non-blocking cells into a single node). The advantage is precisely that the memory usage is much decreased and the node count significantly lowered. Less nodes = smaller search space = faster searches.

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