Hi community, I am new here and start with a very tricky question. I am designing a strategy game (comparable to Warcraft 3 or stuff like that). I have two difficult functional requirements, which I want to handle with high performance: -Picking Units in Range: For Splash damage attacks (explosions, spells, ...) I want to be able to pick all units in Range of a specific point. Since there may be many units on the battlefield the naive approach of just looping over all units and testing is not possible, of course -Aura effects: Units should be able to have effects comparable to Warcraft's Auras: I.e. Whenever a unit comes into a specific range of a unit having an aura, an effect is applied to it. For example the movementspeed of all enemies in XXX Range of a unit could be slowed to 50% with such an aura. But how to efficiently check when a unit comes in range of an aura giving unit? I cannot check every unit against every aura every frame. The game is 2D, at least these two effects can work on a 2D landscape (even if the landscape might get 3D). Here is my approach so far: The map on which the battle is done is divided into a uniform grid. Whenever a unit moves to another cell of the grid, it is registered there. I build a quadtree on this grid. I use this quadtree for the "Picking units in Range" task by going down from the root only if one quad is in the desired bounding rectangle of the pick and is not empty (i.e. contains units). Is this approach good for picking units in range or is there a better one? And now to the aura effects: I really have no clue at the moment how to manage such an effect with high performance. I also haven't found any information about this on google. However, Warcraft 3 seems to handle it very performant. Even with hundrets of units and many different auras, the game is still not losing any framerate. I think the core feature that would allow me auras is to detect when a unit comes into a specific range of an aura unit. But how to do that with high performance? Can someone help me here? (Sorry for my bad english, if something is unclear, just ask, I will try to explain that part better then)

when you update a unit that produces an aura, do a range check from that unit to all other units and if the unit is within range then apply the aura. you dont even have to do this every frame, do it like once per second...sure this will let a unit have it a little bit longer if it is moving away (up to 1 second longer as he moves out of range) or takes up to 1 second longer for it to acquire the aura as it moves closer to you...but 1 second wont be noticeable when you are dealing with large numbers of units. the players attention will be dealing with other stuff than watching to make sure the buff gets applied at the exact instant the unit is in range.

you could even make the check ever 0.5 seconds or whatever interval you would like. the shorter the interval, the more precise it will be.

Thank you for the quick answer!

Yes, I already thought about this approach. If there is no better one I will do it like that. But then there are two things left open:

a) In Warcraft, the aura is really applied instantaneously at the exact range. So either they use another approach there, or their check interval is really low (<0.1 seconds). So damn, how do they do it? :)

b) Is my approach for the unit picking good? If also auras rely on picking units it is twice important to make those picks really fast.

Quote:Original post by gexxx

a) In Warcraft, the aura is really applied instantaneously at the exact range. So either they use another approach there, or their check interval is really low (<0.1 seconds). So damn, how do they do it? :)

Wow has really low update rates, probably once per second or so. The reason you think it's instant is because your client is delayed anyway.

Also - checking whether a point is in a certain radius is *really* fast for 5 units, or even 40 (don't they apply to party only, or raid, or group or something). And WoW isn't perfectly synced between UI and server, so icons popup instantly, but actions take time to actually come in effect on server. Extrapolation and all that.

Quote:b) Is my approach for the unit picking good? If also auras rely on picking units it is twice important to make those picks really fast.

There are many clever ways to do this.

But the stupid one will work best:

Quote:Whenever a unit moves to another cell of the grid, it is registered there.

Why "apply" auras. When an aura is activated, mark the cells it affects. On a grid, this means cells (x-1,y), (x,y), (x+1,y), (x, y-1), ... and so on. All units already know which grid tile they are on - so just just check which auras active in that tile apply to that unit.

This means the complexity is O(n_tiles_affected) each time aura is activate or expires, or when the unit changes tiles (once a second at most, not when the sprite animation is updated).

You might want to define auras as a bitmask, so that which ones are active can be stored efficiently on each tile.

Remember that computers today can run several billion calculations each second. The above requires hundreds, per aura activation per second.

I don't think a range check is much of a performance hit (more so in 2d), you could probably do thousands without losing fps. You can optimize the range check by not taking the square-root of the displacements but rather square your radius.

i would just use the normal distance between two points calculation to see if they are in range. unless there are a large number of aura producing units, then doing the checks from only those units to the other units shouldnt be too bad

example...

200 units in the game
4 of them produce auras
so each of those 4 units will do 199 checks each for a total number of 796 checks. that doesnt seem like too many calculations. and i would really try out the doing it only every 0.25 - 0.5 seconds. i dont think it will be as noticeable as you think. unless the units are moving really really fast, it shouldnt be noticeable.

You don't really need a quad tree. It's not too difficult to calculate which grid squares are covered by a circle directly. You could easily do this every frame for each unit with an aura.

You might find standard circle drawing routines useful. Instead of setting pixels just process the units in the grid squares. Note that you'll need to adapt that algorithm to fill in the circle by drawing horizontal lines instead of single pixels.

Thank you for the answers.

@Antheus: I am talking about Warcraft 3, not WoW, Warcraft 3 has instantaneous auras and can handle battles with 150 units and many auras without much of performance loss.

I have also thought about the mark cell approach. However, there are drawbacks:
a) The tiles are kinda small and aura ranges can be very big, so there might be hundred or more tiles affected.
b) If the aura giving unit moves, many tiles have to be unmarked and others have to be marked. Calculating the set of tiles that has to be unmarked is no easy job, so the naive approach would first unmark all old tiles and then mark all new, probably remarking most of the tiles. Whenever a unit moves to a new tile, it must check against all auras on this tile (to check if it has them).

This stuff sounds like a big overhead. Maybe just doing the pick each 0.5 seconds approach would outperform it.

@Mussi: Of course, the range check is no big deal. But checking against all units for all AoE attacks, spells and auras, is a big load of work with O(n²) complexity (assuming all units on the field use AoE attack). I would have to check for each unit's attack all units for hit -> n². Of course also a quadtree has worst case n² if all units stand near together on one tile. But that is very unlikely to happen.

So is the quadtree + grid + registering upon changing grid cells a good approach? Or are there better approaches? I am really confused about that, since most of the game's performance will rely on it.

edit:
@Adam_42: I also thought about that, but since tiles should be very small if auras rely on them, there will be many tiles, if the explosions or auras are large. Checking 200 tiles just for 3 units that lure around in them is a big overhead. The quadtree allows me to find tiles with units in them efficiently.

"So is the quadtree + grid + registering upon changing grid cells a good approach? Or are there better approaches? I am really confused about that, since most of the game's performance will rely on it."

I think you're grossly over-estimating the amount of time n² comparisons is going to take for a couple of hundred units. Have you tried benchmarking this?

By simply comparing squared distances (or even checking Manhattan distance first) you avoid a square root (as mentioned earlier) and I think you'll find that the performance impact of this is going to be minimal.

Using a grid system and only checking distances with units in nearby grid squares will reduce this even further. A quad-tree is also a perfectly acceptable way to do this.

Quote:Original post by gexxx
@Adam_42: I also thought about that, but since tiles should be very small if auras rely on them, there will be many tiles...

Why do they need to be very small? You can use large tiles if you still do a distance check for the units in nearby tiles

Quote:I think you're grossly over-estimating the amount of time n² comparisons is going to take for a couple of hundred units. Have you tried benchmarking this?

true, this was a bit exaggerated. I just wanted to tell that this AoE picking stuff will be happen very often in the game. Stuff that happens very often and needs "complex" computations is the first thing to be optimized. Since the system is not fully implemented yet, I couldn't benchmark it yet.

I agree that basically even the naive approach would be okay but I started this rather than an engine that I can reuse for other games. Since I don't know how big the games I might imagine some day will get, I want to make it good from the beginning :).

edit: Yes, the tiles don't need to be small in the current approach. This answer was about the mark tiles for auras approach where the aura is given only by marking the tile.