Problème pathfinding A star

**Lyofen** · 21/11/2012, 13h22

Bonjour,

Habitué à faire du C et C++, j'ai décidé de me mettre au C# il y a peu histoire de commencé sur XNA pour essayer de sortir un petit jeu avant que la xbox360 ne soit plus d'actualité, mais je suis confronté à un petit problème au niveau de mon algo de pathfinding A*...

J'ai voulu donc mettre au point un pathfinding A*, avec 4 voisins (donc pas de mouvements en diagonale), mais mon code actuel ne trouve pas du tout le chemin.

J'utilise une map de nodes précalculée pour que chaque node ait déjà ses 4 voisins en mémoire, et pour le moment il n'y a pas de case "mur", c'est à dire bloquante pour trouver le chemin.

Je vous mets tout le code qui permet de faire fonctionner la fonction FindPath():

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Il y a sûrement beaucoup de choses que je pourrais optimiser, ou d'autres méthodes plus rapides, mais je fais appel à vous pour me dire si il y a une partie du code qui ne marcherait pas en C# ou si j'ai carrément oublié une étape qui m'empêcherait de trouver le chemin, j'essaierai d'optimiser dans un second temps.

J'ai pas passé énormément de temps sur ce code, mais là j'avoues que depuis quelques temps j'essais différents trucs et sa coince toujours, donc je remercie ceux qui se pencheront sur mon problème et j'attends votre avis !

**Lyofen** · 22/11/2012, 19h41

Bon, on va dire que le problème est résolu, je suis passé carrément par une autre solution, qui n'utilise pas de pointeur vers le parent, pas de grille précalculée... et ça marche très bien.

Je remercie ceux qui ont essayé de se pencher sur mon problème (si ya =°), puis si mon nouveau code de A* intéresse quelqu'un faite moi signe !

**e.Saad** · 21/04/2016, 20h54

Bonjour ! Je suis actuellement en train de faire un jeu d'infiltration, et je suis intrigué... Quelle solution as-tu trouvé ?

Je patauge dans la semoule, personnellement.

**Lyofen** · 28/06/2016, 17h40

Salut, je réponds un peu en retard... =x

Honnêtement je ne me souviens plus du tout où j'ai mis le code sur le pathfinding, mais je me souviens avoir utilisé le code de ce tuto:

J'ai d'ailleurs du mettre des commentaires dessus (pseudo Remy.Tabardel) car j'avais rencontré quelques problèmes.

Bon courage ! (même si t'as du trouver depuis

)

Problème pathfinding A star

C#

Discussions similaires

Partager

Partager