Jason's Development Blog

I really like procedurally generated content. It’s hard to get right, but when you do…well, ever played Dwarf Fortress or Minecraft? Well I like Dwarf Fortress a lot as a game, once you get past the simple graphics it’s a very fun game, and it gets more and more fun with every new release. And oh yes, there is fun to be had with this game.

Over at GameDev.net, a must-see sight for Game Development, /* Why you crying? */ has an interesting post in which JTippetts talks about Minecraft-like procedural generation using Perlin Noise. Personally, I found it a fascinating little read that got me thinking a lot about procedural content. Using Perlin Noise to generate a heightmap is nothing new, in fact it’s relatively ancient technology. But none-the-less it definitely can have some impressive results.

For those interested in Perlin Noise, I suggest a walk through Wikipedia. As computer science nuts, we should always take advantage of Wikipedia actually being pretty decent for our chosen field and whilst the Perlin noise doesn’t have much detail on the implementation itself  it does have useful links.

Or, if you want me to just show you a few useful links, here’s some on three different types of noise to get you started, all of which I pulled off my…you guessed it, walk through Wikipedia.

• Make Noise by Ken Perlin
• Simplex Noise Demystified
• An explanation and implementation of Value Noise (mislabeled as Perlin noise)

For now I’m just looking and not really “touching” but colour me interested and don’t be surprised if I get my hands dirty in a later post. And if you want to get your hands dirty, but not too dirty, I recommend the LGPL’d LibNoise library. No sense in reinventing the wheel.

Quote of the Day
“During the test (a 20 sword free-for-all), a guy got stabbed in the lower body twice, his guts popped out, and then a third guy came up and severed his exposed guts, so that all seems to be working.”
Tarn Adams aka. Toady One, creator of Dwarf Fortress

And now for something completely different…booze!

Ingredients:

• 1 part Vodka
• 1 part White Rum and Coconut
• 2 parts Cranberry Juice
• 3 parts Orange Juice

Just put these into a cocktail mixer, punch bowel, milk jug or container of your choice, mix, and voila and nice and sneakily strong drink punch. I worked it out, and it comes to about 10% alcohol. Enjoy.

Quote of the Day
“It only takes one drink to get me drunk– I can just never remember if its the eighth or ninth.”
George Burns

' Author: Jason Morley (Source: http://www.morleydev.co.uk/blog/2010/11/18/generic-bresenhams-line-algorithm-in-visual-basic-net/)
' Licence: Public Domain

Module Module1

    Sub Swap(ByRef X As Long, ByRef Y As Long)
        Dim t As Long = X
        X = Y
        Y = t
    End Sub

    ' If the plot function returns true, the bresenham's line algorithm continues.
    ' if the plot function returns false, the algorithm stops
    Delegate Function PlotFunction(ByVal x As Long, ByVal y As Long) As Boolean

    Sub Bresenham(ByVal x1 As Long, ByVal y1 As Long, ByVal x2 As Long, ByVal y2 As Long, ByVal plot As PlotFunction)
        Dim steep As Boolean = (Math.Abs(y2 - y1) > Math.Abs(x2 - x1))
        If (steep) Then
            Swap(x1, y1)
            Swap(x2, y2)
        End If

        If (x1 > x2) Then
            Swap(x1, x2)
            Swap(y1, y2)
        End If

        Dim deltaX As Long = x2 - x1
        Dim deltaY As Long = y2 - y1
        Dim err As Long = deltaX / 2
        Dim ystep As Long
        Dim y As Long = y1

        If (y1 < y2) Then
            ystep = 1
        Else
            ystep = -1
        End If

        For x As Long = x1 To x2
            Dim result As Boolean
            If (steep) Then result = plot(y, x) Else result = plot(x, y)
            If (Not result) Then Exit Sub
            err = err - deltaY
            If (err < 0) Then
                y = y + ystep
                err = err + deltaX
            End If
        Next

    End Sub

    Function plot(ByVal x As Long, ByVal y As Long) As Boolean
        Console.WriteLine(x.ToString() + " " + y.ToString())
        Return True 'This just prints each co-ord
    End Function

    Sub Main()
        ' example
        Bresenham(1, 1, 10, 15, New PlotFunction(AddressOf plot))
        Console.ReadLine()
    End Sub

End Module

I wrote this quickly for someone over on a roguelike forum whose Bresenham’s Line Algorithm code wasn’t working. What makes it generic? It uses delegate so you can plug any plotting function you like in there. This means it could be used for graphics, calculating line of sight, and much more without actually needing to touch the function or do needless position calculations.

C# version:

// Author: Jason Morley (Source: http://www.morleydev.co.uk/blog/2010/11/18/generic-bresenhams-line-algorithm-in-visual-basic-net/)
// Licence: Public Domain

using System;

namespace Bresenhams
{
    /// <summary>
    /// The Bresenham algorithm collection
    /// </summary>
    public static class Algorithms
    {
        private static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp;
            temp = lhs;
            lhs = rhs;
            rhs = temp;
        }

        /// <summary>
        /// Plot the line from (x0, y0) to (x1, y1)
        /// </summary>
        /// <param name="x0">The start x</param>
        /// <param name="y0">The start y</param>
        /// <param name="x1">The end x</param>
        /// <param name="y1">The end y</param>
        /// <param name="plot">The plotting function (parameters: x-co-ord, y co-ord. If eturns false, the algorithm stops)</param>
        public static void Line(int x0, int y0, int x1, int y1, Func<int, int, bool> plot)
        {
            bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
            if (steep)
            {
                Swap<int>(ref x0, ref y0);
                Swap<int>(ref x1, ref y1);
            }
            if (x0 > x1)
            {
                Swap<int>(ref x0, ref x1);
                Swap<int>(ref y0, ref y1);
            }

            var dX = (x1 - x0);
            var dY = (y1 - y0);
            var err = (dX / 2);
            var ystep = (y0 < y1 ? 1 : -1);
            var y = y0;

            for (var x = x0; x <= x1; ++x)
            {
                if (!(steep ? plot(y, x) : plot(x, y)))
                    return;

                err = err - dY;
                if (err < 0)
                {
                    y += ystep;
                    err += dX;
                }
            }
        }
    }
}

Quote of the Day
“It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.”
How do we tell truths that might hurt? – Edsger W. Dijkstra