PathFinding - Problème Heuristic

Proton Overflow · 25 Janvier 2017

Bonjour tout le monde, j'ai un problème avec le path finding de BlueDream: https://github.com/alexandre10044/Pathfinder-2.0
Je l'ai converti en VB.Net et j'ai donc ça:

Code:

Imports System.Collections.Generic
Imports System.Linq
Imports System.Text
Imports System.Threading.Tasks
Imports System.Drawing

Namespace CrystalTouch.Engine.PathFinding
    Public Class Pathfinder

#Region "Declarations"

        Private useDiagonals As Boolean
        Private find_ As Boolean = False

        Private destinationCell As Cell, startCell As Cell
        Private currentMap As Map

        Private matrix As New CellMatrix()
        Private openList As New CellList()

        Private Const MapWidth As Short = 20
        Private Const MapHeight As Short = 14

        Public ReadOnly Property LoadedMapId() As Integer
            Get
                If currentMap IsNot Nothing Then
                    Return currentMap.Mapid
                End If
                Return 0
            End Get
        End Property

#End Region

#Region "Constructeurs"


        Public Sub New()
        End Sub

#End Region

#Region "Public method"

        Public Sub SetMap(map As Map, useDiagonal As Boolean)
            currentMap = map
            useDiagonals = useDiagonal
            matrix.Clear()
            openList.Clear()
            Me.find_ = False
            Dim cell As CellData
            Dim id As Integer = 0
            Dim loc1 As Integer = 0
            Dim loc2 As Integer = 0
            Dim loc3 As Integer = 0
            For line As Integer = 0 To 19
                For column As Integer = 0 To 13
                    cell = currentMap.CellData(id)
                    If map.IsEntityOnCell(CShort(id)) Then
                        cell.Mov = False
                    End If
                    matrix.Add(id, New Cell(cell.MapChangeData <> 0, cell.Mov, True, column, loc3, id,
                    New Point(loc1 + column, loc2 + column)))
                    id += 1
                Next
                loc1 += 1
                loc3 += 1
                For column As Integer = 0 To 13
                    cell = currentMap.CellData(id)
                    If map.IsEntityOnCell(CShort(id)) Then
                        cell.Mov = False
                    End If
                    matrix.Add(id, New Cell(cell.MapChangeData <> 0, cell.Mov, True, column, loc3, id,
                    New Point(loc1 + column, loc2 + column)))
                    id += 1
                Next
                loc3 += 1
                loc2 -= 1
            Next
        End Sub

        Public Function GetCompressedPath(startCellId As Short, destinationCellId As Short) As Short()
            Return PathingUtils.GetCompressedPath(find(startCellId, destinationCellId)).ToArray()
        End Function

        Public Function GetPath(startCellId As Short, destinationCellId As Short) As List(Of CellWithOrientation)
            Return find(startCellId, destinationCellId)
        End Function

        
#End Region

#Region "Private method"

        Private Function Find(startCellId As Short, destinationCellId As Short) As List(Of CellWithOrientation)
            startCell = matrix(CInt(startCellId))
            destinationCell = matrix(CInt(destinationCellId))

            matrix(startCellId).Start = True
            matrix(startCellId).InClosedList = True

            matrix(destinationCellId).[End] = True
            destinationCell = matrix(destinationCellId)
            For Each cell As Cell In matrix.Values
                cell.SetH(matrix(destinationCellId))
            Next

            Dim currentCell As Cell = matrix(startCellId)

            Dim startTime As Integer = Environment.TickCount

            While Not find_
                FindAvalableCell(currentCell)

                If Not Find_ Then
                    If openList.Count = 0 Then
                        Return Nothing
                    End If

                    currentCell = openList(0)
                    currentCell.InClosedList = True
                    currentCell.InOpenList = False
                    openList.RemoveAt(0)
                End If

                If (Environment.TickCount - startTime) > 500 Then
                    Return Nothing
                End If
            End While

            Dim cells As New List(Of CellWithOrientation)()
            currentCell = matrix(destinationCellId)

            While currentCell.Parent IsNot Nothing
                cells.Insert(0, New CellWithOrientation(currentCell.Id, currentCell.Location.X, currentCell.Location.Y))
                currentCell = currentCell.Parent
            End While
            cells.Insert(0, New CellWithOrientation(startCellId, matrix(startCellId).Location.X, matrix(startCellId).Location.Y))
            Return cells
        End Function

        Private Sub FindAvalableCell(cell As Cell)
            Dim avalableCell As Cell

            '#Region "Haut-Droite"
            If cell.Position(0) = 0 AndAlso cell.Position(6) = 0 Then
                avalableCell = If(cell.Pair, matrix(cell.Id - 14), matrix(cell.Id - 13))
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Bas-Droite"
            If cell.Position(2) = 0 AndAlso cell.Position(6) = 0 Then
                avalableCell = If(cell.Pair, matrix(cell.Id + 14), matrix(cell.Id + 15))
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Haut-Gauche"
            If cell.Position(0) = 0 AndAlso cell.Position(4) = 0 Then
                avalableCell = If(cell.Pair, matrix(cell.Id - 15), matrix(cell.Id - 14))
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Bas-Gauche"
            If cell.Position(2) = 0 AndAlso cell.Position(4) = 0 Then
                avalableCell = If(cell.Pair, matrix(cell.Id + 13), matrix(cell.Id + 14))
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Droite"
            If cell.Position(6) = 0 AndAlso cell.Position(7) = 0 AndAlso useDiagonals Then
                avalableCell = matrix(cell.Id + 1)
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Gauche"
            If cell.Position(4) = 0 AndAlso cell.Position(5) = 0 AndAlso useDiagonals Then
                avalableCell = matrix(cell.Id - 1)
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Haut"
            If cell.Position(0) = 0 AndAlso cell.Position(1) = 0 AndAlso useDiagonals Then
                avalableCell = matrix(cell.Id - 28)
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            '#Region "Bas"
            If cell.Position(2) = 0 AndAlso cell.Position(3) = 0 AndAlso useDiagonals Then
                avalableCell = matrix(cell.Id + 28)
                If avalableCell.[End] Then
                    avalableCell.Parent = cell
                    find_ = True
                    Return
                End If

                If avalableCell.Walkable Then
                    If Not avalableCell.InOpenList AndAlso Not avalableCell.InClosedList Then
                        avalableCell.Parent = cell
                        avalableCell.InOpenList = True
                        openList.Add(avalableCell)
                        FixeCell(avalableCell, cell)
                    End If
                End If
            End If
            '#End Region

            SortOpenList()
        End Sub

        Private Sub SortOpenList()
            Dim ok As Boolean = False
            While Not ok
                ok = True
                Dim temp As Cell
                For i As Integer = 0 To openList.Count - 2
                    If openList(i).F > openList(i + 1).F AndAlso PathingUtils.DistanceToPoint(openList(i).Location, destinationCell.Location) < PathingUtils.DistanceToPoint(openList(i + 1).Location, destinationCell.Location) Then
                        temp = openList(i)
                        openList(i) = openList(i + 1)
                        openList(i + 1) = temp
                        ok = False
                    End If
                Next
            End While
        End Sub

        Private Sub FixeCell(cellInspected As Cell, currentCell As Cell)
            Dim MovementCost As Double = GetFixedMouvementCost(cellInspected, currentCell)
            cellInspected.G = CUInt(MovementCost)
            cellInspected.H = CUInt(GetFixedHeuristic(cellInspected, currentCell))
            cellInspected.F = cellInspected.G + cellInspected.H
        End Sub

        Private Function GetFixedMouvementCost(cellInspected As Cell, currentCell As Cell) As Double
            Dim poid As Double = PointWeight(cellInspected.Location)
            Return cellInspected.G + (If(cellInspected.Location.Y = currentCell.Location.Y OrElse cellInspected.Location.X = currentCell.Location.X, 10, 15)) * poid
        End Function

        Private Function GetFixedHeuristic(cellInspected As Cell, currentCell As Cell) As Double
            Dim _loc8_ As Boolean = cellInspected.Location.X + cellInspected.Location.Y = Me.destinationCell.Location.X + Me.destinationCell.Location.Y
            Dim _loc9_ As Boolean = cellInspected.Location.X + cellInspected.Location.Y = Me.startCell.Location.X + Me.startCell.Location.Y
            Dim _loc10_ As Boolean = cellInspected.Location.X - cellInspected.Location.Y = Me.destinationCell.Location.X - Me.destinationCell.Location.Y
            Dim _loc11_ As Boolean = cellInspected.Location.X - cellInspected.Location.Y = Me.startCell.Location.X - Me.startCell.Location.Y

            Dim Heuristic As Double = 10 * Math.Sqrt((destinationCell.Location.X - cellInspected.Location.X) * (destinationCell.Location.Y - cellInspected.Location.Y) + (destinationCell.Location.X - cellInspected.Location.X) * (Me.destinationCell.Location.X - cellInspected.Location.X))

            If cellInspected.Location.X = Me.destinationCell.Location.X Or cellInspected.Location.Y = Me.destinationCell.Location.Y Then
                Heuristic = Heuristic - 3
            End If
            If (_loc8_) Or (_loc10_) Or cellInspected.Location.X + cellInspected.Location.Y = currentCell.Location.X + currentCell.Location.Y Or cellInspected.Location.X - cellInspected.Location.Y = currentCell.Location.X - currentCell.Location.Y Then
                Heuristic = Heuristic - 2
            End If
            If cellInspected.Location.X = Me.startCell.Location.X Or cellInspected.Location.Y = Me.startCell.Location.Y Then
                Heuristic = Heuristic - 3
            End If
            If (_loc9_) Or (_loc11_) Then
                Heuristic = Heuristic - 2
            End If

            Return Heuristic
        End Function

        Private Function PointWeight(point As Point) As Double
            Dim result As Double = 1
            Dim cellId As Integer = PathingUtils.CoordToCellId(point.X, point.Y)
            Dim speed As Integer = currentMap.CellData(cellId).Speed
            If speed >= 0 Then
                result = result + (5 - speed)
            Else
                result = result + (11 + Math.Abs(speed))
            End If
            Return result
        End Function

#End Region

    End Class
End Namespace

Jusqu'ici tout va bien, j'utilise le PathFinding, mais au niveau de :

Code:

Dim Heuristic As Double = 10 * Math.Sqrt((destinationCell.Location.X - cellInspected.Location.X) * (destinationCell.Location.Y - cellInspected.Location.Y) + (destinationCell.Location.X - cellInspected.Location.X) * (Me.destinationCell.Location.X - cellInspected.Location.X))

À un moment j'ai 10 * Math.Sqrt(-15) et du coup ça me fait une erreur arithmétique car cellInspected.H doit être en UInteger.
Et à cause de cela, je ne peux pas trouver la endCell, le PathFinding ne fonctionne pas.

Si quelqu'un a une idée... Merci beaucoup.
Pour info je dev sur DofusTouch.

Ashlanfox · 25 Janvier 2017

Tu te rends rapidement compte qu'il y a une erreur dans la racine

asyade · 25 Janvier 2017

Moi je fais comme sa

Code:

Math.Abs(source.X - target.X) + Math.Abs(source.Y - target.Y)

sa reviens presque au meme mais bon sa fais toujours d'autres méthodes ... (commentaire inutile meu bon)

Ashlanfox · 25 Janvier 2017

Oui ça s'appelle la distance de Manhattan et c'est bien mieux que de calculer la racine. Je ne sais pas si tu as vu comment résoudre un système non linéaire avec newton-raphson, mais dans tous les cas je te déconseille de calculer une racine si c'est pour répéter ton algorithme fréquemment.

Proton Overflow · 25 Janvier 2017

Comment puis-je faire alors ?
La racine c'est la distance euclidienne?
Merci pour votre aide

Ashlanfox · 25 Janvier 2017

Et bien si tu souhaites travailler avec la racine, il faut que tu modifies son contenu (sqrt(x*y + y²)):

Code:

Math.Sqrt((destinationCell.Location.X - cellInspected.Location.X) * (destinationCell.Location.Y - cellInspected.Location.Y) + (destinationCell.Location.X - cellInspected.Location.X) * (Me.destinationCell.Location.X - cellInspected.Location.X))

Pour plutôt (sqrt(y² + x²)):

Code:

Math.Sqrt((destinationCell.Location.Y - cellInspected.Location.Y) * (destinationCell.Location.Y - cellInspected.Location.Y) + (destinationCell.Location.X - cellInspected.Location.X) * (Me.destinationCell.Location.X - cellInspected.Location.X))

Et pour information:

Proton Overflow · 25 Janvier 2017

D'accord merci beaucoup !

Labo · 25 Janvier 2017

Ashlanfox a dit:

Je vois mal le rapport entre les systèmes non-linéaires et les plus court chemins…

Ashlanfox · 26 Janvier 2017

Labo a dit:

C'est simple, x = sqrt(y) c'est trouver un x > 0 (pour un y > 0) tel que x² = y, c'est donc l'équivalent de x² - y = 0, soit résoudre un système non linéaire.
Si on prend y = 5 c'est résoudre x² - 5 = 0, et donc d'après la méthode de Newton (je pense que c'est celle utilisée en C, mais pas sûr, ça explique tout de même la démarche fastidieuse qu'est la fonction sqrt) c'est si l'on ne dispose que de la première dérivé:

Vu qu'on travaille sur des fonctions polynomiales, leurs dérivés est extrêmement simple à déterminer donc pour notre cas y = 5:

Et c'est là que la partie marrante commence, il faut trouver un X1 (pour démarrer la suite) tel que la suite {Xn} converge vers notre x, ce qui est follement couteux. D'après l'exemple si on commence avec X1 = 2:

Et donc dans le cas des plus courts chemin, s'il utilisait fréquemment la fonction racine sur des nombres bien précis les performances peuvent diminuer.

Arth · 26 Janvier 2017

C:

/*********************************************************************/
/* An ultimate sqrt routine. Given an IEEE double machine number x   */
/* it computes the correctly rounded (to nearest) value of square    */
/* root of x.                                                        */
/*********************************************************************/

[...]

Les implementations change en fonction du systeme, mais generalement cela semble etre celle-ci.

https://sourceware.org/git/?p=glibc...d30416ca9b92cdc87a6cc840ca30791bba558;hb=HEAD

Newton ou pas, vu la taille du code, (X*X+Y*Y < D*D) est évidemant plus efficace que (sqrt(X*X+Y*Y)<D).

Proton Overflow · 26 Janvier 2017

Donc je devrais utiliser sqrt(x^2+y^2) ou sqrt(xy+y^2) ou sqrt((x1-x2)^2+(y1-y2)^2) ?
Edit: en utlisant la méthode proposé par Ashlanfox

Code:

Math.Sqrt((destinationCell.Location.Y - cellInspected.Location.Y) * (destinationCell.Location.Y - cellInspected.Location.Y) + (destinationCell.Location.X - cellInspected.Location.X) * (Me.destinationCell.Location.X - cellInspected.Location.X))

Et tout fonctionne, merci beaucoup !

Labo · 26 Janvier 2017

Ashlanfox a dit:

Ok, je savais même pas que c'était calculé comme ça. Enfin cela fait sens, vu qu'à chaque itération on augmente quadratiquement la précision.
Enfin bon, on va pas se mentir, même en Python la perte de temps est vraiment négligeable vu la dimension de la map !

RedBust · 26 Janvier 2017

Je plussoie, si on se sert de la distance de Manhattan en pathfinding c'est parce que le calcul euclidien est bien plus coûteux en ressources !
La qualité du contenu est encore meilleure que l'an dernier je devrais vraiment prendre le temps de vous lire de plus près j'en apprendrais sûrement beaucoup

PathFinding - Problème Heuristic

Proton Overflow

Membre

Ashlanfox

Membre

asyade

Membre Actif

Ashlanfox

Membre

Proton Overflow

Membre

Ashlanfox

Membre

Proton Overflow

Membre

Labo

Membre Actif

Ashlanfox

Membre

Arth

Contributeur

Proton Overflow

Membre

Labo

Membre Actif

RedBust

Membre Actif