# What is star A routing algorithm #

In game development, there is often a need to let the player controlled character automatically find the way to the target location, or let the AI character move to the target location. The actual situation may be very complex. For example, there are obstacles on the map that cannot be passed, or rivers and swamps that need to pay a price (time or other resources). We want to let the character find a path to reach the target at the least cost, Some special algorithms need to be used, and the A-star routing algorithm is one of the most widely used routing algorithms at present. The highly praised A* Pathfinding project plug-in on the unity asset store is also implemented based on the A-star routing algorithm. In short, the A-star algorithm is an algorithm to find the shortest path and avoid obstacles.

# Basic concept of A-star algorithm #

To realize the A-star algorithm, we first need to abstract the complex game map into a pathfinding grid. The simplest way is to divide the game map into multiple square units or regular polygon units, or into non-uniform convex polygons. These grids can be regarded as "pathfinding points". The finer the grid, the better the pathfinding effect, but the greater the amount of calculation, so for the actual game environment, We need to balance the performance and effect.

The basic idea of the A-star algorithm is to use these grids to realize path finding, traverse the surrounding points from the starting point, find the point most likely to be on the shortest path, and continue to traverse around based on this point until it reaches the end point, and the path will be found.

It can also be seen from this idea that the A-star algorithm can only get an approximate optimal solution. In fact, for the routing problem, there is often more than one optimal solution. If you have to find all the solutions, you can only traverse all possible paths one by one, but this is too inefficient. Therefore, the A-star algorithm does not traverse the whole map, but only the points on the shortest path and the points around it, Therefore, an approximate optimal solution is obtained.

So how to determine which point is most likely to be on the shortest path when traversing the surrounding points? This is the core of star A algorithm: F=G+H

Each wayfinding point has three attributes: F, G and h. f can be understood as the total cost of passing through this point. The lower the cost, of course, this point is more likely to be on the shortest path. G is the cost from the starting point to this point, and H is the cost from this point to the end point. The sum of these two costs is the total cost of this point. For specific calculation, an example is given below.

We also need two sets, one is the open set and the other is the close set. The open set stores the points for which the cost has not been calculated, and the close set contains the calculated points. At the beginning, there is only a starting point in the open set and no element in the close set. Each iteration takes the point with the smallest F in the open set as the base point, and the adjacent points around the base point are treated as follows:

(1) If this point is an obstacle, ignore it directly.

(2) If this point is not in the open table and the close table, the open table is added

(3) If the point is already in the open table and the cost of the path where the current base point is located is lower, update its G value and parent

(4) If this point is in the close table, ignore it.

After processing, add the base point to the close set.

When the end point appears in the open table, the iteration ends.

If the open table is empty before reaching the destination, there is no path to reach the destination.

# Implementation of A-star algorithm #

Let's start to implement the simplest A-star algorithm. The A-star algorithm has quite a lot of changes for the actual development. How to design it depends on the needs of the game. Here, unity is used to realize the most basic 2D square grid pathfinding. In the actual development, unity's navigation grid or A* Pathfinding Project plug-in can also be directly used.

In this implementation, I define a 10x10 grid, which has some impassable obstacles.

public class Point { public int X; public int Y; public int F; public int G; public int H; public Point parent=null; public bool isObstacle = false; public Point(int x,int y) { X = x; Y = y; } public void SetParent(Point parent,int g) { this.parent = parent; G = g; F = G + H; } }

Here, a Point class is defined to represent each wayfinding Point, X and Y represent coordinates, F, G and H are the three attributes mentioned above, isObstacle represents whether the Point is an obstacle (unable to pass), and parent represents the parent node of the Point. Whenever we traverse to the next Point that can be on the shortest path, we set its father as the current node, In this way, after the end of the path finding, we can go back to the starting Point step by step by visiting the parent node and store the path.

using System.Collections; using System.Collections.Generic; using UnityEngine; public class AStar : MonoBehaviour { public const int width = 10; public const int height = 10; public Point[,] map = new Point[height,width]; public SpriteRenderer[,] sprites = new SpriteRenderer[height, width];//One to one correspondence between picture and node public GameObject prefab; //Pictures representing nodes public Point start; public Point end; void Start() { InitMap(); //Test code AddObstacle(2, 4); AddObstacle(2, 3); AddObstacle(2, 2); AddObstacle(2, 0); AddObstacle(6, 4); AddObstacle(8, 4); SetStartAndEnd(0, 0, 7, 7); FindPath(); ShowPath(); } public void InitMap()//Initialize map { for(int i=0;i<width;i++) { for (int j = 0; j < height; j++) { sprites[i, j] = Instantiate(prefab, new Vector3(i, j, 0),Quaternion.identity).GetComponent<SpriteRenderer>(); map[i, j] = new Point(i, j); } } } public void AddObstacle(int x,int y)//Add obstacles { map[x, y].isObstacle = true; sprites[x, y].color = Color.black; } public void SetStartAndEnd(int startX,int startY,int endX,int endY)//Set start and end points { start = map[startX,startY]; sprites[startX, startY].color = Color.green; end = map[endX, endY]; sprites[endX, endY].color = Color.red; } public void ShowPath()//Display path { Point temp = end.parent; while(temp!=start) { sprites[temp.X, temp.Y].color = Color.gray; temp = temp.parent; } } public void FindPath() { List<Point> openList = new List<Point>(); List<Point> closeList = new List<Point>(); openList.Add(start); while(openList.Count>0)//Continue as long as there are elements in the open list { Point point = GetMinFOfList(openList);//Select the point with the lowest F value in the open set openList.Remove(point); closeList.Add(point); List<Point> SurroundPoints = GetSurroundPoint(point.X,point.Y); foreach(Point p in closeList)//Delete the points that are already in the closed list in the surrounding points { if(SurroundPoints.Contains(p)) { SurroundPoints.Remove(p); } } foreach (Point p in SurroundPoints)//Traverse around points { if (openList.Contains(p))//The surrounding points are already in the open list { //Recalculate G. if it is smaller than the original G, change the father of this point int newG = 1 + point.G; if(newG<p.G) { p.SetParent(point, newG); } } else { //Set up father and F and join the open list p.parent = point; GetF(p); openList.Add(p); } } if (openList.Contains(end))//As long as there is an end, it ends { break; } } } public List<Point> GetSurroundPoint(int x,int y)//Get a point around a point { List<Point> PointList = new List<Point>(); if(x>0&&!map[x-1,y].isObstacle) { PointList.Add(map[x - 1, y]); } if(y>0 && !map[x , y-1].isObstacle) { PointList.Add(map[x, y - 1]); } if(x<height-1 && !map[x + 1, y].isObstacle) { PointList.Add(map[x + 1, y]); } if(y<width-1 && !map[x , y+1].isObstacle) { PointList.Add(map[x, y + 1]); } return PointList; } public void GetF(Point point)//Calculate the F value of a point { int G = 0; int H = Mathf.Abs(end.X - point.X) + Mathf.Abs(end.Y - point.Y); if(point.parent!=null) { G = 1 + point.parent.G; } int F = H + G; point.H = H; point.G = G; point.F = F; } public Point GetMinFOfList(List<Point> list)//Get the point with the lowest F value in the set { int min = int.MaxValue; Point point = null; foreach(Point p in list) { if(p.F<min) { min = p.F; point = p; } } return point; } }

The above is the code of star A algorithm. I use A 100x100 pixel picture to represent each node, and modify their color to represent the starting point, ending point, obstacle and path. Here, I calculate that the cost of moving each grid is 1, so the g value of the starting point is 0, G+1 for each traversal, and H is the sum of the differences between the current node and the ending point on the x-axis and y-axis.

Final effect (green represents the starting point, red represents the end point, black represents the obstacle, and gray represents the path)

Before pathfinding

Pathfinding results

# last #

Star A pathfinding has quite A lot to expand. As long as we grasp the core, we are constantly calculating the cost of surrounding points and finding the path to the end at the lowest cost. This cost can be calculated according to various complex situations. For example, the AI of an FPS game, in which players will certainly attack the enemy within the fire range, At this time, if you are exposed to the player's gun in order to take the shortest path, the gain is not worth the loss. At this time, you can increase the generation value of the points within the player's attack range, so that AI can make A trade-off between the shorter path and the risk of attack, or there are reward props in A certain place. At this time, you can reduce the generation value of the points near the reward props, so that AI is more inclined to take some routes to obtain props. In short, you understand the idea of the algorithm, It can be flexibly applied to various pathfinding situations.