Breadth-first search on a grid
Preparing the grid
Getting the node from an object's position
In order to translate the world space to grid-space, we need to work out what node the object is in, so we can then store info in that node, and then use the node for pathfinding. We will most often have to use this function to get the AI's position and the target's position.
Getting a node's neighbours
To start the pathfinding process, we need to find the neighbours of each node. We can then programming the breadth-first search algorithm. Both of these functions are public so the AI can access them.
Implementing breadth-first search
The basic algorithm
We start off with the current node, which we can find using the AI's position and the nodeFromWorldPoint function we created. We add this node to a list named "openNeighbours" - we'll add to this list all the nodes that we are yet to check. In order to check through the list using a "flood fill" technique (which is the most common, and seemingly most natural method used), we get the neighbours of the current node using the getNeighbours function and add them to the openNeighbours list if they have not been checked already (they should be in the closedNeighbours list if so) and they are walkable. Once we are done checking all the neighbours we can remove the current node from openNeighbours and add it to closedNeighbours so it isn't checked multiple times. This process continues whilst the openNeighbours list is not empty.
The loop can be seen here:
I have also created a visual representation by colouring the current node being checked black whilst the process runs:
Finding a target node
We take the mouse position when the left muse button is clicked and store that position. The mouse position is then converted into game space by using raycasting that is built into Unity (The raycast will get the point that the mouse is aiming at according to the viewer). In the pathfinding process we can then use the raycast hit position and convert it into a node - this node is then taken as the target node.
Early Exit
With a target node, we can now exit the algorithm early so it doesn't check anything unnecessary if the target node has already been found. We do this by simply questioning whether the current node = the target node, if it is true, then we "break" out of the loop.
Here I've marked the target node green, so you can see that the algorithm stops at the correct position:
