Discussion :

[Invité]

Bonsoir,

j'ai fais un pathfinding, mais il ne marche pas très bien. Enfin il ne marche pas toujours et des fois il me fais des trucs bizard. Pourriez-vous m'aider ?

Conseil ? Amélioration ?
Voilà mon code:

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
 
Public Class Pathfinding
    Public movepath As New List(Of UInteger)
    Public Cells As New List(Of CellInfo)
    Public cellactuel As UInteger
    Public cellarrivée As UInteger
    Public IsPath As Boolean = False
    Public CanMove As Boolean = True
    Public Sub FindPath(ByVal listcellopen As List(Of UInteger), ByVal actuell As UInteger, ByVal arrive As UInteger)
        '--Variables--
        cellactuel = actuell
        cellarrivée = arrive
        movepath.Add(cellactuel)
 
        '--Vérification--
        If cellactuel = cellarrivée Then
            Exit Sub
        End If
        '--Cellules--
        For i = 0 To 559
            Dim obstacle As Boolean = False
            If listcellopen.Contains(i) Then
                obstacle = False
            Else
                obstacle = True
            End If
            Cells.Add(New CellInfo(i, obstacle))
        Next
 
        '--FindPath--
        While Not cellactuel = cellarrivée
            '--Variables--
            Dim casewalk As New List(Of Integer)
            Dim x = Cells(cellactuel).X
            Dim y = Cells(cellactuel).Y
            '--Calcul H--
            For i = 0 To 559
                Cells(i).Calcul_H(Cells(cellarrivée).X, Cells(cellarrivée).Y)
            Next
            '--Calcul algo--
            For i = 0 To Cells.Count - 1
                If Cells(i).X = x And Cells(i).Y = y + 1 And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x And Cells(i).Y = y - 1 And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x - 1 And Cells(i).Y = y And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x + 1 And Cells(i).Y = y And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x + 1 And Cells(i).Y = y + 1 And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x - 1 And Cells(i).Y = y - 1 And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x - 1 And Cells(i).Y = y + 1 And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
                If Cells(i).X = x + 1 And Cells(i).Y = y - 1 And Cells(i).obstacle = False Then
                    casewalk.Add(i)
                End If
            Next
            'Une fois qu'on a nos 8 case ainsi que leur cout F rien de plus simple que le comparer
            Dim H As Integer = 99999
            Dim index As Integer
            For i = 0 To casewalk.Count - 1
                'F est inférieur il devient la meilleur case
                If h > Cells(casewalk(i)).H Then
                    H = Cells(casewalk(i)).H
                    index = casewalk(i)
                End If
            Next
            'On a la cell avec le cout F le plus bas :P
            movepath.Add(index)
            cellactuel = index
            Cells(index).obstacle = True
        End While
    End Sub
End Class

Mes autres class:

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
Public Class MapPosition
    'X gauche à droite
    'Y bas en haut
    Public X As Integer = 0
    Public Y As Integer = 0
    Public H As Integer
    Public Id_cell As UInteger
 
    Public Function CalculXY(ByVal cellid As UInteger)
        X = cellid Mod 14
        Y = cellid \ 14
        Return X
        Return Y
    End Function
    Public Function CalculCellid(ByVal X As Integer, ByVal Y As Integer)
        Id_cell = Y * 14 + X
        Return Id_cell
    End Function
    Public Function calculh(ByVal xstart As Integer, ByVal ystart As Integer, ByVal xend As Integer, ByVal yend As Integer)
        h = (Math.Abs(xend - xstart) + Math.Abs(yend - ystart))
        Return h
    End Function
End Class

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
Public Class CellInfo
    Public X As Integer
    Public Y As Integer
    Public H As Integer
    Public index As Integer
    Public obstacle As Boolean = False
 
    Sub New(ByVal indexx As Integer, ByVal obstaclee As Boolean)
        index = indexx
        Dim Map = New MapPosition
        Map.CalculXY(index)
        X = Map.X
        Y = Map.Y
        obstacle = obstaclee
    End Sub
    Public Sub Calcul_H(ByVal Xarrivé As Integer, ByVal Yarrivé As Integer)
        H = 10 * (Math.Abs(Xarrivé - X) + Math.Abs(Yarrivé - Y)) 'la distance à l'arrivé est égale à al diff en abscisse + la diff en ordonnée)
 
    End Sub
End Class

Cordialement

[DonQuiche]

Bonjour.

Vu le pavé de code, si tu souhaites de l'aide je te conseille vivement...
* D'utiliser les balises "code" plutôt que "quote". Et de préciser : code="VB".
* D'ajouter des commentaires. Parce que les cas 531, 517, etc, ce n'est guère parlant à moins d'avoir des pouvoirs psychiques.
* D'expliquer à quel problème est appliqué l'algorithme. Quel type de terrain (grille, hexagones, pixel près, etc), quelles contraintes de mouvements, etc ?

EDIT : Cela dit CalculeXY et CalculeCellID peuvent déjà être refaites complètement pour être plus courtes, plus rapides, plus compréhensibles, et bien moins sujettes à des bugs.
Tout le code de CalculeXY peut être remplacé par ces deux lignes :

Code :

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

1
2
X = (cellid Mod 28) + 1
Y = 40 - (cellid \ 14)

Et celui pour CalculeCellID par :

Code :

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

1
2
3
Xnumber = (X \ 2) + 14 * (X Mod 2)
Ynumber = 560 - Y * 14
Id_cell = Xnumber + Ynumber

EDIT 2 : Et une fois le code réécrit comme je l'ai fait, je me dis qu'il est bogué. Pour une grille 14*N le bon code serait :

Code :

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

1
2
X = cellid Mod 14
Y = cellid \ 14

Code :

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

Id_cell = Y * 14 + X

[Invité]

Merci à toi pour ton aide
C'est une grille, et des fois le chemin n'est pas bon, il ne prend pas le meilleur.

[-N4w4k-]

Salut,

je ne connais pas le pathfinding mais après un minimum de recherche, il revient souvent que:

A* est l'un des algorithmes les plus efficaces pour trouver un chemin rapidement, cependant, il se peut que dans des schémas assez complexes, comme un labyrinthe ou il faut faire beaucoup d'allers retours ou s'éloigner souvent de son objectif pour mieux l'atteindre, il peut ne pas retourner le chemin le plus court ou être un peu moins rapide que d'autres.

C'est peut-être pourquoi il ne prend pas le "meilleur chemin" à chaque fois..

[DonQuiche]

@Alexandre
L'algorithme implémenté n'est pas A*, c'est un algorithme glouton naïf. Je te conseille de réétudier A* pour le comprendre. Une différence importante :
* A chaque étape l'algo glouton considère les huit cases les plus proches et choisit la plus prometteuse.
* A chaque étape A* choisit le plus prometteur des bouts de chemins envisagées jusqu'ici et prolonge ce chemin en créant 7 nouveaux chemins.

Exemple avec des déplacements horizontaux ou verticaux uniquement (3 nouveaux chemins par chemin) et une grille 12*N. Mettons qu'à l'étape 4 les deux chemins les plus prometteurs soient :
* (12,24,36,35) : 4 km parcourus, 8 km restants estimés
* (12,13,25,37) : 5 km parcourus, 8 km restants estimés

Le premier semble le meilleur, on va donc tenter de le prolonger :
* (12,24,36,35,34) : 5 km parcourus, 10 km restants estimés
* (12,24,36,35,23) : 5 km parcourus, 11 km restants estimés
* (12,24,36,35,47) : 5 km parcourus, 9 km restants estimés
* (12,13,25,37) : 5 km parcourus, 8 km restants estimés

En définitive les chemins générés par celui qui semblait le plus prometteur sotn décevants et moins prometteurs que le quatrième. Au prochain coup on tentera donc de prolonger le quatrième.

[Invité]

Merci de votre aide, j'ai pourtant suivi les indications de cette page plutot bien réputé:
http://blog.lalex.com/post/2003/09/1...-pathfinding-A

[DonQuiche]

Ce n'est pas l'article en question le problème : il présente une application particulère de A* au problème d'une grille. Et il le fait correctement en insistant sur l'importance de maintenir une liste "ouverte" et une liste "fermée" et la nécessité de prendre en compte à la fois les coûts G et H (et F = G + H). Toi, tu n'as pas de liste "ouverte", pas de liste "fermée", et tu ne calcules jamais G ! Et en plus ton heuristique (H) n'est pas terrible mais c'est celle présentée par l'article (qui soulignait sa médiocrité mais n'a pas suggéré d'alternative).

[Invité]

D'accord merci à toi.

J'ai un problème avec le calcul des coordonées X ; Y.

Ma grille est spécial, la voici:
Je l'ai numéroté avec les coordonées X ; Y.
Je me suis trompé cela ne commence pas par 1 mais par 0 mais tu as compris.



La numérotation est spécial. Comment pourrais-je calculer mes coordonées de cette façon ?

[DonQuiche]

D'abord il y a un problème : pour chaque indice "i" tu as deux cases possibles, donc deux couples (x, y). Ensuite, veux-tu que l'axe des abscisses soit horizontal à l'écran, ou parallèle à un des traits de ta grille ?

Si je ne considère que les indices du haut et que tu souhaites un axe horizontal, alors, pour une grille 10*N :

Code :

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

1
2
3
x = (i Mod 10) 
y = 2 * (i \ 10) + (i Mod 2)
i = (y \ 2) * 10 + x