Ошибка алгоритма Bresenham - постоянно выходя за пределы

Я прототипирую игру, используя алгоритм Брешенема для движения игрока. Я использовал реализацию под «EDIT» здесь, но я не храню баллы: Bresenham algorithm in Javascript Ошибка алгоритма Bresenham - постоянно выходя за пределы

Я слабо разбираюсь в математике (и я не разработчик!), Поэтому это, вероятно, затрудняло мою способность выяснить, в чем моя проблема. Я нашел отличный пост, который объясняет алгоритм на более высоком уровне: Simplified Bresenham's line algorithm: What does it *exactly* do?

Вот некоторые результаты моего кода. С каждой итерацией цикла я проверяю, если мы вышли из разумной области. Это происходит последовательно. Есть проблема с вычислением ошибок и точками поиска, но у меня нет математической компетентности, чтобы знать, как ее исправить.

В приведенном ниже коде currentX и currentY должны постоянно меняться, чтобы приблизиться к targetX и targetY. Вы увидите, что есть точка, где один из текущих и целевых коордов будет таким же, но другой будет совсем другим. Это не имеет никакого смысла, потому что по алгоритму currentX и currentY BOTH должны быть очень близки к целевым координатам к тому времени.

EDIT 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

EDIT: Код размещен ниже.

EDIT2: Более соответствующий код размещен ниже.

hermes.js - описывает характер игрока (Hermes) и как он относится к 2-й игровой плоскости

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 - игра логики высокого уровня. Ключ, чтобы сосредоточиться на это обработчик события клика, в противном случае существует не так много здесь еще

источник

2012-04-03 user422318

Можете ли вы разместить свой реальный код? – jfriend00

currentX и currentY, безусловно, идут в правильном направлении. Вы говорите, что они в конечном итоге не сходятся на цели? –

Не беспокойтесь о «ошибке2», размахивая дико - так работает алгоритм. 'error2' - промежуточный расчет, который определяет, в каком направлении воздействовать на« лестницу ». Это не является прямой мерой величины отклонения от прямой. –

Я сделал fiddle here, с моей собственной реализацией js Bresenham, и он сходится красиво на (34,26) от (100,100).

Не могу сразу понять, почему ваш код не сходится.

Интересно, влияет ли какое-либо действие на объект .currentX' and '.currentY во время работы алгоритма? Попробуйте работать с приватными var currentX и var currentY и установить .currentX' and '.currentY объекта в symapathy. Это устранит внешнее влияние.

источник

2012-04-03 04:51:44

Наблюдение Неона о 'if (this.currentX

См. Обновление моей [скрипки] (http://jsfiddle.net/4K5Mm/3/), реализованной как метод '.slideTo()' конструктора Player. Это должно быть нечто вроде подмножества вашего собственного кода. –

Я тебя люблю. Я изменил структуру кода, чтобы работать как ваш с .slideTo(), и теперь currentX, Y сходятся на targetX, Y! Теперь, я просто должен исправить мой рисунок, чтобы я мог видеть слайдер персонажа. – user422318

Прости меня, если я читаю это неправильно: он выглядит, как вы смешиваете свои иксы и у-х в одном месте.

В начале кода есть блок

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-03 04:49:03 soundslikeneon

'если (это.currentX

Спасибо, что заметили смешение x и y. Клянусь, как бы я ни смотрел на код, думая: «О, там должна быть какая-то глупая небольшая ошибка», я никогда этого не вижу. Следовательно, я не специализированный разработчик. ^^ Кроме того, спасибо за отзыв проверки работоспособности. Мой код все еще не работает. >< – user422318

Все еще не работает ?? Можете ли вы отредактировать свой пост, чтобы отразить все сделанные вами изменения? Это только что получило личное :) – soundslikeneon

Ошибка алгоритма Bresenham - постоянно выходя за пределы

ответ

Смежные вопросы