-
Notifications
You must be signed in to change notification settings - Fork 1
/
SiteForPathfinding.cs
170 lines (151 loc) · 5.8 KB
/
SiteForPathfinding.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// Author: Clément Hardy
using Landis.Library.UniversalCohorts;
using Landis.Core;
using Landis.SpatialModeling;
using System.Collections.Generic;
using System.IO;
using Landis.Library.Metadata;
using System;
using System.Diagnostics;
namespace Landis.Extension.ForestRoadsSimulation
{
/// <summary>
/// A class made to help the Dijkstra algorithm to be simpler. See "DijkstraSearch" class for use.
/// </summary>
public class SiteForPathfinding : Priority_Queue.FastPriorityQueueNode, IComparable<SiteForPathfinding>
{
public Site site;
public double distanceToStart;
public SiteForPathfinding predecessor;
public bool isClosed;
public bool isOpen;
public SiteForPathfinding(Site site)
{
this.site = site;
this.distanceToStart = double.PositiveInfinity;
this.predecessor = null;
this.isClosed = false;
this.isOpen = false;
}
/// <summary>
/// Finds the distance to the starting point of the current search via
/// the predecessors of this site and register it in the object.
/// WARNING : The function will throw an exception
/// if the predecessors do not lead to the starting site one way or another.
/// </summary>
/// <returns>
/// A double which is the distance (cost) to the starting site.
/// </returns>
/// /// <param name="startingSite">
/// The starting site of the search.
/// </param>
public double FindDistanceToStart(SiteForPathfinding startingSite)
{
double distanceToStart = 0;
SiteForPathfinding currentSite = this;
SiteForPathfinding nextPredecessor;
bool foundStartingSite = false;
// Case of this node being the starting site (you never know)
// so as to avoid potential errors.
if (this.site.Location == startingSite.site.Location) {foundStartingSite = true; nextPredecessor = currentSite; }
else nextPredecessor = this.predecessor;
while (!foundStartingSite)
{
distanceToStart = distanceToStart + this.CostOfTransition(nextPredecessor.site);
if (nextPredecessor.site.Location == startingSite.site.Location) foundStartingSite = true;
else
{
currentSite = nextPredecessor;
nextPredecessor = currentSite.predecessor;
}
}
return(distanceToStart);
}
/// <summary>
/// This function retrieves the list of sites that are used in a least-cost path
/// to go back to the starting site. Best used if the current site is the goal that
/// have been reached.
/// </summary>
/// <returns>
/// A list of sites that are the least-cost path. The list will not contain the current
/// site, as it is the goal.
/// </returns>
/// /// <param name="startingSite">
/// The starting site of the search.
/// </param>
public List<SiteForPathfinding> FindPathToStart(SiteForPathfinding startingSite)
{
List<SiteForPathfinding> ListOfSitesInThePath = new List<SiteForPathfinding>();
SiteForPathfinding currentSite = this;
SiteForPathfinding nextPredecessor;
bool foundStartingSite = false;
// Case of this node being the starting site (you never know)
// so as to avoid potential errors.
if (this.site.Location == startingSite.site.Location) { foundStartingSite = true; nextPredecessor = currentSite; ListOfSitesInThePath.Add(currentSite); }
else nextPredecessor = this.predecessor;
while (!foundStartingSite)
{
ListOfSitesInThePath.Add(nextPredecessor);
if (nextPredecessor.site.Location == startingSite.site.Location) foundStartingSite = true;
else
{
currentSite = nextPredecessor;
nextPredecessor = currentSite.predecessor;
}
}
return (ListOfSitesInThePath);
}
/// <summary>
/// Same than FindPathToStart, but returns a list of sites.
/// </summary>
public List<Site> FindPathToStartAsSites(SiteForPathfinding startingSite)
{
List<Site> ListOfSitesInThePath = new List<Site>();
SiteForPathfinding currentSite = this;
SiteForPathfinding nextPredecessor;
bool foundStartingSite = false;
// Case of this node being the starting site (you never know)
// so as to avoid potential errors.
if (this.site.Location == startingSite.site.Location) { foundStartingSite = true; nextPredecessor = currentSite; ListOfSitesInThePath.Add(currentSite.site); }
else nextPredecessor = this.predecessor;
while (!foundStartingSite)
{
ListOfSitesInThePath.Add(nextPredecessor.site);
if (nextPredecessor.site.Location == startingSite.site.Location) foundStartingSite = true;
else
{
currentSite = nextPredecessor;
nextPredecessor = currentSite.predecessor;
}
}
return (ListOfSitesInThePath);
}
/// <summary>
/// Calculate the cost of going from this site to another.
/// </summary>
/// <returns>
/// A double which is the cost of transition.
/// </returns>
/// /// <param name="otherSite">
/// The other site where we want to go to.
/// </param>
public double CostOfTransition(Site otherSite)
{
// The cost of transition is half the transition in this pixel, and half the transition in the other, as we're going from centroid to centroid.
double cost = (SiteVars.CostRasterWithRoads[this.site] + SiteVars.CostRasterWithRoads[otherSite])/2 ;
// We multiply the cost according to the distance (diagonal or not)
if (otherSite.Location.Row != this.site.Location.Row && otherSite.Location.Column == this.site.Location.Column) cost = cost * Math.Sqrt(2.0);
return (cost);
}
/// <summary>
/// A function to compare two sites for the priority queue in the dijkstra algorithm. If one of the two sites has a smaller distance to start than the other, then it has a bigger priority.
/// </summary>
/// <param name="other">The other site to compare this one too.</param>
public int CompareTo(SiteForPathfinding other)
{
if (other.distanceToStart > this.distanceToStart) { return (-1); }
else if (other.distanceToStart < this.distanceToStart) { return (1); }
else { return (0); }
}
}
}