Robot Simulator and Turtle Graphics, Revisited

This is an update to last week’s post about using VPython to make a robot simulator.  Last week, the vturtle.py module was really just a fancy turtle graphics engine.  The robot could move around and leave a drawing trail, but it could only dead reckon because it didn’t have any sensors.

This week, I added the ability to create obstacles for the robot, in the form of walls… or other robots.  The robot can now “bump into” things, with a stall sensor indicating when its movement is impeded.  You can also add proximity sensors, with configurable range and mounted in configurable locations around the circumference of the robot chassis.  (As before, everything is modeled after the Scribbler; I experimented with the real thing to come up with a reasonable default setup, which includes three sensors looking left, front, and right, with about 10 cm range.)

You can download the updated version at the usual location.  Here is a screenshot of a simple demo with the robot “wall-following” a maze:

The vturtle robot wall-following through a maze.

Admittedly, much of the motivation for this project stemmed from its utility for students learning about programming.  Working with the Scribbler itself is a lot of fun, but it is not always available (e.g., when the students are not in the classroom), and even when it is, it can be a little flaky at times.  This simulator allows students to experiment with pretty complex robot behavior any time, anywhere they have a computer.

But there was another reason I found this project interesting.  There is some nice mathematics involved in the collision detection and proximity sensing, some old hat, some new to me.

All of the sensor-related computation involves detecting the intersection between:

1. Two circles, when the robot collides with another robot;
2. Two line segments, a proximity sensor beam and a wall; or
3. A circle and a line segment (more on this later).

The first case is the simplest; just compare the distance between the robots with the sum of their radii.  The second case is more involved, and is perhaps the most elegant, but is a pretty standard computational geometry problem.

The third case, the intersection of a circle and a line segment, was one I had not investigated before, and occurs in two situations: when a robot collides with a wall, or when a robot’s proximity sensor beam intersects another robot.  The general problem is shown below:

Intersection of a circle and line segment.

Given a line segment and a circle centered at with radius , we want to determine if the two intersect.  Representing points with corresponding vectors, we can parameterize points on the line segment with:

An intersection occurs when a point on the line segment is also on the circle; that is, when is distance from :

Letting and , we can express this condition more efficiently without the underlying square root operation as:

This expands into a quadratic in ,

where

So there is an intersection iff this quadratic has a root in [0,1].  See the vturtle.py code for an example implementation.

Finally, following is example source code for the maze demo screenshot above:

import vturtle

# Create robot on a walled tabletop.
robot = vturtle.Robot(obstacles=vturtle.maze(rows=5, columns=5, cell_size=40))
robot.pen_up()

robot.fast_forward(5)

# Move until we find a wall.
while not robot.sensor(1):
    robot.forward(3)

# Wall-follow, keeping a wall on our right.
robot.left(90)
while True:
    while not robot.sensor(1) and robot.sensor(2):
        robot.forward(3)
    if robot.sensor(2):
        robot.left(90)
    else:
        robot.forward(15)
        if robot.stalled():
            robot.backward(3)
        robot.right(90)
        robot.forward(20)