by Morton Goldberg
[Editor's Note: You can download the files for this quiz at:
--JEG2]
Turtle Graphics
===============
Turtle graphics is a form of computer graphics based on the ideas of turtle geometry, a formulation of local (coordinate-free) geometry. As a brief introduction to turtle graphics, I quote from [1]:
Imagine that you have control of a little creature called a turtle
that exists in a mathematical plane or, better yet, on a computer
display screen. The turtle can respond to a few simple commands:
FORWARD moves the turtle in the direction it is facing some
number of units. RIGHT rotates it clockwise in its place some
number of degrees. BACK and LEFT cause the opposite movements. ...
The turtle can leave a trace of the places it has been: [its
movements] can cause lines to appear on the screen. This is
controlled by the commands PENUP and PENDOWN. When the pen is
down, the turtle draws lines.
For example, the turtle commands to draw a square, 100 units on a side, can be written (in a Ruby-ized form) as:
4.times { forward 100; right 90 }
For more information, see [2] and [3].
This quiz is a bit different from most. If the usual Ruby quiz can be likened to an essay exam, this one is a fill-in-the-blanks test. I'm supplying you with a complete turtle graphics package, except -- to give you something to do -- I've removed the method bodies from the key file, lib/turtle.rb. Your job is to repair the damage I've done and make the package work again.
Turtle Commands
===============
There are quite a few turtle commands, but that doesn't mean you have to write a lot of code to solve this quiz. Most of the commands can be implemented in a couple of lines. It took me a lot longer to write a description of the commands than it did for me to implement and test all of them.
I use the following format to describe turtle commands:
long_name | short_name <arg>
description ...
Example: ...
All turtle commands take either one argument or none, and not all turtle commands have both a long name and a short name.
Required Commands
-----------------
These commands are required in the sense that they are needed to reproduce the sample designs. Actually, you could get away without implementing 'back' and 'left', but implementing them is far easier than trying to write turtle code without them.
pen_up | pu
Raises the turtle's pen. The turtle doesn't draw (lay down a visible
track) when its pen is up.
pen_down | pd
Lowers the turtle's pen. The turtle draws (lays down a visible track)
when its pen is down.
forward | fd <distance>
Moves the turtle forwards in the direction it is facing.
Example: forward(100) advances the turtle by 100 steps.
back | bk <distance>
Moves the turtle backwards along its line of motion.
back <distance> == forward -<distance>
Example: back(100) backs up the turtle by 100 steps.
right | rt <angle>
Turns the turtle clockwise by <angle> degrees.
Example: right(90) turns the turtle clockwise by a right angle.
left | lt <angle>
Turns the turtle counterclockwise by <angle> degrees.
left <angle> == right -<angle>
Example: left(45) turns the turtle counterclockwise by 45 degrees.
Traditional Commands
--------------------
These commands are not needed to reproduce any of the sample designs, but they are found in all implementations of turtle graphics that I know of.
home
Places the turtle at the origin, facing north, with its pen up. The
turtle does not draw when it goes home.
clear
Homes the turtle and empties out it's track. Sending a turtle a clear
message essentially reinitializes it.
xy
Reports the turtle's location.
Example: Suppose the turtle is 10 turtle steps north and 15 turtle steps
west of the origin, then xy will return [-15.0, 10.0].
set_xy | xy= <point>
Places the turtle at <point>. The turtle does not draw when this command
is executed, not even if its pen is down. Returns <point>.
Example: Suppose the turtle is at [10.0, 20.0], then self.xy = [50, 80]
moves the turtle to [50.0, 80.0], but no line will drawn between the [10,
20] and [50, 80].
heading
Reports the direction in which the turtle is facing. Heading is measured
in degrees, clockwise from north.
Example: Suppose the turtle is at the origin facing the point [100, 200],
then heading will return 26.565 (approximately).
heading= | set_h <angle>
Sets the turtle's heading to <angle>. <angle> should be given in degrees,
measured clockwise from north. Returns <angle>.
Example: After self.heading = 135 (or set_h(135) which is easier to
write), the turtle will be facing southeast.
pen_up? | pu?
Reports true if the turtle's pen is up and false otherwise.
pen_down? | pd?
Reports true if the turtle's pen is down and false otherwise.
Optional Commands
-----------------
These commands are only found in some implementations of turtle graphics. When they are implemented, they make the turtle capable of doing global (coordinate) geometry in addition to local (coordinate-free) geometry.
I used one of these commands, go, to draw the mandala design (see designs/mandala.tiff and samples/mandala.rb). If you choose not to implement the optional commands, you might try writing a turtle program for drawing the mandala design without using go. But, believe me, it is much easier to implement go than to write such a program.
go <point>
Moves the turtle to <point>.
Example: Suppose the turtle is home (at the origin facing north). After
go([100, 200]), the turtle will be located at [100.0, 200.0] but will
still be facing north. If its pen was down, it will have drawn a line
from [0, 0] to [100, 200].
toward | face <point>
Turns the turtle to face <point>.
Example: Suppose the turtle is at the origin. After toward([100, 200]),
its heading will be 26.565 (approximately).
distance | dist <point>
Reports the distance between the turtle and <point>.
Example: Suppose the turtle is at the origin, then distance([400, 300])
will return 500.0 (approximately).
Interfacing to the Turtle Graphics Viewer
=========================================
Implementing turtle graphics without being able to view what the turtle draws isn't much fun, so I'm providing a simple turtle graphics viewer. To interface with the viewer, turtle instances must respond to the message track by returning an array which the viewer can use to generate a line drawing.
The viewer expects the array returned by track to take the following form:
track ::= [segment, segment, ...] # drawing data
segment ::= [point, point, ...] # points to be joined by line segments
point ::= [x, y] # pair of floats
Example: [[[0.0, 0.0], [200.0, 200.0]], [[200.0, 0.0], [0.0, 200.0]]]
This represents an X located in the upper-right quadrant of the viewer; i.e., two line segments, one running from the center of the viewer up to its upper-right corner and the other running from the center of the top edge down to the center of the right edge.
[Editor's Note: I added a script to dump your turtle graphics output to PPM image files, for those that don't have TK up and running. It works identically to Morton's turtle_viewer.rb, save that it writes output to a PPM image file in the current directory. For example, to output the included tree image, use `ruby turtle_ppm_writer.rb samples/tree.rb`. --JEG2]
Unit Tests
==========
I'm including the unit tests which I developed to test turtle commands. For the purposes of the quiz, you can ignore tests/turtle_view_test.rb. But I hope you will find the other test suite, tests/turtle_test.rb, helpful. It tests every one of the turtle commands described above as well as argument checking by the commands. Don't hesitate to modify any of the unit tests to meet the needs of your quiz solution.
References
==========
[1] Abelson, H. & A. diSessa, "Turtle Geometry", MIT Press, 1981.
[2] Harvey, B., "Computer Science Logo Style", Chapter 10.
http://www.cs.berkeley.edu/~bh/pdf/v1ch10.pdf
[3] Wikipedia, http://en.wikipedia.org/wiki/LOGO_programming_language
Quiz Summary
I'm going to move my standard thank you note right to the beginning of this summary, because it's very important this time. Morton put in a lot of work prepping this problem so it would be Ruby Quiz size and fun at the same time. He even nursed me through my additions. Thank you Morton! More thanks to those who fiddled with the problem, showing Morton how much we appreciate his efforts.
Alright, let's get to the solutions.
Solving this problem isn't too tricky. The main issue is to have the Turtle track its state which consists of where it currently is, which way it is facing, and if the pen is currently up or down. Then you need to make the methods that alter this state functional. A surprising number of the methods have trivial implementations, but you do need a little trigonometry for some.
Let's walk through Pete Yandell's turtle.rb file to see how a solution comes together. Here's the start of the code:
include Math # turtles understand math methods
DEG = Math::PI / 180.0
attr_accessor :track
alias run instance_eval
def initialize
clear
end
attr_reader :xy, :heading
# ...
The only line in there not provided by the quiz is the call to clear() in initialize(). We'll look at what that does in just a moment, but first let's talk a little about what the quiz gave us for free.
We've already decided a little trig is needed so the functions of the Math Module are included for us. Now those Math methods expect arguments in radians, but our Turtle is going to work with degrees. The conversion formula is radians = degrees * (PI / 180) and that's exactly what the DEG constant sets up for us.
Skipping down, we see that instance_eval() is given a new name, so we can invoke Turtle code more naturally. This tells us how our object will be used. Because user code is evaluated in the context of this object, it will have access to all the methods we are about to build and even the methods borrowed from Math.
The rest of the code provides accessors to the elements of Turtle state we identified earlier. Since they are there, we might as well take the hint and tuck our instance data away in them. We still need to figure out how to track the pen's up/down state though. Finally, The track() method provides access to the Turtle path we are to construct. The viewer will call this to decide what to render.
I'll jump ahead in the code now, to show you that clear() method and another method it makes use of:
# Homes the turtle and empties out it's track.
def clear
@track = []
home
end
# Places the turtle at the origin, facing north, with its pen up.
# The turtle does not draw when it goes home.
def home
@heading = 0.0
@xy = [0.0, 0.0]
@pen_is_down = false
end
# ...
As you can see, clear() resets the Turtle to the beginning state (by calling home()) and clears any drawing that has been done. The constructor called this method to ensure all the state variables would be set before we run() any code.
We can now see that pen state will be tracked via a boolean instance variable as well. Here are the methods that expose that to the user:
# Raise the turtle's pen. If the pen is up, the turtle will not draw;
# i.e., it will cease to lay a track until a pen_down command is given.
def pen_up
@pen_is_down = false
end
# Lower the turtle's pen. If the pen is down, the turtle will draw;
# i.e., it will lay a track until a pen_up command is given.
def pen_down
@pen_is_down = true
@track << [@xy]
end
# Is the pen up?
def pen_up?
!@pen_is_down
end
# Is the pen down?
def pen_down?
@pen_is_down
end
# ...
Most of those should be obvious implementations. The surprise, if any, comes from the fact that pen_down() puts a point on the track. This makes sense though, if you think about it. If you touch a pen to a piece of paper you have made a mark, even though you have not yet drawn a line. The Turtle should function the same way.
Here are the other setters for our Turtle's state:
# Place the turtle at [x, y]. The turtle does not draw when it changes
# position.
def xy=(coords)
raise ArgumentError unless is_point?(coords)
@xy = coords
end
# Set the turtle's heading to <degrees>.
def heading=(degrees)
raise ArgumentError unless degrees.is_a?(Numeric)
@heading = degrees % 360
end
# ...
These should be pretty straight-forward as well. I haven't shown it yet, but is_point?() just validates that we received sensible parameters. Beyond the checks, these methods just make assignments, save that heading=() restricts the parameter to a value between 0 and 359.
We've got the state, so it's time to get the Turtle moving. Let's start with turns:
# Turn right through the angle <degrees>.
def right(degrees)
raise ArgumentError unless degrees.is_a?(Numeric)
@heading += degrees
@heading %= 360
end
# Turn left through the angle <degrees>.
def left(degrees)
right(-degrees)
end
# ...
The right() method is the workhorse here. It validates, adds the requested number of degrees, and trims the heading if we have passed 360. Pete then wisely reuses the code by defining left() in terms of a negative right() turn. Two for the price of one.
We can turn, so it's time to mix in a little motion:
# Move forward by <steps> turtle steps.
def forward(steps)
raise ArgumentError unless steps.is_a?(Numeric)
@xy = [ @xy.first + sin(@heading * DEG) * steps,
@xy.last + cos(@heading * DEG) * steps ]
@track.last << @xy if @pen_is_down
end
# Move backward by <steps> turtle steps.
def back(steps)
forward(-steps)
end
# ...
Remember your trig? We have the angle (@heading) and the length of the hypotenuse of a right triangle (steps). What we need are the lengths of the other two sides which would be the distance we moved along the X and Y axes. Note the use of DEG here to convert degrees to into the expected radians.
Once you accept how forward() calculates the new location, drawing the line is almost a let down. The point where we were will already be on the track, either from a previous line draw or from a pen_down() call. Just adding the new point to that segment that contains the last point ensures that a line will be drawn to connect them.
Again, we see that back() is just a negative forward().
Here are the rest of the Turtle movement commands:
# Move to the given point.
def go(pt)
raise ArgumentError unless is_point?(pt)
@xy = pt
@track.last << @xy if @pen_is_down
end
# Turn to face the given point.
def toward(pt)
raise ArgumentError unless is_point?(pt)
@heading = atan2(pt.first - @xy.first, pt.last - @xy.last) /
DEG % 360
end
# Return the distance between the turtle and the given point.
def distance(pt)
raise ArgumentError unless is_point?(pt)
return sqrt( (pt.first - @xy.first) ** 2 +
(pt.last - @xy.last) ** 2 )
end
# ...
go() is just forward() without needing to calculate the new point. (In fact, forward() could have called go() with the new point for even more aggregation goodness.) toward() uses an arc tangent calculation to change headings and distance() uses the Pythagorean theorem to tell you how many steps the given point is from where you are.
Here's the final bit of code:
# Traditional abbreviations for turtle commands.
alias fd forward
alias bk back
alias rt right
alias lt left
alias pu pen_up
alias pd pen_down
alias pu? pen_up?
alias pd? pen_down?
alias set_h heading=
alias set_xy xy=
alias face toward
alias dist distance
private
def is_point?(pt)
pt.is_a?(Array) and pt.length == 2 and
pt.first.is_a?(Numeric) and pt.last.is_a?(Numeric)
end
end
Those aliases were provided with the quiz and is_point?() is the helper method used to check the passed arguments to xy=(), go(), toward(), and distance().
If you slot that file into the provided quiz project and start running samples, you should see pretty pictures and I'm a real sucker for pretty pictures. Thanks again Morton. Great quiz idea!
Tomorrow we will tackle a fun algorithmic problem for us tournament players...
