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

}

Answer 1

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.

Answer 2

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!