# Approximately circular range of motion on a square tile grid

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?

• Can you make the problem more precise than "it's a bit hit and miss"? What specific cases behave differently than you want, and how should they behave instead? Jun 17, 2020 at 12:44
• instead of cost += 0.3f; try cost *= 1.4f; Jun 17, 2020 at 14:47

## 1 Answer

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.