Turtle Graphics (#104)

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Morton G.

[Editor’s Note: You can download the files for this quiz at:

http://rubyquiz.com/turtle.zip

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

pen_down
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 .
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 .
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

On 12/1/06, Ruby Q. [email protected] wrote:

by Morton G.

    Turtle Graphics
    ===============

3 cheers, great quiz!

Ironically, I very recently implemented a turtle graphics system using
GTK and Ruby.

Here are some images that came from it to whet your appetite:
http://www.danceliquid.com/images/LS/

It used cairo for the anti-aliased line drawing.

Whee!
-Harold

On Dec 1, 2006, at 9:42 AM, Harold H. wrote:

It used cairo for the anti-aliased line drawing.

I tried to use the new pure Ruby PNG library to get anti-aliased line
drawing in the quiz files, but that sucker is a bit broken. :wink:

James Edward G. II

On 12/1/06, Ruby Q. [email protected] wrote:

[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]

Hello,
Does the above work for everyone?

(~/turtle_graphics) > ruby turtle_ppm_writer.rb samples/tree.rb
turtle_ppm_writer.rb:47:in run_code': undefined method each’ for
nil:NilClass (NoMethodError)
from turtle_ppm_writer.rb:27:in initialize' from turtle_ppm_writer.rb:75:in new’
from turtle_ppm_writer.rb:75

ruby 1.8.5 (2006-08-25) [powerpc-darwin8]

Kurt

On 12/2/06, James Edward G. II [email protected] wrote:

On Dec 1, 2006, at 9:42 AM, Harold H. wrote:

It used cairo for the anti-aliased line drawing.

I tried to use the new pure Ruby PNG library to get anti-aliased line
drawing in the quiz files, but that sucker is a bit broken. :wink:

James Edward G. II

Ha! I did the exact same thing the day they announced that PNG lib.
There is some kind of bug in their implementation of that tricksy line
drawing algorithm they’re using. I spent about 20 minutes trying to
unravel it and then quit.

I found it kind of ironic that they chose some super speedy line
drawing routine meant to save cycles when writing directly to video
ram in mode 13h from the early ninety’s. Sitting right next to a pure
ruby implementation of png, compression and all, the contrast was
stark.

(:,
-Harold

“Harold H.” [email protected] writes:

Ha! I did the exact same thing the day they announced that PNG lib.
There is some kind of bug in their implementation of that tricksy line
drawing algorithm they’re using. I spent about 20 minutes trying to
unravel it and then quit.

I found it kind of ironic that they chose some super speedy line
drawing routine meant to save cycles when writing directly to video
ram in mode 13h from the early ninety’s. Sitting right next to a pure
ruby implementation of png, compression and all, the contrast was
stark.

To be fair, they don’t do the compression in pure ruby - they call
Zlib, so the really computationally intensive bit isn’t in ruby.

Also, the fast line-drawing algorithm used for writing to that old
320x200 VGA mode wasn’t what they’re using here. Here, they’re doing
anti-aliased lines, which no one would ever think of trying when you
only have 256 colors available and the pixels are going to be visibly
squares no matter what you do.

That old line drawing algorithm I could just pull out of a book on my
shelf; what they’re doing here is enough different that it’s very
tough to disentangle.

On Dec 1, 2006, at 3:44 PM, Daniel M. wrote:

That old line drawing algorithm I could just pull out of a book on my
shelf; what they’re doing here is enough different that it’s very
tough to disentangle.

Unfortunately, that kept me from trying very hard to fix it. I also
worried they weren’t too interested in the library since the example
had notes about how it was busted.

I also had issues where I would draw lines in bounds, but it would
access pixels outside the image area in anti-aliasing which caused
exceptions to be tossed.

James Edward G. II

On Dec 1, 2006, at 10:50 AM, Kurt Hindenburg wrote:

ruby 1.8.5 (2006-08-25) [powerpc-darwin8]
Making it work is the quiz. You need to finish the turtle.rb file so
a track() is returned to draw.

James Edward G. II

/usr/local/lib/ruby/site_ruby/1.8/tk.rb:1187: warning: instance variable
@encoding not initialized

Is it something I am doing wrong, or some other problem? I don’t know
much about Tcl/Tk.

On 12/2/06, Daniel M. [email protected] wrote:

To be fair, they don’t do the compression in pure ruby - they call
Zlib, so the really computationally intensive bit isn’t in ruby.

Thanks for the correction here.

Also, the fast line-drawing algorithm used for writing to that old
320x200 VGA mode wasn’t what they’re using here. Here, they’re doing
anti-aliased lines, which no one would ever think of trying when you
only have 256 colors available and the pixels are going to be visibly
squares no matter what you do.

People were most definitely drawing anti-aliased lines in mode 13h:
http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

Aesthetically sensible when, as you say, each pixel is a visible
rectangle? no.

Still pretty fun though. hehe. :wink:

That old line drawing algorithm I could just pull out of a book on my
shelf; what they’re doing here is enough different that it’s very
tough to disentangle.

It’s a bit of a shame too, this lib would otherwise be perfect for
doing cross-platform turtle graphics in Ruby.

Regards,
-Harold

People were most definitely drawing anti-aliased lines in mode 13h:
http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

Aesthetically sensible when, as you say, each pixel is a visible rectangle? no.

Actually, it’s exactly when you want anti-aliasing. If your pixels
were small enough, anti-aliasing would be unnecessary.

Of course, if your pixels are very large, then yeah, I suppose it
won’t help much. Maybe that’s what you were getting at…

On Dec 1, 2006, at 7:22 PM, Edwin F. wrote:

/usr/local/lib/ruby/site_ruby/1.8/tk.rb:1187: warning: instance
variable
@encoding not initialized

Is it something I am doing wrong, or some other problem? I don’t know
much about Tcl/Tk.

I’d look into this, but you aren’t giving enough info for me to have
a clue as to how to reproduce it.

OTOH, since it’s only a warning, it probably OK to let it go for now
unless you’re seeing visible problems such as bad graphic output.
I’ve seen a number of harmless warnings both from Ruby/Tk and Tk
itself before.

Regards, Morton

On Dec 1, 2006, at 10:42 AM, Harold H. wrote:

Ironically, I very recently implemented a turtle graphics system using
GTK and Ruby.

Why ironic? I’s say you have a head start on solving the quiz. I look
forward to seeing your submission.

Here are some images that came from it to whet your appetite:
http://www.danceliquid.com/images/LS/

It used cairo for the anti-aliased line drawing.

Nice images. The design you call Penrose, I call Hilbert. That and
several other classic turtle designs (both the turtle code and the
graphic output) are included with the quiz for participants to test
against their Turtle class. The turtle code is in the samples folder
and the graphics (.tiff files) are in the designs folder. Also,
compare tree.tiff to your tree.png – fairly similar.

Regards, Morton

Morton G. wrote:

On Dec 1, 2006, at 7:22 PM, Edwin F. wrote:

/usr/local/lib/ruby/site_ruby/1.8/tk.rb:1187: warning: instance
variable
@encoding not initialized

Is it something I am doing wrong, or some other problem? I don’t know
much about Tcl/Tk.

I’d look into this, but you aren’t giving enough info for me to have
a clue as to how to reproduce it.

OTOH, since it’s only a warning, it probably OK to let it go for now
unless you’re seeing visible problems such as bad graphic output.
I’ve seen a number of harmless warnings both from Ruby/Tk and Tk
itself before.

Regards, Morton

Sorry I didn’t provide more information earlier; I kind of assumed that
other people would have got the warnings, too. Although the warnings are
in fact harmless, and the graphics appear to be just fine, it’s a bit
annoying when you get 27,690 warnings (that’s right: 27 thousand plus
warnings). These consisted of the following two warnings:

/usr/lib/ruby/1.8/tk.rb:2313: warning: redefine encoding=
/usr/lib/ruby/1.8/tk.rb:2316: warning: redefine encoding

followed by 27,688 repetitions of this warning:

/usr/lib/ruby/1.8/tk.rb:1187: warning: instance variable @encoding not
initialized

All I did was run this command line:

ruby turtle_viewer.rb samples/tree.rb

The warnings occur for any run of turtle_viewer.rb.

Here’s my Ruby version:

ruby 1.8.4 (2005-12-24) [x86_64-linux]

I’m running this on Ubuntu Edgy x86-64. But I get the same warning when
I run on a 32-bit RHEL3 system using Ruby 1.8.5, too.

I can’t post my code (yet) because of the 48-hour deadline, but I can
tell you that it does not have the word “encoding” anywhere in it :slight_smile:

I’ll investigate further. I was just wondering if anyone else saw this.
Thanks.

On 12/2/06, Morton G. [email protected] wrote:

On Dec 1, 2006, at 10:42 AM, Harold H. wrote:

Ironically, I very recently implemented a turtle graphics system using
GTK and Ruby.

Why ironic? I’s say you have a head start on solving the quiz. I look
forward to seeing your submission.

I guess ‘coincidentally’ would have been a better word. :stuck_out_tongue:

Unfortunately, I have scant time for Ruby Q… The one (possibly
two?) submission I made was a total fluke. :((

compare tree.tiff to your tree.png – fairly similar.

My implementation includes an L-system exploration library which can
feed instructions directly to the pen. (which is abstracted from the
turtle in my code)

The turtle (which is implemented using eval in a very straight forward
manner), and the L-system library, can both produce strings of
instructions for the pen. (the pen is capable of both cairo and
gtk::drawingarea drawing)

I pulled most of the L-systems I was drawing from fractint, actually,
because the my L-system library is nearly interface compatible with
it. So credit goes out to the crazy wizards who contributed L-systems
to fractint.

There’s even the option of having the turtle generate a string of
instructions, which can then be further iterated on by the L-systems,
an option that has yet to be properly exploited.

With that said, the code is a dirty, voracious, sub-optimal, tightly
coupled, borderline embarrassing, pile of hack. (As most of my one
weekend personal projects are.) But maybe it would be interesting to
you or others.

I’ve put it online, feel free to grab it:
http://www.danceliquid.com/docs/turtlegraphics.zip

But no cheating on the quiz with it… :wink:

Regards,
-Harold

Hidetoshi NAGAI wrote:

From: Edwin F. [email protected]
Subject: Re: tk.rb warning in Turtle Graphics (#104)
Date: Sat, 2 Dec 2006 17:03:13 +0900
Message-ID: [email protected]

warnings). These consisted of the following two warnings:

/usr/lib/ruby/1.8/tk.rb:2313: warning: redefine encoding=
/usr/lib/ruby/1.8/tk.rb:2316: warning: redefine encoding

followed by 27,688 repetitions of this warning:

/usr/lib/ruby/1.8/tk.rb:1187: warning: instance variable @encoding not
initialized

Don’t worry about those. Those are no problem.

Redefinition of TclTkLib.encoding and encoding= depends on
the difference between using ‘tcltklib.so’ only and with ‘tk.rb’.

@encoding is used to check the encoding of a string.
It depends that the value of non-initialized instance varible is nil.
Of course, if check the existence of the variable first,
the warning will be removed.
But then, checking a string to pass to a Tcl/Tk interpreter needs
two steps (check and refer).
Such check is called very frequently. So, I ignored the warning.


Well, I found a bizarre and (to me) totally inexplicable way to get rid
of the warning. This is from the quiz turtle_view.rb file. Adding an
explicit return value (any value; I used nil) to the draw method gets
rid of the warning. WTF???

Transform the turtle’s track into TkcLine objects and add them to

the

canvas’ display list. This method expects a track to be an array of

the form

track ::= [segment, segment, …]

segment ::= [point, point, …]

point ::= [x, y]

where x and y are floats.

def draw
@turtle.track.each do |seqment|
if seqment.size > 1
pts = seqment.collect { |pt| transform(pt) }
TkcLine.new(@canvas, pts)
end
end
nil # Adding this (or any return value) stops that @encoding
warning
end

I just dunno. Weird.

From: Edwin F. [email protected]
Subject: Re: tk.rb warning in Turtle Graphics (#104)
Date: Sat, 2 Dec 2006 17:03:13 +0900
Message-ID: [email protected]

warnings). These consisted of the following two warnings:

/usr/lib/ruby/1.8/tk.rb:2313: warning: redefine encoding=
/usr/lib/ruby/1.8/tk.rb:2316: warning: redefine encoding

followed by 27,688 repetitions of this warning:

/usr/lib/ruby/1.8/tk.rb:1187: warning: instance variable @encoding not
initialized

Don’t worry about those. Those are no problem.

Redefinition of TclTkLib.encoding and encoding= depends on
the difference between using ‘tcltklib.so’ only and with ‘tk.rb’.

@encoding is used to check the encoding of a string.
It depends that the value of non-initialized instance varible is nil.
Of course, if check the existence of the variable first,
the warning will be removed.
But then, checking a string to pass to a Tcl/Tk interpreter needs
two steps (check and refer).
Such check is called very frequently. So, I ignored the warning.

On Dec 2, 2006, at 4:28 AM, Edwin F. wrote:

the form

 end
 nil # Adding this (or any return value) stops that @encoding

warning
end

I just dunno. Weird.

I’m just as mystified as you area as to why it works, but I’m glad
you found a work-around that turns off all the warnings.

Regards, Morton

On 1 Dec 2006, at 16:07, James Edward G. II wrote:

On Dec 1, 2006, at 9:42 AM, Harold H. wrote:

It used cairo for the anti-aliased line drawing.

I tried to use the new pure Ruby PNG library to get anti-aliased
line drawing in the quiz files, but that sucker is a bit broken. :wink:

In a bout of “why can’t graphics be easy like it was on my BBC”, I
proposed as ASCII art Turtle graphics ruby quiz :slight_smile: I knocked up a
quick implementation (invoking code reuse (woo!) of some bits I had
left over from the earlier dungeon quiz), but the graphics were so
cheesy, I didn’t want to inflict them on the community.

On Dec 3, 2006, at 8:30 PM, Dema wrote:

Here is my straight-to-the-point answer:

Your solution passes all the unit tests I supplied and is certainly
good enough to reproduce all the sample designs. So you have good
reason to think it’s completely correct. However, one of the optional
methods has a problem.

Turn to face the given point.

def toward(pt)
@heading = atan(pt[0].to_f / pt[1].to_f) / DEG
end

This won’t work in all four quadrants.

I apologize for not providing tests good enough to detect the
problem. Here is one that will test all four quadrants.

# Test go, toward, and distance. # Verify heading measures angles clockwise from north. def test_coord_cmnds nne = [100, 173] @turtle.go nne x, y = @turtle.xy assert_equal(nne, [x.round, y.round]) @turtle.home @turtle.run { pd; face nne; fd 200 } assert_equal(30, @turtle.heading.round) assert_equal([[[0, 0], nne]], snap(@turtle.track)) sse = [100, -173] @turtle.home @turtle.run { face sse; fd 200 } assert_equal(150, @turtle.heading.round) ssw = [-100, -173] @turtle.home @turtle.run { face ssw; fd 200 } assert_equal(210, @turtle.heading.round) nnw = [-100, 173] @turtle.home @turtle.run { face nnw; fd 200 } assert_equal(330, @turtle.heading.round) @turtle.home assert_equal(500, @turtle.dist([400, 300]).round) end

Regards, Morton