Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Evasion, the process of evading, is the opposite of chasing. Instead of trying to decrease the distance to the target we try to maximize it.

It takes much time while evading multiple objects simultaneously. I use BFS here. To make it faster what algorithms should I use?

share|improve this question
2  
I think you mean "evasion" –  BigStuuu Sep 10 '12 at 12:55
    
@BigStuuu, Yes, "evasion" –  Mahbubur R Aaman Sep 10 '12 at 15:01
add comment

1 Answer

up vote 10 down vote accepted

I suggest you use Steering Behaviors to simulate these types of behaviour. See this page for an example of evasive behaviour implemented in this way.

The basic idea is you only consider simple properties like the position and velocity vectors of your prey and predators to compute the desired change in these properties in linear time. This results in responsive yet realistic behaviour.

However, this comes at the cost of not taking other factors in consideration, like more high-level goals (the position of power-ups for example) or the position of static obstacles, as you would in pathfinding. These can be taken into account by combining the Steering Behaviors approach with, for example, potential fields (see Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)) or pathfinding (e.g. Corridor Map Method). In the case of the latter you want to decrease the update frequency (and trust the Steering Behaviors to compensate for any errors that might occur because of this) or do partial replanning, possibly combined with a more hierarchical approach (e.g. Near-Optimal Hierarchical Pathfinding (HPA*).

If you want a more specific answer, improve your question with more details about your problem. For example, consider describing what your game is about and the number of NPCs we're talking about.

share|improve this answer
    
You can also handle competing goal progression with fuzzy logic. So if the prey is fleeing the predator, it may also move towards a cave (or power up or whatever.) This can produce interesting situations where the predator stands between the cave and the prey and the prey hesitates fleeing out-and-out and as the predator goes after a different prey it moves in a wide berth around the predator to reach the cave. All with limited additional cost. (sub cave for something mobile, like a medic on a battle field, to see why Potential Fields aren't a good solution here.) –  DampeS8N Sep 10 '12 at 17:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.