RobWork part 1 - Installation

Introduction

In this series of tutorials I will show some of the functionalities of RobWork (a set of libraries for robotic research). We will design and model a simple SCARA-type robot and then maybe go on with some fancier and cooler stuff. I will try to write these tutorials in easy-to-stomach pieces and I also can't promise to post them regularly.

Note. We will do these tutorials on Ubuntu system. I encourage you to give it a try even if you haven't tried it yet. It should be perfectly fine installed on a virtual machine.

RobWork (http://www.robwork.dk) is an extensive collection of C++ libraries for use in robotics. I used RobWork in the course of my PhD work on the automating of gripper design and also employed in in some other robotic-related projects (such as modelling of CNC machines and in my other research). I can certainly recommend it for your robotic needs!

RobWork is developed by the robotics group at the Maersk Mc-Kinney Moller Institute at the University of Southern Denmark (http://www.sdu.dk/en/Om_SDU/Institutter_centre/SDURobotics).

Features of RobWork are (among others):

• modelling of robots (serial, tree and parallel),
• kinematic and dynamic modelling of devices (manipulators, controllers and sensors),
• robot forward and inverse kinematics,
• path planning and optimization,
• collision detection,
• grasping simulation,
• interfaces to ODE, Bullet and RWPE physics engines,
• script interfaces to Python, LUA and JAVA (Matlab!),
• all of this wrapped in a neat RobWorkStudio GUI.

You can read more about RobWork on its page, which also sports a comprehensive documentation of its functions.

Obviously, we have to start with the installation of RobWork. Further down I also describe the installation of Blender, which we will use as our 3D modelling tool.

RobWork

RobWork installation is described HERE. You should follow the guide on that page and install all parts of RobWork  software (with an exception for RobWorkHardware which we will not use). In a nutshell:

1. Install the build tools:

sudo apt-get install subversion git mercurial

sudo apt-get install gcc g++ cmake cmake-curses-gui

2. Install the RW, RWS and RWSIM dependencies (including some of the optional):

sudo apt-get install libboost-dev libboost-date-time-dev libboost-filesystem-dev libboost-program-options-dev libboost-regex-dev libboost-serialization-dev libboost-system-dev libboost-test-dev libboost-thread-dev
sudo apt-get install libxerces-c3.1 libxerces-c-dev
sudo apt-get install swig liblua5.2-dev python-dev default-jdk
sudo apt-get install qtdeclarative5-dev
sudo apt-get install libode-dev libode4

3. Create the RobWork directory and download the source code:

cd

mkdir robwork && cd robwork

svn co https://svnsrv.sdu.dk/svn/RobWork/trunk/

cd trunk

4. Create the build directory and issue the CMake command. If there are errors at this step, make sure that you have installed all the required dependencies.

mkdir build && cd build

cmake -DCMAKE_BUILD_TYPE=Release ..

5. (Optional) You can  use ccmake at this point to review the build settings. In particular, make sure that RobWork, RobWorkStudio and RobWorkSim are all enabled (see Fig. 1).

ccmake .

Fig. 1. Build settings.

6. If all is well, we can then proceed with the compilation. This will likely take quite some time. You can stop the make at any time and resume it afterwards; it will retain its progress. You can set the -j N parameter to run the compilation in N parallel threads.

make

or

make -j 4

Hopefully you did not get any build errors! You can verify that all is done correctly by navigating to the ~/robwork/trunk/RobWorkStudio/bin/release and trying to run the RobWorkStudio executable (see Fig. 2).

./RobWorkStudio

Fig. 2. RobWorkStudio.

It is reportedly possible to install RobWork also on Windows... but I don't recommend it (ugh, programming in Windows!). I might make a tutorial on that some other day.

Blender

Blender is an open-source 3D computer graphics software. Even though it is free, it's quite powerful - we won't even use a fraction of its capabilities to create the 3D geometry models for our robot's parts.

Installing Blender on Ubuntu is pretty straightforward. You can probably do it through the Ubuntu Software, but the following command executed in terminal will also do the job:

sudo apt install blender

We will also like to have an option of importing/exporting AC3D files, such that we can enhance our robot geometry with some color. In order to have that possibility you will have to install a 3rd party plugin available at https://github.com/majic79/Blender-AC3D. Download and unpack the ZIP of the repository.

It is important to run Blender at least once before installing the plugin. You should also edit and save the user settings while doing that, so that the config directory appears in your home folder. The plugin is installed by placing the io_scene_ac3d directory from the unpacked archive in your Blender configuration directory (for me it was ~/.config/blender/2.76 - press Ctrl+H to show hidden folders) in the sub-directory scripts/addons (that you likely have to create).

The next step is running Blender again, and going into File->User Preferences. In the Add-ons tab select the Import-Export category (on the left) and enable the

Import-Export: AC3D (.ac) format plugin (see Fig. 3).

Fig. 3. Enabling the AC3D support in Blender.

Summary

Okay! In this part we got acquainted with RobWork and installed our tools successfully. In the next part we will design our SCARA robot.

Elementary Cellular Automata

I have previously wrote about various classic 2D cellular automata: WATOR, the voting game and Wireworld (here and here). There is a whole class of simpler one dimensional automatons though. These were researched by Stephen Wolfram (of Mathematica and WolframAlpha fame).

What is the elementary cellular automaton anyway?

Imagine a boundless tape of cells (not necessarily infinite; it could connect end to end like a loop). The cells can be in '1' or '0' state at any given moment. The time passes in turns in this universe, and each turn the cell changes its value depending on the state of its neighbours and itself. For example, consider a fragment of the tape stating '...010...'. For this combination of states, a rule might say that the value of the center cell in this fragment becomes '0' the next turn.

There is a limited number of such rules. Since only three bits govern the evolution of the center cell state, the combinations are '000', '001', '010' etc. (8 combinations) - and for each of these the center state can become either '0' or '1', the total number of rules is 2^8 = 256 rules. These are easily encoded as a number. For instance, rule 11010 = 011011102 says that the center cell becomes '1' when the tape fragment the turn before is wither '110', '101', '011', '010', '001' (see the picture below).

Fig. 1. Rule 110.

I made a simple demo for testing various elementary cellular automaton rules. The demo is available HERE, and its source code is hosted on Gitlab HERE. The demo lets you easily change the rules (even as the automaton is working) either by typing the number in or clicking on the graphical tape fragment representations on the left side. You can also modify the tape cells manually by clicking and moving a mouse in the view in the middle. The left mouse button sets the tape cells to '1' and the right mouse button clears them to '0'. You can also randomize the state of the tape the automaton starts from.

Fig. 2. Elementary Cellular Automata demo.

It's a simple world, but it can still yield interesting results. Some of them are presented below.

Rule 90

Starting from a single pixel in the middle we get a Sierpinski triangle of sorts:

Fig. 3. Rule 90 makes a Sierpinski triangle.

Rule 60

Rule 60 also makes a Sierpinski triangle but sort of kicked to its side:

Fig. 4. Rule 60.

Rule 30

It's an interesting one. Seemingly random structures emerge under this rule. It is reportedly used for some of the randomization routines in Wolfram's Mathematica.

Fig. 5. Rule 30.

Rule 110

This one produces curious structures that move across the tape and interact between themselves. It has been proven that rule 110 is Turing complete and thus can be used to model any calculation. I have no idea how to use it yet!

Fig. 6. Rule 110 is a Turing complete CA.

It could certainly be interesting to experiment with the remaining rules and see what they are capable of. Perhaps you have an idea of how this simple setup could be extended? Feel free to play around with the provided demo.

More reading:

https://en.wikipedia.org/wiki/Elementary_cellular_automaton

http://mathworld.wolfram.com/ElementaryCellularAutomaton.html

Airfight

Long time ago (almost 20 years!), when I was a brilliant young lad who still knew pretty much everything and was consequently tremendously bored sitting through the classes, I invented a simple pen-and-paper game to play with my friends.

Airfight (Samoloty) is a turn-based WWI / WWII airplane duelling game that can be played with only a piece of paper, a pen or two and any straight-edge implement. It greatly resembles the way that miniature battle games are played nowadays, but I haven't yet heard of any of them when I first made it up.

Was the game, fun, playable and addictive? Well, let me just say that it had easily been more attractive than the long and interesting hours of religious studies! I also managed to get a couple of people to play it, so it couldn't have been half bad ;)

Let me quickly take you through how the game was played (as far as I can recall the rules).

Fig. 1. I also made a PC implementation - more on that below.

THE RULES

The purpose of the game is to win an airplane duel. Each player controls one of the airplanes and they act in alternating turns. The fight is won when the opponent's aircraft crashes or its pilots are killed. You can force the crashing of the plane by destroying it with your guns directly, damaging it so it loses all its fuel, engine power or steering. When the steering is destroyed, the plane will often crash on the page's border.

The game was meant to be very simple and require little in the way of accessories to play it. As a consequence, some of the rules (like hit zones and the turning radius) are quite arbitrary. Perhaps they could be improved somehow?

Setup

To play the game you need: a piece of paper (usually A5, but any larger size is also alright), a pen (two if you do mind sharing) and any straight edge implement (a ruler is good). Each player draws his airplane doll and picks a starting position on the opposite sides of the page. The typical setup looks like this:

Fig. 2. Game setup.

Airplane systems

The airplane doll is used to track the damage done to the aircraft and the amount of remaining fuel and ammo. The game uses a clever (even if I say so myself!) mechanic to establish the hit zones with damage to different systems affecting the performance of the plane in different areas. The plane doll looks like this:

Fig. 3. Airplane doll.

The round circles indicate the damage done / remaining hit points of the system. An empty circle is 3 HP (or 0 damage), while a completely shaded circle is 0 HP (or: completely destroyed). Some systems have more than one circle to represent its health.

Fig. 4. Representing hit points / damage. Top row illustrates a typical system. Bottom row illustrates the damage to the engine block.

The systems of the aircraft are:

• Propeller, which is used to move the aircraft forward. The propeller is fragile (3 HP) but it is a relatively small target. When the propeller is completely destroyed, the airplane loses 1 speed per turn. When the plane loses all its speed it  crashes.
• Engine. The engine provides power to the aircraft. Each turn you can only move the plane by as many squares as the engine HP left (which is 6 squares at the beginning). When the engine is destroyed, the plane crashes.
• Oil (coolant). This serves as a shield to the engine. Typically, the enemy bullets would first damage the coolant, only to be able to hit the engine after no oil is left. After the oil reservoir is first hit, it springs a leak, and from that point on it loses 1 HP/turn. While the leak is going, the aircraft leaves a dense smoke trail. (Optional: after the oil is all gone, the engine loses 1 HP/turn as well.) There are 4 circles for the coolant, and so the system packs 12 HP.
• Crew. The crew resides in the cockpit in the very center of the craft. It would rarely get hit (you have to be very persuasive as the determination of hit zones is quite arbitrary!), but once the pilot dies, the player loses. The crew has 6 HP.
• Guns/ammo. The plane has two guns, each with it's own supply of ammo (4 circles per gun, or 12 HP - or shots). Each shot taken with a gun reduces the supply by 1 HP. Any hits to the ammo zone also reduce the amount of shots left appropriately.
• Fuel. The fuel forms the biggest hit zone. Each turn you lose 1 HP of fuel for movement. Each hit to the tank also destroys the fuel left by appropriate amount. When the tank is struck, a leak forms, which then empties the reservoir at the rate of 1 HP per turn. Once the fuel is fully depleted, the plane starts to lose 1 speed per turn, and when it reaches 0 it crashes. The plane with a leaking tank leaves a trail of smoke. Each plane starts with 18 HP worth of fuel, but you can customize that amount.
• Left/right steering. This is split left to right and into the tail/wing assemblies. Each side has 6 HP. The damage to the steering surfaces affects the controllability of the craft (more on this in the following section).

Flying

During your turn you can execute two actions, one after another: moving and shooting. I think in the original game it was always 'move first, then shoot', but I see no reason why the sequence of the actions can't be picked by the player.

There are two parts to the movement: speed and turning radius. The first is controlled by the remaining engine HP left, in that you can only move as many squares as the engine HP left. You can move on any sort of curve and it's the length of that curve that counts. You have to do your best to approximate the distance.

Fig. 5. Flying the plane with various levels of speed.

The turning radius decides on the maneuverability of the plane. You have two sets of steering controls, each of which can be damaged or destroyed and you can only turn left/right as much as the remaining health of the system lets you. This is still pretty much arbitrary (modern figure games use curve shaped accessories to determine the turning radius rigorously), but you'd have to do your best to fly your plane true to its current capabilities. For instance, with the right side rudders completely destroyed, you shouldn't be able to turn right at all!

You have 6 HP for the steering on each side (12 HP in total). The turning radius could be scaled with the current HP to total HP ratio using this picture for reference:

Fig. 6. Turning radius related to the steering HP left.

Shooting

When you choose to shoot, you can use each of your guns once. There is an arcade aspect to this mechanic. You place a dot 1 square away from where the gun is on your plane avatar (it's either left or right bottom corner of the triangle) and use the ruler to draw a straight line through those two points. You can only shoot vaguely in 90 degree sector facing front of your plane.

Fig. 7. Shooting the target.

A hit is scored when the line crosses the enemy's avatar. You have to use the plane doll to approximate where on the enemy craft the hit has occured and process the damage accordingly:

Fig. 8. Finding out where the damage occured.

There is a social aspect to this, as the hit zone assingment is quite arbitrary. Arguing is allowed, provided you do it in a civilized way. Maybe a good way to keep it fair would be that both you and your opponent each decide on the hit zone and then you use a coin toss to pick one?

Each hit takes out 1 HP of the affected system, but you can use a damage multiplier (e.g. 2x) if you wish for a shorter game.

Sample game

Ok, let's try with a sample game!

Fig. 9. Player at the bottom wins. The plane on the top crashes due to the lack of fuel and due to oil leak destroying the engine.

I found my old notebook in which I apparently play-tested the game:

Fig. 10. Old game of  Samoloty.

AIRFIGHT ON A PC

Much, much later (but still like ~10 years ago), I made a computer implementation of the game.

It was done in C++ and used the Allegro library (http://liballeg.org/) for graphics and control. I used soe of the graphics I found on the web for the planes and the backgrounds and to my eternal shame I didn't record the authors (if you know them, please let me know).

The game is available on my GitHub HERE. Binaries are included, so all you have to do is to download the game and play.

Fig. 11. Game menu.

Features

• Two-player split-screen real-time shooting match!
• Several aircraft to choose from (Spitfire, Bf110, Flying Fortress and F16),
• Different types of weapons (machine guns, flak cannons, rockets, self-aiming guns, bombs),
• Hit zones,
• Very primitive artifical "intelligence".

Installation

As mentioned above, simply go to my GitHub repository and download the game. The binaries for Windows are included. If you wish, you can build the game from the source. A Code::Blocks project for the Windows version is included, and a Linux Makefile is also available.

For the Linux version, you will have to install the Allegro library package (version 4.2).

Playing the game

Select your starting craft and start a new game! If you wish to play with another person, you should first disable a primitive form of artificial intelligence enabled by default for the second plane. Go to the Options and switch off the Test2 checkbox.

The controls are as follows.

Player #1:

• ← → turn the plane left and right,
• ↑ accelerates the plane,
• ↓ switches the boost on and off (the boost briefly multiplies your speed),
• Right Shift cycles between the weapons,
• Right Control fires the guns.

Player #2:

• Z C turn the plane left and right,
• X accelerates the plane,
• A switches the boost on and off (the boost briefly multiplies your speed),
• Left Shift cycles between the weapons,
• Left Control fires the guns.

Just the same as in the pen-and-paper version, your goal is to destroy the opponent's plane. There is a brief warm-up period at the start of the game during which your weapons are locked. Once you achieve a certain speed, your plane 'takes off'. From that point you can't slow down too much, otherwise you'll stall and crash.

There are hit zones here as well. Destroying your engine will make your plane slow down and stall. Fuel may leak, the ammo may get destroyed and the guns may jam. The hit zones are implemented through an underlying sprite map with color encoding:

Fig. 12. Hit zones of the flying fortress.

The bullets each cover some distance between frames and so there is a chance for them to hit even the internal aircraft systems by chance.

Fig. 13. Flying Spitfire.

Fig. 14. Flying Bf110.

The game isn't terribly well balanced. Who knows, maybe I'll make a new version some day.

As to why do the planes seem to fly belly-up in the sky... You won't understand ;)

Double pendulum

Introduction

It seems like it's breaking the laws of physics... and certainly the laws of our intuition! Certainly, the movement of the chaotic pendulum just looks wrong. And how come such a simple physical system exhibits such a vivid variety of behaviours?

A double pendulum is simply two rods attached together. You release it from a certain height and the rods twist and turn together (see fig. 1). It is not just an artifact of simulation - the real device behaves just like that (watch it here  for example, narrated by Steve Mould).

Fig. 1. Chaotic dance of the double pendulum.

The double pendulum is a chaotic system. The evolution of its parameters in time is very sensitive to the starting configuration. If you release it the from a position just a few milimeters off, it will move completely different than in the previous experiment. In making this demonstration I wanted to show this intriguing behaviour.

Simulator

The JavaScript interactive demonstration of the double pendulum (see fig. 2) is available here: DEMO.

The source is available on GitHub: SOURCE.

Fig. 2. Double pendulum JavaScript demonstration.

So what are the features?

• simulate double pendulum with custom parameters (masses, lengths, time scale, gravitation),
• click on the image to place the pendulum,
• watch beautiful trails!,
• observe positions and energies in the panel on the left,
• add multiple pendulums with a slighly varied initial position to see the effects of chaos,
• QWOP style force control!

Click Start/Stop to see the simulation going. You can place the pendulum wherever you want by simply clicking in the animation. I made the inverse kinematics solver try to place the pendulum with the 'elbow' pointing downwards at any position.

The color of the trail is going to be randomly generated every time you click. The parameters can be changed in the panel on the right at any time.

You can slow down the animation and add some damping so that the pendulum will eventually stop. The damping force is proportional to the angular velocities of the two rods.

You can add multiple shadows of the original pendulum by changing the value in the pendulums box. The new pensulums will be added close to the current position of the pendulum with a certain level of uncertainty, which you can control by the position noise slider. The noise is generated as offsets in the rod angles.

You can control the pendulum manually as well. I implemented QWOP style controls (see fig. 3):

• Q accelerates the top rod clockwise,
• W accelerates the top rod counterclockwise,
• O accelerates the bottom rod clockwise,
• P accelerates the bottom rod counterclockwise.

Fig. 3. Moving the pendulum QWOP style.

Model

Double pendulum is a deceptively simple physical system. It should be relatively simple to derive the equations of motion through the Lagrangian formalism; the equations get complex very fast though. I quickly gave up trying to do this on paper and enlisted help of Matlab. Matlab in turn proved to have problems with symbolic expression derivatives wrt. to other symbolic functions... I ended up manually substituting some of the equations. The physical model of the contraption is shown in fig. 4.

Fig. 4. Physical model of a double pendulum system.

The model is described with the following properties:

• θ1, θ2 - angles of the pendulum rods relative to the vertical,
• l1, l2 - lengths of the rods,
• m1, m2 - masses at the ends of the rods,
• τ1, τ2 - additional torques at the pendulum joints,
• g - the gravitational acceleration,
• b - damping coefficient.

There seem to be lots of sources available on the web for the double pendulum. I checked some more popular Google results, and only one of those was correct (check the page out, they also have a nice interactive demo going!): https://www.myphysicslab.com/pendulum/double-pendulum/double-pendulum-en.html.

I wanted to have a slightly extended model, allowing for introducing user input torques in the pendulum joints, and including a simpel damping model. I used the following script to obtain the equations of motion (see fig. 5): SCRIPT.

Fig. 5. Equations of motion of the double pendulum system (click to enlarge).

And this is the LaTeX source for your convenience: LATEX.

The equations of motion are solved in JS using a Runge-Kutta 4th order fixed step solver (dt = 0.01 s).

Inverse kinematics

One of the features of the simulator is moving the pendulum to the cursor position with a mouse click. This requires a method for converting the (x, y) coordinates to the proper values for the pendulum joints (θ1, θ2). A simple way to tackle this is to use transposed Jacobian to iterate to the correct solution.

The position of the bottom bob of the pendulum is given by:

The Jacobian describes how the (x, y) changes due to changes in (θ1, θ2):

This is calculated as:

The following algorithm is executed then:

1. Assume a starting configuration (θ1, θ2).
2. Find the position of the pendulum (x, y) = f(θ1, θ2) at the assumed configuration.
3. Calculate the error vector e = (xdesired, ydesired) - (x, y).
4. If the magnitude of the error vector is sufficiently small (|e| < ε) finish.
5. Calculate the Jacobian J, and transpose J'.
6. Compute the offset to the (θ1, θ2) coordinates: Δθ = J' e.
7. Update the θ coordinates: θ = θ + α Δθ.
8. Go to step 2.

Examples

Some examples generated with the demo tool are presented below.

The first GIF shows the chaotic behaviour of the system. Two pendulums are released close together:

Fig. 6. Two pendulums start close together but soon grow apart...

Fig. 7. A bowl of pendula seems to be a proper collective noun.

You can add up to 100 pendulums (see fig. 8)!

Fig. 8. Uh-oh...

And this is what happens when you spin them around (and l2  is smaller than l1):

Fig. 9. Pendulum doughnut.

I wish I could add all the GIFs here! The generated images are massive though, so you'll have to check out the simulator yourself ;)

Making Deventer's Mazes

In my previous post (the very first one!) I described how to solve an unique 3D maze puzzle by using RRT path planner provided by RobWorkStudio.

The original puzzle was designed by Oscar van Deventer and it consists of three orthogonal flat plates, each carved with the 2-dimensional maze. The three plates restrict the movement of a star-shaped cursor within the cube, such that it can only move on an invisible 3-dimensional path projected by the mazes on the side (see fig. 1).

Fig. 1. Deventer's maze recreation. The cursor is the star-shaped orange-ish shape inside the cube.

We were left with an open question of how to programmatically generate a new puzzle just like this.

The naive extension of backtracking algorithm into 3D works well, but it is not suitable to make Deventer's Maze without modification. The projection of 3D path generated by the algorithm on the orthogonal walls of the puzzle would inevitably contain loops. Indeed, the absence of loops on the walls seem to be the leading constraint in this problem.

A simple idea would be to build 4 separate mazes in parallel using the backtracking algorithm. 3 of these mazes would be two dimensional, representing the sides of the cube, while the fourth one would be fully 3D. The 3D maze would be the primary one used for the construction: the backtracker would explore the cells at will, except that while finding neighbouring adjacent unvisited cells, the side mazes would be used to guard against forming loops. Simply put, if the new candidate unvisited cell's projection is visited, and  no direct connection exists to that cell on the side maze, it is not elligible to be the candidate for the neighbour. Unvisited projection cells and those that already have connection (including to itself) are allowed.

This generation procedure has to be repeated, since not all of the cells will be visited on the first call of the backtracker. Some of the cells will be inaccessible from any one given path, and thus the backtracker has to be called again, starting from the next unvisited cell found.

This is perhaps a little obfuscated explanation; please check the code for the details.

I made an implementation of the Deventer Maze generator in Javascript HERE.

The repository is available at: https://github.com/dagothar/deventer.

.

Fig. 2. JS implementation of the generator. Take a look!

This is how the algorithm looks in action (fig. 3):

Fig. 3. Generating a new 8 x 8 x 8 maze.

The result is presented below (fig. 4):

Fig. 4. The result.

Of course, it is also possible to build larger puzzles (see fig. 5), although it quickly becomes a computational challenge.

Fig. 5. Generating large mazes may take a while (25 x 25 x 25).

I programed the generator such that you can try solving the generated mazes as well. The black star shape is the cursor, and you can move it using the W / A / S / D / Q / E keys:

• W / S move the cursor in the X direction (away / towards the red maze),
• A / D move the cursor left / right (away / towards the green maze),
• Q / E move the cursor down / up (towards / away the blue maze).

It is quite difficult to solve even the simplest mazes (see 3 x 3 x 3 in fig. 6)! In case you get stuck, you can use the input fields for the cursor position in the panel on the right to move without the path constraints.

Fig. 6. Navigating the 3 x 3 x 3 maze.

The panel on the right also provides some information. First, it indicates if the current maze corners all belong to a single path component. This will not always be the case. Next, the number of separate paths is provided. The first path will most likely be the largest component and its size is also provided.

There are still a couple of problems with this approach though. Very often, no path is generated that connects all corners of the maze. Such a result I do not consider to be a proper puzzle, since not all of the corners can be reached from single chosen starting configuration. The issue could perhaps be amended by growing separate and unbiased trees at every corner of the cube and then prioritizing the merging of the trees. I am not sure that would guarantee that the generated puzzle is proper.

Of course, it is likely not possible to make a nice random and aesthetic tree exploring all cells of the puzzle. The original creation itself did have cells which were not reachable from the starting configuration.

It would be nice to create the actual 3D models based on the generator presented here. I will work on that in the future.

Mazes

Fig. 1. Yo, I heard you like mazes...

(Check out the application here.)

There is scarcely anything in the world that I like more than mazes. It wasn't until quite recently till I had an opportunity to navigate a real hedge maze made out of planted bushes, located in Egeskov in Fyn, Denmark. The maze proved to be considerably more dificult than I expected! It took me nearly 40 minutes to get to the exit. I greatly recommend this wonderful place - there are lots of other amazing things to see there!

Fig. 2. Egeskov maze (from egeskov.dk).

This post is about mazes. I made a little JS application for maze generation, solving and general maze playfulness (see fig. 3). The application is located HERE, and the source code is available at https://github.com/dagothar/labyrinth.

Fig. 3. The Labirynth application.

The demo includes following features:

• create mazes of various dimensions using backtracking method,
• navigate mazes using W, S, A, D keys,
• click on the maze to make the Theseus dot go to the indicated direction,
• animated maze creation,
• customize maze looks (cell dimensions and color),
• upload your own background (makes for some nice avatar pictures!),
• test out parametrizable modified normal distribution used for maze generation,
• bugs (?).

Many resources are available on the topic of maze generation on the web. One that I can certainly recommend is Jamis Buck's blog: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap. The blog contains very good descriptions, implementations and animations of various maze generation algorithms. The author has also published a book: Mazes for programmers (which I ordered, but unfortunately it haven't arrived yet; maybe I shall make a review when it does?).

I use a staple of maze generation algorithms: a recursive backtracker. Simply put, each step a connection to a randomly selected neighbouring cell is made by removing the wall in between. If there are no neighbours to choose from, you follow the carved path backwards, until there is an adjacent unexplored cell. The procedure is repeated until all of the cells are explored. One of the bonus features of the method is that you get the tree like structure of the cells completely free of charge, making the subsequent navigation queries that much easier. See the maze being carved out in fig. 4.

Fig. 4. Building a regular maze.

I made it so that you can easily solve the maze and move the Theseus around with a simple click of a mouse (see fig. 5).

Fig. 5. Solving the maze.

You can also upload your own background image and get some nice effects! (You should probably set the transparency on the path/wall colors for this to work).

One of the interesting things you can do is to give a 'kick' to the distribution of offsets used when selecting the next neighbouring cell. You can scale, twist and turn the normal distribution so that some directions are preferred to the others. This could possibly make the generated mazes more interesting giving them some kind of structure. 

How is the distribution 'stretched'? A couple of transformations are applied: scaling, rotation and translation. See the image below for the visual explanation (fig. 6).

Fig. 6. Modifying the random offset distribution for selecting new tiles to explore.

Mathematically, the new distribution is calculated as:

x = randn()

y = randn()

nx = sx*cos(a) * x - sy*sin(a) * y + tx;

ny = sx*sin(a) * x + sy*cos(a) * y + ty;

where x and y are random variables with normal distribution, sx and sy are scaling factors, a is the angle and tx/ty are the translations.

I made the application such that custom user expressions can be used to change the shape of normal 2D distribution. This is done by entering JavaScript language expressions into assorted fields: Angle, X scale, Y scale, X translation and Y translation. All JS math function can be used in these. Additionally, the following variables are available:

• x - the current column of the maze,
• y - the current row of the maze,
• cx - the center column of the maze,
• cy - the center row of the maze.

Check the text below for some ideas and examples.

Note: The maze generation starts at the row and column indicated by the red dot. Some of the effects are achieved when starting from the center of the grid.

Let's try that with the following set of distribution parameters (see fig. 7):

x scale:

Math.sqrt(Math.pow(x-cx, 2)+Math.pow(y-cy,2))

y scale:

Math.sqrt(Math.pow(x-cx, 2)+Math.pow(y-cy,2))

x translation:

-(x-cx)

y translation:

-(y-cy)

Such a distribution prefers the choice of the newly explored cells located close to the center of the maze. The effect seen in fig. 7 is a maze in which the passages tend to align slightly in concentric layers starting in the middle.

Fig. 7. Building 'ring' maze.

In the example below, the distribution is somewhat stretched and the angle depends on the angular position of the current cell with respect to the middle of the maze (see fig. 8). The parameters are (angles are in radians!):

angle:

1.57+Math.atan2(y-cy, x-cx)

x scale:

3

Fig. 8. Building 'concentric' maze.

The next maze shows the usage of the trigonometric functions. It is built on a 32x32 grid, so that the values of 0.1x and 0.1y span the [0, pi] range. The angle and translation parameters are left as default, but scaling is done in the following fashion:

x scale:
10*Math.sin(0.1*x)

y scale:
10*Math.sin(0.1*y)

The result is shown in fig. 9. The sides of the maze are mostly horizontal/vertical pathways, while the center remains tangled like in a regular maze. The center forms a characteristic 'bump'.

Fig. 9. Building 'bump' maze.

Another example - switching corridor directions:

x scale:
(x-cx)/(y-cy)>0 ? 20 : 1

y scale:
(x-cx)/(y-cy)>0 ? 1 : 20

Fig. 10. Checker-pattern maze.

What kind of a maze can you build?