Optimising movement on hex grid

Question

I am making a turn based hex-grid game. The player selects units and moves them across the hex grid. Each tile in the grid is of a particular terrain type (eg desert, hills, mountains, etc) and each unit type has different abilities when it comes to moving over the terrain (e.g. some can move over mountains easily, some with difficulty and some not at all).

Each unit has a movement value and each tile takes a certain amount of movement based on its terrain type and the unit type. E.g it costs a tank 1 to move over desert, 4 over swamp and cant move at all over mountains. Where as a flying unit moves over everything at a cost of 1.

The issue I have is that when a unit is selected, I want to highlight an area around it showing where it can move, this means working out all the possible paths through the surrounding hexes, how much movement each path will take and lighting up the tiles based on that information.

I got this working with a recursive function and found it took too long to calculate, I moved the function into a thread so that it didn't block the game but still it takes around 2 seconds for the thread to calculate the moveable area for a unit with a move of 8. Its over a million recursions which obviously is problematic.

I'm wondering if anyone has an clever ideas on how I can optimize this problem.

Here's the recursive function I'm currently using (its C# btw):

private void CalcMoveGridRecursive(int nCenterIndex, int nMoveRemaining)
{
    //List of the 6 tiles adjacent to the center tile
    int[] anAdjacentTiles = m_ThreadData.m_aHexData[nCenterIndex].m_anAdjacentTiles;

    foreach(int tileIndex in anAdjacentTiles)
    {
        //make sure this adjacent tile exists
        if(tileIndex == -1)
            continue;

        //How much would it cost the unit to move onto this adjacent tile
        int nMoveCost = m_ThreadData.m_anTerrainMoveCost[(int)m_ThreadData.m_aHexData[tileIndex].m_eTileType];

        if(nMoveCost != -1 && nMoveCost <= nMoveRemaining)
        {
            //Make sure the adjacent tile isnt already in our list.
            if(!m_ThreadData.m_lPassableTiles.Contains(tileIndex))
                m_ThreadData.m_lPassableTiles.Add(tileIndex);

            //Now check the 6 tiles surrounding the adjacent tile we just checked (it becomes the new center).
            CalcMoveGridRecursive(tileIndex, nMoveRemaining - nMoveCost);
        }
    }
}

At the end of the recursion, m_lPassableTiles contains a list of the indexes of all the tiles that the unit can possibly reach and they are made to glow.

This all works, it just takes too long. Does anyone know a better approach to this?

Answer 1

Thanks for the input everyone. I solved this by replacing the Recursive function with Dijkstra's Algorithm and it works perfectly.

Answer 2

As you know, with recursive functions you want to make the problem as simple as possible. This still looks like it's trying to bite off too much at once. A couple thoughts:

1. Try using a HashSet structure to store m_lPassableTiles? You could avoid that Contains condition this way, which is generally an expensive operation.

2. I haven't tested the logic of this in my head too thoroughly, but could you set a base case before the foreach loop? Namely, that nMoveRemaining == 0?

3. Without knowing how your program is designed internally, I would expect m_anAdjacentTiles to contain only existing tiles anyway, so you could eliminate that check (tileIndex == -1). Not a huge performance boost, but makes your code simpler.

By the way, I think games which do this, like Civilization V, only calculate movement costs as the user suggests intention to move the unit to a certain spot. In other words, you choose a tile, and it shows how many moves it will take. This is a much more efficient operation.

Of course, when you move a unit, surrounding land is revealed -- but I think it only reveals land as far as the unit can move in one "turn," then more is revealed as it moves. If you choose to move several turns into unknown territory, you better watch it carefully or take it one turn at a time. :)

(Later...)

... wait, a million recursions? Yeah, I suppose that's the right math: 6^8 (8 being the movements available) -- but is your grid really that large? 1000x1000? How many tiles away can that unit actually traverse? Maybe 4 or 5 on average in any given direction, assuming different terrain types?

Correct me if I'm wrong (as I don't know your underlying design), but I think there's some overlap going on... major overlap. It's checking adjacent tiles of adjacent tiles already checked. I think the only thing saving you from infinite recursion is checking the moves remaining.

When a tile is added to m_lPassableTiles, remove it from any list of adjacent tiles received into your function. You're kind of doing something similar in your line with Contains... what if you annexed that if statement to include your recursive call? That should cut your recursive calls down from a million+ to... thousands at most, I imagine.