Sign in to follow this  
gexxx

Unity Data Structures and Approach for AoE effects

Recommended Posts

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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
"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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 P1 and P2 is lower then some threshold d you simply have to do the following

v = P2 - P1
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.

Share this post


Link to post
Share on other sites
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. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Forum Statistics

    • Total Topics
      628281
    • Total Posts
      2981801
  • Similar Content

    • By ForgedInteractive


      Who We Are
      We are Forged Interactive, a small team of like-minded game developers with the sole purpose of making games we love! We're a team of artists, animators, programmers, level designers, writers, composers, producers, and other creative minds. We want to make games that you, the modern gamer want to play! We hope to build a community that enjoys our games as much as we love creating them. With your feedback and support we will be able to achieve that.

      About the Game
      GAME NAME is a fun, action-packed army builder with unique characters, challenges and engaging levels. Set forth on an adventure to protect friends, family and countrymen from new adversaries. Once defeated your enemies turn coat and join you in your adventures. Players can enjoy a range of troops and abilities based on their gameplay style which become more important as maps introduce more challenging terrain, enemies and bosses. Strong orc knights, dangerous shamans, and even a dragon are out on the prowl. Knowing when to fight and when to run, and how to manage your army is essential. Your actions alone decide the fate of this world.

      Previous Work by Team
      Although we are working towards our first game as a team, our team members themselves have past experience in the industry.
      This includes members who have worked on titles including:
      Final Fantasy Kingsglaive, FIFA, Xcom 2 and Civilization.

      Who are we looking for? 3D Modellers Concept Artists Marketing Specialists Level Designer

      What do we expect? Reference work or portfolio. Examples what have you already done and what projects you have worked on academic or otherwise. The ability to commit to the project on a regular basis. If you are going on a two-week trip, we don't mind, but it would be good if you could commit 10+ hours to the project each week. Willingness to work with a royalty based compensation model, you will be paid when the game launches. Openness to learning new tools and techniques
      What can we offer? Continuous support and availability from our side. You have the ability to give design input, and creative say in the development of the game. Shown in credits on websites, in-game and more. Insight and contacts from within the Industry.
      Contact
      If you are interested in knowing more or joining. Please email or PM us on Skype. Myself or Colin will reply to you within 48 hours.

      E-mail: Recruitment@ForgedInteractive.com
      Skype: ForgedInteractive

      Regards,
      David and Colin

      Follow us on:

      Facebook: https://www.facebook.com/ForgedInteractive/
      Twitter: @ForgedInteract
      Youtube: https://www.youtube.com/channel/UCpK..._as=subscriber
      Reddit: https://www.reddit.com/user/Forged_Interactive/
    • By Eck
      I just saw their courses were knocked down to $10 each and figured I'd share the info here. They have stuff for Unity, Unreal, drawing, business, etc. I haven't used their stuff before, but the previews I looked at seemed pretty good and there is a user review system as well.
      https://www.udemy.com/courses/search/?q=Unity&src=ukw
      - Eck
       
    • By zizulot
      first and only logo , for now
    • By sidbhati32
      I am working on a game in which we control a rectangular box at the bottom of the screen. Three sphere which has alphabets in it fall down. When the game starts, a word is generated from the predefined list of words(which I'll give) and we are supposed to touch the correct sphere having the alphabet based on that word. The question is how to detect if I have touched the correct sphere. 
      secondly, if I have touched a correct sphere before and there is no recurrence of that alphabet in that word then during the second wave the game should not proceed if I touch the same alphabet again.
      Looking forward to your answers, i have to submit this project in a couple of days. please help! (Working on Unity 3D)
      Thanks
    • By NDraskovic
      Hey guys,   As the title says, I'm trying to control a desktop game by using my mobile phone as a controller.  I created two scenes, one that acts as a server, other as a client.    Server has this code: void Start () {         Test = "Nothing yet happened";         NetworkServer.Listen(25000);         NetworkServer.RegisterHandler(888, ServerReceiveMessage);     }         private void ServerReceiveMessage(NetworkMessage message)     {                 StringMessage msg = new StringMessage();         msg.value = message.ReadMessage<StringMessage>().value;         if (!String.IsNullOrEmpty(msg.value))         {             Test = "Message received";             string[] deltas = msg.value.Split('|');             Horizontal = Convert.ToSingle(deltas[0]);             Vertical = Convert.ToSingle(deltas[1]);             TestScript.MoveForward(Vertical);             TestScript.RotateAroundY(Horizontal);         }         else         {             Test = "Nothing received";         }     }  
        And client this:  private void Connect()     {              client.Connect(IPAddress, 25000);           }     void Start () {         client = new NetworkClient();         Connect();            }         void Update () {    #if UNITY_ANDROID         MobileTouches = Input.touches;         if (MobileTouches.Length > 0)         {             for (int i = 0; i < MobileTouches.Length; i++)             {                 if (MobileTouches[i].phase == TouchPhase.Moved)                 {                     Horizontal = MobileTouches[i].deltaPosition.x;                     Vertical = MobileTouches[i].deltaPosition.y;                 }else if(MobileTouches[i].phase == TouchPhase.Stationary)                 {                     Connect();                                  }             }         } #elif UNITY_EDITOR               Horizontal = Input.GetAxis("Horizontal");         Vertical = Input.GetAxis("Vertical"); #endif         thumb.Translate(Vector3.up * Vertical * Time.deltaTime);         thumb.Translate(Vector3.right * Horizontal * Time.deltaTime);         SendControllerInfo();     }     static public void SendControllerInfo()     {         if (client.isConnected)         {             StringMessage msg = new StringMessage();             msg.value = Horizontal + "|" + Vertical;             client.Send(888, msg);         }     }  
        Ip address is hard coded, I just replaced it with the "IpAddress" variable. The code itself builds fine, and when I try to run in on a desktop computer, it works as expected (just a simple movement of an object on the server screen). However when I try to publish the client scene to a mobile device (Android), it doesn't connect to the server. They are both connected to the same network. Can anyone tell me what the problem might be?   Thanks
  • Popular Now