Category Archives: Programming

Projects involving some sort of programming or scripting

I wrote a Hello World program.

Evolution - it works. Given enough time.

Genetic algorithms have got to be one of the crazier ideas in computer science – take an initial population and cross-breed/mutate to create the next generation. It doesn’t always find the optimal solution, but it sure tries hard and is fun to watch!

Python 3 code here.


Project SDVX: Part 3

← Part 2 | None 

Previously I got the Arduino Uno with the intention of using it to read my rotary encoders, which were to be used as my controller’s analog knobs. It turns out that the Uno can read the encoders… it just can’t output to keyboard/mouse. So I went and got myself another Arduino, the Leonardo. Should have done my research first.

It's about the same size as the Uno, but uses a micro-USB cable

It’s about the same size as the Uno, but uses a micro-USB cable

In any case, after a bit of research I found this tutorial on bildr. The code works well, and throwing in a Mouse.move statement allows the encoder to control a mouse cursor. This is useful because K-shoot Mania has a setting which lets you control the left and right lasers by “Custom Controller (Mouse X/Y)”.

The middle pin connects to ground, and the other two connect to input pins.

The middle pin connects to ground, and the other two connect to input pins.

I’m still doing a bit of fine tuning with the code so that it plays smoothly, but I’m glad that the encoders work. I’ll have to start making a box to house all the components soon.

← Part 2 | None 

Fibonacci in FRACTRAN

I’ve always found esoteric programming languages pretty amusing – they’re silly, occasionally witty, but most of all there’s the ones which take a lot of thinking, like Golfcode or Whitespace.

Today I had a bit of fun and tried writing a Fibonacci number generator in FRACTRAN. FRACTRAN, invented by the infamous John Conway, is a programming language where programs are just a list of fractions, and input is a single positive integer n. At each iteration, n is updated by multiplying it by the first fraction in the list which results in another positive integer, until this is no longer possible.

For instance, one of the simplest FRACTRAN programs is just:


Given input in the form of n = 2a × 3b, the program will continue multiplying n by 3/2 until n is no longer divisible by 2. This will happen when n is of the form 3a+b, so the single instruction program 3/2 is actually an addition program which stores the result of a+b as the exponent of 3 in the output.

The reason why FRACTRAN works is that what you really have is a bunch of registers labelled by prime numbers. For example, 3072 = 210 × 31 represents a state where register 2 has the value ten, and register 3 has the value one. Each fraction is then an instruction to increase or decrease the register values, provided that the result doesn’t make any register have a negative value. So for 3/2, if n is divisible by two then register 3 is incremented by one and register 2 is decremented by one. This shows how if statements are possible in FRACTRAN.

The Fibonacci program I wrote is the following:

39/55 33/65 78/77 66/91 1/11 1/13 5/2 7/3 11/1

The program starts with the initial value 3 = 20 × 31 and if at any iteration a number of the form 2a × 3b appears, then a and b are successive Fibonacci numbers.

It’s my first FRACTRAN program so it could probably be improved, but hey I’m pretty happy that I got it working. The hardest part was figuring out how to do loops in FRACTRAN, which is a surprisingly tough challenge.

My program works like so:

  • Initially, registers 2 and 3 store a and b respectively, which are consecutive Fibonacci numbers (with a < b by the initial condition).
  • a and b are then transferred to registers 5 and 7 respectively.
  • a is added from register 5 to register 2, while b is added from register 7 to both registers 2 and 3.
  • The result is that registers 2 and 3 now hold b and a+b respectively

This is how the fractions work:

  • 11 and 13 are indicator variables. If either of the registers are set to something nonzero, then one of the first four fractions will trigger, either subtracting 1 from register 5 and adding 1 to register 2, or subtracting 1 from register 7 and adding 1 to both registers 2 and 3. There’s two indicator variables because I couldn’t figure out how to do loops well – here registers 11 and 13 alternate from being 0, 1 and 1, 0 respectively so that one of them will always be set while this addition step is being performed.
  • This addition will continue until n is no longer divisible by 2 or 3, in which case 1/11 and 1/13 nullify the indicator variables
  • After this, 5/2 and 7/3 do the transferring from registers 2,3 to registers 5,7
  • Once the transfer is complete, 11/1 retriggers the indicator variable and we go again

Of course, if you want the program to actually terminate, then a slight modification can be made (to make register 2 the only input, the other registers got shifted up by one):

85/91 65/119 255/143 195/187 1/13 1/17 7/3 11/5 13/2 1/11

This version takes in input of the form 2n × 5 and returns 7F(n).

I think the nice thing about FRACTRAN is how easy programs are to explain to people, even if they don’t do computer science. Unfortunately though, explaining how the program actually works is a lot harder.

For some additional FRACTRAN trivia, somebody actually created a FRACTRAN interpreter in FRACTRAN, which goes to show that even a language that is easy to describe can be capable of quite a lot.

A three.js voxel digital circuit simulator

Well the university semester’s now over. I never ended up updating about my three.js project much as many of the middle weeks involved researching into improving my program’s performance.

In any case, here’s the final result. It’s not great (memory usage is high) but it works. You can even do stuff like make binary counters!

Actually, this is half the reason I made the JK flip flop a block

Actually, this is half the reason I made the JK flip flop a block

Edit: It’s been over a year now, and recent updates to Chrome have meant that the simulator no longer works with the latest Chrome versions. Darn.

[Week 3] Research into three.js and rendering performance

A slow week with the project, largely due to the performance obstacle that I’ve run into. After last week’s block placement test, I decided to try rendering more and more cubes to see how many cubes my computer could render before it starts lagging.

I created two tests – 10000 cubes and 90000 cubes. My computer could still handle 10000 cubes, but 90000 cubes took ages to load and it was very hard to move in the environment. This is a bit of a problem, because I expect the number of cubes that need to be rendered to possibly be in the several hundred thousands. I made another benchmarking test – it turns out that my computer will drop to a single digit frame rate at about 22500 cubes.

Of course, I haven’t done any optimisations yet. Everything is in a simple array, and every cube is rendered individually. But not being able to handle 90000 cubes even at this stage is a worry. Even though three.js abstracts away all the low-level WebGL, examples like this, this and this make me feel as though that there’s got to be a way around it.

There’s a lot of posts on the internet saying that using shaders can improve performance for WebGL, but there’s a bit of a problem for me – I still don’t get what shaders are. They don’t only “shade”, you see – not nowadays, anyway. Shaders confuse me.

On another note, 0fps has some great tips on building a voxel engine. I’m not sure how easy run-length encoding plus an interval tree would be to implement, but it’s an idea alright. I’m still trying to figure out a good way to store my cubes so that:

  • They don’t take up much space (the world can get large)
  • It’s easy to read/write from the data structure
  • I can get the neighbour of a cube easily

I have to say, optimising performance is one hell of a problem.

… oh and I’ve also figured out how to get textures working.

[Week 2] Block placement

Why the random colours? I was too lazy to do anything else.

Why the random colours? I was too lazy to do anything else.

My project has evolved to the state of “webtoy”!

Here’s the latest demo – it’s a block placement test. Nothing fancy so far, but at least I have some functionality going on.

I have a few notes though:

  • The crosshair may be slightly offcentre. I have yet to figure out how to fix this one properly.
  • Try to use Chrome. The site will load fine in Firefox, but there’s a few bugs and I haven’t actually bothered to try testing in Firefox yet.

If anyone’s interested in how the block detection was done… the magic phrase is “ray casting”. I didn’t implement the ray casting myself though – three.js has a RayCaster class inbuilt. Also, the intersect function that three.js has even detects which face of the cube is selected, so that saved me a lot of work.

The other thing I had to figure out was how to convert from Euler angles to a direction vector. Luckily, StackOverflow is very good at questions like these.