[Pathfinding] Beyond A*

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.

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..

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.

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.

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.