< Summary

Class:DroneGame.Grid
Assembly:Drone
File(s):/github/workspace/Assets/Scripts/Grid.cs
Covered lines:131
Uncovered lines:28
Coverable lines:159
Total lines:368
Line coverage:82.3% (131 of 159)
Covered branches:0
Total branches:0
Covered methods:11
Total methods:15
Method coverage:73.3% (11 of 15)

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
Grid()0%110100%
PushToHistory(...)0%6200%
GetTileWorldCoordinate(...)0%2100%
Awake()0%110100%
MoveDrone()0%20400%
SetColor(...)0%2100%
DownloadAndParseGridData()0%5.025090%
GenerateGrid(...)0%330100%
GetOrCreateTile(...)0%220100%
FromLetterNumberToVector(...)0%110100%
GetShortestPath(...)0%44096%
GetShortestPath(...)0%440100%
FindAllPathsFrom(...)0%880100%
GetNeighbors(...)0%110100%

File(s)

/github/workspace/Assets/Scripts/Grid.cs

#LineLine coverage
 1using System.Collections.Generic;
 2using System.Linq;
 3
 4using UnityEngine;
 5using UnityEngine.Networking;
 6
 7using TMPro;
 8
 9using Newtonsoft.Json;
 10
 11using MyBox;
 12using System.Collections;
 13
 14namespace DroneGame
 15{
 16  /// <summary>Mostly just a short way to type the dictionary inside a dictionary
 17  /// for the parsed data from the API</summary>
 18  public sealed class ParsedData : Dictionary<string, Dictionary<string, float>>
 19  {
 20
 21  }
 22
 23  /// <summary>The returned final path</summary>
 24  public struct PathReturn
 25  {
 26    /// <summary>Calculated total time that it would take the drone to travel</summary>
 27    public float totalTime;
 28
 29    /// <summary>The path in coordinates</summary>
 30    public List<string> path;
 31
 32    /// <summary>The tile data of the coordinates</summary>
 33    public List<TileData> tiles;
 34  }
 35
 36  /// <summary>Dijkstras algorithm returns all paths to the Start position,
 37  /// since that operation can take a while to complete depending on the amount of nodes
 38  /// we cache the results </summary>
 39  public struct CachedPath
 40  {
 41    /// <summary>Key is the coordinate and value is
 42    /// how long it would take to reach the start position </summary>
 43    public Dictionary<string, float> shortestPath;
 44
 45    /// <summary>Key is the coordinate and value is the shortest next path to Start</summary>
 46    public Dictionary<string, string> previousNodes;
 47  }
 48
 49  /// <summary>The 2D grid that will be used for the path finding</summary>
 50  public sealed class Grid : MonoBehaviour
 51  {
 52
 253    public string url = "https://mocki.io/v1/10404696-fd43-4481-a7ed-f9369073252f";
 254    readonly Dictionary<string, CachedPath> _cachedPaths = new();
 55    public ParsedData parsed;
 256    List<string> _pathHistory = new();
 57
 58    [Header("Prefabs/Assets")]
 59    [SerializeField] Tile _tilePrefab;
 60    [SerializeField] Connector _connectorPrefab;
 61    [SerializeField] Drone _drone;
 62
 63    [Header("UI Inputs")]
 64    [SerializeField] TMP_InputField _startCoordinateInput;
 65    [SerializeField] TMP_InputField _pickupCoordinateInput;
 66    [SerializeField] TMP_InputField _dropOffCoordinateInput;
 67
 68    [Header("Other UI")]
 69    [SerializeField] TextMeshProUGUI _pathElement;
 70    [SerializeField] TextMeshProUGUI _pathHistoryUi;
 71    [SerializeField] TextMeshProUGUI _loading;
 72
 73
 274    readonly HashSet<Tile> _changedColorsTiles = new();
 75
 76    /// <summary>Dict used to convert from letters to numbers</summary>
 277    private readonly Dictionary<char, int> _letterToInt = new(){
 78        {'A', 0},
 79        {'B', 1},
 80        {'C', 2},
 81        {'D', 3},
 82        {'E', 4},
 83        {'F', 5},
 84        {'G', 6},
 85        {'H', 7}
 86    };
 87    Dictionary<string, TileData> _allTilesData;
 88    Dictionary<string, Tile> _allTiles;
 89    string _lastPath;
 90
 91    public TileData this[string coordinate]
 92    {
 6693      get => _allTilesData[coordinate];
 94    }
 95
 96    void PushToHistory(string entry)
 097    {
 098      _pathHistory.Add(entry);
 099      var historyCount = _pathHistory.Count;
 0100      if (historyCount > 5) _pathHistory.RemoveAt(0);
 0101    }
 102
 0103    public Vector3 GetTileWorldCoordinate(string coordinate) => _allTilesData[coordinate].globalCoordinates;
 104
 105    /// <summary>This is a default unity function, it is called when the object is instantiated into the scene</summary>
 106    [ButtonMethod]
 107    void Awake()
 1108    {
 1109      StartCoroutine(DownloadAndParseGridData(url));
 1110    }
 111
 112    /// <summary>This is meant to be called from a button in the UI
 113    /// This method does:
 114    /// * Set some colors for a couple tiles
 115    /// * Get inputs from the UI
 116    /// * Call the pathfinding functions
 117    /// * Start the drone Coroutine that makes it move
 118    /// </summary>
 119    public void MoveDrone()
 0120    {
 0121      if (_drone.alreadyMoving) return;
 122
 0123      var start = _startCoordinateInput.text.ToUpper();
 0124      var pickup = _pickupCoordinateInput.text.ToUpper();
 0125      var dropOff = _dropOffCoordinateInput.text.ToUpper();
 126
 0127      foreach (var currTile in _changedColorsTiles) currTile.ResetColor();
 0128      _changedColorsTiles.Clear();
 0129      SetColor(start, Color.green);
 0130      SetColor(pickup, Color.yellow);
 0131      SetColor(dropOff, Color.blue);
 132
 0133      if (_lastPath != null) PushToHistory(_lastPath);
 0134      var shortestPath = GetShortestPath(new string[] { start, pickup, dropOff });
 0135      _lastPath = $"Path: {string.Join(" -> ", shortestPath.path)}\nTotal Time:{shortestPath.totalTime}";
 0136      _pathElement.text = _lastPath;
 0137      _pathHistoryUi.text = string.Join('\n', _pathHistory);
 138
 0139      StartCoroutine(_drone.FollowPath(shortestPath.tiles));
 0140    }
 141
 142    /// <summary>Set color of a tile based o it's coordinates</summary>
 143    private void SetColor(string coords, Color color)
 0144    {
 0145      var tileToChange = _allTiles[coords];
 0146      tileToChange.SetColor(color);
 0147      _changedColorsTiles.Add(tileToChange);
 0148    }
 149
 150    /// <summary>Download and parse the API</summary>
 151    IEnumerator DownloadAndParseGridData(string url)
 1152    {
 1153      var www = UnityWebRequest.Get(url);
 154
 1155      yield return www.SendWebRequest();
 156
 1157      if (www.result != UnityWebRequest.Result.Success) Debug.Log(www.error);
 158
 1159      var json = www.downloadHandler.text;
 1160      parsed = JsonConvert.DeserializeObject<ParsedData>(json);
 1161      _loading?.gameObject.SetActive(false);
 162
 163#if !UNITY_INCLUDE_TESTS
 164      if (_loading == null) throw new("Loading UI not defined");
 165#endif
 1166      GenerateGrid(parsed);
 167#if !UNITY_INCLUDE_TESTS
 168      _drone.Initialize(this);
 169#endif
 1170    }
 171
 172    /// <summary>Generate grid based on the parsed API</summary>
 173    void GenerateGrid(ParsedData parsed)
 1174    {
 1175      _allTilesData = new();
 1176      _allTiles = new();
 177
 131178      foreach (var currParsedTile in parsed)
 64179      {
 64180        var coordinate = currParsedTile.Key;
 64181        var neighbors = currParsedTile.Value;
 182
 64183        var currTile = GetOrCreateTile(coordinate);
 184
 64185        var currInstance = Instantiate(_tilePrefab, transform);
 64186        currInstance.Initialize(currTile);
 187
 64188        _allTiles[coordinate] = currInstance;
 189
 640190        foreach (var currNeighbor in neighbors)
 224191        {
 224192          var neighborDistance = currNeighbor.Value;
 224193          var neighborCoordinate = currNeighbor.Key;
 224194          var converted = GetOrCreateTile(neighborCoordinate);
 195
 224196          currTile.neighbors[neighborCoordinate] = neighborDistance;
 197
 198          // Since I want to have a visualization of the grid paths,
 199          // I am adding a connector between the tiles and their neighbors
 224200          var createdConnection = Instantiate(_connectorPrefab, transform);
 224201          createdConnection.Initialize(currTile, converted, neighborDistance);
 224202        }
 64203      }
 1204    }
 205
 206    /// <summary>Return an already created tile or create a new one if a tile
 207    /// with the coordinates does not already exist</summary>
 208    /// <param name="key">The coordinate in the format A2</param>
 209    /// <returns>A brand new or already existing Tile</returns>
 210    private TileData GetOrCreateTile(string key)
 288211    {
 288212      if (_allTilesData.ContainsKey(key))
 224213      {
 224214        return _allTilesData[key];
 215      }
 216
 64217      var createdTile = new TileData
 218      {
 219        globalCoordinates = FromLetterNumberToVector(key),
 220        letterCoordinate = key,
 221        neighbors = new()
 222      };
 64223      _allTilesData[key] = createdTile;
 64224      return createdTile;
 288225    }
 226
 227    /// <summary>Transform letter and number coordinate system to a Vector to be used by Unity later</summary>
 228    private Vector3 FromLetterNumberToVector(string letterAndNumber)
 64229    {
 64230      var firstNumber = _letterToInt[letterAndNumber[0]];
 64231      var secondNumber = int.Parse(letterAndNumber[1].ToString());
 232
 64233      return new(firstNumber, 0, secondNumber);
 64234    }
 235
 236    // TODO: Convert this into an async operation
 237    public PathReturn GetShortestPath(string[] positions)
 3238    {
 3239      var positionsLen = positions.Length;
 3240      if (positionsLen < 2) throw new("positions need to have at least 2 items");
 241
 3242      var totalTime = 0f;
 243
 3244      var path = new List<string>();
 3245      var tiles = new List<TileData>();
 246
 18247      for (int pathIndex = 1; pathIndex < positionsLen; pathIndex++)
 6248      {
 6249        var previousCoordinate = positions[pathIndex - 1];
 6250        var nextCoordinate = positions[pathIndex];
 251
 6252        var currPath = GetShortestPath(previousCoordinate, nextCoordinate);
 6253        totalTime += currPath.totalTime;
 254
 6255        if (pathIndex < positionsLen - 1)
 3256        {
 3257          currPath.path.RemoveAt(currPath.path.Count - 1);
 3258          currPath.tiles.RemoveAt(currPath.tiles.Count - 1);
 3259        }
 260
 6261        path = path.Concat(currPath.path).ToList();
 6262        tiles = tiles.Concat(currPath.tiles).ToList();
 6263      }
 3264      return new()
 265      {
 266        path = path,
 267        totalTime = totalTime,
 268        tiles = tiles
 269      };
 3270    }
 271
 272    /// <summary>Find the shortest paths between start and end using Dijkstras algorithm
 273    /// All paths to start node are automatically cached so if it is asked
 274    /// again, there's no need to recalculate it</summary>
 275    /// <seealso cref="FindAllPathsFrom"/>
 276    public PathReturn GetShortestPath(string startPosition, string endPosition)
 11277    {
 278      // If the API were dynamic, we would recreate the grid in here by simply called Awake after deleting the grid
 279      // But since it is static, we don't have to.
 280      CachedPath currCachedPath;
 11281      var path = new List<string>();
 282
 283      // No need to do anything other than return start position if the start and end are the same
 11284      if (startPosition == endPosition)
 1285      {
 1286        path.Add(startPosition);
 1287        return new PathReturn()
 288        {
 289          path = path,
 290          totalTime = 0,
 291          tiles = new() { _allTilesData[path[0]] }
 292        };
 293      }
 17294      if (_cachedPaths.ContainsKey(startPosition)) currCachedPath = _cachedPaths[startPosition];
 295      else
 3296      {
 3297        currCachedPath = FindAllPathsFrom(startPosition);
 3298        _cachedPaths[startPosition] = currCachedPath;
 3299      }
 300
 10301      var node = endPosition;
 10302      var previousNodes = currCachedPath.previousNodes;
 73303      while (node != startPosition)
 63304      {
 63305        path.Add(node);
 63306        node = previousNodes[node];
 63307      }
 308
 10309      path.Add(startPosition);
 10310      path.Reverse();
 311
 10312      return new()
 313      {
 314        path = path,
 315        totalTime = currCachedPath.shortestPath[endPosition],
 73316        tiles = (from currCoordinate in path select _allTilesData[currCoordinate]).ToList()
 317      };
 11318    }
 319
 320    /// <summary>Find all paths to the start position using Dijkstras algorithm
 321    /// This is necessary because the API only have seconds instead of distance, which we can use as weight
 322    /// if we had distance information, we could use A* which is more effective</summary>
 323    CachedPath FindAllPathsFrom(string startPosition)
 3324    {
 3325      var unvisitedNodes = _allTilesData.Keys.ToList();
 3326      var shortestPath = new Dictionary<string, float>();
 3327      var previousNodes = new Dictionary<string, string>();
 328
 393329      foreach (var currNode in unvisitedNodes)
 192330      {
 192331        shortestPath[currNode] = float.MaxValue;
 192332      }
 333
 3334      shortestPath[startPosition] = 0;
 335
 195336      while (unvisitedNodes.Count > 0)
 192337      {
 192338        string minNode = null;
 13056339        foreach (var currNode in unvisitedNodes)
 6240340        {
 6432341          if (minNode == null) minNode = currNode;
 6577342          else if (shortestPath[currNode] < shortestPath[minNode]) minNode = currNode;
 6240343        }
 344
 192345        var neighbors = GetNeighbors(minNode);
 1920346        foreach (var currNeighbor in neighbors)
 672347        {
 672348          var neighborCoordinate = currNeighbor.Key;
 672349          var totalCost = shortestPath[minNode] + currNeighbor.Value;
 672350          if (totalCost < shortestPath[neighborCoordinate])
 231351          {
 231352            shortestPath[neighborCoordinate] = totalCost;
 231353            previousNodes[neighborCoordinate] = minNode;
 231354          }
 672355        }
 192356        unvisitedNodes.Remove(minNode);
 192357      }
 3358      return new CachedPath
 359      {
 360        shortestPath = shortestPath,
 361        previousNodes = previousNodes
 362      };
 3363    }
 364
 365    /// <summary>Get all neighbors of the tile<summary>
 192366    Dictionary<string, float> GetNeighbors(string coordinates) => _allTilesData[coordinates].neighbors;
 367  }
 368}
Generated by: ReportGenerator 5.0.4.0
09/21/2023 - 15:19:18
GitHub | www.palmmedia.de

Methods/Properties

Grid()
Item(System.String)
PushToHistory(System.String)
GetTileWorldCoordinate(System.String)
Awake()
MoveDrone()
SetColor(System.String, UnityEngine.Color)
DownloadAndParseGridData()
GenerateGrid(DroneGame.ParsedData)
GetOrCreateTile(System.String)
FromLetterNumberToVector(System.String)
GetShortestPath(System.String[])
GetShortestPath(System.String, System.String)
FindAllPathsFrom(System.String)
GetNeighbors(System.String)