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

Revision 4590, 6.9 KB checked in by dezhidki, 7 years ago (diff)

Puut lisätty, woodcutter toimii.

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 DEBUG
66            totalTime = TimeSpan.Zero;
67            Console.WriteLine("[START] From: [ " + xStart + ", " + zStart + " ] to : [ " + xEnd + ", " + zEnd + "].");
68#endif
69
70            this.xStart = xStart;
71            this.xEnd = xEnd;
72            this.zStart = zStart;
73            this.zEnd = zEnd;
74
75            Node startNode = new Node(xStart, zStart, null, 0, EstimateCost(xStart, zStart), true, false);
76            open.Add(startNode);
77            nodeMap[xStart + zStart * level.Width] = startNode;
78
79            isPathFinding = true;
80            canPathFind = true;
81
82            if ((xStart == xEnd && zStart == zEnd))
83                isPathFinding = false;
84
85            if (xEnd < 0 || zEnd < 0 || xEnd >= level.Width || zEnd >= level.Height)
86            {
87#if DEBUG
88                Console.WriteLine("[FAIL] End is out of level boundaries.");
89#endif
90                canPathFind = false;
91            }
92            else if (tiles[xEnd + zEnd * level.Width])
93            {
94#if DEBUG
95                Console.WriteLine("[FAIL] End is solid.");
96#endif
97                canPathFind = false;
98            }
99        }
100
101        public void FindPath(int maxVisits)
102        {
103#if DEBUG
104            DateTime startTime = DateTime.Now;
105#endif
106            calls++;
107
108            Node current = null;
109            int visits = 0;
110            do
111            {
112                visits++;
113                if (visits == maxVisits)
114                {
115#if DEBUG
116                    totalTime += DateTime.Now - startTime;
117                    Console.WriteLine("[PAUSE] Calls so far: " + calls + ". Time spent: " + ((DateTime.Now - startTime).TotalMilliseconds) + " ms.");
118#endif
119                    return;
120                }
121
122                current = GetBestOpenNode();
123                if (current == null)
124                {
125#if DEBUG
126                    totalTime += DateTime.Now - startTime;
127                    Console.WriteLine("[FAIL] No more open nodes! Calls: " + calls + ". Total time: " + totalTime.TotalMilliseconds + " ms.");
128#endif
129                    canPathFind = false;
130                    return;
131                }
132                current.IsClosed = true;
133                current.IsOpen = false;
134                open.Remove(current);
135
136                for (int x = current.X - 1; x <= current.X + 1; x++)
137                {
138                    for (int z = current.Z - 1; z <= current.Z + 1; z++)
139                    {
140                        if (x == current.X && z == current.Z) continue;
141                        if (x < 0 || z < 0 || x >= level.Width || z >= level.Height) continue;
142                        if (tiles[x + z * level.Width]) continue;
143                        if (tiles[x + current.Z * level.Width] && tiles[current.X + z * level.Width]) continue;
144
145                        int moveCost = (x == current.X || z == current.Z) ? MOVE_STRAIGHT : MOVE_VERTICAL;
146                        int travelCost = current.TravelCost + moveCost;
147
148                        Node neighbour = nodeMap[x + z * level.Width];
149
150                        if (neighbour != null)
151                        {
152                            if (neighbour.IsOpen && travelCost < neighbour.TravelCost)
153                            {
154                                neighbour.IsOpen = false;
155                                open.Remove(neighbour);
156                            }
157                            if (neighbour.IsClosed && travelCost < neighbour.TravelCost)
158                                neighbour.IsClosed = false;
159                        }
160                        if (neighbour == null || (!neighbour.IsClosed && !neighbour.IsOpen))
161                        {
162                            neighbour = new Node(x, z, current, travelCost, EstimateCost(x, z), true, false);
163                            open.Add(neighbour);
164                            nodeMap[x + z * level.Width] = neighbour;
165                        }
166                    }
167                }
168            } while (current.X != xEnd || current.Z != zEnd);
169
170            isPathFinding = false;
171
172#if DEBUG
173            totalTime += DateTime.Now - startTime;
174            Console.WriteLine("[FINISH] Calls: " + calls + ". Total time: " + totalTime.TotalMilliseconds + " ms.");
175#endif
176
177            path.Add(new Node(xEnd, zEnd, current, 0, 0, false, false));
178            Node reverse = current.Parent;
179            while (reverse.X != xStart || reverse.Z != zStart)
180            {
181                path.Add(reverse);
182                reverse = reverse.Parent;
183            }
184
185            path.Reverse();
186        }
187
188        private Node GetBestOpenNode()
189        {
190            Node result = null;
191
192            if (open.Count == 1)
193            {
194                result = open[0];
195                return result;
196            }
197
198            foreach (Node node in open)
199            {
200                if (result == null || node.TotalCost < result.TotalCost)
201                    result = node;
202            }
203
204            return result;
205        }
206    }
207}
Note: See TracBrowser for help on using the repository browser.