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

Revision 4754, 7.4 KB checked in by dezhidki, 6 years ago (diff)

Housekeeping

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