Continuous space pathfinding algorithm

[Ced666]

Hello !

I'm looking for a pathfinding algorithm that works in continuous space. What I mean by continuous space is that the positions can take any value and are not limited by 'tiles'. The A* pathfinding algorithm works only if the space is divided into squares (or hexagons, ...).

I'm struggling with this problem and I don't know what to do.
The conditions are:
- All the obstacles can be simplified to a rectangle on the map (to avoid too complex things). Rectangle is aligned with the axis
- The node that is moving is also represented by such a square and the complete square must be used for pathfinding (there can't be an overlap of two squares).
- Like always, it should be fast enough
- It should also detect the shortest path in every situation.

I think a way to go is to model the space into squares that are free (you can move everywhere in the square) and then, on basis of these squares, use the A* algorithm.
But I'm stuck at this modeling part. The only thing I have is the coordinates of all the obstacles rectangle. From there, how can I construct the "free squares" ?

Any help is really appreciated.

[Eternl Knight]

Well, A* is not strictly a "tile" based game pathfinder. It works just as well with finding shortest paths through a graph of nodes. This is how most "QuakeBots" work. The general idea is to create a series of points visible to one another spaced through-out the world. These are then connected based on visibility and/or accessiblity (for example, although you might be able to see across a ravine - it does not necessarily mean you can jump across it!) This tends to be done as a preprocessing step. Then the A* simply finds the closest nodes to the start & destination positions and calculates the shortest path through the node graph.

I am pretty sure that the IrrWizard application has an implmentation of this (though the method used is no "strictly" A*, it is close enough for purposes of describing how it works).

Amit's Game Programming page (clicky link) is a great place to start for path-finding in a game environment.

--EK

[Ced666]

No sorry, it works with nodes, that was what I meant. So, you still need to divide your space into nodes.
The purpose here is that it will be used in a RTS game. So, I don't know how I can make use of waypoints . Image you select a unit (start position) and you move it some where (end position).
I know how A* works but this will probably be used as the second step. My real problem is how I'm gonna prepare the 'nodes' for the algorithm, in order that every point on the map could be reached.

I was thinking of something that could help: dividing the space into (very) small squares. Then, for each square, check if it is partly occupied or not and mark it as traversable or not. Then, to reduce processing time for the algo, we then need to reduce the number of nodes (they will be really too many of them at this stage). For that, we can merge neighbouring free squares into larger rectangle (I don't know exactly how to do that as it sounds simple but it could be rather complicated). Then, once the optimization is finished, run the algorithm with the reduced set of nodes. Of course, inside a free-square, every point is accessible (as there is no obstacles inside).

The disadventage is that the grid needs to be populated each time a unit has moved (units are of course obstacles too). Fortunately, my game is turn-based and thus, only one unit will be moving at a time (so, I won't have situations where I need to have an adaptive pathfinding).
Another disadventage is that there can be some problems when traversing a node, if I always go to the node center (don't see how I can optimize the path through the different nodes).
Does that sound good ?