A Star Pathfinding Algorithm

A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solutionfor the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs: starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.

Each tile in the grid has a sensor that informs the tile if it is occupied or not. Other than that each tile knows its position in the grid.

All of the tiles are created dynamically given a starting position. After all tiles are created the script that is responsible for this operation creates a list of objects. Each of this objects represents a tile. The class that I am using to represent this objects is called Node. Each of those representations must then be informed for their “physical” neighbors.

The pathfinding algorithm is implemented with a classical way but instead of having a starting point it uses the current position of the main character.

Last but not least the input of the pathfinding algorithm is the tile that the player desires to go. This input is given from the mouse. I created a function that creates a raycast from the mouse to the game’s world space and if an unoccupied tile is clicked then the algorithm finds the shortest path for the main character.

Leave a Comment