Bresenham algorithm derived and application in rpg game

The Bresenham algorithm was originally used to draw straight lines in graphics. No matter how large the screen resolution is, it is always composed of square pixels. When drawing an angled straight line on the screen, the pixels will not all fall on the straight line. For points on a straight line, an algorithm is needed to calculate the point closest to the straight line or the most suitable point. BresenHam algorithm is one of them. This algorithm only uses faster integer addition, subtraction and bit shifting, so it is very efficient.
The Bresenham algorithm is generally also used in rpg games or other games that require pathfinding. The map of this type of game will be divided into very small grids (for example: 32 pixels * 32 pixels), using tools, you can mark the blocking area of ​​the map, and then export the map configuration file (for example, json or xml, etc.).
When the entity of the rpg game needs to find a way, the first step needs to calculate whether the entity can pass through the target point in a straight line according to the blocking information of the map. At this time, the bresenham algorithm is needed.
This article only considers the case where the slope of the straight line is greater than 0 and less than 1.

Let’s first look at a dda algorithm:
function dda(x0: number, y0: number, x1: number, y1: number) {
let output = [];
let k = (y1-y0) / (x1-x0);
let x = x0 + 1; // initial value of x
while (x <= x1) {
let y = Math.floor(k * (x + 1) + 0.5);
output.push({ x: x, y: y });
x = x + 1;
}< br>return output;
}
There is very little code, but the multiplication and addition of floating-point numbers are used in the calculation, which is not an efficient method.

Next, let’s look at the derivation process of the bresenham algorithm.
There are two derivation methods for the Bresenham algorithm, as shown in the following figure:

For the sake of simplicity, suppose that the linear equation is y = kx, which means that the starting point is the origin of the coordinates.

1. Set variables, xStep = 1; totalXstep = 0; totalYstep = 0; lineY = 0; gridY = 0; preGridY = 0; deltaX = x1-x0; deltaY = y1-y0. Where lineY is the real ordinate on the line, gridY is the coordinate of the selected grid, and preGridY is the coordinate of the previous grid.
2. From y = kx, we know that when x increases by 1, the increment of y is k.
3. Start deduction from x0.
   A. When x = x0 + 1, totalXstep = totalXstep +1, lineY = y0 + k, the discriminant is k-0.5.
   When k-0.5 >= 0, gridY = y0 + 1, totalYstep = totalYstep + 1;
   When k-0.5 <0, gridY = y0;
   preGridY= gridY;
   B . When x = x0 + 2, totalXStep = totalXStep + 1, lineY = y0 + totalXstep k, the discriminant is totalXstep k – (totalYstep + 0.5);
   When totalXstep k – ( totalYstep + 0.5) >=0, gridY = preGridY +1, totalYstep = totalYstep + 1;
   when totalXstep k – (totalYstep + 0.5) <0, gridY = preGridY,
   preGridY= gridY;
4. From the above, the discriminant is totalXstep k – (totalYstep + 0.5) >=0, k = deltaY / deltaX; substitute k into the left formula, and multiply both sides by deltaX, Multiply by 2 to get:
   2totalXstep deltaY –2deltaXtotalYstep – deltaX >=0
   It can also be written as:
   2 totalXstep deltaY> 2deltaX*totalYstep + deltaX
   Therefore, this algorithm only leaves integer multiplication and addition.

Next, let’s change to another derivation method.
1. Set variables d1, d2, Xi, Xi+1, Yi, Yi+1, Y, X, Hi, Hi+1

2. d1 = Y -Yi =(k(Xi +1) + b) –Yi
   d2 = Yi +1-Yi = Yi +1 -(k(Xi +1) + b)
3. d1-d2 = 2k(Xi +1) – 2 Yi +2b-1
   4. Substitute k = deltaY/deltaX into the above formula to get
   deltaX(d1-d2) = 2deltaY Xi -2deltaX Yi + c
   Let Hi = deltaX(d1-d2) = 2deltaY Xi -2deltaX Yi + c
   then Hi+1 = 2deltaY Xi+1 -2deltaX em> Yi+1 + c
   Hi+1-Hi = 2deltaY( Xi+1-Xi) – 2deltaX( Yi+1-Yi)
   Let Xi+1 = Xi + 1.
   Hi+1 = Hi +2deltaY – 2deltaX( Yi+1-Yi)
   Then:
   A. If you select the pixel at the top right, that is: Yi+1 – Yi =1, then Hi+1 = Hi +2deltaY – 2deltaX
   B. If you select the right pixel, that is, Yi+1 = Yi, then: Hi+1 = Hi +2deltaY
   The first parameter h0 at the starting pixel (x0, y0) is:
   h0 = 2deltaY – deltaX ;
   This algorithm only uses faster integer addition, subtraction and bit shifting, and is an efficient algorithm.
   function bresenham(x0: number, y0: number, x1: number, y1: number) {
   let output = [];
   let deltaX = x1-x0;
   let deltaY = y1- y0;
   let err = 2 deltaY-deltaX;
   let x = x0;
   let y = y0;
   while (x <= x1) {
   x++;< br>//First assume that the point on the right is taken, indicating that err+2deltaY is less than 0; // In fact, it is also possible to assume that the point on the upper right is taken, and the judgment conditions are different err = err + 2 deltaY; if (err >= 0) {//It means that the point on the right is wrong, and the point on the upper right should be taken y++;err = err-2 * deltaX;}output.push({ x: x, y: y} );}}