Bresenham algorithm failure -- continually going out of bounds

Question

I'm prototyping a game using the Bresenham algorithm for player movement. I used the implementation under the "EDIT" here, but I don't store the points: Bresenham algorithm in Javascript

I'm weak at math (and I'm not a developer!), so this has probably hindered my ability to figure out what my issue is. I found a great post that explains the algorithm at a higher level: Simplified Bresenham's line algorithm: What does it *exactly* do?

Here is some output from my code. With each loop iteration, I check if we've gone out of a reasonable area. This happens consistently. There's an issue with my error calculation and finding points, but I don't have the math competency to know how to fix it.

In the code below, currentX and currentY should constantly be changing to approach targetX and targetY. You'll see that there's a point where one of the current and target coords will be the same but the other will be very different. This doesn't make any sense because, by the algorithm, the currentX and currentY BOTH should be very close to the target coordinates by then.

EDIT 3: New output

entering loop
 in loop. currentX,currentY = 100,100 | targetX,targetY = 27,22
 error2 = 10

 in loop. currentX,currentY = 99,99 | targetX,targetY = 27,22
 error2 = 20

 in loop. currentX,currentY = 98,98 | targetX,targetY = 27,22
 error2 = 30

 in loop. currentX,currentY = 97,97 | targetX,targetY = 27,22
 error2 = 40

 in loop. currentX,currentY = 96,96 | targetX,targetY = 27,22
 error2 = 50

 in loop. currentX,currentY = 95,95 | targetX,targetY = 27,22
 error2 = 60

 in loop. currentX,currentY = 94,94 | targetX,targetY = 27,22
 error2 = 70

 in loop. currentX,currentY = 93,93 | targetX,targetY = 27,22
 error2 = 80

 in loop. currentX,currentY = 92,93 | targetX,targetY = 27,22
 error2 = -66

 in loop. currentX,currentY = 91,92 | targetX,targetY = 27,22
 error2 = -56

 in loop. currentX,currentY = 90,91 | targetX,targetY = 27,22
 error2 = -46

 in loop. currentX,currentY = 89,90 | targetX,targetY = 27,22
 error2 = -36

 in loop. currentX,currentY = 88,89 | targetX,targetY = 27,22
 error2 = -26

 in loop. currentX,currentY = 87,88 | targetX,targetY = 27,22
 error2 = -16

 in loop. currentX,currentY = 86,87 | targetX,targetY = 27,22
 error2 = -6

 in loop. currentX,currentY = 85,86 | targetX,targetY = 27,22
 error2 = 4

 in loop. currentX,currentY = 84,85 | targetX,targetY = 27,22
 error2 = 14

 in loop. currentX,currentY = 83,84 | targetX,targetY = 27,22
 error2 = 24

 in loop. currentX,currentY = 82,83 | targetX,targetY = 27,22
 error2 = 34

 in loop. currentX,currentY = 81,82 | targetX,targetY = 27,22
 error2 = 44

 in loop. currentX,currentY = 80,81 | targetX,targetY = 27,22
 error2 = 54

 in loop. currentX,currentY = ,80 | targetX,targetY = 27,22
 error2 = 64

 in loop. currentX,currentY = ,79 | targetX,targetY = 27,22
 error2 = 74

 in loop. currentX,currentY = 77,78 | targetX,targetY = 27,22
 error2 = 84

 in loop. currentX,currentY = 76,78 | targetX,targetY = 27,22
 error2 = -62

 in loop. currentX,currentY = 75,77 | targetX,targetY = 27,22
 error2 = -52

 in loop. currentX,currentY = 74,76 | targetX,targetY = 27,22
 error2 = -42

 in loop. currentX,currentY = 73,75 | targetX,targetY = 27,22
 error2 = -32

 in loop. currentX,currentY = 72,74 | targetX,targetY = 27,22
 error2 = -22

 in loop. currentX,currentY = 71,73 | targetX,targetY = 27,22
 error2 = -12

 in loop. currentX,currentY = 70,72 | targetX,targetY = 27,22
 error2 = -2

 in loop. currentX,currentY = 69,71 | targetX,targetY = 27,22
 error2 = 8

 in loop. currentX,currentY = 68,70 | targetX,targetY = 27,22
 error2 = 18

 in loop. currentX,currentY = 67,69 | targetX,targetY = 27,22
 error2 = 28

 in loop. currentX,currentY = 66,68 | targetX,targetY = 27,22
 error2 = 38

 in loop. currentX,currentY = 65,67 | targetX,targetY = 27,22
 error2 = 48

 in loop. currentX,currentY = 64,66 | targetX,targetY = 27,22
 error2 = 58

 in loop. currentX,currentY = 63,65 | targetX,targetY = 27,22
 error2 = 68

 in loop. currentX,currentY = 62,64 | targetX,targetY = 27,22
 error2 = 

 in loop. currentX,currentY = ,64 | targetX,targetY = 27,22
 error2 = -68

 in loop. currentX,currentY = 60,63 | targetX,targetY = 27,22
 error2 = -58

 in loop. currentX,currentY = 59,62 | targetX,targetY = 27,22
 error2 = -48

 in loop. currentX,currentY = 58,61 | targetX,targetY = 27,22
 error2 = -38

 in loop. currentX,currentY = 57,60 | targetX,targetY = 27,22
 error2 = -28

 in loop. currentX,currentY = 56,59 | targetX,targetY = 27,22
 error2 = -18

 in loop. currentX,currentY = 55,58 | targetX,targetY = 27,22
 error2 = -8

 in loop. currentX,currentY = 54,57 | targetX,targetY = 27,22
 error2 = 2

 in loop. currentX,currentY = 53,56 | targetX,targetY = 27,22
 error2 = 12

 in loop. currentX,currentY = 52,55 | targetX,targetY = 27,22
 error2 = 22

 in loop. currentX,currentY = 51,54 | targetX,targetY = 27,22
 error2 = 32

 in loop. currentX,currentY = 50,53 | targetX,targetY = 27,22
 error2 = 42

 in loop. currentX,currentY = 49,52 | targetX,targetY = 27,22
 error2 = 52

 in loop. currentX,currentY = 48,51 | targetX,targetY = 27,22
 error2 = 62

 in loop. currentX,currentY = 47,50 | targetX,targetY = 27,22
 error2 = 72

 in loop. currentX,currentY = 46,49 | targetX,targetY = 27,22
 error2 = 82

 in loop. currentX,currentY = 45,49 | targetX,targetY = 27,22
 error2 = -64

 in loop. currentX,currentY = 44,48 | targetX,targetY = 27,22
 error2 = -54

 in loop. currentX,currentY = 43,47 | targetX,targetY = 27,22
 error2 = -44

 in loop. currentX,currentY = 42,46 | targetX,targetY = 27,22
 error2 = -34

 in loop. currentX,currentY = 41,45 | targetX,targetY = 27,22
 error2 = -24

 in loop. currentX,currentY = 40,44 | targetX,targetY = 27,22
 error2 = -14

 in loop. currentX,currentY = 39,43 | targetX,targetY = 27,22
 error2 = -4

 in loop. currentX,currentY = 38,42 | targetX,targetY = 27,22
 error2 = 6

 in loop. currentX,currentY = 37,41 | targetX,targetY = 27,22
 error2 = 16

 in loop. currentX,currentY = 36,40 | targetX,targetY = 27,22
 error2 = 26

 in loop. currentX,currentY = 35,39 | targetX,targetY = 27,22
 error2 = 36

 in loop. currentX,currentY = 34,38 | targetX,targetY = 27,22
 error2 = 46

 in loop. currentX,currentY = 33,37 | targetX,targetY = 27,22
 error2 = 56

 in loop. currentX,currentY = 32,36 | targetX,targetY = 27,22
 error2 = 66

 in loop. currentX,currentY = 31,35 | targetX,targetY = 27,22
 error2 = 76

 in loop. currentX,currentY = 30,34 | targetX,targetY = 27,22
 error2 = 86

 in loop. currentX,currentY = 29,34 | targetX,targetY = 27,22
 error2 = -60

 in loop. currentX,currentY = 28,33 | targetX,targetY = 27,22
 error2 = -50

 in loop. currentX,currentY = 27,32 | targetX,targetY = 27,22
 error2 = -40

 in loop. currentX,currentY = 26,31 | targetX,targetY = 27,22
 error2 = -30

 in loop. currentX,currentY = 25,30 | targetX,targetY = 27,22
 error2 = -20

 in loop. currentX,currentY = 24,29 | targetX,targetY = 27,22
 error2 = -10

 in loop. currentX,currentY = 23,28 | targetX,targetY = 27,22
 error2 = 0

 in loop. currentX,currentY = 22,27 | targetX,targetY = 27,22
 error2 = 10

 in loop. currentX,currentY = 21,26 | targetX,targetY = 27,22
 error2 = 20

 in loop. currentX,currentY = 20,25 | targetX,targetY = 27,22
 error2 = 30

 in loop. currentX,currentY = 19,24 | targetX,targetY = 27,22
 error2 = 40

 in loop. currentX,currentY = 18,23 | targetX,targetY = 27,22
 error2 = 50

 in loop. currentX,currentY = 17,22 | targetX,targetY = 27,22
 error2 = 60

 in loop. currentX,currentY = 16,21 | targetX,targetY = 27,22
 error2 = 70

 in loop. currentX,currentY = 15,20 | targetX,targetY = 27,22
 error2 = 80

 in loop. currentX,currentY = 14,20 | targetX,targetY = 27,22
 error2 = -66

 in loop. currentX,currentY = 13,19 | targetX,targetY = 27,22
 error2 = -56

 in loop. currentX,currentY = 12,18 | targetX,targetY = 27,22
 error2 = -46

 in loop. currentX,currentY = 11,17 | targetX,targetY = 27,22
 error2 = -36

 in loop. currentX,currentY = 10,16 | targetX,targetY = 27,22
 error2 = -26

 in loop. currentX,currentY = 9,15 | targetX,targetY = 27,22
 error2 = -16

 in loop. currentX,currentY = 8,14 | targetX,targetY = 27,22
 error2 = -6

 in loop. currentX,currentY = 7,13 | targetX,targetY = 27,22
 error2 = 4

 in loop. currentX,currentY = 6,12 | targetX,targetY = 27,22
 error2 = 14

 in loop. currentX,currentY = 5,11 | targetX,targetY = 27,22
 error2 = 24

 in loop. currentX,currentY = 4,10 | targetX,targetY = 27,22
 error2 = 34

 in loop. currentX,currentY = 3,9 | targetX,targetY = 27,22
 error2 = 44

 in loop. currentX,currentY = 2,8 | targetX,targetY = 27,22
 error2 = 54

 in loop. currentX,currentY = 1,7 | targetX,targetY = 27,22
 error2 = 64

 in loop. currentX,currentY = 0,6 | targetX,targetY = 27,22
 error2 = 74

 in loop. currentX,currentY = -1,5 | targetX,targetY = 27,22
 error2 = 84

 crash. x-distance from target = 29 | y-distance = 17
 in loop. currentX,currentY = 27,22 | targetX,targetY = 27,22
 loop done. currentX,currentY = 27,22 | targetX,targetY = 27,22

EDIT: Code posted below.

EDIT2: More relevant code posted below.

hermes.js - describes the player's character (Hermes) and how he relates to the 2d game plane

var Hermes = function(currentX,currentY) {
this.currentX = currentX;
this.currentY = currentY;
this.targetX = currentX;
this.targetY = currentY;
this.radius = 20;
this.speed = 5;
this.health = 500;

var dir = **I removed this string to protect my privacy**
this.imgSrc = dir + "/img/hermes.jpg";

// https://stackoverflow.com/questions/4672279/bresenham-algorithm-in-javascript
// Bresenham's line algorithm
// will fall apart if i add obstacles.
this.Move = function() {

    var sx, sy;
    var dx = Math.abs(this.targetY - this.currentY);
    var dy = Math.abs(this.targetX - this.currentX);
    var error = dx - dy;

    if (this.currentX < this.targetX) {
        sx = 1;
    }
    else {
        sx = -1;
    }

    if (this.currentY < this.targetY) {
        sy = 1;
    }
    else {
        sy = -1;
    }

    console.log("entering loop");

    while (true) {  

        console.log("in loop. currentX,currentY = " + this.currentX + "," + this.currentY + " | targetX,targetY = " + this.targetX + "," + this.targetY);

        // this.Draw();
        redraw();

        if ((this.currentX == this.targetX) && (this.currentY == this.targetY)) break;
        // if ( (sx*this.currentX >= sx*this.targetX) && (sy*this.currentY >= sy*this.targetY) ) break;
        var error2 = error << 1;
        if (error2 > -dy) {
            error = error - dy;
            this.currentX = this.currentX + sx;
        }
        if (error2 < dx) {
            error = error + dx;
            this.currentY = this.currentY + sy;
        }

        console.log("error2 = " + error2);
        console.log("");

        // temp
        if (this.currentX < -1 || this.currentY < -1 || this.currentX > 600 || this.currentY > 600) {
            console.log("crash. x-distance from target = " + (this.targetX - this.currentX) + " | y-distance = " + (this.targetY - this.currentY) );
            this.currentX = this.targetX;
            this.currentY = this.targetY;
        }

    } // end while loop

    console.log("loop done. currentX,currentY = " + this.currentX + "," + this.currentY + " | targetX,targetY = " + this.targetX + "," + this.targetY);

}; // end move fxn

this.Draw = function () {
    context.drawImage(hermesAvatar, this.currentX, this.currentY, 43, 52);
}; // end draw fxn
}; // end hermes

game.js - high level game logic. The key to focus on is the click event handler, otherwise there's not much here yet

var canvas;
var context;

var map;
var mapArray;
var mapHeight;
var mapWidth;

var hermes;
var hermesAvatar;

var taco1;
var tacoAvatar;

var graph;

$(document).ready(
    function() {
        // begin initialization of an ass ton of globals
            canvas = document.getElementById("canvas");
            context = canvas.getContext("2d");
            map = new Image();
            map.onload = function(){ // do i need this? will jquery do it? 
                context.drawImage(map,0,0);
            };
            map.src = "colored_map.png";

            mapHeight = 597; // make canvas.height?
            mapWidth = 710;

            hermes = new Hermes(100,100);
            hermesAvatar = new Image();         
            hermesAvatar.src = hermes.imgSrc;

            taco1 = new Taco(400, 400);
            tacoAvatar = new Image();
            tacoAvatar.src = taco1.imgSrc;

        // end initialization of globals

    hermes.Draw();
    taco1.Draw();

    // click to send hermes to a point
    $("#canvas").click(
        function(e) {
            var mouseX = e.pageX - this.offsetLeft;
            var mouseY = e.pageY - this.offsetTop;

            hermes.targetX = mouseX;
            hermes.targetY = mouseY;

            hermes.Move();
            redraw();
        }
    );


    } // end parameter fxn to $(document).ready()
); // end $(document).ready()


function redraw() {

    // clears the canvas
    canvas.width = canvas.width; 

    context.drawImage(map,0,0);
    hermes.Draw();
    taco1.Draw();

    // rendering interface functions go here

}

currentX and currentY are certainly going in the right direction. Are you saying they don't eventually converge on the target? — Beetroot-Beetroot, Apr 03 '12 at 03:50
Don't worry about `error2` swinging about wildly - that's the way the algorithm works. `error2` is an intermediate calculation that determines which direction in which to influence the "staircase". It's not a direct measure of the magnitude of deviation from the straight line. — Beetroot-Beetroot, Apr 03 '12 at 03:57
Code added. :) @Beetroot-Beetroot Yes, currentX and currentY are headed in the right direction. They don't converge, though. Shouldn't the last few coords be something like (35,27) if the target is (34,26)? currentY reaches its target first (way before x!) but keeps decreasing. — user422318, Apr 03 '12 at 03:59
@jfriend00 Code added. :) It's part of a pseudo-class created for the player's character. — user422318, Apr 03 '12 at 04:02

score 1 · Answer 1 · answered Apr 03 '12 at 04:49

1

Forgive me if I'm reading this wrong: it looks like you are mixing up your x's and y's in one spot.

At the beginning of your code there is the block

if (this.currentX < this.targetY) {  
    sx = 1;  
}

This should probably read this.currentX < this.targetX.

Another thing you might do just for sanity checking is to change the === logic for the break to be <= or >=. Since you know the direction from sx and sy already, this can be done in one line:

if ((sx*this.currentX >= sx*this.targetX) && (sy*this.currentY >= sy*this.targetY)) break;

You might as well store sx*this.targetX and sy*this.targetY to save yourself the repeated computation in the loop, but that can be done after you get the code working!

answered Apr 03 '12 at 04:49

soundslikeneon

416
3
4

`if (this.currentX < this.targetY) { ` - good point. I missed that. – Beetroot-Beetroot Apr 03 '12 at 04:54
Thanks for noticing the mix-up of x and y. I swear, no matter how much I stare at the code thinking, "oh, there's gotta be some stupid small mistake", I never see it. Hence, I'm not a dedicated developer. ^^ Also, thanks for the sanity check tip. My code still doesn't work. > – user422318 Apr 03 '12 at 05:29
Still doesn't work?? Can you edit your post to reflect all of the changes you've made? This just got personal :) – soundslikeneon Apr 03 '12 at 06:00

score 0 · Accepted Answer · answered Apr 03 '12 at 04:51

0

I have made a fiddle here, with my own js implementation of Bresenham and it converges nicely on (34,26) from (100,100).

Can't immediately see why your code should fail to converge.

I wonder if something else is influencing the object's .currentX' and '.currentY while the algorithm is running? Try working with private var currentX and var currentY and setting the object's .currentX' and '.currentY in symapathy. That will eliminate outside influence.

answered Apr 03 '12 at 04:51

Beetroot-Beetroot

18,022
3
37
44

Neon's observation about `if (this.currentX < this.targetY)` will most probably fix it. On second thoughts, my "outside influence" theory is probably a red herring. – Beetroot-Beetroot Apr 03 '12 at 05:24
See update of my [fiddle](http://jsfiddle.net/4K5Mm/3/) implemented as a `.slideTo()` method of a Player constructor. This should be something like a subset of your own code. – Beetroot-Beetroot Apr 03 '12 at 07:57
I love you. I changed my code structure to work like yours with the .slideTo(), and now the currentX,Y converge on targetX,Y! Now, I just gotta fix my drawing so I can see the player character slide. – user422318 Apr 04 '12 at 00:09
Satisfying though it is to have Bresenham working, is possible that the screen won't update until the target point is reached - in other words you may well not see the step by step movement. In general, browsers don't attempt to keep the graphical interface (the screen) updated with intermediate DOM state but jump to whatever final state occurs. A way round this is to use jQuery's `.animate()` which employs multiple, sequential threads to provide breaks in which the browser is free to update the screen. The `.animate()` method also offers the advantage of completing in a given time, say 500ms. – Beetroot-Beetroot Apr 04 '12 at 01:44
Also, please reserve some love for @soundslikeneon who spotted the X-Y bug. – Beetroot-Beetroot Apr 04 '12 at 23:47

Bresenham algorithm failure -- continually going out of bounds

2 Answers2