Path-finding with Depth Limited Search (Unity/C#~)

Question

I am making a grid based game where characters can move their units turn by turn. Each character has a move amount (for example 4 - where they can move 4 tiles). I've implemented a DLS (which is limited to their move amount). Using this, all available tiles that the player can move to are highlighted.

This works fine. However, I would like modify the algorithm (or implement a specific one) to work out the route. For example, the player wants to G3 - what route should the character take (forward 1, left 1 etc). Bearing in mind that each tile can have different properties (such as some may be blocked).

Code

private void DLS(int x, int z, int depth, float jump, float previousHeight)
    {
        int resistance=1;
        if (depth >=0)
        {
            tiles[x,z].GetComponentInChildren<CheckIfClicked>().Selected();
            if (x+1 < 25)
            {
                CheckTile(x+1, z, depth, jump, previousHeight);
            }
            if (x-1 >= 0)
            {
                CheckTile(x-1, z, depth, jump, previousHeight);
            }
            if (z+1 <25) 
            {
                CheckTile(x, z+1, depth, jump, previousHeight);         
            }
            if (z-1 >=0)  
            {
                CheckTile(x, z-1, depth,jump, previousHeight);          
            }
        }
    }

    private void CheckTile(int x, int z, int depth, float jump, float previousHeight)
    {   
        float tileHeight = tiles[x, z].GetComponent<TileDimensions>().height;
        float difference = tileHeight - previousHeight;
        if (difference<0) difference*=-1;
        if (!tiles[x, z].GetComponentInChildren<CheckIfClicked>().occupied && difference<jump)
        {
            int resistance = tiles[x, z].GetComponent<TileDimensions>().getResistance();
            if (resistance<0) resistance=1;
            DLS(x, z, depth-resistance, jump, tileHeight);  
        }
    }

My code takes advantage of the different tile properties (such as the tiles resistance (some tiles limit the movement) and height (you can only climb so far up)).

Bushes Bushes · Accepted Answer · 2014-07-18T09:55:36

If you wish to use a more efficient algorithm there are two suggested implementations:

1) A star. A star is best used when you know the destination you want to travel to but you need to find the way of getting there. e.g if you clicked in tile G3, and were in G1, you know where you need to go. A star takes advantage of a heuristic which tries to "guess" how much further you have to go. This means that when searching for potential routes, A star will attempt to take what should be the shortest route before attempting to look at other routes. There's a fantastic tutorial here: http://www.policyalmanac.org/games/aStarTutorial.htm

2) Djikstra's algorithm. This is better used when you don't know where you're going but you want to find the nearest node that contains a certain "thing", i.e. you might want your A.I to search for the nearest health pack in an FPS. I've not implemented Djikstra's algorithm before but there are plenty of tutorials available online.

With both you can add properties such as resistance on certain tiles and whatever else.

Path-finding with Depth Limited Search (Unity/C#~)

2 Answers