Line algorithm that connects all points, no diagonals

Question

I am on a Tron Lightbike. I want to go to a point but I can only make 90-degree turns. This prevents line shapes like this: And only alows lines like this:

Storing these moves I have a Queue implementation (FIFO) that stores the moves as Integers.

UP:    0
RIGHT: 1
DOWN:  2
LEFT:  3

I have the enemy's X and Y position, and I have my X and Y position. I want to make a line where all points are connected (no diagonals) that goes from me to the enemy, and store the direction numbers in my Queue.

What is the way to generate this type of line?

Answer 1

I assume you want a result like this:

This can be achieved by moving from the source cell to the target cell, going e.g. right and down one cell at a time, and deciding each step based on the vertical distance from the ideal line to the center point of the grid cell:

If x is half the size of a grid cell, and α is the slope of the ideal line, then the threshold vertical distance from the center point to the ideal line is x.(1 - tan(α)). If the distance is smaller than this, move horizontally, if it is larger than this, move vertically.

You can also look at it like this: if the ideal line only goes through the left and right edge of the current cell, move horizontally; if it goes through the top/bottom edge of the current cell, move up/down.

If the ideal line is more vertical than horizontal (tangent > 1) use a similar method, but turned 90°: measure the horizontal distance from the cell center to the ideal line, and move vertically for a smaller distance, and horizontally for a greater distance.

---

This JavaScript code snippet shows the algorithm for mainly horizontal lines, like in the example, and the equivalent method for mainly vertical lines, using the cotangent:

function tronPath(a, b) {
    var path = [a];
    var x = a.x, y = a.y;                         // starting cell
    var dx = a.x == b.x ? 0 : b.x > a.x ? 1 : -1; // right or left
    var dy = a.y == b.y ? 0 : b.y > a.y ? 1 : -1; // up or down
    if (dx == 0 || dy == 0) {
        // STRAIGHT LINE ...
    }
    else if (Math.abs(b.x - a.x) > Math.abs(b.y - a.y)) {
        // MAINLY HORIZONTAL
        var tan = (b.y - a.y) / (b.x - a.x);      // tangent
        var max = (1 - Math.abs(tan)) / 2;        // distance threshold
        while (x != b.x || y != b.y) {            // while target not reached
            var ideal = a.y + (x - a.x) * tan;    // y of ideal line at x
            if ((ideal - y) * dy >= max) y += dy; // move vertically
            else x += dx;                         // move horizontally
            path.push({x:x, y:y});                // add cell to path
        }
    }
    else {
        // MAINLY VERTICAL
        var cotan = (b.x - a.x) / (b.y - a.y);    // cotangent
        var max = (1 - Math.abs(cotan)) / 2;      // distance threshold
        while (x != b.x || y != b.y) {            // while target not reached
            var ideal = a.x + (y - a.y) * cotan;  // x of ideal line at y
            if ((ideal - x) * dx >= max) x += dx; // move horizontally
            else y += dy;                         // move vertically
            path.push({x:x, y:y});                // add cell to path
        }
    }
    return path;
}
var a = {x:1, y:1}, b = {x:11, y:5};
var path = tronPath(a, b);
document.write(JSON.stringify(path));