Algorithm to Solve a User Defined Maze

Level of Mathematics Required: None

So I decided to make a “Pathfinder Robot” as my first semester MATLAB project. Not only did I learn lots of new stuff while doing it, I also ended up making my own algorithm for it. The usual one that is used is called A*. A* finds out the shortest path, but does not use the shortest number of moves. This one uses a different approach, to solve the maze in the shortest number of turns as well as the shortest path.

I will also upload in here the original program that I made later on.

1. Get the maze from the user. Also get the starting and ending points.

Get the maze from the user and save it in a 20 by 20 matrix of zeros and ones. Zeros denote the open area and ones indicate walls.
Get the maze from the user and save it in a 20 by 20 matrix of zeros and ones. Zeros denote the open area and ones indicate walls.

2. Break down your maze into horizontal and vertical segments. A segment is any uninterrupted path in the maze measuring 1 by n or n by 1 depending on whether it is horizontal or vertical, where n is any integer greater than 1. A 1 x 1 segment does not match our definition of segment here.

Red: some horizontal segments. Blue: some vertical segments Green and Orange: some NON segments
Red: some horizontal segments.
Blue: some vertical segments
Green and Orange: some NON segments

Do note that the orange “segments” were generated while segmenting the maze horizontally, and the green “segments” were made while segmenting the maze vertically. Do note that each of the orange parts WILL form part of some vertical segment and each of the green parts WILL form part of some horizontal segment. However, if a white box is locked by all 4 sides, then it will not form part of either a horizontal or a vertical segment.

This forms our complete definition of the segment for this program.

3. Each segment must be assigned a number. In this maze, we have 50 horizontal and 44 vertical segments. Store the information of each segment in a matrix. (The starting and ending points, for example).

4. For each horizontal segment, find out ALL the vertical segments that intersect it and save them into an array also.

5. Do the same for vertical segments. Remember a horizontal segment will ALWAYS intersect with a vertical and vice versa.

6. Run a recurrence process starting from the starting segment. Find out all possible pathways that extend from the starting segment. For example, if the starting segment has 6 intersecting segments, you have 6 possible moves in the first place. For each first move, find out all possible second moves and so on. On every level however, do keep checking if you have already encountered the destination segment. Break the loop then.

7. Highlight the path using the segments. This is tricky. You do not highlight the entire segment, only the part of it that lies between the segment before and after it in the sequence.

Important Notes

Do remember that your sequence of moves in every single possible route will be such that if the first segment was horizontal, the second will be vertical and the third will again be horizontal and the fourth will again be vertical. You can exploit this fact to prevent your robot from moving backwards (thats not what we want). Here’s how. Suppose this was your sequence (it’s stored in a array)

sequence={1, 4, 4, 51, 7, 9, 11}

Each element on an odd index of the array denotes a horizontal segment and each element on an even index denotes a vertical segment. Before appending a new horizontal segment to the sequence, check that the number does not already exist on an odd index of the array, and before appending a new vertical segment to the sequence, check that the number does not already exist on an even index of that array. 4 is used twice here, but its fine since one of them denotes a horizontal segment and the other denotes a vertical segment. We basically don’t want to encounter the same segment twice.

Do remember that as “full” as your maze is, the less the number of possible paths and the less the computation. However, if your maze has large open spaces, the number of intersections in that open space increase drastically and slow down your program. To solve this, move on to optimization.

Optimization

So your user left out lot’s of extra space in the maze. You do not want it. What do you do? Well, you simply cancel it out from your main program sequence by placing a “patch” on the maze. This “patch” is more of a “crime scene, do not enter” type of stuff. You move from the sides, you do not enter it.

Yellow: Trim from the outside Magenta: Trim from the inside

Yellow: Trim from the outside
Magenta: Void/Trim from the inside

First of all, “trim” the maze from the outside, leaving just a track of unit thickness around the maze (don’t block it all).

Next,

  • Probe the maze for any 4 x 4 regions of empty space.
  • Void out (magenta) only the central 2 x 2 of this space.
  • Expand this 2 x 2 first horizontally and then vertically, as much as you can, but again, leaving a track of unit thickness on the side of expansion. (That’s the reason we void out only the central 2 x 2 of the 4 x 4 region.)
  • DO NOT search for another 4 x 4 region unless you have expanded the first one as much as it could be.
  • Assign numbers to these patches as you create them.

There’s a possibility that the patches lengthen the route while decreasing the computation. See below:

Moving between the two blue dots involves just 2 segments, but because of the magenta patch, it now needs 4 segments.

Moving between the two blue dots involves just 2 segments, but because of the magenta patch, it now needs 4 segments.

Doesn’t matter. Once you are done, correct this for each patch (that’s what we assigned them numbers for). Just scan the sides of each patch and detect the points where the path moves away from the patch. There will be two such points, connect them together and delete the part that “wipes around the patch”.

Grey part shows deleted part of the route.

Grey part shows deleted part of the route.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s