This lesson will outline the basics of implemeting the A* (A star) pathfinding algorithm for usage in a two dimensional grid.

Roblox has a built-in PathfindingService, but it often isn't the best choice for a game. PathfindingService is great for pathfinding in a 3 dimensional space. However, the nodes along the path are disorganized and often not well-aligned. If you'd like to constrain your path nodes into a grid-space (think Minecraft or any other voxel-based game), or you'd like to use pathfinding in a two-dimensional grid-space, it may be in your best interest to implement a custom pathfinding algorithm.

A common algorithm used to implement pathfinding is known as 'A*', (pronounced 'A star'). It is used in many modern-day products, including Google Maps, Uber, Lyft, etc.

The input to the pathfinding function is a two-dimensional table of numbers that represents the world. Further, a starting position and a goal position (represented here as *Vector2*) are inputted.

```
function CalculatePath(worldGrid, start, goal)
```

*worldGrid* is a two-dimensional table made up of *costs*. These *costs* can be used to describe a two dimensional world. The purpose of A* is to find a path within the world such that the total cost of a path is minimized. This is best understood with an example:

```
local worldGrid = {
{1, 10, 1, 1},
{1, 10, 10, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
}
local start = Vector2.new(1, 1)
local goal = Vector2.new(4, 1)
local bestPath = CalculatePath(worldGrid, start, goal)
```

Imagine that *worldGrid* represents a bird's eye view of a grid. Each value represents how "hard" it is to walk through that part of the grid. In this example, imagine that the value *1* represents an empty grid-space and that the value *10* represents a wall, which should be avoided by the path. The values *start* and *goal* represent coordinates in the grid. In this example, *start* represents the top left spot in *worldGrid* and *goal* represents the top right spot. *bestPath*, the value returned by the call to *CalculatePath*, is a table of Vector2 coordinates. Let's print out the coordinates and see what we get:

```
for _, coord in ipairs(bestPath) do
print(string.format("[x: %d, y: %d]", coord.X, coord.Y))
end
-- output:
-- [x: 1, y: 1]
-- [x: 1, y: 2]
-- [x: 1, y: 3]
-- [x: 2, y: 3]
-- [x: 3, y: 3]
-- [x: 4, y: 3]
-- [x: 4, y: 2]
-- [x: 4, y: 1]
```

Notice that these coordinates trace out a path inside of *worldGrid* and that the walls, denoted by cost *10*, are avoided. Also notice that the first element in *bestPath* is *start* and the last element in *bestPath* is *goal*.

The output from CalculatePath is a table of coordinates that represent the best-possible path, where the first element in the table is *start* and the last element is *goal*. Please see the example provided above.

Note: From here on, I will use the term *node* to refer to a single point in the 2D grid.

*openSet* is a table containing nodes that we're currently exploring. Initially, it contains only the *start* node, as that is the first node in the path. Repeatedly, the algorithm picks the least-cost node from the *openSet*, then checks the other nodes next to it to see if they should be added to the path.

The *cameFrom* table is used to determine, well, where a node came from. It'll make more sense in the code below.

The *costSoFar* table is used to count the total cost it took to reach a node. Imagine node *A* has cost *10* and node *B* has cost *20*. If node *C* is reached by exploring *A*, then *B*, then finally reaching *C*, then *costSoFar[C] = 30*.

As mentioned previously, A Star works by finding the path of least-cost from *start* to *goal*. Along the way, we calculate a cost value at each node that represents how much cost we've accumulated so far. The cost function *f(node)* is given as follows:

f(node) = g(node) + h(node)

Easy enough! The value *g(node)* is called the *backward cost* and the value *h(node)* is called the *forward cost*. If you've ever learned about other pathfinding algorithms, you might recognize the idea of a backward cost. The backward cost is how much cost was accumulated to reach *node*. It can be found using the *costSoFar* table mentioned earlier. The *forward cost* is specific to the A Star algorithm. It's simply a value that says how far away the node we're at is from the *goal* node. There are many different functions that can be used for *h(node)*. These functions are called *heuristic functions*. In this lesson, I will use the Manhattan Distance function, but there are many other valid functions that can be used. The Manhattan Distance function is given by:

manhattanDistance(node) = abs(goal.X - node.X) + abs(goal.Y - node.Y)

A close reader might notice that the manhattenDistance is zero if *node == goal*. This is not a coincidence. When we've reached the goal, there is no more forward cost!

```
function CalculatePath(worldGrid, start, goal)
local WIDTH = #worldGrid
local HEIGHT = #worldGrid[1]
-- make sure input coordinates are within the grid
assert(start.X >= 1 and start.X <= WIDTH)
assert(start.Y >= 1 and start.Y <= HEIGHT)
assert(goal.X >= 1 and goal.X <= WIDTH)
assert(goal.Y >= 1 and goal.Y <= HEIGHT)
-- tables used to represent the pathfinding state
local nodeSet = {}
local openSet = {}
local cameFrom = {}
local costSoFar = {}
local path = {}
local winnerNode = nil
-- initialize nodeSet. each entry gets its coordinate
-- value, its cost value, and f, which represents f(node)
local nodeSet = {}
for i = 1, WIDTH do
nodeSet[i] = {}
for j = 1, HEIGHT do
nodeSet[i][j] = {
coord = Vector2.new(i, j),
cost = worldGrid[i][j],
f = nil
}
end
end
-- references to our start and goal nodes
local startNode = nodeSet[start.X][start.Y]
local goalNode = nodeSet[goal.X][goal.Y]
-- helper function used to insert into the openSet. openSet is
-- sorted by its nodes' cost values, so make sure to
-- insert at the correct index
local function putInOpenSet(node, newCost)
node.f = newCost + manhattanDistance(node, goalNode)
for i, existingNode in ipairs(openSet) do
if node.f < existingNode.f then
table.insert(openSet, i, node)
return
end
end
table.insert(openSet, node)
end
-- initial state of the A* algorithm
costSoFar[startNode] = 0
openSet[1] = startNode
-- main A* loop
while #openSet > 0 do
-- openSet is sorted, so the least-cost node
-- is located at index 1
local currentNode = openSet[1]
table.remove(openSet, 1)
-- if we've reached the goal coordinate, then we're done
if currentNode.coord.X == goal.X and currentNode.coord.Y == goal.Y then
winnerNode = currentNode
break
end
-- explore all neighbors of currentNode
local neighbors = getNeighbors(currentNode)
for _, neighbor in ipairs(neighbors) do
local newCost = costSoFar[currentNode] + worldGrid[neighbor.coord.X][neighbor.coord.Y]
if not costSoFar[neighbor] or newCost < costSoFar[neighbor] then
costSoFar[neighbor] = newCost
putInOpenSet(neighbor, newCost)
cameFrom[neighbor] = currentNode
end
end
end
-- follow the 'breadcrumbs' backwards to the starting node
-- so we can retrace the path we took
while winnerNode ~= startNode do
table.insert(path, 1, winnerNode.coord)
winnerNode = cameFrom[winnerNode]
end
return path
end
```

You might notice that there's no implementation yet for *manhattanDistance* or *getNeighbors*. These functions are implementation-dependent, meaning you may implement them however you'd like. For this tutorial, I will make *getNeighbors* return nodes that are north, south, east and west of the parent node, but I will ignore diagonal neighbors. I will also implement *manhattanDistance* as I described earlier in this lesson.

```
-- helper function for getNeighbors
local function isValidPosition(x, y)
return x >= 1 and x <= WIDTH and y >= 1 and y <= HEIGHT
end
local function getNeighbors(node)
local neighbors = {}
if isValidPosition(node.coord.X - 1, node.coord.Y) then
table.insert(neighbors, nodeSet[node.coord.X - 1][node.coord.Y])
end
if isValidPosition(node.coord.X + 1, node.coord.Y) then
table.insert(neighbors, nodeSet[node.coord.X + 1][node.coord.Y])
end
if isValidPosition(node.coord.X, node.coord.Y - 1) then
table.insert(neighbors, nodeSet[node.coord.X][node.coord.Y - 1])
end
if isValidPosition(node.coord.X, node.coord.Y + 1) then
table.insert(neighbors, nodeSet[node.coord.X][node.coord.Y + 1])
end
return neighbors
end
local function manhattanDistance(node, goalNode)
local xDist = math.abs(goalNode.coord.X - node.coord.X)
local yDist = math.abs(goalNode.coord.Y - node.coord.Y)
return xDist + yDist
end
```

Unlike PathfindingService, if you want to use this algorithm, it is up to you to call *CalculatePath* and convert the path coordinates into their respective world coordinates.

There are definitely faster ways of implementing A* than the code I provided here. If you'd like to speed the algorithm up, try using a *MinHeap* or a *FibonacciHeap* instead of a simple sorted array to represent *openSet*. I wanted to try to keep the explanation here simple, and I thought going with a sorted array was my best bet.

To close, I'd like to suggest using other tutorials on A* along with this one. This doesn't go super in-depth into how the algorithm works, but instead gives a brief overview. I think it's helpful to see how A* can be implemented in a Roblox context, hence this tutorial.