Approximately circular range of motion on a square tile grid

Question

I've been working on a grid based tactics style game to learn the ropes of Unity. I have an issue with movement range for a player unit. Let's say the units move range is 3 spaces..

If I set up each grid tile with 4 neighbours (up down left right), I get this movement range:

If I give each tile diagonal neighbours too- 8 in total, I get this;

What I'm actually looking for is what you'd see in these type of games traditionally, like this;

Here is the code that finds the unit move range list, starting at tile (5, 5). It adds the initial tile/node and its neighbours to the movelist, then works outward looping through all their neighbours. It's based off a youtube tutorial.

public HashSet<Node> getUnitMovementOptions() {

    float[,] cost = new float[mapSizeX, mapSizeY];
    HashSet<Node> moveList = new HashSet<Node>();
    HashSet<Node> tempMoveList = new HashSet<Node>();
    HashSet<Node> finalMoveList = new HashSet<Node>();

    int moveSpeed = 3;
    Node unitStartNode = graph[5, 5];
    finalMoveList.Add(unitStartNode);        
    
    /// Initial costs for the neighbouring nodes
    foreach (Node n in unitStartNode.neighbours) {
        cost[n.x, n.y] = costToEnterTile(n.x, n.y, unitStartNode.x, unitStartNode.y);
        if (moveSpeed - cost[n.x, n.y] >= 0) {
            moveList.Add(n);
            }
        }

    finalMoveList.UnionWith(moveList);
    
    while (moveList.Count != 0) {
        foreach (Node n in moveList) {
            foreach (Node neighbour in n.neighbours) {
                if (!finalMoveList.Contains(neighbour)) {
                    cost[neighbour.x, neighbour.y] = costToEnterTile(neighbour.x, neighbour.y, n.x, n.y) + cost[n.x, n.y];
                    
                    if (moveSpeed - cost[neighbour.x, neighbour.y] >= 0) { tempMoveList.Add(neighbour); }
                    }
                }
            }

        moveList = tempMoveList;
        finalMoveList.UnionWith(moveList);
        tempMoveList = new HashSet<Node>();
        }

    Debug.Log("Total move spaces for this unit is: " + finalMoveList.Count);
    return finalMoveList;
    }

Here is the costToEnterTile function:

public float costToEnterTile(int targetX, int targetY, int sourceX, int sourceY) {

    Tile t = tileTypes[tiles[targetX, targetY]]; // get current tile type
    float cost = t.movementCost;

    // diagonal
    if (sourceX != targetX && sourceY != targetY) {
        cost += 0.3f;
    }

    return cost;
}

If I tamper with the cost value in here, I can get different results in the movement range overall shape, but it's a bit hit and miss depending on the movement range.

Can anyone offer insights in to what path I need to head down to solve this?

Answer 1

I recognise the metrics you used, they are the City Block and the Chessboard metrics respectively. The former resembles a 4-connectivity grid whereas the latter is about 8-connectivity, and you'll be happy to know that there IS a metric that merges the two to achieve the circle-looking shape you are looking for.

The quasi-Euclidean metric measures the total Euclidean distance along a set of horizontal, vertical, and diagonal line segments:

But, there's something more you can do to detect the right cells to move through (you need to work with pathfinding, I guess). You can first find out the potential cells involved in the movement, and find out what is the best metric to use: quasi-euclidean is a very particular metric and could be a little bit overkill for your scopes.

A simple euclidean distance with the right values could do the job, and later you may play around with pathfinding algorithms on the previous result. I suggest these two great guides by Red Blob Games: Circle fill on a grid, addressing the very problem your question is about, and Pathfinding for Tower Defense that focuses both on pathfinding and grid search for games.