qiao
Clearance-based pathfinding
Hi!
First of all, this is a very nice library!
I am trying to make a small RTS-like game, with differently sized units. (Like a small soldier, medium sized car, big tank). Is it possible to take entities of different sizes into account? So the lib returns a path based on clearance?
You could always use multiple grids of different sizes. Alternately you could rebuild one of the algorithms to enforce a clearance value. Shouldn't be too difficult...
Ok, I thought some more about this. Here's one way to do it:
Modify your desired pathfinding algorithm to take a unit size. To make it easy assume all units are multiples of the grid size. When evaluating the "cost" of a particular cell/node check all surrounding nodes (within a node distance of unitSize -1). If there is a wall within that check then reject the current node (treat it as a wall). You'd have to be careful not to actually update the grid to treat the node as a wall.
That should work. Might have to see what it does about corners and edge cases but as long as your node size is << your unit size then you should be fine. Let me know if you make any progress.
Alternately, you could make several passes over the static map, one pass for each unit size, and precompute this unit-aware wall map. Then you would store multiple "isWall" values, one for each unit size, in the map itself. This would make online/realtime pathfinding as fast as normal.
Alternately #2 you could precompute a closest wall map with each node containing a value for the # of spaces between that node and the closest node. You save this value to the node itself. Then modify the "isWall" check to look at these values. Walls have a value of 0. Nodes right next to walls are a 1. Nodes next to those nodes are a 2 and so on. If you have a unit that is a value of 2 it can only enter nodes with a value >= 2.