Jason's Development Blog

No to Internet Censorship. Stop this bullshit.

Quote of the Day
“The current draft of ACTA would profoundly restrict the fundamental rights and freedoms of European citizens, most notably the freedom of expression and communication privacy.”
An open letter signed by many organizations, including Consumers International, EDRi (27 European civil rights and privacy NGOs), the Free Software Foundation (FSF), the Electronic Frontier Foundation (EFF), ASIC (French trade association for web 2.0 companies), and the Free Knowledge Institute (FKI)

' 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