source: 2013/30/DenisZ/CastleMaster/CastleMaster/CastleMaster/Ai/AStar.cs @ 4593

Revision 4593, 7.0 KB checked in by dezhidki, 7 years ago (diff)

Optimoitu viimeisen päivityksen AStarin ominaisuutta.

Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using CastleMaster.World;
6using CastleMaster.Units.Mobs;
7
8namespace IsometricEngineTest.Ai
9{
10    public class AStar
11    {
12        public const int MOVE_STRAIGHT = 10;
13        public const int MOVE_VERTICAL = 14;
14        public const int MOVE_COSTS_SAVED = MOVE_VERTICAL - 2 * MOVE_STRAIGHT;
15        private readonly double TIRE_FIX;
16
17        private Level level;
18        private Mob mob;
19        private List<Node> open, path;
20        private bool[] tiles;
21        private Node[] nodeMap;
22        private bool isPathFinding = false;
23        private bool canPathFind = true;
24        private int calls;
25        private int xStart, zStart, xEnd, zEnd;
26
27#if DEBUG
28        private TimeSpan totalTime = TimeSpan.Zero;
29#endif
30
31        public AStar(Level level, Mob mob)
32        {
33            this.level = level;
34            this.mob = mob;
35            open = new List<Node>();
36            path = new List<Node>();
37
38            TIRE_FIX = (1.0 + (MOVE_STRAIGHT / 1000.0));
39        }
40
41        public List<Node> Path { get { return path; } }
42
43        public bool IsPathFinding { get { return isPathFinding; } }
44
45        public bool CanFindPath { get { return canPathFind; } }
46
47        public int EstimateCost(int x, int z)
48        {
49            int dx = Math.Abs(x - xEnd);
50            int dz = Math.Abs(z - zEnd);
51
52            int h = MOVE_STRAIGHT * (dx + dz) + MOVE_COSTS_SAVED * Math.Min(dx, dz);
53            h = (int)(h * TIRE_FIX);
54            return h;
55        }
56
57        public void InitializePathFinder(int xStart, int zStart, int xEnd, int zEnd, bool ignoreSolidnessForEnd)
58        {
59            tiles = level.BuildSolidnessTable(mob, ignoreSolidnessForEnd, xEnd, zEnd);
60            nodeMap = new Node[level.Width * level.Height];
61            open.Clear();
62            path.Clear();
63            calls = 0;
64
65            if(ignoreSolidnessForEnd)
66                tiles[xEnd + zEnd * level.Width] = false;
67
68#if DEBUG
69            totalTime = TimeSpan.Zero;
70            Console.WriteLine("[START] From: [ " + xStart + ", " + zStart + " ] to : [ " + xEnd + ", " + zEnd + "].");
71#endif
72
73            this.xStart = xStart;
74            this.xEnd = xEnd;
75            this.zStart = zStart;
76            this.zEnd = zEnd;
77
78            Node startNode = new Node(xStart, zStart, null, 0, EstimateCost(xStart, zStart), true, false);
79            open.Add(startNode);
80            nodeMap[xStart + zStart * level.Width] = startNode;
81
82            isPathFinding = true;
83            canPathFind = true;
84
85            if ((xStart == xEnd && zStart == zEnd))
86                isPathFinding = false;
87
88            if (xEnd < 0 || zEnd < 0 || xEnd >= level.Width || zEnd >= level.Height)
89            {
90#if DEBUG
91                Console.WriteLine("[FAIL] End is out of level boundaries.");
92#endif
93                canPathFind = false;
94            }
95            else if (tiles[xEnd + zEnd * level.Width])
96            {
97#if DEBUG
98                Console.WriteLine("[FAIL] End is solid.");
99#endif
100                canPathFind = false;
101            }
102        }
103
104        public void FindPath(int maxVisits)
105        {
106#if DEBUG
107            DateTime startTime = DateTime.Now;
108#endif
109            calls++;
110
111            Node current = null;
112            int visits = 0;
113            do
114            {
115                visits++;
116                if (visits == maxVisits)
117                {
118#if DEBUG
119                    totalTime += DateTime.Now - startTime;
120                    Console.WriteLine("[PAUSE] Calls so far: " + calls + ". Time spent: " + ((DateTime.Now - startTime).TotalMilliseconds) + " ms.");
121#endif
122                    return;
123                }
124
125                current = GetBestOpenNode();
126                if (current == null)
127                {
128#if DEBUG
129                    totalTime += DateTime.Now - startTime;
130                    Console.WriteLine("[FAIL] No more open nodes! Calls: " + calls + ". Total time: " + totalTime.TotalMilliseconds + " ms.");
131#endif
132                    canPathFind = false;
133                    return;
134                }
135                current.IsClosed = true;
136                current.IsOpen = false;
137                open.Remove(current);
138
139                for (int x = current.X - 1; x <= current.X + 1; x++)
140                {
141                    for (int z = current.Z - 1; z <= current.Z + 1; z++)
142                    {
143                        if (x == current.X && z == current.Z) continue;
144                        if (x < 0 || z < 0 || x >= level.Width || z >= level.Height) continue;
145                        if (tiles[x + z * level.Width]) continue;
146                        if (tiles[x + current.Z * level.Width] && tiles[current.X + z * level.Width]) continue;
147
148                        int moveCost = (x == current.X || z == current.Z) ? MOVE_STRAIGHT : MOVE_VERTICAL;
149                        int travelCost = current.TravelCost + moveCost;
150
151                        Node neighbour = nodeMap[x + z * level.Width];
152
153                        if (neighbour != null)
154                        {
155                            if (neighbour.IsOpen && travelCost < neighbour.TravelCost)
156                            {
157                                neighbour.IsOpen = false;
158                                open.Remove(neighbour);
159                            }
160                            if (neighbour.IsClosed && travelCost < neighbour.TravelCost)
161                                neighbour.IsClosed = false;
162                        }
163                        if (neighbour == null || (!neighbour.IsClosed && !neighbour.IsOpen))
164                        {
165                            neighbour = new Node(x, z, current, travelCost, EstimateCost(x, z), true, false);
166                            open.Add(neighbour);
167                            nodeMap[x + z * level.Width] = neighbour;
168                        }
169                    }
170                }
171            } while (current.X != xEnd || current.Z != zEnd);
172
173            isPathFinding = false;
174
175#if DEBUG
176            totalTime += DateTime.Now - startTime;
177            Console.WriteLine("[FINISH] Calls: " + calls + ". Total time: " + totalTime.TotalMilliseconds + " ms.");
178#endif
179
180            path.Add(new Node(xEnd, zEnd, current, 0, 0, false, false));
181            Node reverse = current.Parent;
182            while (reverse.X != xStart || reverse.Z != zStart)
183            {
184                path.Add(reverse);
185                reverse = reverse.Parent;
186            }
187
188            path.Reverse();
189        }
190
191        private Node GetBestOpenNode()
192        {
193            Node result = null;
194
195            if (open.Count == 1)
196            {
197                result = open[0];
198                return result;
199            }
200
201            foreach (Node node in open)
202            {
203                if (result == null || node.TotalCost < result.TotalCost)
204                    result = node;
205            }
206
207            return result;
208        }
209    }
210}
Note: See TracBrowser for help on using the repository browser.