Tag: maze following

A Physical Turtle

February 20th, 2013 — 8:29pm

After my PyconUk session on turtles I promised myself I would do something about providing some turtle features that would allow maze building and, hence, maze following. The result is the physical_turtle module that is now available from BitBucket or the Python package index.

The package provides a ‘blind’ turtle. That is, the turtle moves until it bumps into something and it has to feel its way around obstacles. The obstacles themselves are made up of ‘solid’ lines that are also drawn with a turtle. Using a turtle to create the obstacles is good, because no-one has to learn anything new in order to generate a maze, plus the whole package works exactly like the built in turtle module, so all existing turtle programs will work.

The README for the package covers the how to. Here, I’m covering the basics of the implementation.

Drawing solid lines turns out to be reasonably straight forward. If the turtle knows it is drawing a solid line then the module can keep track of these lines as they are drawn. This is easier then trying to look into the screen display list for the lines, and is less dependent on the intimate details of same. Each line has a length and a width, so the result is a set of rectangles. The rectangles are not, in any sense, solid internally, but the path of an exploring turtle is not allowed to cross any of the rectangle edge lines.

There is a great deal written about collision detection and this articleis just a start. Much of it, not unreasonably, appears to be aimed at games systems. In this environment the moving object is moved one step for every cycle through the internal game loop and the collision problem boils down to deciding if a collision will happen in the next increment (or has happened in this increment). The turtle module doesn’t work like this. Oh, I know, there are various drawing loops down in the depths of the code that support the animation, but these can be switched off by the user to speed up drawing to achieve whatever effect might be required. So that, and the fact that the drawing loops are not very accessible from the point of view of enhancing the inner workings, together mean that a different approach is needed.

The approach I use is to project the turtle path forward and look for the first intersection with any solid line. The result is something like this:

Simple Line Intersection on Turtle path

Simple Line Intersection on Turtle path

The obvious problem is that the turtle path has gone very close to that corner. If we want to allow the turtle to have some non-zero size we have to do something else. We can do this using the same internal line intersection geometry by running two guard lines parallel to the turtle path. Each of the three lines will be truncated to a greater or lesser extent by the surroundings. The shortest result is the required travel distance for the turtle, as shown here:

Using guard lines to give the Turtle some size

Using guard lines to expand the width of the Turtle path

This is still not enough. If the turtle hits a wall at a glancing angle it may stop too soon, and if it hits the wall more or less head on it will be too close. If the turtle path is exactly 90 degrees to the wall the path will stop exactly at the wall and we then have to manage another problem, which is that the turtle will then permanently intersect the wall and can never move. We need to add a further layer to allow for the supposed non-zero size of the turtle.

The solution here is to find the length of the perpendicular from the current end of the turtle path to the nearest intersecting wall. If this is too small we shorten the path by some amount, and if it is too large, we lengthen the path. This is repeated, adjusting the increments in a standard search pattern, until we find a path length that is near enough to what we want. In other words, we give the turtle a circular shape of known size and adjust the end point of the line so that the circle is as close as possible to the current obstacle. This is what the final position might look like:

End point of turtle path adjusted for Turtle size

End point of turtle path adjusted for Turtle size

The algorithm is not fool proof. Directing the turtle towards and just beside a long spike will confuse it. This is an attempt at doing the calculations as quickly as possible while still catching nearly all cases. It should be enough to build applications that demonstrate interesting geometries

Comments Off on A Physical Turtle | Development, Education

Using Maze Following as a Teaching Project

February 10th, 2013 — 6:00pm

PyConUK 2012 had a teaching sprint that brought together teachers and geeks for mutual enlightenment. As part of that sprint we split into groups and attempted to devise teaching plans using different computing ideas. This is the result from one such group.

The goal of the project was to build on students’ knowledge of turtle geometry (learnt, perhaps from Logo) and to use Python’s turtle graphics to give a turtle the ability to navigate a maze. This means giving the turtle the ability to tell where the maze is, as well as working out some algorithm for navigation. Thinking about all the elements needed to demonstrate success lead to a number of assumptions that allow us to decide what the student has to do and what is already given. We also needed to consider how the project might be made more interesting.

As it stands, we did not get as far as a detailed lesson plan. Nor did we consider teaching issues such as diversity. The conversation did, however, lead to ideas for ways of providing the technical support for the assumptions hinted at above.

The Elements of a Maze Navigation System

These are the things that need to be thought about when dealing with mazes. Some of these will be provided, and some will be developed by the students.

The Maze

  • Maze Definition – how does the user, student or teacher, define the shape that is to be the maze?

    At some levels this is a study in its own right. The geek side of the table mentioned automatic maze generation tools, but our overall level of knowledge of such things meant we could not sensibly evaluate such things for classroom use. We had thought that it might be good for students to be able construct their own mazes and two suggestions came up:

    • Use a text file with the maze laid out on the page, with walls represented as ‘x’ characters (for example).
    • Use a turtle ( with some magic property) to draw a maze.

    We did not talk about either option a great deal. Both options seemed to allow student or teacher to provide a maze definition. However, it was clear that, in either case, the facilities needed to turn either form of input into an internal representation that a turtle could detect were going to be given and not developed by the class.

  • Maze Representation (internal) – how are the maze walls represented inside the computer system?

    The secondary question here is – and how does the turtle detect them?

    The turtle module does not provide anything helpful here and some extra code is going to be needed. This is not for the classroom (maybe later?) and must be given.

  • Maze Representation (visual) – how are the maze walls drawn on the screen?

    This is related to both the internal representation and the definition problem. No solutions, only questions.

  • Turtle Senses – how does the turtle detect a maze wall?

    The turtle must be given some kind of sense so it knows where it can go and where it can’t (because there is a wall in the way).

    • Sight is useful and leads to thinking about how far ahead, and how much, the turtle can see.
    • Touch is useful. A ‘blind’ turtle can feel its way around an object and can work equally well in a confined space as in an open one.

    Neither of these senses is part of the turtle module and some extra features must be given.


Maze following algorithms exist that are more or less good at the general case. Abelson and DiSessa give a good discussion of these and bring out relevant geometry learning points. Identifying different ways of dealing with obstacles (where a maze is just a kind of obstacle) is what the students are aiming at.

Teaching Progression

  • Recapitulation

    Students already know about moving turtles around so the initial recap step uses this knowledge to have the students draw a turtle path that avoids a simple box of known size. Specifically, head in a direction, go round the box and continue on the same line as though the box wasn’t there.


    Since the size is known there is no need for any generalisation and the recap is simply a reminder placed in the intended context of object avoidance.

  • Use the turtle’s sense

    Introduce the sense (touch or site) that the turtle has and play with simple avoidance and shape following.

    Generalise the original recap scenario to take boxes of any size.

  • Provide an initial maze to get out of. Simple stuff like a box with an indentation.


  • Play with more complex objects.

  • Test the algorithms generated so far with some edge cases.

Increasing Interest

Allow students to generate mazes for other students to solve.

Look at the time it takes any of the current algorithms to solve a given maze.

Other Discussions in the Group

We looked at an example of a robot game where two robots worked round a maze (under player control), using a weapon to destroy the other robot. The interesting part here was that the robots had sight and weapon at 90 degrees to each other so that using the weapon meant seeing the target and then turning through 90 to fire.

We were introduced to StarLogo; essentially a multi-turtle simulation facility. The immediate relevance was the sense capabilities that the turtles have.

Further Action

A large part of the maze provision needs to be provided, as does a basic turtle sense. Watch this space…


Turtle Geometry: The Computer as a Medium for Exploring Mathematics.
Harold Abelson and Andrea DiSessa

Comments Off on Using Maze Following as a Teaching Project | Education

Back to top