12
\$\begingroup\$

I'm using Unity3d to develop a RTS/TD hybrid prototype game. What is the best approach for "awareness" between units and their enemies? Is it sane to have every unit check the distance to every enemy and engage if within range?

The approach I'm going for right now is to have a trigger sphere on every unit. If an enemy enters the trigger, the unit becomes aware of the enemy and starts distance checking. Does this save some unnecessary checks?

What's the best practice here?

\$\endgroup\$
1
  • \$\begingroup\$ I should add that the unit/enemy count is going to be in the scale of Supreme Commander \$\endgroup\$
    – Phil
    Dec 28, 2010 at 20:41

3 Answers 3

10
\$\begingroup\$

Look into bounding volume hierarchies (BVH). They're most commonly used in collision detection to reduce the number of checks needed when calculating collisions or in rendering to perform frustum culling on objects. Since you're already using spheres, I'd suggest a sphere-tree though other volumes such as AABBs may be more efficient. I'm not sure what sort of support Unity has for such things as I've never used it, but there is probably something for this already within the collision detection or rendering parts of the engine.

Basically, you would want to group enemies that are near each other together into multiple parent spheres. When a unit is moved, you would check it's trigger sphere against the parent sphere instead of checking each enemy. If the trigger sphere intersects with the parent sphere, you would check each enemy within. If it doesn't, you can discard all of the enemies that are within it. You would want to set up multiple levels of spheres based on a maximum sphere size or enemy count for each sphere and perform the check based off of a top-level sphere. Then it's just a matter of walking down the tree in order to check each enemy without needing to perform the distance check for each one.

Steps required each frame:

  1. Move enemies
  2. Rebuild/update the BVH for new enemy positions
  3. Move units and check against sphere-tree.

This can reduce the checks needed when there are lots of enemies but the overhead of updating and storing the tree may not be worth it when there aren't that many. I'm not familiar with Supreme Commander to know what you're after, so I'm just assuming 'hundreds'. You'll need to profile in different situations to find out whether the overhead will be worth it to you.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ +1 this approach will be simplest although it will have some errors. OP may want to implement this and then implement something like an octree. Also, in most RTSs, the units react with some delay. In fact, most AI in games is calculated 10-30 frames per second where the game may be running at 30-60 frames per second (the numbers are, of course, approximations). \$\endgroup\$
    – Samaursa
    Dec 29, 2010 at 5:33
  • \$\begingroup\$ Thank you, this was exactly what I needed to take me one step further. I'll look up BVH and how to implement it in Unity. Very pedagogical and informative post! +1 \$\endgroup\$
    – Phil
    Dec 29, 2010 at 14:42
  • \$\begingroup\$ Oh and check out Supreme Commander if you're in to RTS. It's a very nice game indeed, as are all Chris Taylor games really. \$\endgroup\$
    – Phil
    Dec 29, 2010 at 14:43
8
\$\begingroup\$

There is no need to implement BVH's, since Unity's collision engine essentially does that for you already.

Simply attach a large bounding-sphere trigger to each unit (representing its range) and handle the OnCollisionEnter() and OnCollisionExit() callbacks to keep track of which enemies are within range of each unit.

Note that the case you're interested in is when another unit collides with the sphere, not when another unit's sphere collides with the sphere.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think this needs to get upvoted to at least just above the accepted answer. Accepted answer is good for studying, but this answer should be on the top as this is the most practical way. \$\endgroup\$
    – Varaquilex
    Apr 27, 2015 at 3:32
  • 2
    \$\begingroup\$ I believe you mean OnTriggerEnter() and OnTriggerExit(), right? \$\endgroup\$
    – Jibb Smart
    Apr 29, 2015 at 4:08
1
\$\begingroup\$

Another solution that scales very well and can be used for a multitude of other things is an influeunce map. Generate a set of grid tiles around the unit to scan within X radius. Scan these tiles for an enemy standing on one of them. If you want to get the closest enemies, you can sort your set by distance.

This might be the most efficient method, especially if you plan to do other things with the influence map like fog of war or pathfinding.

Here's a video I made explaining the concept: https://www.youtube.com/watch?v=MEd6XV2Pecw.

And here's an implementation: https://www.youtube.com/watch?v=y_ewoxlZlgc

I recommend not initializing the grid tile's unit collection at startup - but instead only when the collection is needed.

Alternatively, you can use an array of X length if you know there will never be more than X units on a tile.

\$\endgroup\$

You must log in to answer this question.

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