Few years ago I have created small game where I wanted to add path finding. I wanted to add ability to click somewhere on map and avatar would try to go there. To make it happen I created small class which calculates correct path on 2D map.
How is it working? Lets go throught maze
Let’s pretend we have small maze. Orange fields are walls. You cannot walk on them obviously.
At first, algorithm is taging positions on map near start position. Let’s start from
Starting field is tagged as
0. Then, every walkable field close to starting field should have tag increased by one (
previous field + 1), so in this case we are tagging these fields as
Now we are doing the same thing. New two fields with tag
1 are added to searching queue. (“Do kolejki” means “To queue”)
[2,1] with tag
1 we need to tag field
[3,1] with 2. (
previous field +1, remember?). We cannot tag more because field
[2,2] already has tag. For next field from queue
[2,2] we are going to search fields close to it and then we can tag these fields as
previous field +1 (in this case
We are doing the same steps for next fields untill we find the destination position. (“itd” on picture means “etc.”)
We need to go back from destination to start position. I called it “mirror searching”. To find the fastest way, algorithm reads tag value from destination field and then goes to field with
destination tag - 1.
We can see that destination field has tag
5. So we need to find the one with tag
4. As you can see it is field
We repeat last step until we reach starting point. Reversing order of steps will give us list of points which will be correct path to destination point.