source: 2015/24/ohjaajat/Dungeon/Dungeon/Dungeon/Pathfinding/PathFinder.cs @ 5967

Revision 5967, 7.3 KB checked in by sieerinn, 4 years ago (diff)
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Threading.Tasks;
6using Point = Microsoft.Xna.Framework.Point;
7
8namespace AStar
9{
10    public class PathFinder
11    {
12        private int width;
13        private int height;
14        private Node[,] nodes;
15        private Node startNode;
16        private Node endNode;
17        private SearchParameters searchParameters;
18
19        /// <summary>
20        /// Create a new instance of PathFinder
21        /// </summary>
22        /// <param name="searchParameters"></param>
23        public PathFinder(SearchParameters searchParameters)
24        {
25            this.searchParameters = searchParameters;
26            InitializeNodes(searchParameters.Map);
27            this.startNode = this.nodes[searchParameters.StartLocation.X, searchParameters.StartLocation.Y];
28            this.startNode.State = NodeState.Open;
29            this.endNode = this.nodes[searchParameters.EndLocation.X, searchParameters.EndLocation.Y];
30        }
31
32        /// <summary>
33        /// Attempts to find a path from the start location to the end location based on the supplied SearchParameters
34        /// </summary>
35        /// <returns>A List of Points representing the path. If no path was found, the returned list is empty.</returns>
36        public List<Point> FindPath()
37        {
38            // The start node is the first entry in the 'open' list
39            List<Point> path = new List<Point>();
40            bool success = Search(startNode);
41            if (success)
42            {
43                // If a path was found, follow the parents from the end node to build a list of locations
44                Node node = this.endNode;
45                while (node.ParentNode != null)
46                {
47                    path.Add(node.Location);
48                    node = node.ParentNode;
49                }
50
51                // Reverse the list so it's in the correct order when returned
52                path.Reverse();
53            }
54
55            return path;
56        }
57
58        /// <summary>
59        /// Builds the node grid from a simple grid of booleans indicating areas which are and aren't walkable
60        /// </summary>
61        /// <param name="map">A boolean representation of a grid in which true = walkable and false = not walkable</param>
62        private void InitializeNodes(bool[,] map)
63        {
64            this.width = map.GetLength(0);
65            this.height = map.GetLength(1);
66            this.nodes = new Node[this.width, this.height];
67            for (int y = 0; y < this.height; y++)
68            {
69                for (int x = 0; x < this.width; x++)
70                {
71                    this.nodes[x, y] = new Node(x, y, map[x, y], this.searchParameters.EndLocation);
72                }
73            }
74        }
75
76        /// <summary>
77        /// Attempts to find a path to the destination node using <paramref name="currentNode"/> as the starting location
78        /// </summary>
79        /// <param name="currentNode">The node from which to find a path</param>
80        /// <returns>True if a path to the destination has been found, otherwise false</returns>
81        private bool Search(Node currentNode)
82        {
83            // Set the current node to Closed since it cannot be traversed more than once
84            currentNode.State = NodeState.Closed;
85            List<Node> nextNodes = GetAdjacentWalkableNodes(currentNode);
86
87            // Sort by F-value so that the shortest possible routes are considered first
88            nextNodes.Sort((node1, node2) => node1.F.CompareTo(node2.F));
89            foreach (var nextNode in nextNodes)
90            {
91                // Check whether the end node has been reached
92                if (nextNode.Location == this.endNode.Location)
93                {
94                    return true;
95                }
96                else
97                {
98                    // If not, check the next set of nodes
99                    if (Search(nextNode)) // Note: Recurses back into Search(Node)
100                        return true;
101                }
102            }
103
104            // The method returns false if this path leads to be a dead end
105            return false;
106        }
107
108        /// <summary>
109        /// Returns any nodes that are adjacent to <paramref name="fromNode"/> and may be considered to form the next step in the path
110        /// </summary>
111        /// <param name="fromNode">The node from which to return the next possible nodes in the path</param>
112        /// <returns>A list of next possible nodes in the path</returns>
113        private List<Node> GetAdjacentWalkableNodes(Node fromNode)
114        {
115            List<Node> walkableNodes = new List<Node>();
116            IEnumerable<Point> nextLocations = GetAdjacentLocations(fromNode.Location);
117
118            foreach (var location in nextLocations)
119            {
120                int x = location.X;
121                int y = location.Y;
122
123                // Stay within the grid's boundaries
124                if (x < 0 || x >= this.width || y < 0 || y >= this.height)
125                    continue;
126
127                Node node = this.nodes[x, y];
128                // Ignore non-walkable nodes
129                if (!node.IsWalkable)
130                    continue;
131
132                // Ignore already-closed nodes
133                if (node.State == NodeState.Closed)
134                    continue;
135
136                // Already-open nodes are only added to the list if their G-value is lower going via this route.
137                if (node.State == NodeState.Open)
138                {
139                    float traversalCost = Node.GetTraversalCost(node.Location, node.ParentNode.Location);
140                    float gTemp = fromNode.G + traversalCost;
141                    if (gTemp < node.G)
142                    {
143                        node.ParentNode = fromNode;
144                        walkableNodes.Add(node);
145                    }
146                }
147                else
148                {
149                    // If it's untested, set the parent and flag it as 'Open' for consideration
150                    node.ParentNode = fromNode;
151                    node.State = NodeState.Open;
152                    walkableNodes.Add(node);
153                }
154            }
155
156            return walkableNodes;
157        }
158
159        /// <summary>
160        /// Returns the eight locations immediately adjacent (orthogonally and diagonally) to <paramref name="fromLocation"/>
161        /// </summary>
162        /// <param name="fromLocation">The location from which to return all adjacent points</param>
163        /// <returns>The locations as an IEnumerable of Points</returns>
164        private static IEnumerable<Point> GetAdjacentLocations(Point fromLocation)
165        {
166            return new Point[]
167            {
168                new Point(fromLocation.X-1, fromLocation.Y-1),
169                new Point(fromLocation.X-1, fromLocation.),
170                new Point(fromLocation.X-1, fromLocation.Y+1),
171                new Point(fromLocation.X,   fromLocation.Y+1),
172                new Point(fromLocation.X+1, fromLocation.Y+1),
173                new Point(fromLocation.X+1, fromLocation.),
174                new Point(fromLocation.X+1, fromLocation.Y-1),
175                new Point(fromLocation.X,   fromLocation.Y-1)
176            };
177        }
178    }
179}
Note: See TracBrowser for help on using the repository browser.