0
\$\begingroup\$

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:

4 neighbours

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

8 neighbours

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

What i want

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?

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – DMGregory Jun 17 '20 at 12:44
  • \$\begingroup\$ instead of cost += 0.3f; try cost *= 1.4f; \$\endgroup\$ – sirreldar Jun 17 '20 at 14:47
0
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.