THE ENTIRE SERIES
More to come…
Note: None of the code for any of these proc-gen tutorials is highly optimised. My goal was to get the concepts across as simply as possible, rather than to make them run as fast as possible. Use the following as a springboard for further learning and experimentation, rather than as the best solution possible.
Also, if you are a complete beginner, it’s probably best to start at the first entry and work your way through, as further into the series we get, the more knowledge from previous entries is assumed.
It’s time for some Bresenham’s! This algorithm is useful for a variety of things, but I use it most commonly to connect two points on a grid. I first learned how to use it when I was making a game set on a procedurally generated island. I created a bunch of different points to represent the coast-line and I needed to connect them together using lines so that I could flood fill the interior/exterior of the island with land and water respectively. Bresenham’s came to my rescue and it’s been part of my repertoire ever since.
Hopefully after reading this tutorial it will be a part of yours as well!
Contents
TWO OPTIONS
There’s generally two options that people have to choose from when connecting two points in an unbroken line, Digital Difference Analyser (DDA) and Bresenham’s line equation (which I will call BL from now on).
However, it isn’t really much of a choice. BL is faster and more efficient, here’s a few reasons why:
- DDA uses floating point arithmetic, whereas BL only uses integers.
- DDA uses multiplication and division, whereas BL only uses addition and subtraction.
- DDA is less precise than BL.
Because of these points, BL is both faster to run and more efficient than DDA. So that’s why we’re going with BL.
As a side-note, some people might ask why not simply use draw_line() for this? Well, I would not be surprised at all to find out that draw_line() is, in fact, using BL under the hood. However, draw_line() has exactly one purpose and that is to put pixels on the screen. If we simply want to draw a line, we should indeed be using draw_line() but if we want to alter the values of cells in a line on a grid or something like that, then draw_line() is no good and that is why we want to implement BL.
THE MATHS
I have something to admit. I’m terrible at maths. This is quite a heavy burden to bear as a game designer (oh woe is me). However, I’m also always open to learning and I eagerly dive into new challenges as they present themselves.
When I first encountered BL and saw this sort of thing:
Substituting m by
and introducing decision variable
di=△x (s-t)
di=△x (2
=2△xyi-2△y-1△x.2b-2yi△x-△x
di=2△y.xi-2△x.yi+c
Where c= 2△y+△x (2b-1)
I think my brain curdled a little. When I very first started doing game dev, it took me an embarrasingly long time to figure out what delta meant (it’s the little triangle, for those not in the know, and it means “change”, often related to change over time or change over distance).
However, when you really break it down, BL is not actually that complex and, at least a basic unoptimised interpretation of it, doesn’t need that sort of “mathy” explanation.
The basic premise is that you look at the angle (the slope, or m, as it is often called) of the line between two points and use that to determine which is currently the closest rounded point to the line as we step along it. For each point, we take the two nearest whole points and calculate the difference between each of those nearest points compared to where the actual line is:
It’s basically a comparison of D1 versus D2 in the above diagram. Whichever is smaller is the point which will be “filled” by BL.
THE GML ALGORITHM
Ok, no more suspense, let’s look at what we’re in for:
function BresenhamLine(x1,y1,x2,y2,func) {
// Differential
var dx = x2-x1;
var dy = y2-y1;
// Increments
var sx = sign(dx);
var sy = sign(dy);
// Segment Length
dx = abs(dx);
dy = abs(dy);
var d = max(dx,dy);
var r = d/2;
if (dx > dy) {
for (var i=0;i<d;i++) {
func(x1,y1);
x1 += sx;
r += dy;
if (r >= dx) {
y1 += sy;
r -= dx;
}
}
}
else {
for (var i=0;i<d;i++) {
func(x1,y1);
y1 += sy;
r += dx;
if (r >= dy) {
x1 += sx;
r -= dy;
}
}
}
}
It might seem intimidating at first but we’ll break it down and it should be perfectly understandable by the end.
Firstly, we have five arguments to the function. The first point we want to start calculating from, x1 and y1, the point where we want the line to end, x2 and y2 and I’ve added a sneaky little method variable called func at the end there which we can use to apply something to each point that BL calculates.
Let’s get into the actual code now:
// Differential
var dx = x2-x1;
var dy = y2-y1;
The differential is the “delta” I mentioned above. It’s basically the difference (or amount of change) between the two points. So we’re looking at the distance between the two x positions and the distance between the two y positions. If we take two points: x1 = 5, y1 = 10 and x2 = 20, y2 = 22, then dx = 20-5 = 15 and dy = 22-10 = 12.
That’s a quick breakdown of it graphically.
// Angle
var sx = sign(dx);
var sy = sign(dy);
This is basically figuring out what angle the line is pointing in. sign(), as a function, returns whether a number is positive or negative, sign(-20) would return -1, sign(20) would return 1, and sign(0) would return 0. So we can use that to tell which direction the angle between each axis of the line is pointing.
Above we can see how the directions would relate. If sign(x2-x1) == -1, we can assume that the line is pointing from right to left, if the sign(x2-x1) == 1, we know the line is pointing left to right. The same goes for up or down.
You might ask why do we need to use sign() to figure out whether a sum is negative or not? The answer is that we don’t at the moment but later on (and in other circumstances unrelated to BL) it can be very useful to have any negative numbers always reduced to -1 and any positive numbers always reduced to 1.
A quick example would if we wanted to add only 1 or -1 to a number depending on whether something is positive or negative: x += sign(xvec); will add either 1, 0 or -1 to x, regardless of what value xvec holds. It’s a nice shorthand way of figuring this stuff out rather than using an if statement.
// Segment Length
dx = abs(dx);
dy = abs(dy);
var d = max(dx,dy);
All this is doing is figuring out which of the differentials is the largest. abs() returns a positive version of a number, regardless of it’s actual value. So abs(-100) will return 100 and abs(100) will also return 100, it just removes the negative. This value d is then used the calculate the “remainder” or r as we move along the line in the next line:
var r = d/2;
So r is the remainder. The remainder is an interesting concept here and really the key to BL. As the computer moves along whichever axis has a greater distance to travel, it calculates the remainder for each step and it then uses the remainder to figure out when it should increment whichever of dx or dy is the smaller of the two. To reiterate, d holds the larger of the two, and the larger one is the axis that will be incremented more often. As we are incrementing the larger one, we eventually reach a point where the smaller of the two needs to be incremented and r is how we know when that needs to happen.
To further explain, if we take the line above, we can see that the distance the line travels along the x axis is much larger than the distance it travels in the y axis. So d would end up holding the differential between x1 and x2 (let’s say it’s 10 pixels, for arguments sake: d = 10). We can also see that the differential between y1 and y2 is only 1 pixel, because the line only moves up once (y2-y1 = dy = 1 (because of GMS’ natural y orientation being downwards is positive, it actually is -1, but we’ll pretend it’s 1 to make it easier to follow the rest). Let’s have a look at the first loop of the function and we can see how the loop will actually play out (the second loop is a copy of the first, just targeting the y1 variable, instead of the x1, which is used when the dy is greater than or equal to the dx value):
// Segment Length
dx = abs(dx);
dy = abs(dy);
var d = max(dx,dy);
var r = d/2;
if (dx > dy) {
for (var i=0;i<d;i++) {
func(x1,y1);
x1 += sx;
r += dy;
if (r >= dx) {
y1 += sy;
r -= dx;
}
}
}
If we do the calculation, d equals 10 (as we decided above) and that means r equals 5 (as we can see on the line r = d/2). We can also see that we add dy to r every loop cycle in the for() loop (the first for() loop from the full code block is the loop that will be executed in this example, as we already know that dx > dy, since the line is moving to the right and the distance between x1 and x2 is much greater than the distance between y1 and y2).
What this means is that we add 1 to x1 every loop cycle (sx = sign(dx) which we know is 1 as dx is positive in this example), and we also add 1 to r every loop cycle (since we already know that dy is 1 from the paragraph above the code block). Since r starts at 5 and we are adding 1 to it every loop cycle, once we have gone 1 step more than halfway along the x axis (or 6 additions to r, because half of dx is 5), r will be greater than dx (which is 10), and so we know that we then need to increment the y axis, which you can clearly see in the picture, about halfway along, the y axis gets changed by 1.
That is how BL works. If dy is greater than 1, it increments the y axis sooner. This “theme” continues as the angle changes (in the gif, this angle change is accomplished by moving the mouse around the screen) until dy is greater than or equal to dx, where it swaps to the else statement and instead targets the y axis as the main axis to increment on, adding dx to the remainder until the remainder is greater than dy and then it increments the x axis (pretty much the inverse of the example I gave above).
WHAT THE FUNC?
I suppose now is the time to explain the point of func(x1,y1). It’s not immediately obvious what this is (unless you’re familiar with methods from other languages).
We’ve touched on methods in previous entries in the series, but in this case, we are passing a method function into the BresenhamLine() function itself, which can make it a little bit confusing. It’s a bit like following a ship through a wormhole. It starts in one place, disappears and then appears in another place. To truly understand what is going on, we need an example of the BresenhamLine() function actually being used, so here’s an example:
if (!is_undefined(start_point)) {
var x1 = start_point[0] div CELLSIZE;
var y1 = start_point[1] div CELLSIZE;
var x2 = mouse_x div CELLSIZE;
var y2 = mouse_y div CELLSIZE;
BresenhamLine(x1,y1,x2,y2,function(_x1,_y1) {
var xx1 = _x1*CELLSIZE;
var yy1 = _y1*CELLSIZE;
var xx2 = xx1+CELLSIZE;
var yy2 = yy1+CELLSIZE;
draw_rectangle(xx1,yy1,xx2,yy2,false);
});
}
Wow, the BresenhamLine() function suddenly seemed to grow a third arm called function at the end when we actually used it? Why is there a random bunch of variables in it? I thought we only set it up to take 5 arguments (x1, y1, x2, y2, func)? What we are doing is basically inserting a function as an argument itself. This function then becomes a method which can be called inside the function itself by calling the func argument. If we look back at the original code block, we can see that func(x1,y1) gets executed every loop of the for() loops. This is where our BL implementation differs from draw_line(). Instead of simply drawing a point, we can actually do anything (of course, for the example I am drawing something, so the function we give it has a draw_*() command in it).
Let’s say we wanted to check each point along a grid, and compare and alter values. If the grid holds a value of 1, we want to change it to 2, and if it holds a value of 0, we want to change it to 4. We would do that like this:
BresenhamLine(x1,y1,x2,y2,function(_x1,_y1) {
if (my_grid[_x1][_y1] == 0) {
my_grid[_x1][_y1] = 4;
}
else if (my_grid[_x1][_y1] == 1) {
my_grid[_x1][_y1] = 2;
}
});
my_grid here is a 2D array that we have created sometime beforehand and populated with some values. This BL will check each cell in my_grid along a line from x1, y1 to x2, y2, checking the value of the cell each time and altering it if it equals 0 or 1. We can literally stick any function we wanted to in there and BL would implement it at each point it visits. Also, to make it a little clearer, I will show an empty function so that you can see the proper formatting without the extra lines:
BresenhamLine(x1,y1,x2,y2, function() {} );
You can see that it’s literally the same format as any function, with rounded brackets () that can take arguments and curly brackets {} to open and close the function, then we close off the actual BresenhamLine function with the end rounded bracket ), ending with a semicolon ; like we should for 90% of code lines. I just split the function up with new lines in the previous examples to make it a little bit easier to read.
Try experimenting with some different functions yourself and see what you can come up with. That’s always the easiest way to start to get a grip on this sort of stuff. Try new things, break it, figure out why the thing you tried broke it, rewrite the thing, etc, etc, until you have a good mental map of what you can and cannot do with the thing.
THE NEXT STEP
We’ve come to the end of another entry and I’m asking myself the question I always do. What should I cover next? We could do another dungeon style generation entry, covering Binary Space Partitioning or Room Perturbation or even using Perlin Noise or Simplex Noise to generate some maps. Or we could go over other useful addition to proc-gen that don’t directly generate anything, like A* Pathfinding, flood-fill, or learning more about how we can shape randomness.
You decide! And the decision has been made: Read on with #5: A Flood of Fills.
If you’ve got any comments, criticisms or advice don’t hesitate to comment and let me know, I’m always happy to hear feedback from readers. And if you like what I’m doing, consider supporting me through either a donation at the bottom of the page or buying my game Spaceslingers!
Sign up to get notified whenever I upload a blog post, so you don’t miss any of the next installments!
RefresherTowel Games 