8
\$\begingroup\$

Currently I'm developing a Diablo like game for mobile platform(iphone5+).

A simple A* search will find the path, but collision avoidance still needs to be taken into consideration.

There will be about 50 monsters active at the same time, so performance is very important.

I found some methods that might work.

  1. NavMesh + RVO

    The recast/detour library works well on the pathfinding part, but its crowd simulation quickly reach the limit(more than 5ms for 30 agents).

    Another library RVO2 seems fine(less than 2ms for 50 agents), but the library has some license issues.

  2. Flow Fields + Physics Engine

    Many RTS games use this method, but it seems that a physics engine is required to resolve collisions. If many agents don't share a common goal, this method might cost more than traditional A* pathfinding.

  3. Steering Behaviors + Physics Engine

    Steering Behaviors includes many concepts, I think simple avoidance behavior might work(just turn left/right if there is something in front) , but the method still requires a physics engine to work together.

I'm still not sure which one to use, maybe there exists other pathfinding and collision avoidance methods.

P.S. Halo:Spartan Strike uses Havok AI(based on RVO?), but I didn't see many enemies in that game, so I wonder whether the first method(NavMesh + RVO) will works well on mobile platform.

\$\endgroup\$
2
  • \$\begingroup\$ Your GPU has more than 50 processing units, so running A-star on the GPU for each monster should run juss as fast as on a regular CPU for ne agent. \$\endgroup\$ Commented Jul 16, 2015 at 6:20
  • \$\begingroup\$ @PieterGeerkens The pathfinding part works fine now on mobile(less than 0.1ms per request), but the collision avoidance part does not. Also we have a lot of render tasks, so I guess the GPU won't have spare time for collision avoidance. \$\endgroup\$ Commented Jul 16, 2015 at 6:35

2 Answers 2

Reset to default
4
+100
\$\begingroup\$

This is a pretty interesting question, and i'm going to try to contribute with what I can.

First, I think you have to clearly define the boundaries for the game you are trying to create, and define those questions (some may already been answered).

  • How far the is the monster aggro ?
  • How many monsters at the same time is your target?
  • How is your terrain organized? Is it tiled?
  • How much collision avoidance do you want?

To quote an answer from here on how pathfinding is done in starcraft 2:

Starcraft II uses a constrained Delaunay triangulation of the map terrain and buildings to produce a navmesh; A* with a funnel filter is used to path along this mesh, taking into account unit radii; then local steering and collision avoidance layers are added on top of that, including a cooperative "push idle units out of the way" feature where it is possible to displace a unit instead of pathing around it in certain cases. Additionally, units moving in parallel are ignored for collision avoidance purposes since they can be guaranteed to not affect each other; [...] SC2 uses six steering forces: following, flocking, grouping, separation, avoidance, and arrival.

So going back to your 3 propositions:

  1. NavMesh + RVO -> If there are license issues, then it is not an option. It might be the easiest implementation though.
  2. Flow Fields + Physics Engine -> It depends honestly, but it seems really compute intensive in a semi dynamic environment as what you want
  3. Steering Behaviors + Physics Engine -> Steering behavior seems to me the way to go. That way you can define some pretty nice flock behaviors for your game, depending for example on the monster type. And it scales well with the mob number. However, i would stay away from physics for collision detection. Simple avoidance behavior is enough, reducing speed or increasing, turning, etc.

Some notes on the Steering behaviors, you can define as much steering forces as you need, with the areas you want. You need at least 3, for flocking/attraction/repulsion, but more are probably interesting.

Then, try to find a library that does steering behaviors to see if it fits your needs (like this? i don't really know any, but it exists).

If the library doesn't fit your needs, then you're up for some fun! But there are enough resources and algorithms to implement flocking behaviors yourself. Example 1 Example 2

If you choose to implement yourself, know there are some nice optimization to be done, as the scope of your agent is reduced for example by its location in the flock. It should anyway be included in some of the algorithms.

Well that's the best of my knowledge, I'm not sure anyway

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for answering. Will steering behavior works well in a dense scene? The demos in this tutorial have many collisions and oscillations. \$\endgroup\$ Commented Jul 20, 2015 at 5:31
1
\$\begingroup\$

If the enemy paths are not very dynamic (Dynamic would be every couple agents are attacking different targets and paths to those targets have to be updated every couple frames)

Then I would do a combination of flowfields and steering behaviours if performance is your main concern. There are some more complicated subjects involved like space partitioning your agents so finding neighbors is easier but it's your best bet for performance. (removing your A* search and using flowfields to direct your agents)

Those two algorithms combined are generally considered the most optimized solution for agent dense scenes with not much dynamic pathing.

I'd avoid physics no matter your final option as it can get heavy.

Collision between agents can almost entirely be handled by steering behaviours and flowfields reduces the weight of 50 agents calculating paths. Keep in mind however that flowfields get more and more expensive the larger your map size, and smaller your grid size, and more dynamic your target selection has to be.

\$\endgroup\$
2
  • \$\begingroup\$ I like the idea of flow fields. But as far as I know, both Planetary Annihilation and Starcraft use physics to avoid collision, so I'm not sure whether flow field can be done without the phyics system. \$\endgroup\$ Commented Jul 24, 2015 at 4:17
  • \$\begingroup\$ They can, all you need to do is create a flow field steering behaviour. Its only function is to check it's current grid location for its flow vector. All a flow field does is direct your agents, the other steering behaviours take care of collision. \$\endgroup\$ Commented Jul 24, 2015 at 12:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.