Data Structures and Approach for AoE effects

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.

No matter how hard you try, you can't make it good from the beginning. The reason is you have no idea if this will be a problem or not. The chosen solution may be better than a naive solution, but if it ends up adding a layer of complexity in your architecture and there was no bottleneck after all, you lost the time it took to create the solution and the time it will take to maintain the solution. At that point, the good solution was the bad one and the bad one was the good.

Before doing any optimization, make sure you profile the code first, identify real bottlenecks and then optimize. If you already have a naive solution that you know works, you can validate your new solution because you have test data. Without it, your optimized solution can be faster, but return bad data and you will never know until you are deep in complexity. It will also allow you to benchmark the solution. Sometimes, complex solutions cause bottlenecks elsewhere. Will maintaining whatever structure you choose cause more overhead than checking for each unit every frame? You can't know until you do them both in a real scenario.

Quote:

Original post by gexxx Stuff that happens very often and needs "complex" computations is the first thing to be optimized.

A range calculation is not complex. To see if the distance between two points P₁ and P₂ is lower then some threshold d you simply have to do the following

v = P₂ - P₁
if (dot(v, v) < d*d) {
// do something...
}

It is not composed by a lot of operations. The naive method has a better data locality and cache usage pattern then the quadtree method and it is better if the number of units is low. On the other hand, if there are a lot of units, then the quadtree method can be faster. There isn't therefore a method which is better in every case, but it depends on the game.

I don't know if the following approach actually works because I never get to implement it. I just considered it sometime in the past.

You need to UPDATE ALL UNITS every simulation cycle. Auras and AOE effects should be updated before units. The most important thing when doing updates is to keep data structures and order of processing cache-friendly or you'll horribly waste CPU power.

Auras (which applies to fog of war also):
a) Each cell of a grid contains the auras which apply to the cell (eventually splited per "player" and "target type" - offensive/defensive). Most certainly there will be a hard-cap for number of auras that a cell can remember. Here you can pick something to allign nicely in memory in case you want to parse the map-grid at a later time cell-by-cell for any fancy reason you may find.

b) You can check-sum each cell to know if the status of any aura/applied auras has changed since the last iteration. This helps you to cache previous auras on unit side and re-compute only when status change (i.e. an aura fades or changes parameters; HINT: plenty of bugs may happen in this piece of code, but you can dodge hardcoding fixes with elegance and help from design side - just the type of buffs/debuffs and type of targets clear from the start :) ). For the first implementation, go with a non-cached version.

c) When an aura is enabled, use a circle fill algorithm to register your aura among the relevant cells. I believe Warcraft 3 stacks "effects" in pre-designed slots in each cell or uses the maximum one of them. This is a design restriction you have to account for (again, make it clear inside your mind how do you want the mechanics to work before you start coding).

d) When the aura-generator unit moves, use an optimized algorithm to unmark cells "behind unit" and mark the new aquired cells (I can't recommend you right now something, but I read a few of them around the Internet). Instead changing all the cells that the circle covers, you modify only the "new" and "outdated" ones (the bigger the circle is, the less they count from circle area - so you get performance increased returns with higher circle range). DO NOT USE linked lists, use a pre-allocated cache-friendly data structure and hopefully a data-processing oriented code (SIMD) for lighting-speed performance :).

e) When the aura-affected unit moves, compute the index of grid-cells that affect it (note that you may have a different grid with less divisions for implementing mechanics then the one using for movement).

Picking units (with mouse - I wrote it and then I noticed it was about AOE):
Just cache units visible in current view. Because you dont have restrictions regarding the number units that can stack over a cell or their size (warcraft 2 and most of older games had unit equal to a cell and most of 2 stacked units ground + aerial, in Starcraft they did a trick making an unit cover multiple mini-cells), it's a good idea to just have a proxi-bounding-rectangle stored in a cache-friendly data structure and iterate through them. Further optimisation, like selecting the unit under every next click can also be made plus pixel-perfect selection, but all these are polish and should not be in the initial implementation.

AOE stuff:
With some changes, code from auras should apply here as well. You will not need the "moving circle" filling part and there might be additional design restrictions (i.e. dmg cap for aoe effects). If you want dmg-cap you may register units to dmg source when you update them (as you did when checking auras for their cell) and apply the dmg after making further calculations (like dividing the entire dmg to number of registered units or other design requirements).


I hope this will answer your question and come again if you need to find out something new. :)