Advertisement

Path Planning and Steering behaviors

Started by November 05, 2017 06:16 AM
5 comments, last by ApochPiQ 7 years ago

I'm writing a Diablo-like type game in Unity and currently working on the AI system. I want my agents to roam and interact with the world.

I recently read the excellent book "Programming Game AI By Example"  and I'm having a bit of a challenge understanding of how to use both path planning and steering behaviors. Let's say that the agent sees the player and decide to seek cover or stand in between the player and a treasure-chest, or even engaging the player while keeping a safe distance and avoiding dynamically created objects (e.g. a fireball spell). The path planning (and Unity's navigation system) allows me easily to set a target for the agent, but how do I incorporate steering behavior at the same time? Path planning helps the agent moves to some point and steering behaviors set forces to guide them... the two seems to compete with each-other and all the resources I see online explain each topic in separate not in conjunction.

Would greatly appreciate if someone can share from his/her own experience or point me to the right resources.

BTW, Which Path Planning and Steering Behaviors packages do you use in your own Unity games?

Thanks!

TLDR:

Path Planning: Where do I have to go?

Steering: How do I need to adjust my velocity to reach a destination point?

 

Path planning answers the question "which sequence of nodes should I follow to reach the target without being blocked by (static) obstacles", while steering handles "I have a next target position I would like to reach (the next node in the planned path). How do I need to rotate/accelerate to get closer to that target while avoiding (dynamic) obstacles that may be in my way?"

In many games pathing only considers static obstacles, although it is possible to adjust the pathing graph every time a dynamic object (e.g. a monster) has moved. If that is the best way depends on your game -- I think it is rather expensive in games with many dynamic obstacles, but I am not experienced enough to comment on that.

In a game steering is used to move an object to a single target position while avoiding other units. The idea is that a monster has multiple goals:

  1. reach the target position
  2. don't intersect walls (most of the time path planning takes care of this)
  3. avoid other entities in my path

You implement these goals independently of each other: each goal has a function that calculcates a "guiding force" that makes the object move in such a way that it honors that goal. These are the individual steering behaviors. To compute the final position of the object you add up all these guiding forces and use them to adjust the object's velocity. There are many steering behaviors; item 3. is particularly hard to get "right" for larger clumps of monsters.

Some basic steering behaviors are:

  1. arrive (takes care of reaching a point and stop)
  2. seek (move to a point but dont stop -- I have found that arrive works well enough even for paths)
  3. avoid (avoids obstacles in its way)
  4. path following (follow a list of positions successively)

Then there are more advanced steering behaviors that handle groups of units well, e.g. separation, flocking, alignment, ...
 

To conclude, two references on steering:

A scientific one http://www.red3d.com/cwr/steer/gdc99/ and a tutorial that confuses physics terminology a bit IIRC (nothing serious), but is nice to understand and visualize individual steering behaviors https://gamedevelopment.tutsplus.com/series/understanding-steering-behaviors--gamedev-12732

 

Advertisement

Thanks for the response duckflock.
Let me rephrase the question: how do you use path planning and steering behaviors at the same time?

Should I instruct the agent follow the waypoints along the path after calculation and apply steering behaviors while its navigating?

Path planning tells you what waypoints to feed into steering. Steering is the only thing that should "control" agent velocity and position. You use a "seek/arrive" force set to steer towards the next point on your path plan. If you run into an obstacle that prevents you making progress, you can re-plan your path.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

Thanks ApochPiQ for the explanation. I'm applying it right now.

One additional question though, when the agent sees a target (e.g. the player) and would like to engage - let's say attacking... Should it plan the path towards the player, get there and then attack or rather should it use seek / arrive or any other of steering behavior using the player as a target directly?

Most of the Unity examples I saw online didn't use any steering behavior, when the agent saw the player, the NavMeshAgent target was just set to the player and when the agent got in proximity it attacked. I wondered if using a steering behavior in this situation is actually better. What do you think?

The flow should look like this, more or less:

1. Pick a place you want to go. This is higher-level AI logic and irrelevant for getting there; it could be controlled by a patrol route, a quest objective, a target you want to fight, or anything else.

2. Feed the destination into a path planning algorithm.

3. Feed the waypoints from the path plan into steering.

4. Optionally feed steering forces into physics or just apply the net resultant velocity directly (depends on the game).

Note how "instructions" or "commands" flow in exactly one direction at all times, i.e. from more general to more specific. There is no cross-talk between steering and path targets, there is no mechanism by which steering can get confused with multiple objectives, and so on. Everything flows down the list and only down the list. This is a defense against convoluted designs where you need to track all kinds of redundant information about your movement so that you can reimplement the same basic goals in three different places - i.e. this is a clean and simple but extremely effective solution.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

This topic is closed to new replies.

Advertisement