### Genre: blog_post

#### Student id: h15

# A* Pathfinding Algorithm

### Table of Contents

**Chapter 1: Introduction**

-**A to B**

-**Connect The Dots: Graphs**

**Chapter 2: Meet the Algorithms**

-**Bro #1: Dijkstra’s Algorithm**

-**Bro #2: Best-First Search Algorithm**

-**A* Is Born**

**Chapter 3: More on A***

-**Weighted Tiles**

-**Suboptimal Path**

-**Comparisons**

**End: Expanding Horizons**

### Chapter 1: Introduction

-**A to B**

-**Connect The Dots: Graphs**

### A to B

Okay, so I have this dilemma: How do I get from A to B as quickly as possible? Hmmm, maybe we can just guess and check like this? That’s nice and dandy and all, but we really shouldn’t depend on luck for these things. What if we make this map a little more complicated? Riiight… We need a more procedural way to do this. That’s where these guys come in handy. They’re what you call algorithms, or a set of well-defined rules in sequence. They’ll show you how to get from A to B for any map (if there is a path). Dijkstra’s is guaranteed to give you the shortest path, but he spends a lot of time exploring the map. Best-First is speedy compared to Dijkstra’s because he narrows his search to areas near the goal. However, because his search is narrower, he can sometimes give a suboptimal path. A* is the star of this post. He’s a combo of the two; he notes how far he is from the start like Dijkstra’s but also focuses on the goal like Best-First. Anyway, before you really get to know them, you need to understand some basics first. So! That leads us into graphs!### Connect The Dots: Graphs

A graph is a collection of nodes or vertices, connected by edges. A square has 4 nodes and 4 edges: The nodes represent some sort of data, so we don’t need to depict them as points like above. Think of constellations! Ah, but how does that relate to our problem? Well, let’s look at our map again. In this case, the nodes represent our terrain tiles, and the edges represent the connection between adjacent tiles (directly horizontal/vertical or diagonal). Throughout, I will use node and tile interchangeably, leaning towards node. The graph representing our tile map is shown below. To further clarify, let’s look at tile A. There are 8 adjacent tiles connected to A directly. We call these tiles “neighbors” of A. Got it? Great! We can finally move on to our three algo brothers. Shhh, shhh, A*, it’s not your time to shine yet. We need to look at your bros first.### Chapter 2: Meet the Algorithms

-**Bro #1: Dijkstra’s Algorithm**

-**Bro #2: Best-First Search Algorithm**

-**A* Is Born**

### Bro #1: Dijkstra’s Algorithm

Dijkstra's Algorithm is like a dog who's slow but very thorough in his search. It finds the shortest path from a source node to all other nodes. Each of our nodes holds some data. The main pieces of data they hold are (1) the tentative cost from the start A to the node and (2) the parent of the node (i.e. the previous node that this node came from). Notice how I say “cost” rather than distance. In a graph, we can give our edges any value; it doesn’t necessarily have to be distance between nodes. Think of if we wanted to add a body of water to the map: If we wanted to mark the body of water as more difficult to cross than the grasslands, we can make the cost to cross it greater than that of grass. But for now, we’ll ignore any extra terrain until we meet A* for simplicity.Now, if we haven’t reached the nodes yet, how do we know that information? Ah, that’s a good point. Really, we don’t know, so we will initialize all of the nodes, except A, with an infinite distance and say that they have no parent. Giving them an infinite distance may seem weird, but this ensures that we update it the first time we find a path to it (since the cost we find to it will definitely be less than infinity). We also have a list, initially empty, that tracks the nodes we visited. To begin the algorithm, we place A on this visited list and then repeat the following steps until we run out of nodes to visit.

(1) Find an unvisited node
closest to our current node

(2) Go to that node and mark it as visited.
This means that we have found the shortest path from A to the current node.
Thus, if the new node is our goal, we can stop the algorithm. The steps
following it are to ensure that we also get the shortest path from A to its
neighbors. But really, if we reached the end, we don’t care about them anymore.
But if this wasn’t the goal, go on to 3)

(3) Look at all of the neighbors
of this new node. If the cost of the path going from A to the neighbor in which
we pass through the current node is shorter than any previous distance to the
neighbor, update it with the shorter path (cost and parent). Another way to look
at this is that the cost from A to the particular neighbor we’re looking at is
the cost from A to the current tile + the cost of the current tile to the
particular neighbor.

### Bro #2: Best-First Search Algorithm

Best-First Search is like a speedy bunny who is so focuses on the end goal that he ends up ignoring potentially better paths. Unlike Dijkstra’s, this algorithm uses a heuristic to estimate the shortest path between A and B (recall that Dijkstra’s is from A to any other node). A heuristic is a method where we use an educated “guess” to lead us to the solution. What you did before was randomly guessing. This is using an educated guess as a guide. Think of a detective who’s searching for a criminal. If she doesn’t have anything to go off, she has to visit every district. But if she gets a good clue that the criminal is around District A, she can direct her investigation there. We can think of the heuristic as a tipoff.In Best-First, the heuristic is the estimated cost from the current node to the end node B. There are various ways to get the heuristic value, but the most common way is with the Manhattan method. This method counts the distance traversed only horizontally and vertically to get to the end, ignoring any diagonal movement and obstacles. This distance, also called the taxicab distance, is named after the New York borough Manhattan, which is known for its grid-like streets. Best-First trades accuracy for speed. If we have no obstacles, BFS works well. Below we go through a simple run-through of Best-First. The numbers on the tiles are the Manhattan distance from those nodes to B. But if we end up introducing a wall, the path will resemble this: That’s because Best-First only thinks of the distance to the end and fails to update the path prior to the wall. In this case, if the wrong lowest cost is chosen, it will keep going and disregard early nodes even if they turn out to be more optimal later. Remember choosing between lowest cost nodes didn’t matter for Dijkstra’s because he goes back to check, but it matters for Best-First because he’ll keep going towards nodes closer to the end. Anyway, that’s all you really need to know, so let’s finally meet A*!

### A* Is Born

A* is a fusion of Dijkstra’s and Best-First.He takes into account both the cost from the start to the current node and the cost from the current node to the end.

F = G + H

Where

G = cost from the start to the current node

H = estimated cost from the current node to the end

G will be calculated the same way as in Dijkstra’s while H will be calculated the same way as in Best-First with the Manhattan distance. Remember, we say H, the heuristic value, is an estimate because there are many things that it doesn’t take into account, like obstacles. We’ll go back to the steps outlined for Dijkstra’s, except we will update it so that we inspect the nodes with the lowest F cost first.

To begin the algorithm, we place A on the visited list and then repeat the following steps until we run out of nodes to visit:

(1) Find an unvisited node with the lowest F cost.

(2) Go to that node and
mark it as visited. If the new node is our goal, stop the algorithm; else, go on
to 3)

(3) Look at all of the neighbors of this new node. If the G cost of
the path going from A to the neighbor in which we pass through the current node
is shorter than any previous distance to the neighbor, update it with the
shorter path (cost and parent).

### Chapter 3: More on A*

-**Weighted Tiles**

-**Suboptimal Path**

-**Comparisons**

### Weighted Tiles

Let’s say we decide to add a river to our map. We can cross it, but it takes a lot of effort to, so we decide to add an extra value of 30 on top of the normal 10 for going horizontal or 14 to go diagonal. This will make the algorithm skirt around the river to find a less costly way to get to B.### Suboptimal Path

Hey, A*! You’re doing so well! What if we add to this river? Let’s go back to where it’ll change. At some point, we’ll get here: And after we run through completely, we’ll get this: That gives us this path: Pretty nice! I think tha- WAIT A MINUTE. THAT’S A SUBOPTIMAL PATH. The optimal one is this: Alright, back up. What just happened? Well, A* is taking after his brother First-Best. At some point we have to choose a lowest cost node (refer back to the image above where the lowest cost node of value 78 is chosen). The estimates place those nodes on the same value, but if we look closely, we can see that the G value of the top value 78 node should be a bit less (because we can get to B through diagonals). This may happen depending on how estimates and lowest cost nodes are chosen during implementation, so just be aware!### Comparison

Besides that occasional mishap, which can be fixed with different implementations, A* is a good combination of Dijkstra’s and Best-First. Let’s do a comparison of the algorithms. Below is a run-through of the three algorithms on a large map. It’s important to note that diagonals are not counted as neighbors here, so we can only move directly horizontally or vertically. Dijkstra’s spends more time exploring the map and gets the correct shortest path. Meanwhile, Best-First, doesn’t spend as much time exploring but also doesn’t find the shortest path. Instead, he bumps into the wall before correcting himself. Lastly, A* spends only a bit of time exploring and finds the correct path.### End: Expanding Horizons

There’s quite a lot you can do with pathfinding! In this post, I showed you three pathfinding algorithms: Dijkstra’s, Best-First, and A*. We focused on A* because it combines the efficiency of Dijkstra’s with the speed of Best-First. A* is the most popular pathfinding algorithm in game development. If you’re interested in learning more, start checking out how weights can affect your units’ movements. For example, you can add them to particular terrain tiles like we did above with the river or subtract them from tiles acting as stairs/teleporters, which take you closer to the target. Also, your tiles don’t have to be squares. You can use hexagonal shapes, and the algorithms still work the same. That actually makes the math easier since the distance to each neighbor is equal. Additionally, it’ll be good to consider movement restrictions, such as those dealing with cutting corners or units that takes up more than one tile space. I recommend checking out the sources below too. RedBlobGames provides great interactive visuals on the algorithms. The author doesn’t use diagonal neighbors in his examples (so only a max of four neighbors for a node), but don’t be confused! The algorithms work the same way!

That’s all for now! Happy pathfinding!

### Sources

Patrick Lester (2005, Jul 18) A* Pathfinding for Beginners. Retrieved fromw http://www.policyalmanac.org/games/aStarTutorial.htm.

Amit Patel (2016, Jun). Introduction to A*. Retrieved from http://www.redblobgames.com/pathfinding/a-star/introduction.html.

Kevin Thompson (n.d.). Taxicab Geometry. Retrieved from http://taxicabgeometry.altervista.org/general/definitions.html.

hakimio (2012, Feb 23). Hexagonal Grid: Path-finding Using A* Algorithm. Retrieved from https://tbswithunity3d.wordpress.com/2012/02/23/hexagonal-grid-path-finding-using-a-algorithm/