Pathfinding Algorithm - Beginner Level
Introduction
Pathfinding algorithms are search methods and are a type of artificial intelligence. They can be used to search for many things such as finding the fastest way to go from a point to another by considering different lands and obstacles.
Initialization
First we need to initialize our values, here are the values required for a basic 2D maze:
1. Map (into array/vector)
2. Starting Point
3. End Point
First, we need a
map, in the case of a 2D maze, we can create a square or a rectangle into an array/vector. To make your maze into an array or a vector, you need to split your maze into small squares, each square is a location that the algorithm will use, and each square can have a value which determines what kind of land this square is. If you make an array/vector of int (integer) you can then set a different number for each different land, here's an example:
0 = neutral land
1 = wall / empty / non-existent
2 = water (can only go on if we use a boat, for example)
3 = transporter (go from a point to another, if you want to use such feature, you might need either an addition array/vector to specify where this point brings you, or to create arrays/vectors of class/struct for your map)
The
starting point is the location we start in the maze and the
end point is the point in the map that we seek.
Searching Algorithm
Our search algorithm will try every possible way and will notify us as soon as it reaches the destination. It will not try them one by one, but all at the same time.
We start from the
starting point and look at all the neighbor squares and look if we can go to this square, if so, we expand up to that point. We then create a new tree for every possible solution from that point. Once this is done, we look if any tree reached the destination, if not, we loop until it either reaches the destination or a deadend. If your maze has
teleporters, don't forget to expand the trees affected by them.
It you do not want the algorithm to go on a square it already went to, you can change the value of the squares it visits for the value of a wall (in this example, it would be 1). If you allow the algorithm to go on previous squares, you might however not allow it to go on the square it comes from, because that would cause infinite loops.
Example
Let's make an example to clarify this. Imagine the following maze:
1110111
1100011
1101011
1100111
1110111
Now, let's give letters so we can visualize the trees:
___a___
__bcd__
__e_f __
__gh___
___i___
Our goal is to go from point
a to point
i. We create a new tree which contains the point
a. We look at all its neighbors and we find that we can only go to point
c (a->c). From
c, we do the same, and we find that we can go to
a,
b and
d. We come from
a, since we don't want to go back, we ignore this, or we could have make
a equals to 1, so our function would not have found the point
a as a possibility. We now have 2 possibilities, so we now have 2 trees:
a->c->b
a->c->d
We continue only it reaches the point
i. Once the tree a->c->d reaches the point
f, it would see that it is a deadend and would
delete itself (unless you want to keep the trees that find a deadend).
Extra
If you want to do a 3D maze, it becomes more complex because you need to take in consideration much more things, such as the height and width of the
object that is moving, to make sure it fits in the path found.
You can add a memory to the system, so it will remember the correct paths it found in previous mazes, this would make it act more like an animal. If you put an animal in a maze, it would go in
squares that it already went and can recognize, even though it might be the wrong way in this new maze.
Conclusion
Pathfinding can be very useful in games, but also in any other situation where you need to find how to go from a point to another. You can add more functions to the algorithm to make it more accurate for your situation as well. Choosing the right Artificial Intelligence for a problem is an important task, but you also need to customize it for your needs and the situation.
What would you rate this article?Please login to rate and upload coding articles. To start registering a free account with us, click here..
