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:
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:
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:
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