This project uses an A-star alogorithm to connect two nodes on a grid. The user chooses the start and end points, and is able to build walls for the algorithm to navigate. The algorithm will then find a path between the two points and the resulting path is indicated by changing the colour of the nodes.
The algorithm is initialized with the position of the first cell. It then examines the cells surrounding it, ignoring any walls or out-of-bounds locations, and assigns a G cost, which is based on the examined cell's position relative to the current cell. Cells that are connected vertically or horizontally are given a score of 10, whereas cells that are connected diagonally are given a score of 14, 14 being roughly equal to the length of a hypotenuse of a triangle with two sides of length 10. The cells that are assigned scores are added to a list of cells to be examined.
On each subsequent iteration of the algorithm, the cell with the lowest F cost is chosen as the cell to be examined. The F cost is the sum of the G cost, which was assigned when the cell was added to the list, and the H cost, which was assigned when the grid was generated. The H cost is the product of the heuristic used, which can vary between algorithms, but is meant to give an estimation of how far a given cell is from the target cell. This version of the algorithm generates the H cost in a similar way to how the G cost was found. The program ignores any existing walls and gives a value based on the shortest path from each cell to the target. As was used when calculating the G cost of a cell, 14 points are given for a diagonal step, and 10 are given for a horizontal or vertical step.
The algorithm keeps selecting the cell with the lowest available F cost from the list to examine until the target cell is reached. If the list runs out before the target is reached, that means that no path is available between the start and the target.