# 3pi maze shortest path?

Hi,
We are working with 3pi to find the shortest path. can any one help how to do this?
Thanks

Hello.

- Ryan

Hi Rayan,

I have read the entire website. My problem is: we are designing a project with3pi to find a shortest path to reach the destination.

A similar one to maze solvers but instead it should explore all paths and find the shortest one to reach the destination. There are ofcourse more than one paths to reach the destination.
We have tried to extend the exaple maze solver but havent suceeded.

Regards

Hello.

If your maze has loops (i.e. more than one path from some point A in the maze to another point B), then you will need to use an entirely different algorithm to solve the maze. The right/left-hand-on-the-wall strategy employed by our sample program is not guaranteed to work in a maze with loops (it can get stuck endlessly circling one of those loops). If you want to find the shortest path through a looped maze, you will need to explore the entire maze and build a map of it in memory as you go. I suggest you look into Dijkstra’s algorithm. Somethings to consider:

1. How do you decide which unexplored maze cell to next visit?
2. How do you compute the shortest path from an arbitrary point in the maze to another arbitrary point?
3. How do you store the entire maze in memory? The 3pi doesn’t have a lot of memory, so you will need to be clever if you are dealing with a large maze.
4. How do you keep track of where the 3pi is in the maze?

This last point might seem like a silly question, but it is probably one of the biggest obstacles to making a successful 3pi looped-maze solver. The 3pi doesn’t have encoders, so it’s easy to lose track of how far you’ve traveled between intersections. It helps tremendously that 3pi’s motors are powered off a regulated voltage (the robot’s timing will not change as your batteries discharge), but you will need to to a lot of tests to work out the best way to convert travel time into the number of grid cells traversed. I do not expect the 3pi to be able to solve a non-gridded maze.

I programmed a 3pi to solved looped mazes with up to 16x16 intersections on a 6" grid, so I know it is doable under at least some circumstances.

- Ben