0
\$\begingroup\$

I've been puzzling over how to do spatial awareness for units and buildings. I've asked a few questions and the final conclusion was spatial partitioning in the same manner used for collision detection. So an object knows if something is close to it and can react appropriately (such as attacking an enemy)

I'm making sure this is what I expect it is, so that my monetary and time investment in reading materials is not a waste for the purpose of completing this game.

\$\endgroup\$
2
\$\begingroup\$

It sounds like you're making an RTS, so let's say you need to have a building that automatically attacks the nearest enemy within 100 metres.


A naive (and inefficient) approach would be to calculate the distance to every enemy unit, find the minimum, and ensure that it's within 100 m. Then you have your target. However, this means that for every N buildings and M enemies, you have to do N*M distance tests.

One optimization you can make is to use a distance squared check to eliminate the relatively expensive square root operation. So instead of checking the distance against 100 m, you check distance^2 against 10,000 m^2. This will save a bit of time but you're still working with an O(N*M) complexity.

Here is where spatial partitioning comes in. Now, you can do a broad test to first find which partitions may potentially intersect with the building's range, and narrow down the list of candidates for enemies to attack significantly. Applying both of these optimizations should give you a significant average-case cost reduction.


This is the exact same thing that you would do in a generic collision detection algorithm - narrowing down the list of candidates through a gauntlet of cheap (and usually parallel) early-out tests. Indeed, you could implement the building's broad phase query as a collision test against the circle/sphere that bounds its range, which might be useful if you're using a 3rd-party collision/physics library.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. I am making an RTS, and I am using Unity. however I will not be using unities spherical colliders as a way of range detection. Their performance is atrocious with any reasonable number of units. Which is why I'm looking into solutions I can roll on my own. I'm looking at: amazon.com/Real-Time-Collision-Detection-Interactive-Technology/… as the book to hopefully learn what I need. As well as amazon.com/… if I find the money. \$\endgroup\$ – Douglas Gaskell Apr 12 '15 at 5:35
  • \$\begingroup\$ Of course it's not the only way to do things, I was just pointing out how similar the two problems are and how they can be implemented in terms of one another. And yeah, any decent book on collision detection should cover spatial partitioning and broad phase detection, which is what you're looking for. \$\endgroup\$ – jmegaffin Apr 12 '15 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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