## A Fractal Height Map Generator in Ruby

[I’m migrating my old articles to the blog in order to switch to it entirely]

Date: 25th March 2010

## Introduction

This article describes the theory behind, and how to implement, a basic fractal height map generator. It is based upon the algorithm defined at http://gameprogrammer.com/fractal.html. Height maps are used in many things: positioning software, graphical rendering, and procedural map generation. Given the right conditions, height maps can be used to create visually stunning images, and are frequently used with an alpha channel to simulate clouds.

All source code used in this article shall be made freely available, under a Creative Commons GPL Licence

The implementation which will be defined here outputs an array of numbers, which on the surface seems fairly mundane. However, with a bit of tweaking with VT100 colour codes, or passing to an image generation program, the algorithm can produce outputs such as this:

The ASCII renderer assigns a colour code to a range of numbers and then depending on your ranges, you can create rainbow-like maps like the one above. The grey scale and transparent images had their number arrays passed to an image generation program called RMagick.

## The Theory

I will go through the basic idea again as it was defined in the gameprogrammer link, to keep a consistency with terms used further in the article. So before we get on to the DiamondSquare algorithm, I shall implement the simpler 1 dimensional algorithm, which will describe the height of a line, similar to a horizon. The patterns created show some fractal behaviour, in that it is said to be self-similar. An object is said to be self-similar when magnified subsets of the object look like, or are identical to, the whole and to each other[1].

In context of this algorithm, it means that as we add more detail, the more rougher and major features will still hold true, but more detail will become apparent as we look closer. This makes the algorithm ideal for recursion or iterative methods. This implementation uses an iterative method.

### Midpoint Displacement in One Dimension

For the creation of the 1 dimensional height map, similar to a horizon, a very simple algorithm is used:

```    def generateLine(length)

# Due to this algorithm being simple for
# the articles sake, length should be
# constrained to the powers of 2.
#
# As we need a midpoint, however, length
# should be defined as (2^n)+1.

# Create an array which describes a line.
# Set the default values to 0American Standard Code for Information Interchange
line = Array.new(length, 0)

# Define the range of the terrain values.
# For this example we shall take the range
# of values to be -63 to 63, with the midpoint
# at 0, out default value.
# Range is then 128.
range = 128;

# Work out the number of line segments
# levels there are in the line. As each line
# segment level is defined by deviding by two
# until length is 1, the number of segments
# is the log_2 of the length.
noSegments = Math.log(length-1, 2)

#Iterate through the levels
(1 .. noSegments).each{ |level|

# Work out the line segment length so you
# can properly address the offset.
segLength = (length/2**level)

# Work out the number of line segments
# within this level
noSegL = (2**level)-1

# Iterate through the line segments and
(1 .. noSegL).each{ |segOffset|

# If value is not zero, skip over it, done on a previous
# level
if( line[segLength*segOffset] == 0 )

# Make sure the current value of the line
# is directly midway between its two parents.
line[segLength*segOffset] = (line[segLength*(segOffset-1)] + line[segLength*(segOffset+1)])/2

# Apply random function to value
line[segLength*segOffset] = randomFunction(line[segLength*segOffset], level, range)

end
}
}

return line
end```

Now as you can see the most important part of that algorithm is that which I have purposely missed, randomFunction. This is where you, quite obviously, define how you want your heights defined. A good way is to simply use a bounded random function, where the bounds are defined by the line segment level you are currently within. For example, a function like: ` `

```    def randomFunction(value, level, range)

# Roughness constant 0 < h < 1
# As h approachs 0, the level dependent
# bounds grow and tend to 1 for all values
# of level
h = 0.8

# Define bounds in terms of level and a roughness
# function
multiplier = 2 ** (-h * level-1)

# Perform random function, bound it, and then apply
# multiplier
value += (rand() * (range) - (range / 2)) * multiplier

# Return
return value
end```

` ` Would offset the value of the line a random amount which is bounded by a function dependent on the line segment level and a roughness coefficient. As this function is the heart of this algorithm and the 2 dimensional algorithm, I will go into some detail on the use of the roughness coefficient. If the roughness coefficient is set to 1, then the multiplier acts the same as : $2^{(-l-1)}; 0 < l < infty ; l in mathbb{Z}^+[/latex]. Decreasing the value of h flattens out the function meaning the bounds are less constrictive and allowing for much rougher terrain. Here is a plot of the multiplier when h=0.8 and h=0.2, and a plot of the generated lines when those constraints are used. X axis is equal to line segment level. [gallery columns="2" ids="434,433"] As you can see, the roughness coefficient makes a massive difference to the outputted numbers. For those interested in recreating the plot, I piped the output of the above code into a text file, and then used GNUPlot to make the images.

### Extending into 2 dimensions - The diamond square algorithm

To extend this algorithm into the second dimension, we have to imagine the terrain data as a two dimensional array of numbers. Each number represents a height in this two dimensional field, and so each column and row can be treated similarly to above.

To split up a two dimensional array in a self-similar way we must use squares, or diamonds, which are analogous to the line segments of the 1 dimensional algorithm. Then, rather than using the ends of a line segment to work out a base height the corners of the square, or diamond, are used. For example:

[gallery columns="2" ids="436,435"]

Like the line segment algorithm, the mathematical 'meat' is the same random function as before. The complexity comes in managing which indexes are part of a diamond or a square. So, for example, here is a code segment which works out indexes of a square, depending on level and location, and applies the random function:

` # Get the corners of an arbitrary square and perform operation # on center. # # @param array Array to use # @param topleftIndexX X index of top left of square # @param topleftIndexY Y index of top left of square # @param length Length of the square # @param level Level into the calculation def processSquare(array, topleftIndexX, topleftIndexY, length, level, range, h) # Get coordinates of the corners of the square toprightIndexX = topleftIndexX toprightIndexY = topleftIndexY + length + ((level == 0) ? -1 : 0) bottomleftIndexX = topleftIndexX + length + ((level == 0) ? -1 : 0) bottomleftIndexY = topleftIndexY bottomrightIndexX = topleftIndexX + length + ((level == 0) ? -1 : 0) bottomrightIndexY = topleftIndexY + length + ((level == 0) ? -1 : 0) middleX = topleftIndexX + (length)/2 middleY = topleftIndexY + (length)/2 # Get values topleftValue = array[topleftIndexX][topleftIndexY] toprightValue = array[toprightIndexX][toprightIndexY] bottomleftValue = array[bottomleftIndexX][bottomleftIndexY] bottomrightValue = array[bottomrightIndexX][bottomrightIndexY] # Get average average = (topleftValue + toprightValue + bottomleftValue + bottomrightValue)/4 # Set new value array[middleX][middleY] = average + calculateOffset(level, range, h) end`

Where calculateOffset is the random function in this application. The diamond calculation algorithm is very similar and looks like this:

` # Get the edges of an arbitrary diamond and perform operation # on center # # @param array Array to use # @param topIndexX X index of top of diamond # @param topIndexY Y index of top of diamond # @param length Length of diamond # @param level Level into the calculation def processDiamond(array, topIndexX, topIndexY, arraylength, level, range, h) # Adjust arraylength -= 1 length = arraylength/(2 ** level) #Get coordinates of the diamond rightIndexX = topIndexX + length/2 rightIndexY = (topIndexY == length) ? length/2 : topIndexY + length/2 leftIndexX = topIndexX + length/2 leftIndexY = (topIndexY == 0) ? arraylength - length/2 : topIndexY - length/2 bottomIndexX = (topIndexX + length/2 == arraylength) ? length/2 : topIndexX + length bottomIndexY = topIndexY middleX = topIndexX + length/2 middleY = topIndexY # Get values topValue = array[topIndexX][topIndexY] rightValue = array[rightIndexX][rightIndexY] bottomValue = array[bottomIndexX][bottomIndexY] leftValue = array[leftIndexX][leftIndexY] # Get average average = (topValue + rightValue + bottomValue + leftValue)/4 # Set new value array[middleX][middleY] = average + calculateOffset(level, range, h) # Wraps if(middleX == arraylength) array[0][middleY] = array[middleX][middleY] end if(middleY == 0) array[middleX][arraylength] = array[middleX][middleY] end end`

The only difference with the above snippet is the different indices it retrieves, and that it must handle wrap around for some of the edges.

So currently, we can create arbitrary diamonds and squares within a 2-dimensional array and assign a fuzzy average of the edges according the h value. Now all we need is some code to manage traversing through the levels of iterations and through the diamonds and squares themselves. Here is my solution:

` # The main control loop for the algorithm. # # @param lengthExp Length exponent # @param range Value range # @param h Roughness constant def generateTerrain(lengthExp, range, h) length = (2 ** lengthExp) + 1 array = Array.new array = createArray(array, length) #Go through Levels (irerative recursion) (0 .. lengthExp - 1).each{ |level| # Iterator for the Square part of the algorithm # Will go through the x-axis coords (0 .. (2 ** level) -1 ).each { |sqx| # Y axis coords (0 .. (2 ** level) -1).each { |sqy| gap = length/2 ** level x = (0 + (gap*sqx)) y = (0 + (gap*sqy)) processSquare(array, x, y, gap, level, range, h) } } # Iterator for the diamond part of the algorithm (0 ... (2 ** (level+1))).each { |dix| # Offset in the number of points on the y-axis. Dependant # on if x iteration is even or odd. offset = (dix.even?) ? 1 : 2 (0 ... (2 ** (level+1)/2)).each { |diy| gap = (length/2 ** (level+1)) ygap = 2 * gap x = (0 + (gap*dix)) if (dix.even?) y = 0 + (ygap*diy) else y = gap + (ygap*diy) end processDiamond(array, x, y, length, level, range, h) } } } return array end`

And this gives us our array with its height map hidden inside. Using a library like RMagick we can output images like the ones shown above. To create the gray scale image, the following code was used:

` image = Image.new(array.length, array.length) (0 ... array.length).each { |x| (0 ... array[x].length).each { |y| val = array[x][y] * (2**9) # Create greyscale image image.pixel_color(x, y, Pixel.new(val, val, val, val)) } } image.display`

Which just takes the value in the array, and multiplies it by 512 which gives the values a range of [latex]0 ge v ge 2^{15}, ; frac{v}{512} in mathbb{Z}$

. This gives us the gaseous image that has been generated above.

## Code Listings

A library version of the ruby code found in this tutorial can be found at GitHub.

## References

1. Voss, Richard D., FRACTALS in NATURE: characterization, measurement, and simulation. SIGGRAPH 1987

Based on a work at gameprogrammer.com.

## Android Maps and Routing

Very quick one here.

I’ve been trying to mapping, especially routing, working on an android application I’m developing. I will save you a lot of trouble and tell you to use the inbuilt Google services.

In fact, I found a gem of a post at http://smartandroidians.blogspot.co.uk/2010/06/showing-route-through-google-map-in.html which shows you how to open an intent for routing. I’ll add in some handy extras.

```// Uri to open - this will work in your browser and is actually the uri that maps generates itself
"&dirflg=w");

// Create an intent to view the URI
Intent intent = new Intent(Intent.ACTION_VIEW, uri);

// [Bonus] Set the intent class as a map, so you can avoid an annoying pop up asking whether to
// open in the browser or maps

// Start the activity and close your launching activity
startActivity(intent);
finish();```

I added a couple of things, as my application wanted walking directions and there was an annoying pop up asking what to open the URI with.
First, adding `...&dirflg=w` to the URI forced walking directions.
Second, setting the intent’s class name as in the snippet set a hint to android for what to open the URI with [2].

This isn’t new, but it was hard to track down something clear via searching, so I’m consolidating.

## Setting up

Having played with a few GLSL shaders in C++, I thought that moving to a DirectX/HLSL solution sould be fairly simple.

Creating the most simple pixel shader was easy enough, and SlimDX is a decent wrapper for DX in C# – so after an hour or so I had the standard working triangle floating in space. I wanted to go further (obviously), and having spent the last few days delving into the demoscene and finding the most amazing site for pixelshader techniques (http://www.iquilezles.org/www/index.htm) I wanted to have a shader to work with (x,y) coordinates that were between (-1,1) rather than absolute screen coordinates.

This requires passing the current render area width and height to the shader to normalise with. This is done using Constant Buffers and on the shader side looks like:

```cbuffer ConstBuffer : register(c0)
{
float2 resolution;
}

float4 VShader(float4 position : POSITION) : SV_POSITION
{
return position;
}

float4 PShader(float4 position : SV_POSITION) : SV_Target
{
// Get normalised (x,y)
float2 p = -1 +  2 * (position.xy/resolution);

// Spikes in the corner
float c = abs(p.x*p.y);
return float4(c,c,c,1.0f);
}```

To get the resolution variable into the register for the shader to use, you must create a ConstantBuffer in the program code and assign it to the shade. The Constant Buffer must be a size which is divisible by 16, so if your data is too small, just put it in a bigger buffer.

```// Create data stream, we only need 8 bytes, but round up to 16
var resolution = new DataStream(16, true, true);
// Fill the stream with width/height info - I'm using a renderform
resolution.Write(new Vector2(form.ClientSize.Width, form.ClientSize.Height));
// Rewind the stream
resolution.Position = 0;
// Create and bind a buffer
resolution, //Stream
16,         // Size
// Flags
ResourceUsage.Dynamic,
BindFlags.ConstantBuffer,
CpuAccessFlags.Write,
ResourceOptionFlags.None,
4),
0); // Register```

This lets us run the above shader, giving us:

## Bonus

Having played on shader toy, I repurposed the Deform effect for a static image.

```cbuffer ConstBuffer : register(c0)
{
float2 resolution;
}

float4 VShader(float4 position : POSITION) : SV_POSITION
{
return position;
}

float4 PShader(float4 position : SV_POSITION) : SV_Target
{
// Get normalised (x,y)
float2 p = -1 +  2 * (position.xy/resolution);

// Deform focus
float2 m = float2(0.2f, 0.1f);

// Deform
float a1 = atan((p.y-m.y)/(p.x-m.x));
float r1 = sqrt(dot(p-m,p-m));
float a2 = atan((p.y+m.y)/(p.x+m.x));
float r2 = sqrt(dot(p+m,p+m));

float2 uv;
uv.x = 0.2 + (r1-r2)*0.25;
uv.y = sin(2.0*(a1-a2));

float w = r1*r2*0.8;
float c2 = abs(uv.x*uv.y);
float4 col = float4(c2,c2,c2,1.0f);

return float4(col.xyz/(0.1+w),1.0f);
}```

Result:

## Rails 3 and lighttpd

This was performed on Archlinux with lighttpd 1.4.28 and rails 3.0.3

## Prerequisites

Required packages:

• lighttpd,
• fcgi,
• ruby,
• and their dependencies…

## Ruby Setup

Required gems:

• fcgi,
• bundler

(if you are behind a proxy, the magic gem command is :

``# gem install GEM -r -p "http://[PROXY_URL]:[PROXY_PORT]"``

)

Once you have that you need to create a “dispatch.fcgi” script to do all the rails magic. I found an example one at http://stackoverflow.com/questions/3296206/rails-3-and-fcgi .

``````#!/usr/bin/ruby

require 'rubygems'require 'fcgi'

require_relative '../config/environment'

class Rack::PathInfoRewriter

def initialize(app)
@app = app
end

def call(env)
env.delete('SCRIPT_NAME')
parts = env['REQUEST_URI'].split('?')
env['PATH_INFO'] = parts[0]
env['QUERY_STRING'] = parts[1].to_s
@app.call(env)
end
end

Rack::Handler::FastCGI.run  Rack::PathInfoRewriter.new(YOUR_APP_NAME::Application)

``````

Running a “bundle install” from your app root will make sure all the necessary gems are available for local use. Follow these instructions and run “ruby public/dispatch.fcgi”, if you get no errors, voila!

## Lighttpd Setup

Now, to set up lighttpd you need to merge this with your config:

``````server.modules   += ( "mod_fastcgi", "mod_rewrite" )

\$HTTP["host"] == "localhost" {

server.document-root       =   "/path/to/your/app/public/"

server.dir-listing         =   "disable"
server.error-handler-404   =   "/dispatch.fcgi"

fastcgi.server             =   (
".fcgi" => (
"localhost" => (
"min-procs" => 1,
"max-procs" => 1,
"socket" => "/tmp/ruby-beholder.socket",
"bin-path" => "/path/to/your/app/public/dispatch.fcgi",
"bin-environment" => ( "RAILS_ENV" => "development" )
)
)
)
}``````

A quick “sudo /etc/rc.d/lighttpd restart” and a check of the error logs will tell you if it has worked

## Ruby and Watir: Sending keyboard events to an element

Ok, so you need to send certain keyboard events to an element to properly test a webpage, but stuck how to do it?

Ive looked at some tutorials on the web, but there doesn’t seem a simple solution.
However, I have been experimenting, and this method seems to work fine.

``````# First off create your Watir::IE object
ie = Watir::IE.new

# Then navigate to the page you are testing
ie.goto("mypage.myserver.com")

# Grab the descriptor of the element you wish to send a keyboard command to
# (for example, a text field)
element = ie.textField(:id, "myText")

# Now, I found that keyboard events only work if the Watir::IE window is on top and has
# focus, so for example if we wish to send a "Pageup" keyboard command to the element
# "myText" we would do so by
ie.bring_to_front
element.focus
element.container.focus
element.container.send_keys("{PGUP"})
``````

` `

`This method does require Autoit(http://www.autoitscript.com/autoit3/) to be installed, and a full list of keyboard events can be found here: http://www.autoitscript.com/autoit3/docs/appendix/SendKeys.htm`

` `