Data Structures For Game Devs: Queues & Stacks | Unity Tutorial (Part 4)

welcome back in this video we'll cover cues and stacks we'll see where and how you can use them in your unity game and check out lots of examples this is a multi-part series on data structures the first of which covers lists areas and a bunch of fundamentals for this video so i recommend you check that out especially if you're a beginner i've also covered hash sets and dictionaries which can be really useful but this video on cues and stacks doesn't directly build on those so cues and stacks are similar in a lot of ways which is why we cover them both in a single video we'll check out cues first which probably have more meaningful real-world applications in games than stacks but you can definitely use both to your advantage so a queue data structure is pretty self-explanatory just like a real world cue things go in then stay in the order they were put in and then come back out in that same order except in real life people may be skipping the line and leaving the queue earlier than they should anyway let's define an example c sharp q as always with generic c-sharp collections you have to specify the data type of the elements you're storing in this case integers we could also store strings game objects or any other data type the fundamental properties of a queue are that you can only add items at the back of the queue and remove items from the front of the queue to do so you would call the dq and enqueue methods the items are always kept in order so whatever you put in first will come out before anything you put in after that this is the first in first out principle anyway you can iterate over all the items in a queue so you can access them one by one and for example check if it contains a specific item however you can remove or insert an item in the middle of the queue i am currently working on a little train game called on track it's still working progress but i already have a few neat examples of cues making my code simpler and shorter so the game periodically spawns new trains that then move through the level while the player needs to make sure they end up at a depot of the same color by operating the railway switches depending on the level the track network may have tracks merging together or simple crossings i don't want trains to just move on top of each other in such places which really doesn't look very nice so let's use crossings for the example but merge points work in exactly the same way to organize traffic each crossing keeps track of any lined up trains in a queue of game objects it uses a collider to detect and register incoming trains and when it's already occupied as another train arrives the train stops and is enqueued to the crossings queue of waiting trains whenever a train leaves the crossing as detected by the collider as well i check if there is a train waiting in line and dequeue it so it continues its journey note that the queue behavior is exactly what we want here if we let lined up trains continue in random order or always from the same preferred track that will not balance out very well so let's take a look at how unity c-sharp q is implemented to figure out if enqueuing and dequeuing are also fast operations just like a list the queue uses an array to store elements internally and it keeps track of the front and back of the actual cue within the array using the head and tail index so at some point in time an integer queue may look like this internally now enqueuing an item simply means adding the item at the tail position and adjusting the tail index but what happens now the percent sign is the modulo operator and it will always return the remainder of a division in our case the tail index was previously set to aid and adding one to that would cause the index to move out of the arrays bounce so the modular operation here returns zero which is the remainder of dividing eight plus one by nine note that the area is indexed starting at 0 so this area is currently 9 elements long and now you can probably guess how dequeueing works of course the queue may eventually reach its internal aries capacity limit which is when the entire array needs to be copied to a new bigger array and that's just how the list implementation works which we covered in the first video by the way you can usually tell any of these collection data structures in their constructors which internal capacity they should begin with if you like anyway to answer our initial question the nq and dq methods are always fast no matter how long the queue is if you on the other hand remove an item from the start of a list that operation will become less efficient the longer your list is that said in practice your runtime performance for all the data structures in this series including lists hashtags and dictionaries from the previous videos will depend on a lot of factors like the patterns in which you allocate the stored objects in memory the access patterns you use how many elements you store the size of the individual elements your systems cache size and latency and so on but if you're a beginner i really recommend not overthinking this or prematurely over optimizing your code anyway now that you understand perfectly how a cue works here's another real world use case giving a game character assignments to complete like for example constructing buildings the character could just keep a queue of work items and complete them one after another which matches the queue concept perfectly the player enqueues new assignments and the character dequeues one whenever a previous work item is complete and with that let's take a look at stacks like i mentioned they're very similar to cues you can add items to a stack by calling the push method and you can remove items by calling the pop method as you can see the ladder is where stacks and cues work differently while the cues dq method will always give you the first item you put in the queue a stack will give you the last one you've put in that's the last in first out principle as opposed to the first and first out principle that applies to queues one very obvious example for stacks could be piles of cards in a card game players can only add cards to the top of the pile and draw cards from the top of the pile here's what a basic implementation could look like note just like we did when de queueing items from a queue we need to check if the stack is empty before removing and returning the topmost item since it would otherwise throw an exception of course a stack will no longer work well if there are extra rules in the card game that let you for example draw a card from the bottom of the pile or add cards to a random location in the pile or things like that by the way the internal implementation of the stack is not too spectacular it works exactly like the list data structure works an internal array holds all the elements and its size is expanded by a growth factor whenever so many elements have been pushed to the stack that the internal area's capacity is reached this may now make you wonder what the point of using a stack would be in the first place since it is basically a more limited version of a list and you wouldn't be wrong stacks are pretty specialized and their advantages come from their limitations and specialized behavior you can only do a few very specific things but you can do them with less code and probably in a slightly safer way than if you used a list let's compare the draw card method for the stack with one that uses a list you need to do a few additional things here like defining the index of the card you want to grab storing the topmost card and then removing it before finally returning that removed card also if you don't know how the internal list implementation works you would maybe instead use the beginning of the list as the top of the pile rather than the back which would result in the draw and add operations taking longer and longer the bigger your list gets that's because the entire internal area for the list is copied every time you add or remove an element at the beginning anyway let me know in the comments below if you have another good example use case for stags or if you think they're mostly useless so let's conclude by looking at object pooling which is a neat and common use case in game dev for both cues and stacks imagine you have a game object that you constantly need to create and destroy many instances of a good example could be enemies that are spawning and getting killed or rapidly firing bullets from a gun or in on track i constantly need to spawn new trains and destroy those that have reached their depot however frequently instantiating and destroying objects is pretty inefficient and it may become an issue if you have to do it a lot as would be likely for the bullet case so in on track instead of destroying trains when they reach their depot i just set those trains in active so that their instances still remain in memory then when it's time to spawn in new train i can just reuse one of the inactive train objects so i don't have to instantiate anything that's a pooling system and one way to keep track of the inactive game objects would be a stack or queue both data structures let me conveniently get and remove an item from the pool using a single fast method dq or pop and they both let me easily and efficiently add an object to the pool using enqueue and push so like i said let me know if you have other interesting examples maybe even from your own games we're now concluding this video series on data structures let me know if this was useful i haven't previously created any educational videos so i'd be happy to get some feedback thanks for watching and good luck with your own game which i'm sure will use a ton of extremely fancy data structures now

Channel: Anni

Views: 1,793

Keywords: game development, unity tutorial, data structures, c# tutorial, game dev tutorial

Id: jlPgg8TBoTc

Length: 9min 8sec (548 seconds)

Published: Fri May 07 2021