|
 |
|
|
|
 
This Article Is Taken From The Game Programming MegaSite, A Definitive Resource For Game Developers!
|
In a real time environment avoiding other units can be a hard nut to crack. Generally considering dynamic modifications on the map can bog down a pathfinder. Important issues like when do we really want to recalculate a units path has to be answered. For example, what should we do when some earlier blocking terrain is blown away and this makes a possible path much shorter for a unit. A unit that has already evaluated a path before this modification and started moving will un-intelligently continue on its long path around the obstacle. Recalculating all moving units paths after a modification comes to mind, but in a realtime environment this will be extremely timeconsuming. Unfortunately there is no good solution to all the problems that come up. Still, small additions to the pathfinder can help a lot.
When is a unit an obstacle? Imagine some unit trying to find a path from A to B and has to avoid lots of other units. We could make some assumptions on what units really are obstacles. First we could drop all moving units as obstacles as the chance of them stopping exactly in the path is minimal. Units standing still should however be considered obstacles and avoided.
Still, some units that are moving will probably stop in the units path so that some quick pathfinding should be done when something new is in the units way. An easy way would be to try to find an immediately connecting position that will take the unit to the second next position in its path. The unit 1 below is trying to move along the "asterisked" line but unit 2 is blocking:
|
The above algorithm should be pretty easy to implement and will avoid a lot of recalculation.
When you are using a path defined by waypoints like the ones found in the direct line pathfinder you have an advantage when recalculating paths. If e.g. the unit couldn't find an immediately connecting tile because it was blocked by several units, it could try to just recalculate a new path to the next waypoint instead of the whole path. This will reduce the distance of the recalculation. You should however have some kind of timeout feature that if the pathfinder didn't reach the waypoint after some steps relative to the distance to the waypoint, you should continue the pathfinding a all the way to the units end. This will ensure that the unit is not using a lot of time finding a path to a waypoint when it maybe has a much better path available. You could however keep the old waypoints, and if any of these are reached in the new path you just keep old ones from there and the new path is found.
To avoid a lot of recalculation of paths when changes are done to the terrain (e.g. a wall is blown away) you could eliminate all those units moving away from the change. This is easily done by calculating the angle between the lines from the unit to its goal and from the unit to the change of terrain. You can then choose e.g. that for angles lower than 90 degrees that units path is totally recalculated.
To make units behave more intelligent you should often think of real world examples. An example is when a wall is blown away by friendly units, it is often to make some of its own units pass. This event could be notified to all friendly units (if they have some sort of communication that is) so that they will find a new path. Another example of such real world AI is to inform a friendly unit that it should move away if it blocks from another friendly unit. This is common sense and should be pretty easy to implement. Together with the immediately-connecting-tile scheme above, much more intelligent movement is generated. Also making a lot of pathfinder flags for each unit can limit the amount of recalculation. These flags can then represent concepts that had to be taken into consideration when the pathfinder was evaluating. E.g. the concept "a wall was obstructing" could be set for that particular unit and when a wall is blown away all those units with this flag set will be evaluated.
All these additions will make the unit behave a bit more intelligently but each of them will steal some more CPU time. It might be that one should rather concentrate on optimizing the pathfinder so that reevaluation isn't that costly. A combination will probably produce the best results.
