Graphs: Finding the paths between things
As part of my studies this year we were required to solve various problems to do with graphs and graph theory recursively, and we were given a specific problem to solve:
"Give a graph G and its vertices and edge's, use python to recursively check if there is a path between a given vertice A and another given vertice B of length <= 3. If there is a path then return True, otherwise return False."
While most people that have encountered graph theory before would have been able to quickly find a solution, this may not have been the best choice of question for people with little prior exposure to graphs. So firstly if you dont yet know graph theory, you should read up on it a little (Lessons 1 and 7 should be more then enough for this excercise) before continuing, and then take a look at the python solution I arrived at.
The idea itself is fairly simple, given some representation of a graph one should be able to go through each path to see if there is a route from A to B. Firstly you should look at what the terminating cases are (whether you do this recursively or not doesnt make that much of a difference, although this problem is tailored for recursion and it is asked for in the quetion). In this case we will terminate a recursive "branch" when one of 3 things happens:
- We find B
- We reach our max path length (without finding B)
- We run out of places to start a path from from the current vertex
Now if you had done anything proper in recursion you will immediately notice this problem uses a breadth first search. The basic concept is that starting from a given point A, you "start" a path for each vertex you can get to from A, and then for each of those continue the path by "continuing" multiple new paths from whatever vertex you are on. This will go through every combination of path that you could go along in the graph. Now, it is important to note that without the above limitations we would get into an infinite loop. Naturally if we find B we will always terminate completely and say that we found it, but without the second terminating case if the graph was undirected or cyclic we would never be able to find every path. So the main terminating case we need to keep in mind when solving this problem is how long is our current path.
Now, what I really wanted to share about this isnt really the solution, but the application this has to game development. There are various things you could do with the theory, I will focus on basic path finding for AI. As part of your game you would no doubt want to have some form of AI present at some stage, and path finding is an easy first step you can take into the implementation. Now, this isnt to say that you should be using this to find the best path, for that you should be using A*, no our aim today is for you to make your in game characters seem more interested in what is going on.
As part of an unseen layer in your game (an "interaction layer" if you'd like) you should have a grid to represent your game world. The logic behind making your NPCs seem part of the world without needing them to all be hard coded in their reactions is that you can then make different events happen in different places and all the NPCs will react differently according to their situation. All you would need to do is adjust the path finding above to find where to move to. The following algorithm should demonstrate what I mean better:
- Start with n = 1 (or n = x, where x is the level you want this reaction to start at).
- For reaction[n]:
- Find if the object for that reaction is nearby
- Check if the object of interest is visible (ie. in line of sight)
- If: reaction conditions met, use that reaction
- Else: n = n + 1
- Until n = number of reactions, go to 2
This is simplistic, and easy to follow. Have a list of reactions an NPC can follow, order them in a list how you want them prioritised. You could also make it so that there are various reactions that can occur in each level but that only one reaction can possible trigger from each level. You should note that you mustnt run the finding of an event all the time, and you should only run it on NPCs that are actually near enough to something to be interested (for example, a guy 10 minutes walk away wont care that you are fighting someone).
Next thing you do is when an event is triggered you can use the above logic and make the NPC react accordingly. Now Im not going to go through the implementation of this system, but by finding a route between NPC and EVENT if there is one of a maximum length you can then choose what to do. As an example:
NPC Joe is walking around town minding his own business when theres an explosion within his event range. First he sees if he cant get to the event at all (the application of the path finding), then he checks if he can see it. He can, so his first reaction is checked (n = 1), this reaction is FEAR, he needs line of sight and range, having both he finds the nearest COVER objects and hides behind it. After 5 seconds when nothing else happens the EXPLOSION object removes itself and plants an INTEREST1 object in its place. Because the interest object is in his event range this causes NPC Joe to go through the steps again, he doesnt need line of sight for INTEREST1, and his reaction (n = 2) is checked, for our event we roll a dice, he gets a 4, we decide 4 means that he would rather go home then see what it was, so he hurries home, slightly different to NPC Bob who was interested and rushed to the scene to see who was hurt.
And there you have it, Joe and Bob seem more interested in whats happening around them, and all you did was gave them new reactions to what is happening around them. Hopefully this will help you diversify the game you are making and it will help you make the game more immersive for the player in question.
Further reading:
