Extended Essay Plan

To what extent has the A* algorithm evolved from the Dijkstra algorithm and the Best-First-Search (BFS) algorithm to become the most efficient in game development?Table of contents:1. TOC o “1-3″ Introduction

1.1 Pathfinding algorithms

1.2 The importance of researching pathfinding algorithms

1.3 Efficiency of algorithms

2. Algortihms

2.1 Dijkstra’s algorithm

2.2 The Best-First Search algorithm

2.3 The A* algorithm

3. INvestigation

3.1 Hypothesis

3.2 Method

3.3 Results and analysis

3.4 Global implications

3.5 Experiment limitations

4. CONClusion

4. Bibliography

Introduction

1.1 Pathfinding algorithms

Pathfinding algorithms, also known as shortest path algorithms, are the plotting by a computer application of the shortest route between two points.1Examples of pathfinding algorithms include the A* algorithm, Dijkstra’s algorithm and the BFS algorithm. Pathfinding algorithms are a vital part of many computer systems today and are used in a variety of applications such as in video games, to find paths on virtual maps2 and in GPS (Global positioning system) to find the shortest paths and alternate routes.3 Over the years many advancements for these algorithms have been found by analyzing and adapting older versions. This allows the creation of a new, more efficient and optimal algorithm that carries out the task to the highest potential. There are two main measures that determine the quality of a pathfinding algorithm: the algorithmic efficiency, defined as a measure of the average execution time necessary for an algorithm to complete work on a set of data and how much work was require to find the path.

Pathfinding algorithms in game development

As the game industry is rapidly growing, so is the use of artificial intelligence in these games. Artificial intelligence in games is explained as ” the various logical constructs programmers use to simulate the behaviors of non –player-driven characters in a game environment.” The most basic aspect of game AI is the use of path finding algorithms to calculate the shortest path from a source to a target in various environments. This is utilized to make it interesting and realistic. The most popular algorithms for pathfinding in games used to be Dijkstra’s, BFS, depth first search and breadth first search however these eventually could not handle the rapid growth of complexity in games. Hence, other algorithms were adapted to solve this issue like the A* algorithm. This paper focuses on how the A* algorithm evolved from the Dijkstra’s algorithms and BFS algorithm to become the fastest and one of the most efficient algorithms in game development.

The importance of researching pathfinding algorithms

It is crucial to understand the importance of researching this question.

Algorithms in general are used on a daily basis not only in computing but also in our everyday lives. Every country makes use of them in both technological aspects and daily occurrences such as farming or creating complex chemical compounds. There also remains immense value in studying how to maximize their efficiency as the world becomes more automated and relies on algorithms. Moreover, maximized efficiency saves a lot of electricity and reduces the environmental consequences of automation. Specifically, the importance of studying them in game development is to ensure that algorithms can aid the increase in complexity and variety of games. Nowadays games are not only for entertainment purposes but also for education and have daily life uses. Many of them also incorporate real life aspects and the market is only threatening to grow. Hence, Researching the evolution of algorithms and analyzing how features can be adopted to create a more optimal algorithm will help to shape new algorithms and keep up with games and there plethora of uses.

Algorithms

To ensure that the algorithms are effectively compared, it is important to first understand their mechanisms and differences with regards to finding a path. This will make it easier to see which aspects from the Dijkstra and BFS algorithm are used in the evolution of the A* algorithm and it will demonstrate how these aspects have contributed to a more optimal algorithm in general and then in game development.

2.1 Dijkstra’s algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest path between nodes in a weighted graph. A weighted graph is a graph where the edges have weights or values and each label is a number. There is a fixed node called the source node and it finds the shortest paths from the source to all the other nodes, producing a shortest path tree. It is a greedy algorithm; the definition of greedy algorithm is “An algorithm paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.” This definition clearly demonstrates that Dijkstra’s algorithm is a greedy algorithm as it makes decisions based on information available at that time. The value of the distance between the nodes must be non-negative and every node must link to at least one other node. However, it doesn’t matter whether it is a directed graph, a graph with directional arrows as connection between nodes, or non-directed graph, a graph where the connection between the nodes has no direction.

Figure 3 below demonstrates how the Dijkstra algorithm works. It starts at the source node, the pink square, and then continuously examines the closest vertex, which has not yet been examined and adds its vertices to the set of vertices that have already been examined. It expands outwards from the source node until it reaches the goal node. The areas that have been scanned by the algorithm are shown below by the blue squares.

PSEUDOCODE

Figure 3 shows the Pseudo code for the Dijkstra’s algorithm. The algorithm starts with an initial node, where the algorithm begins, and then traverses through the graph till it reaches the goal node, where it stops. The aim of the algorithm is to find the path with the lowest cost from the initial node to the goal node. A temporary distance is assigned to every node, also known as the vertex. The initial node is assigned a value of 0 and every other node is assigned a value of infinity (see in figure 3). This is because it doesn’t cost anything to get to the initial node as the algorithm starts here, hence it is assigned a value of 0. However, since the other nodes distances are unknown, at the start, they are assigned a value of infinity (this a standard value that is assigned to unknown distances). Before the graph traversal begins, the algorithm creates a set of visited and unvisited nodes to help find the shortest path.

The algorithm, then, begins at the initial node. Every time the algorithm traverses through the graph, it stops and works around a current node. The same loop is run for every current node that the graph examines. After the initial node, the current node becomes the unvisited node with the smallest temporary value. Then the algorithm checks the cost from the current node to all its unvisited neighbors, a neighbor node is any node that is directly connected to the current node. The distance to the node and the weight of the branch is added up and compared to the current temporary value. If the value is smaller than the stored value, it replaces it and becomes the new temporary value for the shortest path. After all the neighbors of that node are considered, the current node will be removed from the set of unvisited nodes and added to the set of visited nodes so that the algorithm can keep track of where to go next. The algorithm continuously loops until all nodes are considered and the goal node is added to the visited set. The ending value is the value of the shortest path from the initial node to the goal node.

2.1 Best-first search algorithm

Best-first search is an algorithm that traverses a graph in order to find the shortest path to one or more goal nodes. It uses heuristics and informed search when finding a path. A heuristic function, h(n), estimates the cost of all paths from the current node to the goal node, it then compares them and goes with the path with the lowest cost first. The path is found easily and quickly, however it does not guarantee that the best path will be found. This is because a heuristic algorithm aims to find the path in a single search, even if the path is not always optimal.

Figure 4 below represents this idea. The pink square is the source node and the blue square is the goal node. If the goal node is to the south of the current node the BFS search will only focus on paths going southward. Then it generates all the possibilities and estimates the cost. The yellow squares are the nodes with the highest heuristic value (highest cost) and the black squares are the nodes with a low heuristic value (low cost).

The BFS algorithm is also a greedy algorithm like the Dijkstra algorithm as it makes the locally optimal choice at each stage. This and the use of the heuristic function are the factors that differentiate the BFS from other algorithms.

Figure 5 shows the Pseudocode for the best-first search algorithm. The algorithm begins with an initial node and goal node, just like the Dijkstra algorithm and it aims to find the shortest path between these nodes. However, unlike the Dijkstra algorithm the BFS makes use of heuristics to find the shortest path. Since it uses heuristics it aims to find the path in the ‘first search’ and hence it might not always be the optimal path.

The algorithm begins by creating a priority queue and a closed list. The initial node is the first item in the priority queue. The first step, as can be seen above, is to check if this node is a goal node. This is determined by a set of criteria that define the goal node. If it is not a goal node it is removed from the queue for evaluation. Once taken out, the heuristic is run on all the child nodes and they are then put into the priority queue, from the lowest cost first to the highest at the end. Then the first node of the queue is removed again (the one with the lowest cost) and checked if it is a goal node. If not then the node is placed in the closed list and its child nodes are evaluated and loaded into the priority queue, in order of cost. This process loops until the goal node is reached.

The BFS algorithm’s primary concern is efficiency. It considers efficiency to be the most important and so always aims to find a path in the first search even if it is not the most optimal path. This can be a major advantage at times where efficiency is extremely important and hence the reason it has been used to create new algorithms such as the A*.

2.1 A* algorithm

The A* algorithm is a pathfinding algorithm that has a variety of uses because of its performance and accuracy. The algorithm itself has evolved by making use of the Dijkstra and BFS algorithm. It utilizes the g(n) function from the Dijkstra algorithm and the h(n) function from the BFS algorithm. In other words the algorithm first determines the exact cost of the path from the initial node to the current node, using the g(n) function, and then determines the estimated cost of the path from the current node to the goal, using the h(n) function. With each iteration of the loop it determines the node that has the lowest F(n) value where F(n) = g(n) + h(n) and then continues down that path.

1143000-342900Figure 5 – Example of A* algorithm

00Figure 5 – Example of A* algorithm

The concept of the A* algorithm is demonstrated above. The pink square represents the start node and the blue represents the goal node. The yellow squares (h) represent vertices that are far from the goal and the light blue squares (g) represent vertices that are far from the start. The A* balances the use of the two functions as it moves to the goal node, calculating the f(n) and choosing the one with the lowest value. The use of this function enables the A* algorithm to find the shortest route in an ideal time and with not much work.

Comparison of the algorithms and the evolution

The Dijkstra algorithm is good in the sense that it finds the shortest path, however, the problem is that it consumes a lot of time exploring paths that are not optimal. On the other hand the BFS algorithm does not look for other paths, however, it cannot ensure that shortest path is found. The A* algorithm makes use of the advantages of the respective algorithms and at the same time cuts out the disadvantages, as the advantage of the Dijkstra is the disadvantage of the BFS and vice versa. Hence the A* algorithm has incorporated the BFS to ensure that a path is found in an optimal time and the Dijkstra’s to ensure that the shortest path is found.

In a game development perspective the adapted features of the A* enables it to be dynamic, flexible and find the shortest path using much less work. It allows it to work in all types of environments, no matter the complexity, at an optimal speed, allowing the game to work efficiently.

3. Investigation

3.1 Hypothesis

I predict that the A* algorithm will always produce the most optimal path, matching that of the Dijkstra algorithm and will always have the second highest percentage efficiency, behind that of the BFS algorithm, where percentage efficiency = path length/work done * 100.

This hypothesis is derived from the fact that the dijkstra algorithm always finds the most optimal path and the A* algorithm can do the same in most scenarios. Moreover, since the BFS uses heuristics and estimations its percentage efficiency must always be higher than that of the A* algorithm, as it focuses more on speed than ensuring the most optimal path is found. The A* algorithm uses factors of the Dijkstra and BFS algorithm to calculate paths using much less work and ensuring that the most optimal path is found.

Method

The algorithms will be tested on 6 different graphs and the data collected will be used to compare how much work was required to find a path. Each algorithm will be tested on a graph of 18×18 units (324 units in total) and a single time of 2 per graph. The work done (squares) and the path length (units) will be recorded, where work done is the amount of squares covered in total and path length is the length of the covered squares. The 6 different graphs are 2D grid version of typical game environments to demonstrate how these algorithms work in games.

These graphs are used to calculate the efficiency of the algorithm at the different complexities. The grey squares represent the obstacles, the light blue and green squares are counted to give the work done, the yellow line represents the path length and then the efficiency is calculated by doing:

57150085725Efficiency = Path length Work done × 100

00Efficiency = Path length Work done × 100

The 6 graphs:

Controlled variables:

In order to ensure that a fair test was carried out and that external factors would not affect the end result some factors remained constant.

Same simulation and set up

The same simulation was used for the 6 different types of graphs and for all the algorithms. Also it was set up the same way each time: an 18×18 units graph and the same starting point for the initial node and goal node during each type of test. If these factors are changed then the calculations differ and this leads to unfair comparison.

Use of same heuristics for the algorithms

The A* algorithm and BFS algorithm can operate with a variety of heuristics which produces slight different results. A normal game development heuristic was used to ensure that a fair comparison and conclusion could be reached.

Keeping the same tabs and background tasks

Since the simulation is run on the computer it is important to ensure that each time the simulation is run with a different algorithm, the tabs and background task on the computer being used are closed. If this is not kept constant the computer would be operating differently each time, affecting the algorithms.

Results and analysis

The results of the 6 different graphs, with the 3 different algorithms can be seen below.

Figure 3 – Simple obstacle test

Graph Algorithm Work done (units) Path length (units) Efficiency (nearest %)

Simple obstacle graph

Dijkstra’s 223 13 6

BFS 31 13 42

A* 58 13 22

This graph is to model simple objects algorithms have to work around in games. All 3 algorithms found the most optimal path but the paths varied slightly. This is possible as some graphs have multiple solutions that are all optimal. The Dijkstra algorithm was the most inefficient. Also the A* algorithm was less efficient than the BFS algorithm as it deviated in all directions from its initial node.

Figure 6 – Shape obstacle test

-2286001814195Dijkstra’s algorithm

BFS algorithm

A* algorithm

Dijkstra’s algorithm

BFS algorithm

A* algorithm

Graph Algorithm Work done (units) Path length (units) Efficiency (nearest %)

Shaped obstacle graph Dijkstra’s 294 21 7

BFS 67 21 31

A* 133 21 16

This graph had an obstacle in a T shape to make it even more complex Dijkstra’s algorithm was once again the least efficient, with its work done covering almost all the squares. The A* algorithm remained less efficient than the BFS and they both decreased in efficiency.

Figure 7 – Random obstacle test

Graph Algorithm Work done (units) Path length (units) Efficiency (nearest %)

Random obstacles graph

Dijkstra’s 297 20 7

BFS 52 20 38

A* 109 20 18

This graphs tests the algorithms ability to find a path when many random obstacles are present. This is something that is implemented a lot in game development. The BFS did the least work, by far and the Dijkistra’s algorithm almost checked all the nodes on the grid. All algorithms found the most optimal path but in very different efficiencies.

Figure 7 – Symmetrical obstacles test

Graph Algorithm Work done (units) Path length (units) Efficiency (nearest %)

Symmetrical obstacle graph

Dijkstra’s 310 29 9

BFS 159 41 26

A* 185 29 16

This is used in game development when the same obstacles are placed symmetrical to one another. The major difference between the work done of the BFS and A* to that of Dijkstra’s demonstrates the heuristic function in the algorithms. BFS also found a significantly larger path than the other two and hence its efficiency didn’t differ much from A*’s.

Figure 7 – Two fixed paths test

Graph Algorithm Work done (units) Path length (units) Efficiency (nearest %)

Two fixed paths graph

Dijkstra’s 72 34 47

BFS 38 36 95

A* 62 34 55

Games usually have an option of a few paths that lead to the same place. These paths are straightforward, with no obstacles or tricks. However, one path is shorter than the other and this test the algorithms ability to do so. Though the BFS was very efficient here, the highest efficiency of all other test, it did not choose the shortest path. The other two choose the shortest path route but in doing so explored all/most of the nodes.

Figure 7 – Maze test

This graph is used to test both the algorithms ability to work around mazes in games and test the algorithms ability in maze games, like snake. The BFS was very efficient but didn’t find the shortest path once again. The Dijkstra’s and A* were very close in efficiency demonstrating that there are still some levels of complexities that the A* struggles with.

Graph Algorithm Work done (units) Path length (units) Efficiency (nearest %)

Maze graph

Dijkstra’s 89 29 33 (32.6)

BFS 35 31 89

A* 87 29 33 (33.3)

Overall analysis

The data gathered is consistent with the research carried out. It proves that the Dijkstra’s algorithm is always the least efficient and that the BFS is always the most efficient. It also shows that the BFS algorithm doesn’t always find the shortest path whereas, the A* algorithm always found the shortest path with a relatively optimal work done and efficiency.

Another interesting idea highlighted in the data was that though the A* algorithm is efficient in most levels of complexities, it still struggles in certain environments. This re iterates the importance of researching this question and the evolution of algorithms to ensure that algorithms can aid game development effectively.

Real life game example

A game in which this evolution can be demonstrated is Civilization V. It is a strategy game in which the player must lead a civilization from the past to the future on a map. The older Civilization IV had less obstacles and was on a square grid map where as Civilization V has a variety of obstacles and is on a hexagonal map. Dijkstra’s algorithm could be used on Civilization IV but started facing problems on Civilization V.

The first problem it faced was that it could not get around the obstacles and kept getting stuck behind them or in them as demonstrated below. However the A* algorithm could because of its dynamic nature.

The second problem it faced was that on a hexagonal map it could not find a path in an optimal amount of time. This is because the path was more complex and there were more nodes to explore. However the A* could find it in an optimal time as it doesn’t need to check all the nodes because of the heuristic aspect.

Having said that, the A* algorithm still faces problems in dealing with the more complicated parts of the game and hence this emphasizes the importance of researching the evolution of algorithms to ensure that algorithms will be able to keep up.

Global implications

There are so many uses of algorithms in the world. They are the backbone of a vast range of activities and serve many different purposes. Arguably the most famous uses for pathfinding algorithms are in GPS systems and game development. However, they are used in many other circumstances. They are used to design transport networks to try and find the fastest route between two points, which saves time and reduces air pollution. Moreover they are used to develop robots that explore places that are hard to reach by humans, like space. This supports research and to enhances solving problems in those areas. Scientific uses include finding the shortest metabolic pathway to combat diseases. The idea behind this is that there is a set of enzyme catalyzed biochemical reactions by which a living organism transforms an initial (source) compound into a final (target) compound. The pathfinding algorithm views the set of possible reactions (paths) and then determines the metabolic pathway (path with lowest cost) of the enzyme. The plethora of uses means that developing efficient algorithms such as the A* will have extremely positive impacts on society.

Experiment Limitations

Experiments carried out on only one software: Since the experiment was carried out on online software that was not tested before, the reliability of this software is not certain. The use of only one software means that no repeats can be done and in turn means that there could have been systematic errors in the experiment.

Solution: Find another pathfinding software and run the exact same experiment on this, to confirm reliability of the results. If the results differ find third software and do the same.

Hard to test higher complexity game development environments:

The software used only allows a certain amount of complexity to be reached. Some game environments are best tested in actual games and their results measured by their ability to complete a task. This would allow further comparison into specifically which environments the A* algorithm is the most efficient by evolving through the Dijkstra’s and BFS.

Solution: Find a program that can run the same game using the three different algorithms. Test the algorithms by giving it a task to achieve in different environments.

Future extensions:

This paper studies three algorithms but many other pathfinding algorithms are used in game developments. Research into the other algorithms could be carried out to each ones benefit specifically. This can then be used to evaluate how other algorithms could be developed using aspects of previous ones.

This paper focuses on the pathfinding aspect of algorithms in game development, however other aspects could be explored. This includes implementation, memory, space efficiency etc

Conclusion

As demonstrated and analyzed from the data collected above it can be concluded that the A* pathfinding algorithm is the most efficient algorithm that always finds the shortest path in an optimal amount of work. It is also very dynamic and can solve problems with different complexities. By adopting features from both the Dijkstra and BFS algorithm, it is able to solve problems to the same standard as Dijkstra’s algorithm but more efficiently and to a higher stander than the BFS.

This means that the A* algorithm has became the most optimal and efficient and is widely used to solve all types of problems. The adapted features ensure that it can solve problems of all complexities efficiently. The results above fully support this as at all levels of complexity the A* algorithm found the most optimal path and in a relatively high amount of efficiency compared to the others. Though the results showed that the BFS algorithm was consistently more efficient than the A* algorithm it didn’t always find the optimal path, which can be seen in the final test. In regards to the Dijkstra algorithm, though it always found the most optimal path like the A* algorithm, it was highly inefficient.

My hypothesis was accurate but there was one issue with it. The hypothesis said that the A* algorithm will always be less efficient than the BFS algorithm, however not a broad enough range of complexities and number of graphs were tested to certify that it will always be less efficient. It can be inferred that in most situations it will have a lower percentage efficiency but its dynamic nature means that in certain situations it could be more efficient.

The Dijkstra algorithm ensures that the shortest path is found, however it is much slower than the BFS algorithm.

This shows that compared to the Dijkstra algorithm, BFS is much faster.

The A* algorithm, hence, used the most optimal features of both the Dijkstra algorithm and BFS algorithm to become the most efficient. It is the most efficient algorithm as it takes into account both the cost from the initial node to the current node and the current node to the goal node. This enables it to be dynamic, flexible and find the shortest path using much less work. In comparison to the other algorithms, the evolution of the two features in the A* algorithm, enables it to produce results to the same standard as the Dijkstra algorithm and at a better standard then the BFS algorithm.