Assets/Scripts/LevelManager.cs
/// <summary>
/// Gets the shortest path distance between two locations in the level
/// using Dijkstra's algorithm.
/// 
/// Precondition is that the starting and ending location must be non-block
/// tiles (i.e. they must be traversable)
/// </summary>
/// <param name="startX">x value of the starting tile</param>
/// <param name="startY">y value of the starting tile</param>
/// <param name="destX">x value of the destination tile</param>
/// <param name="destY">y value of the destination tile</param>
/// <returns>Shortest path distance between the two points, or -1 if
/// the destination could not be reached.</returns>
Gets the shortest path distance between two locations in the level
using Dijkstra's algorithm.

Precondition is that the starting and ending location must be non-block
tiles
Gets the shortest path distance between two locations in the level using Dijkstra ' s algorithm . Precondition is that the starting and ending location must be non - block tiles
public int GetShortestPathDistance(int startX, int startY, int destX, int destY)
    {
        List<string> unvisited = new List<string>();
        for (int i = 0; i < width; i++)
            for (int j = 0; j < height; j++)
                if (level[i, j] != CELL_BLOCK) unvisited.Add(i + "_" + j);
        Dictionary<string, int> distances = new Dictionary<string, int>();
        foreach (var v in unvisited)
        {
            distances[v] = int.MaxValue;
        }
        distances[startX + "_" + startY] = 0;
        var targetLoc = destX + "_" + destY;
        while(unvisited.Count > 0)
        {
            string toVisit = null;
            foreach (var v in unvisited)
            {
                if(toVisit == null || distances[v] < distances[toVisit])
                {
                    toVisit = v;
                }
            }
            unvisited.Remove(toVisit);
            if (toVisit == targetLoc)
                return distances[toVisit];
            int x = int.Parse(toVisit.Split('_')[0]);
            int y = int.Parse(toVisit.Split('_')[1]);
            List<string> neighbors = new List<string>();
            if (x - 1 > 0 && level[x - 1, y] != CELL_BLOCK)
                neighbors.Add((x - 1) + "_" + y);
            if (x + 1 < width && level[x + 1, y] != CELL_BLOCK)
                neighbors.Add((x + 1) + "_" + y);
            if (y - 1 > 0 && level[x, y - 1] != CELL_BLOCK)
                neighbors.Add(x + "_" + (y - 1));
            if (y + 1 < height && level[x, y + 1] != CELL_BLOCK)
                neighbors.Add(x + "_" + (y + 1));
            int altDistance = distances[toVisit] + 1;
            foreach (var neighbor in neighbors)
            {
                if (altDistance < distances[neighbor])
                    distances[neighbor] = altDistance;
            }
        }
        return -1;
    }
public int GetShortestPathDistance ( int startX , int startY , int destX , int destY ) { List < string > unvisited = new List < string > ( ) ; for ( int i = 0 ; i < width ; i ++ ) for ( int j = 0 ; j < height ; j ++ ) if ( level [ i , j ] != CELL_BLOCK ) unvisited . Add ( i + " " + j ) ; Dictionary < string , int > distances = new Dictionary < string , int > ( ) ; foreach ( var v in unvisited ) { distances [ v ] = int . MaxValue ; } distances [ startX + " " + startY ] = 0 ; var targetLoc = destX + " " + destY ; while ( unvisited . Count > 0 ) { string toVisit = null ; foreach ( var v in unvisited ) { if ( toVisit == null || distances [ v ] < distances [ toVisit ] ) { toVisit = v ; } } unvisited . Remove ( toVisit ) ; if ( toVisit == targetLoc ) return distances [ toVisit ] ; int x = int . Parse ( toVisit . Split ( ' ' ) [ 0 ] ) ; int y = int . Parse ( toVisit . Split ( ' ' ) [ 1 ] ) ; List < string > neighbors = new List < string > ( ) ; if ( x - 1 > 0 && level [ x - 1 , y ] != CELL_BLOCK ) neighbors . Add ( ( x - 1 ) + " " + y ) ; if ( x + 1 < width && level [ x + 1 , y ] != CELL_BLOCK ) neighbors . Add ( ( x + 1 ) + " " + y ) ; if ( y - 1 > 0 && level [ x , y - 1 ] != CELL_BLOCK ) neighbors . Add ( x + " " + ( y - 1 ) ) ; if ( y + 1 < height && level [ x , y + 1 ] != CELL_BLOCK ) neighbors . Add ( x + " " + ( y + 1 ) ) ; int altDistance = distances [ toVisit ] + 1 ; foreach ( var neighbor in neighbors ) { if ( altDistance < distances [ neighbor ] ) distances [ neighbor ] = altDistance ; } } return - 1 ; }
Gets the shortest path distance between two locations in the level
using Dijkstra's algorithm.
Gets the shortest path distance between two locations in the level using Dijkstra ' s algorithm .
// Find the unvisited node with the shortest distance // We've reach our destination! Return the distance // Visit all of the node's neighbors and update their distances // Our destination was not found
Shortest path distance between the two points, or -1 if
the destination could not be reached.
Shortest path distance between the two points or - 1 if the destination could not be reached .
startX
int
x value of the starting tile
x value of the starting tile
startY
int
y value of the starting tile
y value of the starting tile
destX
int
x value of the destination tile
x value of the destination tile
destY
int
y value of the destination tile
y value of the destination tile