9
\$\begingroup\$

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?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I think you mean "evasion" \$\endgroup\$
    – BigStuuu
    Sep 10, 2012 at 12:55
  • \$\begingroup\$ @BigStuuu, Yes, "evasion" \$\endgroup\$ Sep 10, 2012 at 15:01

1 Answer 1

12
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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.) \$\endgroup\$
    – DampeS8N
    Sep 10, 2012 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .