source: 2014/30/MiskaK/The Reclaim/The Reclaim/The Reclaim/The Reclaim/Map.cs @ 5689

Revision 5480, 9.9 KB checked in by anlakane, 6 years ago (diff)

Lisätty Reclaim versionhallintaan

Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using Jypeli;
6
7public class Map
8{
9    public MapNode[,] Nodes { get; private set; }
10
11    public Map(int rows, int columns)
12    {
13        Nodes = new MapNode[rows, columns];
14
15        for (int i = 0; i < rows; i++)
16            for (int j = 0; j < columns; j++)
17                Nodes[i, j] = new MapNode(false, new IntPoint(i, j));
18    }
19
20    public MapNode this[int i, int j]
21    {
22        get
23        {
24            return Nodes[i, j];
25        }
26        set
27        {
28            Nodes[i, j] = value;
29        }
30    }
31
32    public void SetNode(int i, int j, MapNode node)
33    {
34        Nodes[i, j] = node;
35    }
36
37    /*public void FindShortestRoute(IntPoint startingPosition, IntPoint targetPosition)
38    {
39        Queue<MapNode> searchQueue = new Queue<MapNode>();
40        searchQueue.Enqueue(GetNodeFromIndex(startingPosition));
41
42        for (int i = 0; i < nodes.GetLength(0); i++)
43            for (int j = 0; j < nodes.GetLength(1); j++)
44                nodes[i, j].IsExamined = false;
45       
46
47        while (searchQueue.Count > 0)
48        {
49            MapNode currentNode = searchQueue.Dequeue();
50            if (currentNode.Position.X == targetPosition.X && currentNode.Position.Y == targetPosition.Y)
51                break; // pitää palauttaa jotain, löytyi reitti
52
53            currentNode.IsExamined = true;
54            MapNode[] empties = GetEmptyNeighbours(currentNode);
55            foreach (MapNode empty in empties)
56            {
57                if (!empty.IsExamined)
58                    searchQueue.Enqueue(empty);
59            }
60        }
61    }*/
62
63    /*public MapNode[] DepthSearch(IntPoint startingPosition, IntPoint targetPosition) // tulee kiva OutOfMemory...
64    {
65        for (int i = 0; i < Nodes.GetLength(0); i++)
66            for (int j = 0; j < Nodes.GetLength(1); j++)
67                Nodes[i, j].IsExamined = false;
68
69        Stack<MapNode> searchStack = new Stack<MapNode>();
70        searchStack.Push(GetNodeFromIndex(startingPosition));
71
72        while (searchStack.Count > 0)
73        {
74            if (searchStack.Peek().Position == targetPosition)
75                return searchStack.ToArray();
76
77            MapNode[] neighbours = GetEmptyNotExaminedNeighbours(searchStack.Peek());
78            if (neighbours.Length == 0)
79                searchStack.Pop(); // tällä tasolla ei ollut reittiä, mennään alaspäin
80            else
81            {
82                searchStack.Push(neighbours[0]); // pääsee pidemmälle, mennään
83                neighbours[0].IsExamined = true;
84            }
85        }
86        return null;
87    }*/
88
89    /// <summary>
90    /// Etsitään lyhin reitti kahden pisteen välillä.
91    /// </summary>
92    /// <param name="startingPosition">Aloituspiste.</param>
93    /// <param name="targetPosition">Lopetuspiste.</param>
94    /// <returns>Lyhin reitti.</returns>
95    public MapNode[] DijkstraSearch(IntPoint startingPosition, IntPoint targetPosition)
96    {
97        List<MapNode> unvisitedNodes = new List<MapNode>();
98
99        const int NodeDistance = 1;
100
101        for (int i = 0; i < Nodes.GetLength(0); i++)
102        {
103            for (int j = 0; j < Nodes.GetLength(1); j++)
104            {
105                if (i != startingPosition.X || j != startingPosition.Y)
106                {
107                    Nodes[i, j].IsExamined = false;
108                    Nodes[i, j].Distance = int.MaxValue;
109                    Nodes[i, j].PreviousNode = null;
110                    unvisitedNodes.Add(Nodes[i, j]);
111                }
112                else
113                {
114                    Nodes[i, j].Distance = 0;
115                    Nodes[i, j].PreviousNode = null;
116                }
117            }
118        }
119
120        MapNode currentNode = Nodes[startingPosition.X, startingPosition.Y];
121        bool firstIteration = true;
122
123        while (unvisitedNodes.Count != 0)
124        {
125            if (!firstIteration)
126            {
127                currentNode = GetNodeWithSmallestDistance(unvisitedNodes);
128                unvisitedNodes.RemoveAt(unvisitedNodes.FindIndex(x => x.Position.X == currentNode.Position.X && x.Position.Y == currentNode.Position.Y));
129            }
130            firstIteration = false;
131            currentNode.IsExamined = true;
132            if (currentNode.Position == targetPosition)
133                break;
134
135            MapNode[] neighbours = GetEmptyNotExaminedNeighbours(currentNode);
136            for (int i = 0; i < neighbours.Length; i++)
137            {
138                int distance = currentNode.Distance + NodeDistance;
139                if (distance < neighbours[i].Distance)
140                {
141                    neighbours[i].Distance = distance;
142                    neighbours[i].PreviousNode = currentNode;
143                }
144            }
145        }
146        List<MapNode> shortestRoute = new List<MapNode>();
147        shortestRoute.Add(currentNode);
148
149        while (shortestRoute[0].PreviousNode != null)
150        {
151            shortestRoute.Insert(0, shortestRoute[0].PreviousNode);
152        }
153        return shortestRoute.ToArray();
154    }
155
156    private MapNode GetNodeWithSmallestDistance(List<MapNode> nodes)
157    {
158        //if (nodes.Count == 0) return
159        int smallestDistance = nodes[0].Distance;
160        int smallestIndex = 0;
161
162        for (int i = 0; i < nodes.Count; i++)
163        {
164            if (nodes[i].Distance < smallestDistance)
165            {
166                smallestDistance = nodes[i].Distance;
167                smallestIndex = i;
168            }
169        }
170        return nodes[smallestIndex];
171    }
172
173    public MapNode[] GetEmptyNeighbours(MapNode node)
174    {
175        List<MapNode> results = new List<MapNode>(4);
176
177        if (node.Position.X - 1 >= 0)
178            if (!(Nodes[node.Position.X - 1, node.Position.Y].IsFull))
179                results.Add(Nodes[node.Position.X - 1, node.Position.Y]);
180
181        if (node.Position.X + 1 < Nodes.GetLength(0))
182            if (!(Nodes[node.Position.X + 1, node.Position.Y].IsFull))
183                results.Add(Nodes[node.Position.X + 1, node.Position.Y]);
184
185        if (node.Position.Y - 1 >= 0)
186            if (!(Nodes[node.Position.X , node.Position.Y - 1].IsFull))
187                results.Add(Nodes[node.Position.X, node.Position.Y - 1]);
188
189        if (node.Position.Y + 1 < Nodes.GetLength(1))
190            if (!(Nodes[node.Position.X, node.Position.Y + 1].IsFull))
191                results.Add(Nodes[node.Position.X, node.Position.Y + 1]);
192
193        if (results.Count == 0)
194            return null;
195        return results.ToArray();
196    }
197
198    public MapNode[] GetEmptyNotExaminedNeighbours(MapNode node)
199    {
200        List<MapNode> empties = new List<MapNode>();
201        MapNode[] emptyNeighbours = GetEmptyNeighbours(node);
202        if (emptyNeighbours != null)
203            empties.AddRange(emptyNeighbours);
204
205        return empties.FindAll(x => x.IsExamined == false).ToArray();
206    }
207
208    public MapNode GetNodeFromIndex(IntPoint index)
209    {
210        //if (index.X < 0 || index.X > nodes.GetLength(0)) return null;
211        //if (index.Y < 0 || index.Y > nodes.GetLength(1)) return null;
212        return Nodes[index.X, index.Y];
213    }
214
215    /// <summary>
216    /// Palauttaa ruudun keskipisteen koordinaatit.
217    /// </summary>
218    /// <param name="node">Ruudun indeksi.</param>
219    /// <returns>Ruudun keskipisteen koordinaatit.</returns>
220    public Vector GetPositionOnWorld(IntPoint node)
221    {
222        double x = -(Nodes.GetLength(0) * GameConstants.TILE_WIDTH / 2) + GameConstants.TILE_WIDTH / 2 + node.X * GameConstants.TILE_WIDTH;
223        double y = Nodes.GetLength(1) * GameConstants.TILE_HEIGHT / 2 - GameConstants.TILE_HEIGHT / 2 - node.Y * GameConstants.TILE_HEIGHT;
224        return new Vector(x, y);
225    }
226
227    /// <summary>
228    /// Palauttaa ruudun indeksin, jossa piste sijaitsee.
229    /// Jos piste on ruudukon ulkopuolella, heitetään poikkeus.
230    /// </summary>
231    /// <param name="position">Koordinaatti</param>
232    /// <returns>Lähimmän ruudun indeksi.</returns>
233    public IntPoint GetCorrespondingNode(Vector position)
234    {
235        if (position.X < -(Nodes.GetLength(0) * GameConstants.TILE_WIDTH / 2) || position.X > Nodes.GetLength(0) * GameConstants.TILE_WIDTH / 2)
236            throw new ArgumentOutOfRangeException("position", "X-coordinate was outside the grid.");
237            // on leveyssuunnassa ruudukon ulkopuolella
238        if (position.Y > Nodes.GetLength(1) * GameConstants.TILE_HEIGHT / 2 || position.Y < -(Nodes.GetLength(1) * GameConstants.TILE_HEIGHT / 2))
239            throw new ArgumentOutOfRangeException("position", "Y-coordinate was outside the grid.");
240            // on korkeussuunnassa ruudukon ulkopuolella
241
242        int x;
243        if (position.X >= 0)
244            x = ((int)Math.Ceiling(position.X / GameConstants.TILE_WIDTH) + Nodes.GetLength(0) / 2) - 1;
245        else
246            x = (int)Math.Floor(position.X / GameConstants.TILE_WIDTH) + Nodes.GetLength(0) / 2;
247
248        int y;
249        if (position.Y >= 0)
250            y = -((int)Math.Ceiling(position.Y / GameConstants.TILE_HEIGHT) - Nodes.GetLength(1) / 2);
251        else
252            y = -(((int)Math.Floor(position.Y / GameConstants.TILE_HEIGHT) - Nodes.GetLength(1) / 2) + 1);
253
254        return new IntPoint(x, y);
255    }
256
257    /// <summary>
258    /// Palautetaan MapNode-taulukon muodostama reitti maailmakoordinaatteina.
259    /// </summary>
260    /// <param name="route">Reitti.</param>
261    /// <returns>Reitti maailmakoordinaatteina.</returns>
262    public List<Vector> GetRouteCoordinates(MapNode[] route)
263    {
264        List<Vector> reitti = new List<Vector>();
265
266        for (int i = 0; i < route.Length; i++)
267        {
268            reitti.Add(GetPositionOnWorld(route[i].Position));
269        }
270        return reitti;
271    }
272
273    private int ToNearestInt(double d)
274    {
275        return (int)(d + 0.5);
276    }
277}
Note: See TracBrowser for help on using the repository browser.