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

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

Muokattu sotilaita viimeiseen muotoon.

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);
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 ApplySolidnessToPos(List<int> posList, bool ignoreEndSolidness)
105        {
106            foreach (int i in posList)
107                tiles[i] = false;
108
109            if(ignoreEndSolidness)
110                tiles[xEnd + zEnd * level.Width] = true;
111        }
112
113        public void Reset()
114        {
115            Path.Clear();
116            isPathFinding = false;
117            canPathFind = true;
118        }
119
120        public void FindPath(int maxVisits)
121        {
122#if DEBUG
123            DateTime startTime = DateTime.Now;
124#endif
125            calls++;
126
127            Node current = null;
128            int visits = 0;
129            do
130            {
131                visits++;
132                if (visits == maxVisits)
133                {
134#if DEBUG
135                    totalTime += DateTime.Now - startTime;
136                    Console.WriteLine("[PAUSE] Calls so far: " + calls + ". Time spent: " + ((DateTime.Now - startTime).TotalMilliseconds) + " ms.");
137#endif
138                    return;
139                }
140
141                current = GetBestOpenNode();
142                if (current == null)
143                {
144#if DEBUG
145                    totalTime += DateTime.Now - startTime;
146                    Console.WriteLine("[FAIL] No more open nodes! Calls: " + calls + ". Total time: " + totalTime.TotalMilliseconds + " ms.");
147#endif
148                    canPathFind = false;
149                    return;
150                }
151                current.IsClosed = true;
152                current.IsOpen = false;
153                open.Remove(current);
154
155                for (int x = current.X - 1; x <= current.X + 1; x++)
156                {
157                    for (int z = current.Z - 1; z <= current.Z + 1; z++)
158                    {
159                        if (x == current.X && z == current.Z) continue;
160                        if (x < 0 || z < 0 || x >= level.Width || z >= level.Height) continue;
161                        if (tiles[x + z * level.Width]) continue;
162                        if (tiles[x + current.Z * level.Width] && tiles[current.X + z * level.Width]) continue;
163
164                        int moveCost = (x == current.X || z == current.Z) ? MOVE_STRAIGHT : MOVE_VERTICAL;
165                        int travelCost = current.TravelCost + moveCost;
166
167                        Node neighbour = nodeMap[x + z * level.Width];
168
169                        if (neighbour != null)
170                        {
171                            if (neighbour.IsOpen && travelCost < neighbour.TravelCost)
172                            {
173                                neighbour.IsOpen = false;
174                                open.Remove(neighbour);
175                            }
176                            if (neighbour.IsClosed && travelCost < neighbour.TravelCost)
177                                neighbour.IsClosed = false;
178                        }
179                        if (neighbour == null || (!neighbour.IsClosed && !neighbour.IsOpen))
180                        {
181                            neighbour = new Node(x, z, current, travelCost, EstimateCost(x, z), true, false);
182                            open.Add(neighbour);
183                            nodeMap[x + z * level.Width] = neighbour;
184                        }
185                    }
186                }
187            } while (current.X != xEnd || current.Z != zEnd);
188
189            isPathFinding = false;
190
191#if DEBUG
192            totalTime += DateTime.Now - startTime;
193            Console.WriteLine("[FINISH] Calls: " + calls + ". Total time: " + totalTime.TotalMilliseconds + " ms.");
194#endif
195
196            path.Add(new Node(xEnd, zEnd, current, 0, 0, false, false));
197            Node reverse = current.Parent;
198            while (reverse.X != xStart || reverse.Z != zStart)
199            {
200                path.Add(reverse);
201                reverse = reverse.Parent;
202            }
203
204            path.Reverse();
205        }
206
207        private Node GetBestOpenNode()
208        {
209            Node result = null;
210
211            if (open.Count == 1)
212            {
213                result = open[0];
214                return result;
215            }
216
217            foreach (Node node in open)
218            {
219                if (result == null || node.TotalCost < result.TotalCost)
220                    result = node;
221            }
222
223            return result;
224        }
225
226
227    }
228}
Note: See TracBrowser for help on using the repository browser.