To install StudyMoose App tap and then “Add to Home Screen”
Save to my list
Remove from my list
Besides social media and networking sites, one of the more popular ways that this demand is met is through the constant updates and releases of new video games. However, in more recent times video games have not only become a form of entertainment but they are also a method through which many earn their living, whether it is their development or through larger esports tournaments where players can earn potentially millions. To put this in perspective in 2017 DOTA 2 prize pool totalled $24.6 million.
When looking at this industry one of the many struggles that the very first developers would have gone through is how to create and efficient movement system without compromising the user experience.
This is especially important in top-down games like DOTA 2 or League of Legends because of the nature of their movement systems and how the players will use simple mouse clicks to administer the movement commands for their in-game characters.
In this essay, I will be exploring Dijkstra's algorithm and its variant the A* search algorithm, both of which are very popular algorithms that are used to calculate movement within these games, but before we take a look at the algorithms themselves we will have to familiarise ourselves with some key terminology.
When referring to graphs in pathfinding there are two types of graphs a sparse graph and a more grid-based environment.
Verified writer
Proficient in: Computer Science For Progress
5 (234)
“ Very organized ,I enjoyed and Loved every bit of our professional interaction ”
The sparse graph will involve a series of nodes which are points, and then the edges which will connect their nodes to show traversable or walkable paths.
Whereas in a grid-based environment the nodes are interconnected and there may be some nodes which cannot be traversed. Refer to the diagram below:
In the diagrams above the green node represents the current position on the object. In the sparse graph, we are limited to the paths we can take by the predetermined edges whereas in the grid-based environment all the squares are their own nodes and it is possible to move vertically, horizontally or diagonally. The grey squares are other entities and so we cannot traverse those nodes. In essence, in the grid-based environment, assuming there are no non-traversable nodes, each node is connected to eight other nodes ie. all its neighbours.
For the purposes of this investigation, I will be using the grid-based environment for all because in games characters can usually move in any given direction as long as there are no non-traversable nodes in the vicinity.
If we were moving from any given node vertically or horizontally this would equate to a particular distance. We will name this particular distance 1 unit. However, the distance to travel from one node to another diagonally is not the same distance. This is because we have to travel a greater distance to get to the node.
To work out what this distance actually is we can use a simple piece of maths known as the Pythagorean theorem. This theorem states that given a right angle triangle angle the length of the hypotenuse (the side opposite the right angle) is equal to the sum of the squared adjacent sides square rooted. The diagram below will show it applied to the situation at hand.
We can draw in the line as below to work out the diagonal distance. Notice how we have now formed a right-angled triangle.
Now we can simply apply Pythagoras theorem:
X2 = 12 + 12
X2 = 2
X = ± 2
However, we know that the distance cannot we be a negative number and so we take 2 as the distance.
We now know that the diagonal distance is root 2. This is, in turn, evaluates to roughly 1.41. We can also scale up the figures. For example, when the horizontal and vertical distance is 10 the diagonal distance is roughly 1.41 times 10 or 14.1.
As mentioned before we can now start to work out the shortest path between the two points on a given map.
On any map, the starting point is often called the origin in my diagrams the origin is shown by a dark green node. For Dijkstra's algorithm, we use the concept of weights. The weight of the node refers to the number of units or the distance of a node from the origin.
The program uses two lists the open and closed lists.
In the open list, the nodes that are directly connected to the origin are added. We can then work out the distance from the origin to the each of the nodes in the open list by using the existing weight (which is zero at the origin) and adding the distance of the node from the origin. We also add the origin to the closed list. This closed list will tell us all the nodes that have already been visited. We now loop through the open list and set the parent of the nodes to the origin and update their weights. The parent node refers to which node we took to get to that node.
-285749285750
This diagram will show us how all the nodes around the origin are set the open list. Currently all the light green nodes are in the open list.
The nodes vertically or horizontally adjacent have a weight of 10. Diagonal nodes have a weight of around 14.
The parent of all the nodes in light green is now the origin (the dark green node).
We now set the current node to the node with the lowest weight in the open list. All the neighbours to the current node not already in the open list are added to it and the current node is added to the closed list.
-390524171450
We chose the leftmost node in the open list and added it to the closed list shown in a light blue colour.
We then added all neighbouring nodes to the open list. We can now update the nodes' weights.
Note that there are actually several nodes with the lowest weight (10). In this case any of the nodes with a weight of 10 can be chosen.
Once again we loop through the open list and update the nodes' weights. However, we now have to consider the fact that the weight of our current node is no longer zero and so we add the current weight and the distance to the node in the open list to calculate the weight for the open list node. The parent is once again added to all the nodes whose weights were updated.
Keep in mind that we only update the weights and change the parents if the newfound weight is smaller than one the node already has. When we finish this the graph looks the one on the right.
The parents for the new nodes in the open list (those with a weight greater than 14) is now the blue node in the closed list.
This process is repeated and the program terminates when the destination node is added to the closed list. The parents can now be traced back to find the shortest path to the destination node.
When everything is finished the completed path finding algorithm appear to be like this:
The A* search is a variant or Dijkstra's algorithm that follows the same methodology as the one above however unlike Dijkstra's algorithm, f(x) the function to find the weight differs slightly. In the A* search f(x)=g(x) + h(x). The g(x) is the same as the function above however the h(x) or heuristic function is new. This basically finds out the approximate distance from our currentNode to the target node.
There are many ways of finding this distance including the Manhattan, Euclidean and Octile functions all of which will work fine.
One of the heuristic functions is known as the Manhattan method. This method basically add the amount of distance you travel horizontally and vertically -266699142875
For example in this case we can see that to get from the blue node to the red node we would have to go 8 across and 2 down. So the manhattan distance is 8 + 2 which is 10.
ie: h(x) = destinationNode.getX -neighbourNode(x).getX +
destinationNode.getY - neighbourNode(x).getY
The getX() and getY()methods return the x and y coordinates or the nodes respectively. The modulus operator '' returns the absolute value of a number. Meaning that if the input is less than 0 it will multiply by -1. This is necessary because the x or y coordinates of the destination node might be less than the node we are comparing meaning we may have to travel in the opposite direction to get to the node.
Due to the A* search taking into account the approximate distances between the nodes and the target this helps optimise the search because we are prioritising nodes that are more likely to be involved in the solution. This is why the A* algorithm is often referred to as the best first search algorithm.
In the diagram above the green node represents the origin and the red node represents the destination. Likewise, the blue nodes are the nodes in the closed list whereas the green ones show us the open list. As we can see in the A* search because of using approximations we end up having to check fewer nodes in order to arrive at the optimal path. Due to the number of operations performed being significantly less, the amount of time that the program takes to execute is also reduced.
The nature of the A* search is also more apparent in this diagram as we can see how the nodes that were expanded on all focused towards the east instead of being evenly spread out like Dijkstra's algorithm. Even though this may appear to be better than the algorithm in every scenario the main problem of the A* Search lies in the heuristic function. The quality of the estimates determines whether the search will find the optimal path.
This is especially true for the admissibility of the function used. The A* search is guaranteed to give an optimal path as long as the heuristic function is admissible. If a function is admissible it means that the function will never be able to overestimate a node, in essence, the actual distance between the node and target node should never be greater than the estimated distance from the heuristic function. This is because if the estimated distance is lower than what they actually are the other possible nodes that the program can take end up looking worse than they actually are, meaning they have less chance of being used in the calculated path.
Another important thing to consider is the consistency of the heuristic function. This means we must make sure that we are using the same method of finding the estimate for all the nodes. As mentioned before there are many ways to do this but for this essay since I will be using the Manhattan method all nodes will also have to be estimated in the same way.
In the process of game development we will have to create a movement system that can provide a good experience to the user. In order to test whether the A* search is truly more suitable for use in games we have to not just theorise but also model some maps from games and see if the A* algorithm comes out on top. Before we start testing we will have to obtain some maps. For this essay I have chosen some maps from a variety of genres so that we do not end up testing under a small scope.
The independent variable that we are looking to test or change in the experiment. In this case we will be testing the suitability of the two algorithms hence 'the type of algorithm used' will be the independent variable.
Before we start we will have to make the experiment a fair test because we do not want to be comparing factors other than the algorithms themselves. To achieve this I came up with something that I will keep constant:
The computer which I will be running the maps on.
The online implementation of the algorithms I will be using
The dependant variable refers to actual data collected or what we are measuring. In this case we have two things that we can use to compare the programs. The time that the program will take to find the shortest path or the amount of operations that are performed until the program find the path. The length of the path is also something we need to look at to see if both the programs have found the optimal path given the map. For this experiment I will be focusing on the amount of instructions that were processed through the execution. This is because the run time will vary from computer to computer whereas the amount of instructions do not vary.
From the theory so far I am lead to think that the A* algorithm will always be more suitable given the heuristic function used is admissible and consistent.
Before we start running the program I will need to model the map using the online implementation.
For the First map I decided to choose the dungeon map from Dragon Age 2. This game is an rpg or a role playing game this game is quite graphically and so the amount of operations will have a large impact on the game performance and user experience.
As you can see our results will not be accurate as when transferring The graph to the program it has lost some of its quality, nevertheless it should still give up a good idea of the algorithm's efficiency and since both algorithms are tested on the same map it should not matter too much.
As you can see from the two finished calculations both of the algorithms have returned the same path.
A* Search Variant However, we can see that the A* search variant had to perform a lot less operations in order to find the same path. For this map in specific we can clearly say that the A* search is more suitable.-28574438150
For the next graph I choose a relatively popular strategy game known as Starcraft. Below will be the map I have chosen from the game and the modeling as well. Unlike Dragon Age the graphics are not as demanding and since it is a strategy game there is a larger focus on the optimisation of the algorithms.
I modeled the Big Game Hunters map from starcraft The model looks like the graph on the left.
First let us run the standard variant of Dijxtra's algorithm and observe what happens.
As you can see we have found the shortest path from the dark green node to the red node. The Details of the search are also available on the left. We can now do the same to the A* search.
At first the difference may not be that noticeable since the paths are very similar but this time we have found a suboptimal path with the A* search. However at the same time we have greatly reduced the operations that would need to have been performed.
The reason for this suboptimal calculation is because at times the algorithm overestimated the 'value' of a node, using the manhattan method, because of all the non- traversable nodes, and so it did not consider all the possible alternatives which in reality could have been better ie the function was not admissible in this case.
For games like Starcraft which is a real time strategy game players will be strategising quite carefully and so the will require precision when commanding their units, because it is a game with such a high ceiling, we could argue that in this case that the standard variant of Dijkstra is better. However, we must take into consideration that in Starcraft the user will be controlling hundreds of units at once if we take a look at the difference in the amount of operations that we will be performing the standard variant will have to perform more than 4 times the amount of instructions. This will have a large detrimental effect on the performance of the game especially because the user will be controlling so many units. For this reason I believe that the A* variant is still more suitable even though it did not find the optimal path. -3047993343275
This graph also shows the A* search on the same graph however it uses a different heuristic function. This time we used the Euclidean distance instead of the Manhattan distance. As I discussed before the heuristic function and quality of the estimates determine the efficiency of the algorithm. In this case because we used a different heuristic we got the optimal result. While still managing to keep the amount of operations relatively low.
The euclidean distance is simply the straight line distance form one node to the other. This can be calculated in a similar way to the diagonal distance, by using pythagoras theorem with two fields of the manhattan value.
Overall, I believe that in terms of performance and user experience the A* search is much better than the Standard variant of Dijkstra's algorithm however this is only when the heuristic function that we are using both admissible and consistent. The A* search is highly dependant on the quality of the estimations used and so it not as consistent as the Standard variant. Furthermore, in the scenario that the heuristic function is not admissible like the Big Game Hunter's map from Starcraft then the developer has to make a choice between the skill ceiling and user experience. In my opinion the A* algorithm is still more suitable, even in this case, because very few users actually stop whether their troops are moving optimally. On the other hand, there is a larger player base that would complain about amount performance issues.
Computer Science Extended. (2019, Nov 22). Retrieved from https://studymoose.com/computer-science-extended-essay
👋 Hi! I’m your smart assistant Amy!
Don’t know where to start? Type your requirements and I’ll connect you to an academic expert within 3 minutes.
get help with your assignment
