Algorithm to Calculate all possible end points with Tile-based movement

Question

I've been trying to develop an algorithm to show which tiles you can move to on a square board based on these parameters:

-You move your characters around the board each turn to any tile within their movement speed.

-Each horizontal/vertical movement is worth 1 tile.

-Each diagonal is worth 1.5 (rounded down- so the first diagonal is worth 1, and the second is worth 2, and back to 1, etc.).

-You cannot move a character onto a tile that has another character on it, so you must go around.

NOTE: I don't currently check to see if a tile is occupied, I want to take this one step at a time, and the first step is getting a correct result of which tiles the character can go to.

I have a 3d array the size of the board. The third dimension has two layers, the first one is initialized as all 99 except the character you are moving (the origin), which is set to 0. This dimension contains the distance to the origin from each tile. The other layer contains the number of diagonals it took to get to that tile.

Basically I have a recursive function that checks each adjacent tile for the lowest distance to the origin, and sets the current tile to that lowest distance number +1 (or +2 if it is the second diagonal). It moves out from the origin recursively, using the tiles it already filled in to generate a map of all of the potential tiles that it can move to.

`

const int edgeOfBoard = 15;
static int[,,] movementCount = new int[edgeOfBoard, edgeOfBoard, 2]; //movement speed/diagonals tracking matrix

static void Main()
{
    int movementSpeed = 4;  //number of tiles character can move
    int x = 7;              //x starting position
    int y = 7;              //y starting position

    for(int i = 0; i < edgeOfBoard; i++)    //fill movementCount with 99
    {
        for(int j = 0; j < edgeOfBoard; j++)
        {
            movementCount[i, j, 0] = 99;
        }
    }

    movementCount[x, y, 0] = 0; //set origin (character's location) as 0 movements from itself

    pathfinder(movementSpeed, x, y, 0); //run pathfinder algorithm
    print();    //print result
}

private static void print() //print result
{
    for(int y = 0; y < edgeOfBoard; y++)    //print movement to get to a given tile
    {
        for(int x = 0; x < edgeOfBoard; x++)
        {
            if(movementCount[x, y, 0] == 99) //replace 99s with " " to make it easier to read
            {
                Console.Write("| ");
            }else
            {
                Console.Write("|" + movementCount[x, y, 0]);
            }
        } 
        Console.WriteLine("|");
    }

    Console.WriteLine();


    for(int y = 0; y < edgeOfBoard; y++)    //print diagonals needed to get to a given tile
    {
        for(int x = 0; x < edgeOfBoard; x++)
        {
            if(movementCount[x, y, 1] == 0) 
            {
                Console.Write("| ");
            }else
            {
                Console.Write("|" + movementCount[x, y, 1]);
            }
        } 
        Console.WriteLine("|");
    }
}

internal static void pathfinder(int movementSpeed, int x, int y, int depth)
{
    if (depth <= movementSpeed) //cuts off when limit is reached
    {

        for (int Y = -1; Y <= 1; Y++)   //checks all adjacent tiles
        {
            for (int X = -1; X <= 1; X++)
            {
                //Console.WriteLine("y = " + y + ", Y = " + Y + ", x = " + x + ", X = " + X + ", mvC[] = " + movementCount[x + X, y + Y, 0]);

                //Checks if current adjacent tile subject is in bounds and is not the origin of the search
                if (y + Y >= 0 && y + Y <= edgeOfBoard && x + X >= 0 && x + X <= edgeOfBoard && !(Y == 0 && X == 0) && (movementCount[x + X, y + Y, 0] == 99)) 
                {
                    int[] lowestAdjacent = findLowestAdjacent(x + X, y + Y); //find the lowest adjacent tile
                    if (lowestAdjacent[0] + 1 <= movementSpeed) //if it is within the movement speed, add it to the matrix
                    {
                        movementCount[x + X, y + Y, 0] = lowestAdjacent[0] + 1; //update movement speed for subject tile
                        movementCount[x + X, y + Y, 1] = lowestAdjacent[1];     //update number of diagonals needed for subject tile
                        //print();
                    }
                }

            }
        }

        for (int Y = -1; Y <= 1; Y++)   //mmove into already checked tiles to recursively check their adjacent tiles
        {
            for (int X = -1; X <= 1; X++)
            {
                if (y + Y >= 0 && y + Y <= 15 && x + X >= 0 && x + X <= 15 && !(Y == 0 && X == 0) && (movementCount[x + X, y + Y, 0] != 99) && (movementCount[x + X, y + Y, 0] < movementSpeed))
                {
                    pathfinder(movementSpeed, x + X, y + Y, depth + 1);
                }
            }
        }
    }
}

private static int[] findLowestAdjacent(int x, int y) //finds lowest number of movements to get to subject tile (x, y)
{
    int[] lowestRtrn = { 99, 0 }; //movement, diagonals
    int lowest = 99;

    for (int Y = -1; Y <= 1; Y++)   //checks each adjacent tile
    {
        for (int X = -1; X <= 1; X++)
        {
            if (y + Y >= 0 && y + Y <= edgeOfBoard && x + X >= 0 && x + X <= edgeOfBoard) //ensures it is within bounds
            {
                int diag = isDiagonalMovement(x, y, x + X, y + Y) ? diagonalMovementIncrease(movementCount[x + X, y + Y, 1] + 1) : 0;   //checks whether or not it should be diagonally increased
                if ((movementCount[x + X, y + Y, 0] + diag) < lowest)   //adds to result if lower than current
                {
                    lowest = movementCount[x + X, y + Y, 0] + diag;
                    lowestRtrn[1] = movementCount[x + X, y + Y, 1] + (isDiagonalMovement(x, y, x + X, y + Y) ? 1 : 0);
                }
            }
        }
    }

    lowestRtrn[0] = lowest;
    return lowestRtrn;  
}   

private static int diagonalMovementIncrease(int diagonalMovements)  //checks if diagonal is second diagonal (+2 instead of +1)
{
    return diagonalMovements % 2 == 0 ? 1 : 0;
}

private static bool isDiagonalMovement(int x, int y, int X, int Y) //checks if (x, y) is diagonal from (X, Y)
{
    if (
        (x + 1 == X && y + 1 == Y) ||
        (x - 1 == X && y + 1 == Y) ||
        (x + 1 == X && y - 1 == Y) ||
        (x - 1 == X && y - 1 == Y)
        )
    {
        return true;
    }
    else
    {
        return false;
    }
}`

Code Result

This is the result when printed with a movement speed of 4, starting at 7, 7 on a 15x15 grid (simply for testing purposes, edgeOfBoard = 15) (99s replaced with " " on the top grid to make it easier to read)

The top grid is the first layer of the third dimension- the amount of tiles it takes to get to that tile. The bottom grid is the number of diagonals it takes to get to that tile.

The upper left and bottom right quadrants work properly, but the upper right and bottom left do not, which is really stumping me. Can you help me either come up with a new algorithm or fix this one?

Answer 1

You can simplify the business of the diagonal steps being counted as 1.5 steps by storing the number of steps multiplied by 2. So a horizontal or vertical step becomes 2 and a diagonal step becomes 3, and the maximum distance x becomes 2*x+1. This means we don't have to store an additional grid with how many diagonals have been used to get to any tile.

Let's start with this grid, where a value of 99 indicates it is unvisited and empty:

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99  0 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

We start with the initial position, the tile with coordinates (5,4), on a stack (which is much simpler than using recursion) or a queue (which will be more efficient than a stack in this case). We will then repeatedly take a tile from the queue, check which of its neighbours have a value that is greater than the current tile's value plus two (or three if they are diagonal neighbours), and if so, replace the neighbour's value and add the tile to the queue. After processing all the neighbours of the first tile, we'd have this situation:

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99  2  0  2 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

and these tiles in the queue:

(5,3), (6,3), (6,4), (6,5), (5,5), (4,5), (4,4), (4,3)

When we take the tile (5,3) from the queue, it has value 2, so its neighbour (4,3) would get value 4; however, that tile already has a smaller value 3, so we keep that smaller value, and don't add the tile to the queue. After processing all neighbours of this tile we get:

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99  5  4  5 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99  2  0  2 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

If the maximum distance that can be reached is e.g. 9 (converted from 4 by doing 2*4+1), we keep taking tiles from the queue and processing their neighbours, until no more new tiles have a value of 9 or less, and the queue is empty. The end result is:

99 99 99 99  9  8  9 99 99 99
99 99  9  8  7  6  7  8  9 99
99 99  8  6  5  4  5  6  8 99
99  9  7  5  3  2  3  5  7  9
99  8  6  4  2  0  2  4  6  8
99  9  7  5  3  2  3  5  7  9
99 99  8  6  5  4  5  6  8 99
99 99  9  8  7  6  7  8  9 99
99 99 99 99  9  8  9 99 99 99
99 99 99 99 99 99 99 99 99 99

To translate a distance to a tile from the +2/+3 logic to the +1/+1.5 logic, integer-divide the value in the grid by 2, so that e.g. 9 becomes 4.

You can use the same 2-dimensional grid to also take into account obstacles. You could e.g. mark the empty tiles by 99 and the obstacles by -1. An initial grid:

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 -1 99 99 -1 99 99
99 99 99 99 99  0 99 -1 99 99
99 99 99 99 99 99 99 -1 99 99
99 99 99 99 99 -1 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

would then lead to:

99 99 99 99  9  8  9 99 99 99
99 99 99  8  7  6  7  8 99 99
99 99  8  7  5  4  5  7  9 99
99  9  7  5 -1  2  3 -1 99 99
99  8  6  4  2  0  2 -1 99 99
99  9  7  5  3  2  3 -1 99 99
99 99  8  6  5 -1  5  7  9 99
99 99  9  8  7  8  7  8 99 99
99 99 99 99  9 99  9 99 99 99
99 99 99 99 99 99 99 99 99 99

---

The details of the main part of the code would then be:

• Take a tile from the queue.
• Iterate over its neighbours: (-1,-1) (0,-1) (1,-1) (1,0) (1,1) (0,1) (-1,1) (-1,0) and for each (dx,dy) check:
• whether coordinates (x+dx, y+dy) are within the grid,
• and whether tile (x+dx, y+dy) is not an obstacle,
• and whether tile (x+dx, y+dy) is empty or has a value larger than the current tile plus 2 or 3.
• If yes to all three conditions, replace the value of (x+dx,y+dy) by the value of the current tile plus 2 or 3.
• If the new value of tile (x+dx, y+dy) is less than the maximum distance minus 1, add the tile (x+dx, y+dy) to the queue.