4064748535

Build Type

push

github

Committed by GitHub

Commit Message

Merge pull request #28 from samsmithnz/AddingMapAndPathFinding

Run Details

806 of 854 branches covered (94.38%)

Branch coverage included in aggregate %.

342 of 342 new or added lines in 8 files covered. (100.0%)

1165 of 1194 relevant lines covered (97.57%)

1263151.22 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.86

/src/PuzzleSolver/Map/PathFinding.cs

﻿using System.Collections.Generic;
using System.Numerics;

namespace PuzzleSolver.Map
{
    public static class PathFinding
    {
        private static int _width;
        private static int _height;
        private static MapTile[,] _tiles;
        private static Vector2 _endLocation;

        /// <summary>
        /// Attempts to find a path from the start location to the end location based on the supplied SearchParameters
        /// </summary>
        /// <returns>A List of Points representing the path. If no path was found, the returned list is empty.</returns>
        public static PathFindingResult FindPath(string[,] map, Vector2 startLocation, Vector2 endLocation)
        {
            _endLocation = endLocation;
            // Initializes a tile grid from a simple grid of booleans indicating areas which are and aren't walkable
            _width = map.GetLength(0);
            _height = map.GetLength(1);
            _tiles = new MapTile[_width, _height];
            for (int y = 0; y < _height; y++)
            {
                for (int x = 0; x < _width; x++)
                {
                    _tiles[x, y] = new MapTile(x, y, map[x, y], _endLocation);
                }
            }
            
            //Establish the start and end tiles
            MapTile startTile = _tiles[(int)startLocation.X, (int)startLocation.Y];
            startTile.State = TileState.Open;
            MapTile endTile = _tiles[(int)endLocation.X, (int)endLocation.Y];

            // The start tile is the first entry in the 'open' list. Now search all of the open tiles for the shortest path
            PathFindingResult result = new PathFindingResult();
            bool success = Search(startTile, endTile);
            if (success)
            {
                // If a path was found, follow the parents from the end tile to build a list of locations
                MapTile tile = endTile;
                while (tile.ParentTile != null)
                {
                    result.Tiles.Add(tile);
                    result.Path.Add(tile.Location);
                    tile = tile.ParentTile;
                }

                // Reverse the list so it's in the correct order when returned
                result.Path.Reverse();
                result.Tiles.Reverse();
            }

            return result;
        }

        /// <summary>
        /// Attempts to find a path to the destination tile using <paramref name="currentTile"/> as the starting location
        /// </summary>
        /// <param name="currentTile">The tile from which to find a path</param>
        /// <returns>True if a path to the destination has been found, otherwise false</returns>
        private static bool Search(MapTile currentTile, MapTile endTile)
        {
            // Set the current tile to Closed since it cannot be traversed more than once
            currentTile.State = TileState.Closed;
            List<MapTile> nextTiles = GetAdjacentWalkableTiles(currentTile);

            // Sort by F-value so that the shortest possible routes are considered first
            nextTiles.Sort((tile1, tile2) => tile1.F.CompareTo(tile2.F));
            foreach (MapTile nextTile in nextTiles)
            {
                // Check whether the end tile has been reached
                if (nextTile.Location == endTile.Location)
                {
                    return true;
                }
                else
                {
                    // If not, check the next set of tiles
                    if (Search(nextTile, endTile)) // Note: Recurses back into Search(Tile)
                    {
                        return true;
                    }
                }
            }

            // The method returns false if this path leads to be a dead end
            return false;
        }

        /// <summary>
        /// Returns any tiles that are adjacent to <paramref name="fromTile"/> and may be considered to form the next step in the path
        /// </summary>
        /// <param name="fromTile">The tile from which to return the next possible tiles in the path</param>
        /// <returns>A list of next possible tiles in the path</returns>
        private static List<MapTile> GetAdjacentWalkableTiles(MapTile fromTile)
        {
            List<MapTile> walkableTiles = new List<MapTile>();
            // Returns the four locations immediately adjacent (orthogonally and NOT diagonally) from the source "fromTile"
            IEnumerable<Vector2> nextLocations = new Vector2[]
                {
                    new Vector2(fromTile.Location.X - 1, fromTile.Location.Y),
                    new Vector2(fromTile.Location.X, fromTile.Location.Y + 1),
                    new Vector2(fromTile.Location.X + 1, fromTile.Location.Y),
                    new Vector2(fromTile.Location.X,  fromTile.Location.Y - 1)
                };

            foreach (Vector2 location in nextLocations)
            {
                int x = (int)location.X;
                int y = (int)location.Y;
                
                // Stay within the grid's boundaries
                if (x < 0 || x >= _width || y < 0 || y >= _height)
                {
                    continue;
                }

                MapTile tile = _tiles[x, y];
                // Ignore non-walkable tiles
                if (tile.TileType != "")
                {
                    continue;
                }

                // Ignore already-closed tiles
                if (tile.State == TileState.Closed)
                {
                    continue;
                }

                //// Already-open tiles are only added to the list if their G-value is lower going via this route.
                if (tile.State == TileState.Open)
                {
                    //float traversalCost = MapTile.GetTraversalCost(tile.Location, tile.ParentTile.Location);
                    //float gTemp = fromTile.G + traversalCost;
                    //if (gTemp < tile.G)
                    //{
                    //    tile.ParentTile = fromTile;
                    //    walkableTiles.Add(tile);
                    //}
                }
                else
                {
                    // If it's untested, set the parent and flag it as 'Open' for consideration
                    tile.ParentTile = fromTile;
                    tile.State = TileState.Open;
                    walkableTiles.Add(tile);
                }
            }

            return walkableTiles;
        }

    }
}

1	using System.Collections.Generic;
2	using System.Numerics;
3
4	namespace PuzzleSolver.Map
5	{
6	public static class PathFinding
7	{
8	private static int _width;
9	private static int _height;
10	private static MapTile[,] _tiles;
11	private static Vector2 _endLocation;
12
13	/// <summary>
14	/// Attempts to find a path from the start location to the end location based on the supplied SearchParameters
15	/// </summary>
16	/// <returns>A List of Points representing the path. If no path was found, the returned list is empty.</returns>
17	public static PathFindingResult FindPath(string[,] map, Vector2 startLocation, Vector2 endLocation)
18	{	2✔
19	_endLocation = endLocation;	2✔
20	// Initializes a tile grid from a simple grid of booleans indicating areas which are and aren't walkable
21	_width = map.GetLength(0);	2✔
22	_height = map.GetLength(1);	2✔
23	_tiles = new MapTile[_width, _height];	2✔
24	for (int y = 0; y < _height; y++)	24✔
25	{	10✔
26	for (int x = 0; x < _width; x++)	120✔
27	{	50✔
28	_tiles[x, y] = new MapTile(x, y, map[x, y], _endLocation);	50✔
29	}	50✔
30	}	10✔
31
32	//Establish the start and end tiles
33	MapTile startTile = _tiles[(int)startLocation.X, (int)startLocation.Y];	2✔
34	startTile.State = TileState.Open;	2✔
35	MapTile endTile = _tiles[(int)endLocation.X, (int)endLocation.Y];	2✔
36
37	// The start tile is the first entry in the 'open' list. Now search all of the open tiles for the shortest path
38	PathFindingResult result = new PathFindingResult();	2✔
39	bool success = Search(startTile, endTile);	2✔
40	if (success)	2✔
41	{	2✔
42	// If a path was found, follow the parents from the end tile to build a list of locations
43	MapTile tile = endTile;	2✔
44	while (tile.ParentTile != null)	11✔
45	{	9✔
46	result.Tiles.Add(tile);	9✔
47	result.Path.Add(tile.Location);	9✔
48	tile = tile.ParentTile;	9✔
49	}	9✔
50
51	// Reverse the list so it's in the correct order when returned
52	result.Path.Reverse();	2✔
53	result.Tiles.Reverse();	2✔
54	}	2✔
55
56	return result;	2✔
57	}	2✔
58
59	/// <summary>
60	/// Attempts to find a path to the destination tile using <paramref name="currentTile"/> as the starting location
61	/// </summary>
62	/// <param name="currentTile">The tile from which to find a path</param>
63	/// <returns>True if a path to the destination has been found, otherwise false</returns>
64	private static bool Search(MapTile currentTile, MapTile endTile)
65	{	9✔
66	// Set the current tile to Closed since it cannot be traversed more than once
67	currentTile.State = TileState.Closed;	9✔
68	List<MapTile> nextTiles = GetAdjacentWalkableTiles(currentTile);	9✔
69
70	// Sort by F-value so that the shortest possible routes are considered first
71	nextTiles.Sort((tile1, tile2) => tile1.F.CompareTo(tile2.F));	30✔
72	foreach (MapTile nextTile in nextTiles)	36!
73	{	9✔
74	// Check whether the end tile has been reached
75	if (nextTile.Location == endTile.Location)	9✔
76	{	2✔
77	return true;	2✔
78	}
79	else
80	{	7✔
81	// If not, check the next set of tiles
82	if (Search(nextTile, endTile)) // Note: Recurses back into Search(Tile)	7!
83	{	7✔
84	return true;	7✔
85	}
86	}	×
87	}	×
88
89	// The method returns false if this path leads to be a dead end
90	return false;	×
91	}	9✔
92
93	/// <summary>
94	/// Returns any tiles that are adjacent to <paramref name="fromTile"/> and may be considered to form the next step in the path
95	/// </summary>
96	/// <param name="fromTile">The tile from which to return the next possible tiles in the path</param>
97	/// <returns>A list of next possible tiles in the path</returns>
98	private static List<MapTile> GetAdjacentWalkableTiles(MapTile fromTile)
99	{	9✔
100	List<MapTile> walkableTiles = new List<MapTile>();	9✔
101	// Returns the four locations immediately adjacent (orthogonally and NOT diagonally) from the source "fromTile"
102	IEnumerable<Vector2> nextLocations = new Vector2[]	9✔
103	{	9✔
104	new Vector2(fromTile.Location.X - 1, fromTile.Location.Y),	9✔
105	new Vector2(fromTile.Location.X, fromTile.Location.Y + 1),	9✔
106	new Vector2(fromTile.Location.X + 1, fromTile.Location.Y),	9✔
107	new Vector2(fromTile.Location.X, fromTile.Location.Y - 1)	9✔
108	};	9✔
109
110	foreach (Vector2 location in nextLocations)	99✔
111	{	36✔
112	int x = (int)location.X;	36✔
113	int y = (int)location.Y;	36✔
114
115	// Stay within the grid's boundaries
116	if (x < 0 \|\| x >= _width \|\| y < 0 \|\| y >= _height)	36✔
117	{	2✔
118	continue;	2✔
119	}
120
121	MapTile tile = _tiles[x, y];	34✔
122	// Ignore non-walkable tiles
123	if (tile.TileType != "")	34✔
124	{	3✔
125	continue;	3✔
126	}
127
128	// Ignore already-closed tiles
129	if (tile.State == TileState.Closed)	31✔
130	{	7✔
131	continue;	7✔
132	}
133
134	//// Already-open tiles are only added to the list if their G-value is lower going via this route.
135	if (tile.State == TileState.Open)	24!
136	{	×
137	//float traversalCost = MapTile.GetTraversalCost(tile.Location, tile.ParentTile.Location);
138	//float gTemp = fromTile.G + traversalCost;
139	//if (gTemp < tile.G)
140	//{
141	// tile.ParentTile = fromTile;
142	// walkableTiles.Add(tile);
143	//}
144	}	×
145	else
146	{	24✔
147	// If it's untested, set the parent and flag it as 'Open' for consideration
148	tile.ParentTile = fromTile;	24✔
149	tile.State = TileState.Open;	24✔
150	walkableTiles.Add(tile);	24✔
151	}	24✔
152	}	24✔
153
154	return walkableTiles;	9✔
155	}	9✔
156
157	}
158	}

samsmithnz / PuzzleSolver / 4064748535

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous