Game Algorithms

hi this is Bob Kuhn from binary hammer and in this video I will talk about how algorithms can implement game mechanics and how those algorithms can be used in other applications I'll walk you through the code and show you how it works and I've provided links to any algorithm that I mentioned so you can read more about them ok my game here is a simple 2d turn-based strategy game where I have two armies orange and blue and the object of the game is for an army to connect both sides of its basis together and it does that by traversing the map the blue army traverses horizontally so it needs to connect the left to right and the orange army connects top to bottom so it moves vertically you can see here that the game is highlighting the next valid move for the player and blues going first and you can see that it's blues turn not just by the highlighting but also the glow of the sides of the bases you can see that the blue is bright and dark is orange and that changes as the game plays so navigating is just a simple act of tapping on the location that you want to traverse to and if it's empty the army automatically occupies it but if the other army is already there then there's going to be a conflict so let me just progress a little bit here and here you can see that this is a valid move for orange because the orange army doesn't occupy it so I can start a conflict by tapping on it and in my game here just to make it simple the aggressor always wins but in a real game I would have a complicated calculation to determine who wins maybe the army has to spread out its troops along all of the occupied territories so we can better defend it maybe they can erect a building to help defend it maybe the army has advanced weaponry to help more guarantee that it would be victorious in a conflict those kinds of things all come into play when determining who wins but for now it's always the aggressor and you can see that orange has split blues territory into two groups left and right here and the highlighting that doesn't make any difference to the highlighting it knows all of the the territories that blue owns and knows how to highlight appropriately and we'll talk about how it's able to do that so let me just progress a little bit further here and you can see that the blue selected the rightmost location but that doesn't make a connection because there's obviously no connection no constant connection to the left so that wasn't a win situation so now I'm just going to finish off the game and win for blue and you heard that the blue army just won because there's a connection from left to right okay so let me describe now how I did that but first I need to describe the problems that need to be solved here first is the highlighting of any applicable move the other is knowing if there's a continuous connection from one site to the other and there's a separate smaller sub problem of having having to do that efficiently and we'll cover all three in this video I first started by thinking that percolation using union-find would work here and what percolation does is answer the question of is one side connected to the other and percolation is really good for static data data that doesn't change and a specific version of union-find can't is the fastest possible way to do that and it's almost o of one so it's almost instant the weighted quick Union with path compression is able to do that but so union-find is great for finding connections in static data but it's not suitable for this game because I need to resolve those conflicts and have the connections change as the game plays out so deleting with union-find is neither simple nor efficient so that's not a good solution so I thought to describe the problem as a graph specifically undirected graph and all the graph is is a set of vertices and a collection of edges that each connect a pair of vertices so pairs of vertices are connected by edges and it's just a collection of those that's all it is so how might you represent that in a data structure well you could use a linked list of edges a vertice has a list of edges which are connections to other verts protects vertices so vertex two for example could have any number of connections to it so that would be represented in two's linked list vertex 20 might have a separate set of connections so the list if you will of connections goes from 2 to 20 you can also represent connections with a 2d matrix of boolean's let's say where each row column entry is set to true whenever there is a connection but neither of those are good solutions because they don't scale and imagine if I can zoom way out and see thousands of locations all at once neither of those are good because they don't scale well a linked list for example will take two long term to traverse because you won't know if a vertex has connections unless you walk the list of those connections he said it goes from 2 to 20 but what about 6 through 19 you won't know those don't have connections unless you walk through the entire list so that's no good it's too slow 2d matrix if I have thousands or even millions of locations that's thousands or millions squared so that will just consume too much memory so that's not a good solution what I did was use what's called adjacency lists and what that is is I have an array of vertices that each contains a pointer to its connections so you can see here I call it adjacent verts in the code that I'm going to show you and there's zero two numbers - one of them and that's how they're identified 0 through number to minus 1 so I have num verts of those in an array and each one of those is points to a collection and that could be linked list set bad any kind of data structure like that I chose set because that's more efficient to delete connections and that's important for me when a location is in conflict and the other army needs to take it over if it's already owned by one it needs to be owned by another sets allow that to happen efficiently you could also do with linked lists it's up to you to determine which collection you want to use so in this is example vertex zero is pointing is connected to 17 5 and 14 vertex 1 isn't connected to anything so it has an empty container 2 connects to 11 and 5 and 3 and 4 is an interesting example and it shows the how the adjacency list is set up to establish a connection you add one in the adjacency list of the other so it's two steps so to connect 3 and 4 you add 4 to 3 s list and 3 to 4 s list and that's important because you don't know which order they're going to be traversed in walk through in in the code so you need to make sure that if 3 is navigated to first you need to know that is connected of 4 likewise if 4 is looked at first you need to know that it's connected to 3 and so on so you can also see in 5 here points 2 is connected to 2 0 to 12 and 32 so if you look at zeros list you can see 5 here and 2 you can also see 5 and that's really all adjacent see lists are it's that simple the point here is that there's an an entry for every vertice and there's also an empty container attached to every vertices so there's no holes and that's for efficiency purposes ok now let me show you some code here I have a structure called vert that for my game needs a team and a connected component ID and we'll get to that shortly and I have an array of these verts that's set to number some arbitrary number that makes sense to my game and I also have another array of sets one for each vert and the sets contain indices to connected verts so those are indices into the verts array whatever vert is connected to some other of art I also have here a visited array of boolean's again one for each vert and will that is important for the traversal of the verts and knowing how to highlight and add to establish a connected component we'll get to that shortly too I'm gonna skip this part here and go down to the bottom that shows the how the adjacency list is set up and to make a connection all the code here by the way is all pseudocode so it's not any specific language but kind of an amalgamation of languages I try to make it as generic as possible so you can derive what needs to be done in whatever language you support so for example here to make a connection to connect a to b i add B to a is adjacent verts list and a to B's adjacent vertex a from B it's just the reciprocal remove B from ace list and a from B's list it's really that simple and to know if two verts are connected you simply ask a z-- verts does it contain B if it is true then they're connected and it's literally that simple tiny amount of code to establish connections and disconnections okay this code here are support routines and the first one in adverts for my game all that does is set each vertex team ID to no team so they're all emptied pretty much and this doesn't have to be a loop if on your cpu it makes more sense to because it's a separate array you can use memset or mem clear or some other kind of really fast and efficient memory clearing method instead of a loop use that your mileage may vary but just to express it here I've shown it as a loop so you might want to do other things in this and it all I need to do right now is just set the team to no team and also mark all verts as unvisited you will see that a couple of times in the other code that I'm going to show you and that's a similar thing here where all you're doing is setting the visited array to false because you haven't visited yet you're about to set up a visited process so you're gonna clear all of those to false and again because it's separate there might be a faster way on your CPU to do that but again I'm just showing that as a loop okay now before I get into the code I need to show you the underlying structure of the data and I have here I'm representing the graph as a 2d grid that makes me a sense for my game other games could be hexagons or circles it really doesn't matter for the data because the connections to vertices is what's important not the graphical representation so you can take that to mean the same data can be represented in many different ways I just chose it to be a 2d grid the connections as I play the game I mentioned that it's based on the who owns the current location to know what can be high related and what can't be highlighted that's just a north-south-east-west adjacency test if I wanted to I could also add diagonals and I would just add more checks to to determine that but to keep my code simple so that you could understand the process I left it to north south east or west and again that's totally arbitrary if you wanted octagons you can have eight connections it's really up to your game and the the code that I'm going to show you supports all of that so to facilitate the opening move you remember that I could show you here that's these two our marked as highlighted even though I don't the the blue army doesn't own any locations yet so how am I able to highlight those two specifically I'm able to do that because I have an extra ring of vertices here and what I do is mark an arbitrary number of them as available to be connected to and that's really just for the opening move I marked the the code knows that oh these two are owned by blue its blues turn so I'll highlight whatever is adjacent to that and visible so this extra ring is not visible to the player it's only the internal grid what's in white here and at six by six again that's arbitrary I'm also able to oh to determine if the left connects to the right normally the first thought the the slower way to do it is to have this vertex check this vertex is there a connection no alright check this vertex against that vertex is there connection no then check that one that one that one so that's n by n checks so in this case it's six by six checks to determine if that's connected as the game plays out I'm maintaining all of the connections to the locations so it always knows what's connected to what so that part is easy but N squared checks is really inefficient so a really cool way to make that all turn into just one check is I have an extra four vertices that is also hidden and all I do is connect the outer ring to them so that in order to check left/right connections all I have to do is make one call to see if this vertex connects to that vertex east-to-west in one check because the everything is connected it just knows that this is connected to that one or not so that's a really cool efficiency optimization step that I included here and so let me show you this which is what I call the debug mode the debug view and there's a few things going on that this shows you the first is all of connections and the current occupier and owner of the vertices and you can see here that these two are highlighted because these two are currently occupied by the blue team and you can't see that because it's hidden from the player but internally it says oh these two are owned by sorry occupied by the blue team I'm going to highlight the adjacent locations next to it and as I play it out you can see the connections being made now there's a special case along the edges that depending on who the player is so the blue what's important is the left column and right column whenever there's a location one by the blue army in either of those columns it needs to connect to this hidden column of vertices to maintain that connection to this extreme extra vertices and also let it live pay attention to these occupied squares here locations after I show the orange move you see that they disappeared and I had to do that because if I didn't this they would still be highlighted so I need to turn that off and just go with now that blue has legitimately owned a location I can just use that to determine whatever the highlighted squares need to be and you can see that is removed here from orange so I'm just going to make some more connections so you can see those so the the code for the orange up here I took over that territory and it always wants to hide to connect to the link the the four vertices around it so north south east west and that's what creates this connection here and the extra rule that I told you about where if it's the orange winning locations across the top or bottom it meet needs to make the connection to this hidden row it also does that as well just establishing more connections here so you can see those and you can see that the shape of the highlighted locations is based on the locations that are currently occupied by whatever team is applicable these numbers here represent the connected components and we're going to talk about that next you can see that there's four of them zero one two three and those are arranged in such a way because it's based on whatever vertice is Traverse to first so this is its left right top to bottom so this is the first one that sees if it's a connecting component so that gets ID zero the next one that isn't zero that is reached is this one here and that's owned this that's owned by blue so that gets its own unique ID of one and it goes through all of the connections for this vert and sets those two one scans through here this is already visited and then it reaches this one which is a new connected component so it sets that ID to two and so on until it reaches this one which is three and I'll show you that now this code here is based off of the algorithm that drives pretty much everything is called depth-first search and that's a recursive algorithm that can be used for example to solve mazes so Traverse mazes to see if you can get from the start to the end and it is not only see if you can get to point A to point B but what the path from A to B is I don't need that here for this game but the algorithm can be used for that there is also what's called breadth-first search and you can use that on the same exact data but that isn't recursive and it solves different problems for example what is the fewest number of connections needed to get from point A to point B so for games that could be suitable for path finding again I don't need that here but if if you wanted to have specific units maybe if you zoom in and you can only control a specific unit a tank or infantry or you know whatever you have you can use that to see if they can get to a destination and what the fewest points is to get there and what the locations are for that so here's the code needed to drive how to set up the connected components and a connected component all that is is what I showed you here is that the entire group of connected vertices to another vertices so for example connected component one what is connected to one and it goes through the adjacency list to determine that so it sets that goes connected to this one and what is this one connected to that that what is this connected to that what does that connect to do that and so on which is an exhaustive search to make sure that it traverses everything that is connected via that adjacency list so it does that with two methods a driver method and a sort of engine method and the engine is what is the recursive part so the driver here which it starts by setting all the verts as unvisited and that's the code that I already showed you in the support method that just sets everything to false I haven't visited it yet and that's important I'm just I set the ID to zero because that's Italy starts at zero and for all of the verts that I haven't visited yet that is not empty so I don't care about empty ones then go into the exhaustive search and I pass in the ID of the vertex that I'm at and the ID I want it to be set to so that I jump down down I jump down here and this is the recursion for any vertex that it enters it needs to set it to be two visited and also sets the connected component ID to whatever is passed in and then what it does is look at everything that is connected to it so it goes through its entire adjacent list in this case it sets it to B and checks if B's if B has been visited if it hasn't then it traverses into it by calling itself with B as the source and the CC identity that was whatever is passed in so that comes in here again and sets what is now B vertex 2 visited and it's ID and it looks at now what is connected to B creates a new B see if it's visited and so on so that's where the exhaustive list traversal comes in and what stops it from going forever is has it been visited yet once all of those are true that is connected it has no more work to do so it just unrolls itself from the recursion and comes back to here now I've set all of those to ID 0 so I can create that in the routes array and the route array is really just the first vertex the index of the first vertex that starts the connected component so I call that the route and I increment the ID for the next time around and I can do that here because I can guarantee that when it reaches here there are no other vertices that are in the connected component that I just reversed because the data is set up to guarantee that once you have the connected component IDs set for all of the vertexes the is connected to check now changes to all you have to do is check the CC ident so if they match they are connected so in this case these two aren't connected yet because they're idents don't match but as soon as I have enough locations the very last one to make a connection the connected component IDs are redetermination ponent ID so what I'm doing there is turning the check into an instant determination instead of anything else that requires time and effort I've it's just a simple lookup so that's o of 1 that's instant time now the highlighting is the next problem that needs to be solved and that's also done by depth-first search it's slightly different because it has different work to do but the structure of it is identical as what I just showed you there is a driver routine and a recursive engine routine and there's also because it's different work I have different data to maintain so here it's an array of boolean to see if it has been highlighted yet or not so it's similar to the visited array different but similar and also a set of connections so that's in a separate array one for each vertex and that's important when conflicts are resolved so if the team that owns a vertex needs to change from blue to orange for example it has to remove it from blue and connect it to orange but and to know what the orange vertex is it's stored in this connector and I'll show you that here so the driver also has to clear its unvisited and also it needs to clear the highlighted so it marks all votes as unhighlight it which really just clears this array similar to the clearing the visited array and what's slightly different here is that it only needs to check all of the connected components so this would be called after the connected components are determined and that's another optimization where the list of connected components is very tiny so this traversal is very quick and again it checks the visited data that was this vertex visit it sorry I didn't tell you what index was but that's a in the the previous example so it's really just an index into the vertex list and also you're comparing its team so if the team matches then I'm in it's it's a a candidate for highlighting so it traverses it goes into the recursive routine for that vertex and marks it has visited again that's very important and also just arbitrarily not arbitrarily just always tries to mark the four adjacent vertices around it north south east and west and I determine what the because my data is represented as a 2d array I just turned the index into X&Y coordinates because this is easier to check what's north and south east and west based on that location so if you jump down here highlight vertex at x and y for team and with a connector so the connector is what this routine was entered with so the vertex that I'm talking about that is adjacent to it so what's important here is that is X or Y off the map if it is if either one is then there's no work to do because that would make a bad data connection then I turn the X&Y coordinate back into an index so I can traverse the so I can look into the highlighted array and if it's already highlighted I don't have to do anything I can exit out and likewise if the team is already set to the team I'm trying to connect to that's a redundant check I don't have to do that so I just exit out so after all of those checks it's now applicable to highlight it so I set it to true for that index and also I set the connector for that index to the connection vertex that it came in as so in this case it's a once it does all of that it does an exhaustive depth-first search list just like the previous code and checks goes through all of the connected vertices in a calls it B asks is B has B even visited yet and is the team applicable if it is then it goes uses that as the source and calls itself recursively and just like the previous code it will set every applicable vertex as highlight able for the next move because you're going through all of the connected components and only doing it for the team that it applies to you're guaranteed to get all of team a's connections connected components that's why the code doesn't care if blue team for example has 20 connected components it'll find them all because they're all in the CC roots array great one last thing is conflict resolution that I call linking and unlinking so if blue owns a vertex location and it needs to change to orange because orange was the aggressor and one that off of blue I need to unlink that from blue and Link it to orange so I'll show you unlink first and I just call unlink with a vertex ID which is just an index into the array spin through its adjacent verts list and remove that remove a from the connected adjacent verts so it goes through A's connections calls it B and removes a from B and then when that's done it clears all of a connections because it's about to establish new connections for it and also it sets the team to no team and I don't really have to do that I just think it's think it's it keeps the data in sync because there's no connections now how can it possibly have a team if there's no connection so I just clear it there it's about to be set to to a team anyway so when it comes in it has an index called a I convert that into a 2d coordinate for my for my data so it asks what is the team at x and y for the north south east and west so for all of the adjacent locations about which I'm about to link it says is the team that is their equal to the team that I want to change it to that I want to link it to if it is then I connect it to the north vert and then set the team to whatever it wants to be and then likewise check South link it to that if it's applicable check East Link that check West link that so up to four connections can be made whenever a vertex needs to change but what's really cool is that you're guaranteed that all of the previous connections that it had are all cleared out so that there's no straggling data or anything like that and that's it those are the four the the three problems that I needed to solve we talked about depth-first search and how to do that I showed you the code on how to do that and the performance of depth-first search and the the adjacency list is really good for space it's the number of edges plus the number of vertex is the log of the number of verts to check if two verts are connected that's also the log of number of verts but one it's instant if you use connected components so that's both of those are very quick one is obviously instant to end to iterate through the verts adjacent to another vert it's the log of the number of verts plus the degree of that vert and the degree just means how many connections it has so it boils down to this is a really quick algorithm and it scales really well you can use this algorithm for all kinds of games specifically tile matching games so match three a collection of objects where you can tap on one and all of the connective connected objects disappear and new ones fall to take it their place it's it's really useful for that too I've seen games where you can shoot a colored bubble up to a cloud of other colored bubbles and the connection that it makes there pops those bubbles and maybe causes other unconnected bubbles to fall off if there's no other connections there and there's also lots of other non gaming applications like for example genetics molecules you know the atoms and the bonds between them circuits yeah even social networks is this friend connected to is this person connected to that person via however many friends in between and also neural networks so I hope this video helped you have access to the code and links to the algorithms that I discussed and that's it now go out there and do great things and thanks for watching

Channel: BinaryHammer

Views: 6,566

Keywords: Video Games, Algorithms, Optimization, Game Design

Id: 3Jk4chTB9j4

Length: 39min 34sec (2374 seconds)

Published: Wed Mar 14 2018