beautypg.com

Example project #2: maze solving, A. solving a line maze, B. working with multiple c files in atmel studio – Pololu 3pi Robot User Manual

Page 29

background image

8. Example Project #2: Maze Solving

8.a. Solving a Line Maze

The next step up from simple line following is to teach
your 3pi to navigate paths with sharp turns, dead ends, and
intersections. Make a complicated network of intersecting
black lines, add a circle to represent the goal, and you have
a line maze, which is a challenging environment for a
robot to explore. In a line maze contest, robots travel as
quickly as possible along the lines from a designated start
to the goal, keeping track of the intersections that they pass
along the way. Robots are given several chances to run the
maze, so that they can follow the fastest possible path after
learning about all of the dead ends.

The mazes that we will teach you to solve in this tutorial
have one special feature: they have no loops. That is, there
is no way to re-visit any point on the maze without
retracing your steps. Solving this type of maze is much easier than solving a looped maze, since a simple strategy
allows you to explore the entire maze. We’ll talk about that strategy in the next section.

We also usually construct our mazes using only straight lines drawn on a regular grid, but this is mostly just to make
the course easy to reproduce – the maze-solving strategy described in this tutorial does not require these features.

For information on building your own course, see our tutorial on

Building Line Following and Line Maze Courses

[http://www.pololu.com/docs/0J22]

.

An additional resource for understanding simple, non-looped maze solving is this

presentation

[http://www.pololu.com/file/download/line-maze-algorithm.pdf?file_id=0J195]

(505k pdf) written by customer (and robotics

professor) R. Vannoy. It doesn’t include any code, but it goes over some important concepts and contains a number of
visuals to help illustrate the important points.

8.b. Working with Multiple C Files in Atmel Studio

The C source code for an example line maze solver is available in the folder

examples\atmegaxx8\3pi-mazesolver

.

Note: An Arduino-compatible version of this sample program can be downloaded as part of the

Pololu

Arduino Libraries

[http://www.pololu.com/docs/0J17]

(see

Section 5.g

) The Arduino sample sketch is all

contained within a single file.

This program is much more complicated than the examples you have seen so far, so we have split it up into multiple
files. Using multiple files makes it easier for you to keep track of your code. For example, the file

turn.c

contains

only a single function, used to make turns at the intersections:

#include

// Turns according to the parameter dir, which should be 'L', 'R', 'S'

// (straight), or 'B' (back).

void turn(char dir)

{

Pololu 3pi Robot User's Guide

© 2001–2014 Pololu Corporation

8. Example Project #2: Maze Solving

Page 29 of 63