Range Detection with Influence Map

For the range detection system of an RTS I'm working on, I set up an influence map. Instead of using distance checks, coordinates within range are generated and checked so overhead increases linearly rather than quadratically with each additional unit. Here's a little demonstration and overview of the system:

 

I'm curious weather this system would beat PhysX. You'll get almost the same effect using a trigger collider. And PhysX has a lot of optimisation to make it scale as the number of colliders increase.

 

I've kind of already beaten PhysX with DPhysics. 900 units all cluttered up in 4 instances: http://forum.unity3d.com/threads/dphysics-and-lockstep-framework-demonstration.318829/.

For the influence map range detection, 800 units worked fine on my Windows computer (with DPhysics and crowd simulation also running). Unfortunately, my Windows doesn't have the power to screen record and it's getting kind of late so I'm going to make the video tomorrow on my Mac.

I actually did profile the influence map before I made a bunch of optimizations. For some strange reason, at 512*512 grid nodes and 200 units, it took at most 1 millisecond to run (except at startup, which gets pretty crazy; about 100 ms). I'm not sure what kind of dark magic is being used here but it's very useful.

I'll verify all this before your eyes tomorrow.

Scratch that... I'm working on it right now. Don't want to seem lazy hehe.

 

Here's a stress test video with 256 * 256 nodes and 800 agents:

.

I've logiced that grid size doesn't matter except at startup and maybe a minor variance in array lookup time.

 

Nice. Thanks for this. I'm planning to use a similar solution for another project I'm doing conceptual work for at the moment. I hadn't thought to use them for range this way before, but I'm totally going to add this, since I have to build almost all of it anyway.

So if I get this right you have a 2D array of hashsets. Each unit adds itself to the HashSet at its location and removes itself when it moves. Then when a range check is needed it simply checks against every HashSet within range for other units.

I'm still curious how this will run against a space partitioning solution. This seems like it would get most expensive when the units are widely spaced.

 

Exactly. Space partitioning actually won't be necessary since a unit checks only the coordinates around it.

The main performance hit is having many HashSets, how it uses so much memory so I left all the hashsets untouched at the start and only initialized them when a unit uses it.

 

I've played around with the influence map and found that HashSets actually aren't needed. Since multiple units most likely aren't going to occupy the same coordinate, the coordinate can have just 1 unit allocated.

 

I was thinking of this too. But this means your grid resolution will have to be smaller then the minimum unit size. Or you restrict units to grid movement.

But as looking up a spot in an array is O(1) it probably won't make much difference if your array is massive, so long as you have enough memory for the array you'll be fine.

 

I've thought about this some more and here's what I concluded: there are many coordinates, but not nearly as many units.

Instead of storing units with the coordinate, I'll store them in the objects that need the information by distributing the info with events. Units will subscribe to the events of every coordinate within range. When a unit stands on a coordinate, the coordinate will shoot out an event and all units subscribed to that coordinate will know about it.

A buffer would need to be used though so that all units subscribe to coordinates before coordinate events are called.

I'm heading to a family party right now so I can probably hang in the back and make this happen. Finally startup won't take forever and memory usage won't be in the millions.

 

This would work if you need to know all of the units in range every frame. But in most cases this is not the case, range checks can be done at some defined frequency rather then every frame. In this case your events could be firing off a lot of extraneous information that's never used.

I can also see some garbage collection and memory allocation issues if its not managed carefully.

I'm still curious to see this benchmarked against space partitioning.

 

According to the unity profiler, with 800 circles, it takes DPhysics (which uses space partitioning) about 20ms while the influence map takes 5ms when everything's moving. Of course DPhysics also simulates the physics which might be responsible for a lot of that 20ms.

Thanks for the caution. I'm still working out the details whilst fighting my car sickness. I'm thinking of storing the last coordinate the unit stood on and calling an event when it leaves. This would make it so that range detection would only need to be updated if the unit moves. Oh gawd, but what about rescanning the coordinates after moving. I guess checking for every unit within range if that units coordinate is still contained.

 

Okay, so I did some testing... events are extremely expensive to add a handler to. It takes over 20ms to add 1000 events!!! With a range of 10, there's about 300 coordinates each units needs to attach itself to.

 

In my head where this is really shinning is with dynamic obstacles.

 

Oh, yeah. I'm going to look to Aaron Granberg's pathfinding solution for how he deals with dynamic obstacles. I think it's similar to an object attaching itself to a coordinate. I was also thinking of only using height blockers for pathfinding and line of sight. Every coordinate has a height value that can be modified and checked whether or not a unit can see past. Then again, inequality checks are much more expensive than a simple boolean check. Maybe for pathfinding, a 'Walkable' boolean can be used for the coordinate to tell the pathfinding whether or not that node is walkable.

 

I was still thinking of line of sight stuff. Get your alrorithm right and things like cover and corners could be done using the same principle. Maybe, I'd have to jump into code to see.

 

I found a great explanation/tutorial of a good algorithm here: https://weesals.wordpress.com/2014/03/15/unity-rts-part-2-line-of-sight/. I verified the code to work perfectly, although a bit expensively. When the time comes, I'll play around with the algorithm and see where I can inject some dark magic in. For now, I'm working on the attacking AI/commands with the range detection.