The 8 bit inspiration, vol. 1: Drawing random trees

In this series we are looking for still valuable ideas from the popular literature of BASIC for 8 bit computers. We implement them on a retro machine for fun. Then we do it on a modern language. Finally we look for interesting (mostly mathematical) lessons to learn from the project. (All this for fun, of course.)

Today's idea comes from this book:

The title in English reads "Etudes for personal computers". The book is in Hungarian. It was published "back in the day", in 1984 in Budapest. It is written by a number of experts - programmers, mathematicians, etc., for a broad audience. The idea is to teach them the basics of BASIC programming, and show them how useful and nice things can be done with a computer. This "do something with your computer" obviously meant that "turn on your computer, write or understand a BASIC code, type it in, think, enjoy and develop it further", as opposed to today's "tip the touchscreen with your fingers, recognize pictograms and turn of your brain" approach…

Chapter II is about "computer graphics" by János Kepes, who is an excellent professional hungarian-english translator, professionally educated in mathematics otherwise. (Not much he wrote a whole book about it; the pioneering literature of this topic in Hungarian.) "Computer graphics" also used to have a different meaning: using your limited computer resources, find some algoirthm which can draw some spectacular picture to the screen. Albeit I don't mind at all that nowadays we are not restricted to this, yet it is an interesting way of thinking. At least I hope you'll agree with this after reading the rest of this post. So the idea by Dr. Kepes is: Let's draw a tree…

But how does a tree look like? Let's take a good look at some of them:

Let's just concentrate on the branches. The tree start with its trunk, which is vertical. Then at some point it branches: the trunk continues and at a point where there is bud initially, a new branches grow, at a seemingly random angle. And this is iterated: branches are interrupted with buds and new branches grow.

But where are the buds and at what will be the angle between two branches? Well, I'm not a biologist to study this question, however, it appears that it is a good model to consider these distances and angles as random variables. A random variable is a number depending on some random factors. But what is a random factor? I'm neither a philosopher to address this more deeply, nevertheless I know what it means mathematically, and to see a nice tree on my computer it will be sufficient.

Or even less is sufficient: whatever it means, BASIC, for instance, has an RND function (on the Plus/4), returning a random number between 0 and 1. Multiplying it with a number, we get a random number between 0 and that number…

O.K. it is not random really. Computers are deterministic machines, so they cannot produce anything really random. But should we throw dies then? Will that be random? Well, if someone would measure the initial speed, location, etc. of my die before throwing, one could calculate the number we get. So is it random? It depends what you mean by that. In the sense that we lack some information and therefore the numbers appear undeterministic to us, it is. In the sense that it would be possible for someone having more information to find them out deterministically, it is random. In fact, to this extent the pseudorandom numbers returned by RND are random, too. In fact, up to our current knowledge, there is yet another kind of randomness in nature: quantum systems have a nondeterministic behavior which cannot be "extended" to a deterministic model, which is a very dramatic consequence of this theory. (We are diving quite deep aren't we? I told you in advance that 8-bit programming will be inspiring. And we are only discussing our first function…) If, however, we register the output of such a device and put it into a box, someone opening the box will not be able to disginguish between good pseudorandom numbers and those… Anyway, to draw trees, the RND of my Plus/4 will be perfectly sufficient. (Later I shall show pictures drawn with my quantum random generator, and indeed, there will be no difference.)

So let's go for the trees then. The algoirithm is:

Take the trunk first and grow it to a random length
At the end there will be a bud. So grow the trunk further with a random length, and find a random angle for the branch. Grow a branch at that angle at random, at a random length again. (We assume that only one branch comes from each bud…)
Now you have two endings, so each will be a bud. So go to step 2 with both buds, and any further buds (i.e. endings). Or stop if your tree is big enough.

That's the way. But let's rather see the code itself. (You may even download it from here. If you eventually do not have Plus/4 at hand, just download VICE to give it a try…) After all, coding is like poetry. So let's see if you like mine:

  10 rem "random tree drawing"
  20 rem "screen size"
  30 mx=260:my=170
  40 ml=6
  50 tree$=chr$(mx/2)
  60 tree$=tree$+chr$(5)
  70 tree$=tree$+chr$(mx/2)
  80 tree$=tree$+chr$(my/5)
  90 color 0,8:color 1,10,5:color 4,4
 100 graphic 1,1
 110 for level=1 to ml
 120 for m=1 to len(tree$) step 4
 130 draw 1,asc(mid$(tree$,m,1)),my-asc(mid$(tree$,m+1,1))
 140 draw 1 to asc(mid$(tree$,m+2,1)),my-asc(mid$(tree$,m+3,1))
 150 if level=ml then circle 1, asc(mid$(tree$,m+2,1)),my-asc(mid$(tree$,m+3,1)),3
 160 next m
 170 nbrs$=""
 180 if level < mlev then gosub 1000
 190 tree$=nbrs$
 200 next level
 210 getkey a$
 220 if a$<>"x" then goto 50
 230 graphic 0
 240 end
1000 rem "grow branches"
1010 for k=1 to len(tree$) step 4
1020 x1=asc(mid$(tree$,k,1))
1030 y1=asc(mid$(tree$,k+1,1))
1040 x2=asc(mid$(tree$,k+2,1))
1050 y2=asc(mid$(tree$,k+3,1))
1060 dx=x2-x1:dy=y2-y1
1070 rem "atan2:"
1080 if dx>0 then let ang=atn(dy/dx)
1090 if dx<0 and dy>=0 then let ang=atn(dy/dx)+3.14159
1100 if dx<0 and dy<0 then let ang=atn(dy/dx)-3.14159
1110 if dx=0 and dy>0 then ang=1.57079
1120 if dx=0 and dy<0 then ang=-1.57079
1130 nbrs$=nbrs$+chr$(x2)
1140 nbrs$=nbrs$+chr$(y2)
1150 l=5+rnd(1)*(my/(2*level))
1160 nbrs$=nbrs$+chr$(x2+int(l*cos(ang)))
1170 nbrs$=nbrs$+chr$(y2+int(l*sin(ang)))
1180 rem "side branch"
1190 let sbs=rnd(1)
1200 nbrs$=nbrs$+chr$(int(x1+sbs*dx))
1210 nbrs$=nbrs$+chr$(int(y1+sbs*dy))
1220 let ang=ang+(-1+2*rnd(1))
1230 nbrs$=nbrs$+chr$(int(x1+sbs*dx+l*cos(ang)))
1240 nbrs$=nbrs$+chr$(int(y1+sbs*dy+l*sin(ang)))
1250 next k

There are some interesting things to note:

If you are eventually not familiar with calculating the direction of the new branch and the coordinates from it, revise your high-school maths, espeecially trigonometry.
BASIC has no atan2 function. So in lines 1070-1120 I had to implement one.
On 8-bit systems people took more care about the resources. Dr. Kepes recommednds to store coordinates in strings of characters, and I followed him (c.f. lines 1020-1050), partly as a tribute. But not only that. It also draws our attention to the fact that our whole tree can be coded as an ASCII string, so such trees can be written down as text… And vice versa: any text is a tree, I wonder how they look like. And how much of information does a tree hold after all?
I had to slow down the growth of the branches at each level (c.f. line 1150) of growing: the younger branches of a tree are shorter. This way the tree looks better and it is not that often leaving the screen.
After finishing a tree, the program will wait for a key to be pressed (line 210), and draw another.
From line 1000 we have the subroutine of growing branches. Back in the day I would have written a streamline program, but from the hindsight it is astonishing how unstructured programs BASIC suggests to write. And how troublesome it is to write a structured code.

You may remember these trees from my last post, but here are two more. I like them indeed, and I hope you will enjoy them, too:

In fact I was sitting next to my real Plus/4 at my 8 bit desk to write this code, to really get the feeling. And it is also unusual how few characters fit onto its screen, and how hard it is to go back and forth in my code. Indeed, life is much easier now with many respects… However, sitting at the Plus/4 you will not switch to your browser. And you will take your time. And think more about a code before you write down some rubbish…

But let's see how a similar program would look like in Python:

#!/usr/bin/env python3
"""Draw random trees"""

import math
import random
import tkinter


MAXX = 512
MAXY = 512
BUD_SIZE = 3
MAXITER = 8

def random_triple(level):
    """Return 3 random numbrs for tree growth"""
    level += 1
    result = (25+random.uniform(0, MAXY/(5.0*level)),
              random.uniform(-math.pi/3.0, math.pi/3.0),
              random.random())
    return result

def grow_branch(branch, level):
    """Given a branch, grow two branches from it:
    its continuation and a side branch"""
    dy = branch[1][1] - branch[0][1]
    dx = branch[1][0] - branch[0][0]
    branch_angle = math.atan2(dy, dx)
    branch_params = random_triple(level)
    branch_cont = ((branch[1][0], branch[1][1]), \
        (branch[1][0] + \
         branch_params[0] * math.cos(branch_angle),\
        (branch[1][1] + \
         branch_params[0] * math.sin(branch_angle))))
    branch_side_angle = branch_angle + branch_params[1]
    branch_side_start = (branch[0][0] + branch_params[2] * \
                         (branch[1][0] - branch[0][0]),
                         branch[0][1] + branch_params[2] * \
                         (branch[1][1] - branch[0][1]))
    branch_side = (branch_side_start, \
            (branch_side_start[0] + \
             branch_params[0] * math.cos(branch_side_angle),\
             branch_side_start[1] + \
             branch_params[0] * math.sin(branch_side_angle)))
    return [branch_cont, branch_side]

def draw_branch(branch):
    """Draws a branch: a line and two buds at its ends.
    The input of form ((x0,y0),(x1,y1))"""
    CANVAS.create_line(branch[0][0] + MAXX/2.0,
                       MAXY - branch[0][1],
                       branch[1][0] + MAXX/2.0,
                       MAXY - branch[1][1],
                       fill="darkblue", width=2.0)
    CANVAS.create_oval(-BUD_SIZE + branch[0][0] + MAXX/2.0,
                       -BUD_SIZE+ MAXY - branch[0][1],
                       BUD_SIZE + branch[0][0] + MAXX/2.0,
                       BUD_SIZE + MAXY - branch[0][1],
                       outline="darkblue")
    CANVAS.create_oval(-BUD_SIZE + branch[1][0] + MAXX/2.0,
                       -BUD_SIZE+ MAXY - branch[1][1],
                       BUD_SIZE + branch[1][0] + MAXX/2.0,
                       BUD_SIZE + MAXY - branch[1][1],
                       outline="darkblue")

#Now the main part. We open a canavas
MASTER = tkinter.Tk()
CANVAS = tkinter.Canvas(MASTER, width=MAXX, height=MAXY)
CANVAS.pack()
#Loop of drawing trees
while True:
    trunk = ((0., 20.), (10 * random.random(), 100.))
    branches = [trunk]
    for the_level in range(MAXITER):
        new_branches = []
        for the_branch in branches:
            draw_branch(the_branch)
            new_branches += grow_branch(the_branch, the_level)
        branches = new_branches
    print("Press ENTER for a next tree or enter 'q' to quit")
    cont = input()
    if cont in {'q', 'x'}:
        MASTER.destroy()
        exit(0)
    CANVAS.delete("all")

Observe how simple and transparent it is, especially as compared to the BASIC version. It is not that a bad age we are living in… In fact, these code also shows a way how to mimique the graphic coding of 8 bit computers: TKinter has functions for drawing lines, points, etc. As for the result of the program, in fact as we have a higher graphic resolution, it is worth growing more levels of the tree, and it is more apparent that it is maybe not the best kind of the randomness we opt for. We get nice trees like this:

but some of them look rather unnatural:

As it is a blog post and not a book, I stop here and let you think about it further.

Update on 2021-02-17:

I was planning to write a next post we will learn a bit about (joint) probability distributions, and we shall use our trees to visualise them. Also, we will take a look at trees generated by genuine quantum random generators (as I'm using one of these in my research), etc. It seems, however, that I'm almost the only reader of my blog. Also, I write these for fun and I started to feel like working when I started the second part. So I leave this exploaration to the reader; this is the end of my tree story. Thanks for reading.