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

Revision 5969, 7.5 KB checked in by sieerinn, 5 years ago (diff)

Reitinlöytö toimii.

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