Finding shortest path in a maze on 2D map

Finding shortest path in a maze on 2D map

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 [1,1].

Finding shortest path in a maze on 2D map

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 1.

Finding shortest path in a maze on 2D map

Now we are doing the same thing. New two fields with tag 1 are added to searching queue. (“Do kolejki” means “To queue”)

Finding shortest path in a maze on 2D map

For field [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 2)

Finding shortest path in a maze on 2D map

We are doing the same steps for next fields untill we find the destination position. (“itd” on picture means “etc.”)

Finding shortest path in a maze on 2D map

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.

Finding shortest path in a maze on 2D map

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 [3,5].

Finding shortest path in a maze on 2D map

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.

Try it on your own

You can download this algorithm implemented in php or javascript on github.

Comments are closed.