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
|
enum DIRECTION
{
UP = 0,
RIGHT = 1,
DOWN = 2,
LEFT = 3
};
class Point
{
public int x = 0;
public int y = 0;
public Point() { }
public Point(int _x, int _y) { x = _x; y = _y; }
}
class Node
{
public int G = 0; // distance pour arriver jusqu'au node
public int H = 0; // distance jusqu'à l'arrivée
public int F = 0; // G + H
public Point point = new Point(0, 0);
public Node parent = null;
public Node[] arNeighbours = new Node[4]; // voisins du node
public Node() {}
}
class Pathfinding
{
const int NODE_DISTANCE_VALUE = 10;
const int MAP_SIZE = 100;
List<Node> listOpen = new List<Node>();
public List<Node> listClose = new List<Node>();
Node currentNode = new Node();
public Node[,] mapNode = new Node[MAP_SIZE, MAP_SIZE];
public Pathfinding()
{
for (int x = 0; x < MAP_SIZE; x++) // on prépare les nodes à l'avance sur mapNode (coordonnées)
{
for (int y = 0; y < MAP_SIZE; y++)
{
mapNode[x, y] = new Node();
mapNode[x, y].point = new Point(x, y);
}
}
for (int x = 0; x < MAP_SIZE; x++) // on met les voisins de chaque node, on laisse null si ça sort du tableau
{
for (int y = 0; y < MAP_SIZE; y++)
{
for (int i = 0; i < 4; i++)
mapNode[x, y].arNeighbours[i] = null;
if ((x - 1) >= 0) // on retient les voisins de chaque node dans le tableau arNeighbours
mapNode[x, y].arNeighbours[(int)DIRECTION.LEFT] = mapNode[x - 1, y];
if ((x + 1) < MAP_SIZE)
mapNode[x, y].arNeighbours[(int)DIRECTION.RIGHT] = mapNode[x + 1, y];
if ((y - 1) >= 0)
mapNode[x, y].arNeighbours[(int)DIRECTION.UP] = mapNode[x, y - 1];
if ((y + 1) < MAP_SIZE)
mapNode[x, y].arNeighbours[(int)DIRECTION.DOWN] = mapNode[x, y + 1];
}
}
}
public void FindPath(Point _start, Point _end)
{
bool bProgress = false;
mapNode[_start.x, _start.y].G = 0; // calculs du node de départ
mapNode[_start.x, _start.y].H = (Math.Abs(_end.x - _start.x) + Math.Abs(_end.y - _start.y)) * NODE_DISTANCE_VALUE;
mapNode[_start.x, _start.y].F = mapNode[_start.x, _start.y].H;
listOpen.Add(mapNode[_start.x, _start.y]); // on ajoute le node de départ à la liste ouverte
while ((listOpen.Count > 0) && (bProgress == false))
{
currentNode = FindNodeOpen(); // récupère node le plus léger de liste ouverte en l'effaçant de la liste ouverte
listClose.Add(currentNode); // ajoute à liste fermée
for (int i = 0; i < 4; i++) // chaque voisin
{
if(currentNode.arNeighbours[i] != null) // si le voisin existe
{
if (IfInClose(currentNode.arNeighbours[i]) == false) // si pas dans liste fermée
{
currentNode.arNeighbours[i].parent = currentNode; // calcul du node voisin en cours
currentNode.arNeighbours[i].G = currentNode.arNeighbours[i].parent.G + NODE_DISTANCE_VALUE;
currentNode.arNeighbours[i].H = (Math.Abs(_end.x - currentNode.arNeighbours[i].point.x) + Math.Abs(_end.y - currentNode.arNeighbours[i].point.y)) * NODE_DISTANCE_VALUE;
currentNode.arNeighbours[i].F = currentNode.arNeighbours[i].G + currentNode.arNeighbours[i].H;
AddToOpen(currentNode.arNeighbours[i]); // ajoute à la liste ouverte (ou remplaçant si un similaire existe dedans en moins bien)
}
}
}
if (currentNode.point == _end) // si le node courant a les mêmes coordonnées que l'arrivée
bProgress = true;
}
}
private Node FindNodeOpen()
{
Node nodetmp = listOpen[0];
int iIndex = 0;
for (int i = 0; i < listOpen.Count; i++) // parcours de liste ouverte
{
if (nodetmp.F > listOpen[i].F) // si node plus léger
{
nodetmp = listOpen[i]; // on prend ce node
iIndex = i; // on retient l'index pour effacer de la liste ouverte
}
}
listOpen.RemoveAt(iIndex); // on efface de la liste ouverte
return nodetmp;
}
private bool IfInClose(Node _newNode)
{
for (int i = 0; i < listClose.Count; i++)
{
if (_newNode.point == listClose[i].point) // si même coordonnée c'est qu'il y a déjà dans liste fermée
{
return true;
}
}
return false;
}
private bool AddToOpen(Node _newNode)
{
for (int i = 0; i < listOpen.Count; i++) // on parcourt liste ouverte
{
if (_newNode.point == listOpen[i].point) // si il y a un node avec même coordonnées
{
if (_newNode.G < listOpen[i].G) // et si le node de la liste ouverte a un chemin plus long
{
listOpen[i] = _newNode; // on remplace par le nouveau node plus léger
return true;
}
}
}
listOpen.Add(_newNode); // si il n'y est pas déjà dans la liste ouverte, on le place à la fin de celle-ci
return false;
}
} |
