Voronoi Diagrams

This post was meant to come out on the 15th April... but I forgot to upload it to the server - I am posting now instead.

Today I bring you another experiment with the HTML5 Canvas - Voronoi diagrams. A Voronoi diagram is an image where you scatter a bunch of points across an image, give each point a colour, and then colour each pixel according to which point is closest.

You can find my implementation here: Voronoi Diagram Generator

Initially I had trouble implementing this algorithm as I was trying to draw the outline of each of the cells first, but the explanation on it's Wikipedia article helped me to realise that there was a much easier way to do it :)

Next time I am trying to implement something that looks rather complicated and difficult I will definitely look for an alternative way of thinking about it.

For those of you who are interested, I used a technique called 32 bit canvas manipulation when writing this one. In a nutshell, this is a way of setting the red, green, blue, and alpha values of a pixel all at once, instead of in 4 separate operations - speeding up the whole rendering process.

IP version tester

You may have heard already - we have run out of IPv4 addresses. An IPv4 address is 32 bits long and looks like this: 37.187.192.179. If you count up all the possible combinations (considering each section may be between 0 and 255), missing out the addresses reserved for special purposes, you get about 3,706,452,992 addresses.

The new system that the world is currently moving to (very slowly mind you) is called IPv6 and is 128 bits long. They look like this: 2001:41d0:52:a00::68e. This gives us a virtually unlimited supply of addresses so we should never run out.

The problem is that the world is moving far too slowly over to it and you can never be sure if you have IPv6 connectivity or not. I built a quick IP version tester to solve this problem. I know there are others out there, but I wanted to build one myself :)

You can find it here: Ip Version Tester.

Learning Three.js four: Maze Birthday Card

Hooray for the fourth 3 dimensional experiment!

This one is a birthday card for someone I know and is also much more complex than the others I have done so far. I ported a maze generation algorithm that I originally wrote in Python 3 to Javascript (I also have ported it to Lua, keep a look out for a post about Lua soon!) and then set about rendering it in 3D.

The aim is to get to the centre of the maze, where some 3D(!) spinning text is waiting for you. The maze generation algorithm is not designed to have the goal in the centre of the maze, so you will find that there are multiple paths that you can take from the centre that lead to different parts of the maze. I will make a separate post about the maze generation algorithm I have written later.

The collision detection is tile based and rather complicated (for me, anyway). I am surprised that nobody has written a library for this sort of thing.....

You can play with it here: Learning Three.js four

Learning Three.js three: Texturing

This week I have been busy, but I have still had time to create a new Three.js experiment. This week, I looked into simple texturing. The Cube in the middle has a simple soil texture, and I gave the skybox a bunch of clouds from opengameart.org. It took a whole lot of fiddling to get it to display the way it has now - I couldn't figure out the correct rotation for the tiles :D

This experiment also uses orbitcontrols.js from here I think? Click and drag to move around, and scroll up / down to zoom.

I have attempted to optimise it by only rendering a frame when the camera is actually moved or a texture is loaded too.

You can find it here: three

Learning Three.js 2: Catch the Sphere

The second thing that I have made in my endeavours to learn three.js is a simple catch the sphere game. Every time you get close to the orange sphere, it will move it to another random place in the room, add one to your score, and play a sound.

I cheated a little bit on the collision detection... I really ought to look into writing a simple 3D collision detection library that uses boxes and spheres.

The collision detection for the sphere is really done in 2D - I check only on the x and z axes to see if you are within a certain distance of the sphere since your y position doesn't change. For the bounding box, I simply check to make sure that your x and z co-ordinates aren't too big or too small.

You can find it here: two

Procedural Castle Generation

See the Pen Procedural Castle Generator by Starbeamrainbowlabs (@sbrl) on CodePen.

(Full screen)

The subreddit /r/proceduralgeneration has recently set up monthly challenges, and after missing the first one I decided to enter the second one. February's challenge was to generate random castles procedurally. The challenge was a lot of fun to take part in - my entry can be seen above.

I've published the code behind my entry on Github, too if you're interested in checking it out.

There were 15 other entries apart from mine. Here are all the entries next to each other:

(Full size image [15MB])

I liked zapetch's because although it's 2D, the generated castles are very varied and they look nice and simple. Moosekk's was great too - The towers look complicated and it has buildings and trees too. Comment down below with your favourites. Why did you like them? Voting is now open - please go and vote here. Your votes will decide who gets to decide on the next challenge!

How it works

Since I can't write a post on something that I've done without explaining just a little bit about how it works, I've written up a quick overview below. If anyone is interested in a longer writeup or any specific part of the generator, please comment down below and I will get back to you as soon as I can.

The generator works by picking a random regular shape, and then randomly altering the location of each of the resulting corners a little bit. After that the towers (and their stairs) and the keep are generated, and the flags are placed. Since the wind only flows in one direction, all the flags all face the same direction.

The moat is generated as a closed smooth line, with it's control points generated by taking the corners of the castle and moving them a set distance away from the main keep. Since the moat originally was way too wide for the drawbridge (whose parameters don't actually have anything to do with the moat at all!), I added a pair of extra control points to the moat's smooth line to bring it closer to the 2 towers that sit either side of the entrance (the moat was built intentionally, right?).

Originally I was going to generate random buildings inside the castle and draw paths between them, the towers, the keep, and the entrance, but the maths behind that got rather complicated and I didn't have time to wrap my head around it. I was also going to generate random people in the castle too, but again I didn't have time for this. I'll probably come back to this at a later date and work on these features.

If this challenge looks interesting, then /r/proceduralgeneration are hosting another challenge this month - this time the challenge is to procedurally generate a side-scrolling platformer.

Happy Christmas!

Happy Christmas!

Posts will resume in the new year.

I have a random snowflake generator for you that I wrote a while ago - my current project is taking longer than I thought :D

Edit: It can be found here Random Snowflake Generator).

HTML5 Canvas Clouds

This week I have some clouds for you, rendered via the HTML5 <canvas>. I wrote these in early 2013. I have not had a lot of time this week, but something cool is coming soon :)

The clouds themselves are stored in an array, and are composed of a random number of circles. This array is then iterated over 60 times a second and rendered using the HTML5 <canvas>. setInterval() is used to schedule the drawing of the frames, but I really should go back and upgrade that to requestAnimationFrame().

Link: HTML5 Canvas Clouds

Sorting: Selection Sort

Since I seem to be doing quite a few sorting algorithsms in my lectures at the moment, it would appear that I will be doing a series of sorting algorithm posts.

Today I did not have all that much time, so I wrote this one in javascript. I present to you: The selection sort.

The selection sort is a sorting algorithm where the smallest number is found and swapped with the number at the beginning, then the next smallest is swaped with the one next to the smallest number, and so on until the whoel sequence has been sorted.

Wikipedia has a rather nice animated GIF that explains the selection sort well here.

My implementation could be made faster be doing it in reverse, but I didn't have time to reverse it at the time of writing this post (check the comments to see if I did it later).

function selectionsort(arr)
{
    var maxid = 0, temp;
    for(var nextid = 0; nextid < arr.length - 1; nextid++)
    {
        //find the next smallest number remaining
        maxid = nextid;
        for(var j = nextid; j < arr.length; j++)
        {
            /*
            Invert to |
            sort desc.V */
            if(arr[j] < arr[maxid])
                maxid = j;
        }
        //swap the next number into place
        arr[nextid] = arr.splice(maxid, 1, arr[nextid])[0];

        console.log("nextid:", nextid, "state:", arr);
    }

    return arr; //for chaining
}

Here is a minified version (146 chars including newlines):

function selectionsort(e){for(var t=0,n=0;n<e.length-1;n++){t=n
for(var l=n;l<e.length;l++)e[l]<e[t]&&(t=l)
e[n]=e.splice(t,1,e[n])[0]}return e}

This was minified with UglifyJS.

Sample Output:

original [ 75, 4, 32, 87, 69, 73, 10, 18, 48, 2, 48, 96, 75, 36, 26 ]
nextid: 0 state: [ 2, 4, 32, 87, 69, 73, 10, 18, 48, 75, 48, 96, 75, 36, 26 ]
nextid: 1 state: [ 2, 4, 32, 87, 69, 73, 10, 18, 48, 75, 48, 96, 75, 36, 26 ]
nextid: 2 state: [ 2, 4, 10, 87, 69, 73, 32, 18, 48, 75, 48, 96, 75, 36, 26 ]
nextid: 3 state: [ 2, 4, 10, 18, 69, 73, 32, 87, 48, 75, 48, 96, 75, 36, 26 ]
nextid: 4 state: [ 2, 4, 10, 18, 26, 73, 32, 87, 48, 75, 48, 96, 75, 36, 69 ]
nextid: 5 state: [ 2, 4, 10, 18, 26, 32, 73, 87, 48, 75, 48, 96, 75, 36, 69 ]
nextid: 6 state: [ 2, 4, 10, 18, 26, 32, 36, 87, 48, 75, 48, 96, 75, 73, 69 ]
nextid: 7 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 87, 75, 48, 96, 75, 73, 69 ]
nextid: 8 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 75, 87, 96, 75, 73, 69 ]
nextid: 9 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 69, 87, 96, 75, 73, 75 ]
nextid: 10 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 69, 73, 96, 75, 87, 75 ]
nextid: 11 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 69, 73, 75, 96, 87, 75 ]
nextid: 12 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 69, 73, 75, 75, 87, 96 ]
nextid: 13 state: [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 69, 73, 75, 75, 87, 96 ]
result [ 2, 4, 10, 18, 26, 32, 36, 48, 48, 69, 73, 75, 75, 87, 96 ]

At some point I may port this to C♯.

(Probably) Coming Soon: (Binary) Insertion sort, Merge Sort, Quick Sort.

Binary Searching

We had our first Algorithms lecture on wednesday. We were introduced to two main things: complexity and binary searching. Why it is called binary searching, I do not know (leave a comment below if you do!). The following diagram I created explains it better than I could in words:

I have implementated the 'binary search' algorithm in Javascript (should work in Node.JS too), PHP, and Python 3 (not tested in Python 2).

Javascript (editable version here):

/**
 * @summary Binary Search Implementation.
 * @description Takes a sorted array and the target number to find as input.
 * @author Starbeamrainbowlabs
 * 
 * @param arr {array} - The *sorted* array to search.
 * @param target {number} - The number to search array for.
 * 
 * @returns {number} - The index at which the target was found.
 */
function binarysearch(arr, target)
{
    console.log("searching", arr, "to find", target, ".");
    var start = 0,
        end = arr.length,
        midpoint = Math.floor((end + start) / 2);

    do {
        console.log("midpoint:", midpoint, "start:", start, "end:", end);
        if(arr[midpoint] !== target)
        {
            console.log("at", midpoint, "we found", arr[midpoint], ", the target is", target);
            if(arr[midpoint] > target)
            {
                console.log("number found was larger than midpoint - searching bottom half");
                end = midpoint;
            }
            else
            {
                console.log("number found was smaller than midpoint - searching top half");
                start = midpoint;
            }
            midpoint = Math.floor((end + start) / 2);
            console.log("new start/end/midpoint:", start, "/", end, "/", midpoint);
        }
    } while(arr[midpoint] !== target);
    console.log("found", target, "at position", midpoint);
    return midpoint;
}

The javascript can be tested with code like this:

//utility function to make generating random number easier
function rand(min, max)
{
    if(min > max)
        throw new Error("min was greater than max");
    return Math.floor(Math.random()*(max-min))+min;
}

var tosearch = [];
for(var i = 0; i < 10; i++)
{
    tosearch.push(rand(0, 25));
}
tosearch.sort(function(a, b) { return a - b;});
var tofind = tosearch[rand(0, tosearch.length - 1)];
console.log("result:", binarysearch(tosearch, tofind));

PHP:

<?php
//utility function
function logstr($str) { echo("$str\n"); }

/*
 * @summary Binary Search Implementation.
 * @description Takes a sorted array and the target number to find as input.
 * @author Starbeamrainbowlabs
 * 
 * @param arr {array} - The *sorted* array to search.
 * @param target {number} - The number to search array for.
 * 
 * @returns {number} - The index at which the target was found.
 */
function binarysearch($arr, $target)
{
    logstr("searching [" . implode(", ", $arr) . "] to find " . $target . ".");
    $start = 0;
    $end = count($arr);
    $midpoint = floor(($end + $start) / 2);

    do {
        logstr("midpoint: " . $midpoint . " start: " . $start . " end: " . $end);
        if($arr[$midpoint] != $target)
        {
            logstr("at " . $midpoint . " we found " . $arr[$midpoint] . ", the target is " . $target);
            if($arr[$midpoint] > $target)
            {
                logstr("number found was larger than midpoint - searching bottom half");
                $end = $midpoint;
            }
            else
            {
                logstr("number found was smaller than midpoint - searching top half");
                $start = $midpoint;
            }
            $midpoint = floor(($end + $start) / 2);
            logstr("new start/end/midpoint: " . $start . "/" . $end . "/" . $midpoint);
        }
    } while($arr[$midpoint] != $target);
    logstr("found " . $target . " at position " . $midpoint);
    return $midpoint;
}
?>

The PHP version can be tested with this code:

<?php
$tosearch = [];
for($i = 0; $i < 10; $i++)
{
    $tosearch[] = rand(0, 25);
}
sort($tosearch);

$tofind = $tosearch[array_rand($tosearch)];
logstr("result: " . binarysearch($tosearch, $tofind));
?>

And finally the Python 3 version:

#!/usr/bin/env python
import math;
import random;

"""
" @summary Binary Search Implementation.
" @description Takes a sorted list and the target number to find as input.
" @author Starbeamrainbowlabs
" 
" @param tosearch {list} - The *sorted* list to search.
" @param target {number} - The number to search list for.
" 
" @returns {number} - The index at which the target was found.
"""
def binarysearch(tosearch, target):
    print("searching [" + ", ".join(map(str, tosearch)) + "] to find " + str(target) + ".");
    start = 0;
    end = len(tosearch);
    midpoint = int(math.floor((end + start) / 2));

    while True:
        print("midpoint: " + str(midpoint) + " start: " + str(start) + " end: " + str(end));
        if tosearch[midpoint] != target:
            print("at " + str(midpoint) + " we found " + str(tosearch[midpoint]) + ", the target is " + str(target));
            if tosearch[midpoint] > target:
                print("number found was larger than midpoint - searching bottom half");
                end = midpoint;
            else:
                print("number found was smaller than midpoint - searching top half");
                start = midpoint;

            midpoint = int(math.floor((end + start) / 2));
            print("new start/end/midpoint: " + str(start) + "/" + str(end) + "/" + str(midpoint));

        else:
            break;

    print("found " + str(target) + " at position " + str(midpoint));
    return midpoint;

The python code can be tested with something like this:

tosearch = [];
for i in range(50):
    tosearch.append(random.randrange(0, 75));

tosearch.sort();
tofind = random.choice(tosearch);

print("result: " + str(binarysearch(tosearch, tofind)));

That's a lot of code for one blog post.....