0

我正在使用 Bresenham 算法为玩家运动制作游戏原型。我在这里使用了“编辑”下的实现，但我没有存储要点：Bresenham algorithm in Javascript

我数学很弱（而且我不是开发人员！），所以这可能阻碍了我找出问题所在的能力。我发现了一篇很棒的文章，它在更高的层次上解释了该算法：简化的 Bresenham 线算法：它*究竟*做什么？

这是我的代码的一些输出。每次循环迭代时，我都会检查我们是否超出了合理的区域。这种情况始终如一地发生。我的错误计算和查找点存在问题，但我没有数学能力知道如何解决它。

在下面的代码中，currentX 和 currentY 应该不断变化以接近 targetX 和 targetY。您会看到当前坐标和目标坐标中的一个是相同的，但另一个会非常不同。这没有任何意义，因为根据算法，到那时 currentX 和 currentY 都应该非常接近目标坐标。

编辑 3：新输出

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

编辑：下面发布的代码。

EDIT2：下面发布了更多相关代码。

hermes.js - 描述玩家的角色 (Hermes) 以及他与 2d 游戏平面的关系

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 - 高级游戏逻辑。重点关注的是click事件处理程序，否则这里还没有太多

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

}
4

2 回答 2

1

如果我读错了，请原谅我：看起来您将 x 和 y 混合在一个位置。

在代码的开头有块 

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

这应该是读this.currentX < this.targetX。

您可能会为完整性检查做的另一件事是将中断的 === 逻辑更改为 <= 或 >=。由于您已经知道 sx 和 sy 的方向，这可以在一行中完成：

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

您也可以存储sx*this.targetX并sy*this.targetY保存循环中的重复计算，但这可以在代码运行后完成！

于 2012-04-03T04:49:03.240 回答
0

我在这里做了一个小提琴，用我自己的 Bresenham js 实现，它很好地收敛到 (100,100) 的 (34,26)。

无法立即看出您的代码为何无法收敛。

.currentX' and '.currentY我想知道在算法运行时是否有其他东西在影响对象？尝试使用私人var currentX和var currentY设置对象的.currentX' and '.currentY同情。这将消除外部影响。

于 2012-04-03T04:51:44.513 回答