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;
}
} |
Partager