A*-Algorithmus [Edit 2]

  • C#

Es gibt 27 Antworten in diesem Thema. Der letzte Beitrag () ist von Eistee.

    A*-Algorithmus [Edit 2]

    Hallo,

    so nach Tagen der fummelei funktioniert es noch immer nicht wie es soll, daher wollte ich mal fragen ob ihr etwas fertiges kennt, was zugleich leicht zu implementieren ist.
    Hätte es gerne selbst geschafft, aber ich kann die Fehler in meinem Code nicht finden. Der Weg selbst wird gefunden es ist aber nicht der kürzeste.
    Das mit den diagonalen neben den Mauern könnte ich fixen aber dann wäre die Wegfindung ja noch immer nicht richtig. Hier mal ein Bild:


    *Topic verschoben*

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Eistee“ ()

    Das Video hilft leider nicht wirklich, denn wenn ich die Diagonalen Felder rausnehme (wie im Video) funktioniert es wie es soll.
    Nur Wenn ich meine Objekte nach diesem Weg bewege, sieht das ganze sehr unnatürlich aus.
    Also eine "gerade"-Diagoinale würde in Stufen abgefahren/abgelaufen (Wie bei Snake), was bei einem Auto total bescheuert aussieht ^^

    Ohne Diagonale wie im Video:
    (Der Startpunkt ist nicht da wo das Modell steht, sondern beim 1. rosa Kasten daneben)

    @nafets3646: Weil ich eine absolute Null in Mathe bin und absolut keine Ahnung habe wie man das macht.
    Ich kann mir zwar vorstellen das man sich 2 Punkte sucht (wie die nach der Mauer auf dem Bild), wo man dann
    eine Diagonale ziehen kann (also alle Felder 'frei' sind), aber wie man soetwas macht ?(

    Oder in der Form:

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Eistee“ ()

    @Eistee
    zeig doch mal deinen kompletten Code^^ Ansonsten setzt doch einfach den Pseudocode von z.B. Wikipedia um

    @nafets3646
    Die Strecke zu smoothen dürfte nicht funktionieren, wenn du iwelche Schrägen einbaust, dann könnten dort ja Kollisionen entstehen.

    Es macht eigentlich keinen Unterschied. Ich persönlich wäre sogar glücklicher, wenn du C# postest, weil ich das besser mag aber auch, weil die Converter schlecht sind. So oder so wirst du wohl genau gleich kompetente Hilfe erhalten. Wenn nen Moderator so pingelig ist, dann soll ers halt verschieben, macht ja nichts. ;)

    Ich Editiere in wenigen Minuten beides (C# & VB) hier drunter.
    Aber ob ihr den Mist nachvollziehen könnt ist eine andere Geschichte ^^

    Vb
    Knoten

    VB.NET-Quellcode

    1. Class Knoten
    2. Public Property position() As Vector2
    3. Get
    4. Return m_position
    5. End Get
    6. Set
    7. m_position = Value
    8. End Set
    9. End Property
    10. Private m_position As Vector2
    11. Public Property vorgaenger() As Knoten
    12. Get
    13. Return m_vorgaenger
    14. End Get
    15. Set
    16. m_vorgaenger = Value
    17. End Set
    18. End Property
    19. Private m_vorgaenger As Knoten
    21. Public Property H_geschaetzteKosten() As Integer
    22. Get
    23. Return m_H_geschaetzteKosten
    24. End Get
    25. Set
    26. m_H_geschaetzteKosten = Value
    27. End Set
    28. End Property
    29. Private m_H_geschaetzteKosten As Integer
    30. Public Property G_GesamtFeldkosten() As Integer
    31. Get
    32. Return m_G_GesamtFeldkosten
    33. End Get
    34. Set
    35. m_G_GesamtFeldkosten = Value
    36. End Set
    37. End Property
    38. Private m_G_GesamtFeldkosten As Integer
    39. Public Property F_StartZumZielUeberHierKosten() As Integer
    40. Get
    41. Return m_F_StartZumZielUeberHierKosten
    42. End Get
    43. Set
    44. m_F_StartZumZielUeberHierKosten = Value
    45. End Set
    46. End Property
    47. Private m_F_StartZumZielUeberHierKosten As Integer
    49. Private Const geradeKosten As Integer = 10
    50. Private Const diagonalKosten As Integer = 14
    52. Public Sub New(Position__1 As Vector2)
    53. position = Position__1
    54. End Sub
    56. Public Function isInList(Liste As List(Of Knoten)) As [Boolean]
    57. For x As Integer = 0 To Liste.Count - 2
    58. If Liste(x).position = Me.position Then
    59. Return True
    60. End If
    61. Next
    62. Return False
    63. End Function
    65. Public Function getIndexBasedOnPosition(Liste As List(Of Knoten)) As Integer
    66. For x As Integer = 0 To Liste.Count - 2
    67. If Liste(x).position = Me.position Then
    68. Return x
    69. End If
    70. Next
    71. Return -1
    72. End Function
    74. Public Function getDirectionalCostBasedOnPredecessor() As Integer
    75. If Me.vorgaenger IsNot Nothing Then
    76. If Me.vorgaenger.position.X = Me.position.X OrElse Me.vorgaenger.position.Y = Me.position.Y Then
    77. ' Der Knoten ist Wagerecht oder Senkrecht zum Knoten
    78. Return 10
    79. Else
    80. ' Der Knoten ist Diagonal zum Knoten
    81. Return 14
    82. End If
    83. Else
    84. Throw New ArgumentNullException("Knoten.vorgaenger", "Dieser Knoten hat keinen Vorgänger")
    85. End If
    86. End Function
    88. Public Function getDirectionalCostOver(Knoten As Knoten) As Integer
    89. If Knoten.position.X = Me.position.X OrElse Knoten.position.Y = Me.position.Y Then
    90. ' Der Knoten ist Wagerecht oder Senkrecht zum Knoten
    91. Return 10
    92. Else
    93. ' Der Knoten ist Diagonal zum Knoten
    94. Return 14
    95. End If
    96. End Function
    98. Public Function getNeighbors(karte As Map) As List(Of Point)
    99. Dim list As New List(Of Point)()
    100. Dim x As Integer = 0, y As Integer = 0
    101. For i As Integer = Math.Max(x - 1, 0) To Math.Min(x + 2, karte.Tiles.GetUpperBound(0)) - 1
    102. For j As Integer = Math.Max(y - 1, 0) To Math.Min(y + 2, karte.Tiles.GetUpperBound(1)) - 1
    103. If i = x AndAlso j = y Then
    104. Continue For
    105. End If
    106. list.Add(New Point(x, y))
    107. Next
    108. Next
    109. Return list
    110. End Function
    112. Public Function getWalkableNeighbors(karte As Map) As List(Of Point)
    113. Dim list As New List(Of Point)()
    114. Dim x As Integer = CInt(Me.position.X), y As Integer = CInt(Me.position.Y)
    115. For i As Integer = Math.Max(x - 1, 0) To Math.Min(x + 2, karte.Tiles.GetUpperBound(0)) - 1
    116. For j As Integer = Math.Max(y - 1, 0) To Math.Min(y + 2, karte.Tiles.GetUpperBound(1)) - 1
    117. If i = x AndAlso j = y Then
    118. Continue For
    119. ElseIf karte.Tiles(i, j).begehbar Then
    120. list.Add(New Point(i, j))
    121. End If
    122. Next
    123. Next
    124. Return list
    125. End Function
    126. End Class

    Objekt mit der Funktion einen Weg zu finden

    VB.NET-Quellcode

    1. Private Function findPathAStar(start As Vector2, ziel As Vector2) As List(Of Knoten)
    2. ' reset
    3. openList.Clear()
    4. closedList.Clear()
    5. Dim zielKnoten As New Knoten(ziel)
    6. ' end
    8. ' Beginne mit Startpunkt A und füge ihn einer "offenen" Liste von Quadraten hinzu
    9. Dim startKnoten As New Knoten(New Vector2(start.X, start.Y))
    10. openList.Add(startKnoten)
    11. ' Füge sie der o.g. Liste hinzu und merke für jedes dieser Quadrate das Startquadrat A als seinen Vorgänger
    12. For Each p As Point In startKnoten.getWalkableNeighbors(karte)
    13. Dim ktn As New Knoten(New Vector2(p.X, p.Y))
    14. ktn.vorgaenger = startKnoten
    15. openList.Add(ktn)
    16. Next
    17. ' Wirf das Startquadrat A aus der offenen Liste und füge es der geschlossenen Liste hinzu
    18. openList.removeWithPosition(startKnoten.position)
    19. closedList.Add(startKnoten)
    20. ' Berechne alle Kosten aller Quadrate in der offenen Liste
    21. For Each knt As Knoten In openList
    22. If knt.vorgaenger IsNot Nothing Then
    23. knt.G_GesamtFeldkosten = knt.vorgaenger.G_GesamtFeldkosten + knt.getDirectionalCostBasedOnPredecessor()
    24. Else
    25. knt.G_GesamtFeldkosten = 0
    26. End If
    27. knt.H_geschaetzteKosten = Math.Abs(CInt(((ziel.X - start.X) + (ziel.Y - start.Y)) * 10))
    28. knt.F_StartZumZielUeberHierKosten = knt.G_GesamtFeldkosten + knt.H_geschaetzteKosten
    29. Next
    31. While Not zielKnoten.isInList(closedList)
    32. ' Das Quadrat mit den niedrigsten F-Kosten.
    33. Dim aktuell As Knoten = openList.getLowestF()
    34. ' Entferne es aus der offenen Liste
    35. openList.removeWithPosition(aktuell.position)
    36. ' füge es der geschlossenen Liste hinzu
    37. closedList.Add(aktuell)
    38. ' Prüfe alle angrenzenden Quadrate und füge sie der offenen Liste hinzu (WENN: begehbar, nicht schon in offener/geschlossener Liste)
    39. For Each p As Point In aktuell.getWalkableNeighbors(karte)
    40. Dim ktn As New Knoten(New Vector2(p.X, p.Y))
    41. ktn.vorgaenger = aktuell
    42. ' Wenn nicht in geschlossener Liste
    43. If Not ktn.isInList(closedList) Then
    44. ' Wenn nicht in offener Liste
    45. If Not ktn.isInList(openList) Then
    46. openList.Add(ktn)
    47. Else
    48. ' Wenn in offener Liste
    49. ' WENN G-Wert für dieses Quadrat (ktn) wenn wir vom aktuellen dort hingehen [z. B. Recht und dann Hoch]
    50. Dim alterGWert As Integer = ktn.G_GesamtFeldkosten
    51. Dim neueGWert As Integer = aktuell.G_GesamtFeldkosten + aktuell.getDirectionalCostOver(ktn)
    52. ' Weg über (aktuell) wäre kürzer:
    53. If neueGWert < alterGWert Then
    54. ' Wir ändern den Vorgänger von ktn auf das aktuelle Quadrat
    55. ktn.vorgaenger = aktuell
    56. ' Berechnen die G-Kosten mit dem neuen Vorgänger sowie die neuen F-Kosten
    57. ktn.G_GesamtFeldkosten = ktn.vorgaenger.G_GesamtFeldkosten + ktn.getDirectionalCostBasedOnPredecessor()
    58. ktn.F_StartZumZielUeberHierKosten = ktn.G_GesamtFeldkosten + ktn.H_geschaetzteKosten
    59. End If
    60. End If
    61. End If
    62. Next
    63. End While
    65. Dim _path As New List(Of Knoten)()
    66. Dim indexOfZiel As Integer = zielKnoten.getIndexBasedOnPosition(closedList)
    67. Dim tempKnoten As Knoten = closedList(indexOfZiel)
    68. While tempKnoten.vorgaenger IsNot Nothing
    69. _path.Add(tempKnoten)
    70. tempKnoten = tempKnoten.vorgaenger
    71. End While
    73. Return _path
    74. End Function

    Extensions

    VB.NET-Quellcode

    1. NotInheritable Class MyExtensions
    2. Private Sub New()
    3. End Sub
    4. <System.Runtime.CompilerServices.Extension> _
    5. Public Shared Function getLowestF(list As List(Of Knoten)) As Knoten
    6. Dim kMitMinFKosten As Knoten = list(0)
    7. For x As Integer = 0 To list.Count - 2
    8. If kMitMinFKosten.F_StartZumZielUeberHierKosten > list(x).F_StartZumZielUeberHierKosten Then
    9. kMitMinFKosten = list(x)
    10. End If
    11. Next
    12. Return kMitMinFKosten
    13. End Function
    15. <System.Runtime.CompilerServices.Extension> _
    16. Public Shared Sub removeWithPosition(list As List(Of Knoten), position As Vector2)
    17. For x As Integer = 0 To list.Count - 2
    18. If list(x).position = position Then
    19. list.RemoveAt(x)
    20. End If
    21. Next
    22. End Sub
    23. End Class


    C#
    Knoten

    C#-Quellcode

    1. class Knoten
    2. {
    3. public Vector2 position {get; set; }
    4. public Knoten vorgaenger { get; set; }
    6. public int H_geschaetzteKosten { get; set; }
    7. public int G_GesamtFeldkosten { get; set; }
    8. public int F_StartZumZielUeberHierKosten { get; set; }
    10. private const int geradeKosten = 10;
    11. private const int diagonalKosten = 14;
    13. public Knoten(Vector2 Position)
    14. {
    15. position = Position;
    16. }
    18. public Boolean isInList(List<Knoten> Liste){
    19. for (int x = 0; x < Liste.Count - 1; x++){
    20. if (Liste[x].position == this.position){
    21. return true;
    22. }
    23. }
    24. return false;
    25. }
    27. public int getIndexBasedOnPosition(List<Knoten> Liste)
    28. {
    29. for (int x = 0; x < Liste.Count - 1; x++)
    30. {
    31. if (Liste[x].position == this.position)
    32. {
    33. return x;
    34. }
    35. }
    36. return -1;
    37. }
    39. public int getDirectionalCostBasedOnPredecessor(){
    40. if (this.vorgaenger != null)
    41. {
    42. if (this.vorgaenger.position.X == this.position.X ||
    43. this.vorgaenger.position.Y == this.position.Y){
    44. return 10; // Der Knoten ist Wagerecht oder Senkrecht zum Knoten
    45. }
    46. else
    47. {
    48. return 14; // Der Knoten ist Diagonal zum Knoten
    49. }
    50. }
    51. else
    52. {
    53. throw new ArgumentNullException("Knoten.vorgaenger", "Dieser Knoten hat keinen Vorgänger");
    54. }
    55. }
    57. public int getDirectionalCostOver(Knoten Knoten)
    58. {
    59. if (Knoten.position.X == this.position.X ||
    60. Knoten.position.Y == this.position.Y)
    61. {
    62. return 10; // Der Knoten ist Wagerecht oder Senkrecht zum Knoten
    63. }
    64. else
    65. {
    66. return 14; // Der Knoten ist Diagonal zum Knoten
    67. }
    68. }
    70. public List<Point> getNeighbors(Map karte)
    71. {
    72. List<Point> list = new List<Point>();
    73. int x=0, y = 0;
    74. for (int i = Math.Max(x - 1, 0); i < Math.Min(x + 2, karte.Tiles.GetUpperBound(0)); i++)
    75. {
    76. for (int j = Math.Max(y - 1, 0); j < Math.Min(y + 2, karte.Tiles.GetUpperBound(1)); j++)
    77. {
    78. if (i == x && j == y)
    79. continue;
    80. list.Add(new Point(x, y));
    81. }
    82. }
    83. return list;
    84. }
    86. public List<Point> getWalkableNeighbors(Map karte)
    87. {
    88. List<Point> list = new List<Point>();
    89. int x = (int)this.position.X, y = (int)this.position.Y;
    90. for (int i = Math.Max(x - 1, 0); i < Math.Min(x + 2, karte.Tiles.GetUpperBound(0)); i++)
    91. {
    92. for (int j = Math.Max(y - 1, 0); j < Math.Min(y + 2, karte.Tiles.GetUpperBound(1)); j++)
    93. {
    94. if (i == x && j == y)
    95. {
    96. continue;
    97. }
    98. else if (karte.Tiles[i, j].begehbar)
    99. {
    100. list.Add(new Point(i, j));
    101. }
    102. }
    103. }
    104. return list;
    105. }
    106. }

    Objekt mit der Funktion einen Weg zu finden

    C#-Quellcode

    1. List<Knoten> findPathAStar(Vector2 start, Vector2 ziel)
    2. {
    3. // reset
    4. openList.Clear();
    5. closedList.Clear();
    6. Knoten zielKnoten = new Knoten (ziel);
    7. // end
    9. // Beginne mit Startpunkt A und füge ihn einer "offenen" Liste von Quadraten hinzu
    10. Knoten startKnoten = new Knoten(new Vector2(start.X, start.Y));
    11. openList.Add(startKnoten);
    12. // Füge sie der o.g. Liste hinzu und merke für jedes dieser Quadrate das Startquadrat A als seinen Vorgänger
    13. foreach (Point p in startKnoten.getWalkableNeighbors(karte)){
    14. Knoten ktn = new Knoten(new Vector2(p.X, p.Y));
    15. ktn.vorgaenger = startKnoten;
    16. openList.Add(ktn);
    17. }
    18. // Wirf das Startquadrat A aus der offenen Liste und füge es der geschlossenen Liste hinzu
    19. openList.removeWithPosition(startKnoten.position);
    20. closedList.Add(startKnoten);
    21. // Berechne alle Kosten aller Quadrate in der offenen Liste
    22. foreach (Knoten knt in openList)
    23. {
    24. if (knt.vorgaenger != null) { knt.G_GesamtFeldkosten = knt.vorgaenger.G_GesamtFeldkosten + knt.getDirectionalCostBasedOnPredecessor(); } else { knt.G_GesamtFeldkosten = 0; }
    25. knt.H_geschaetzteKosten = Math.Abs((int)(((ziel.X - start.X) + (ziel.Y - start.Y)) * 10));
    26. knt.F_StartZumZielUeberHierKosten = knt.G_GesamtFeldkosten + knt.H_geschaetzteKosten;
    27. }
    29. while (!zielKnoten.isInList(closedList))
    30. {
    31. // Das Quadrat mit den niedrigsten F-Kosten.
    32. Knoten aktuell = openList.getLowestF();
    33. // Entferne es aus der offenen Liste
    34. openList.removeWithPosition(aktuell.position);
    35. // füge es der geschlossenen Liste hinzu
    36. closedList.Add(aktuell);
    37. // Prüfe alle angrenzenden Quadrate und füge sie der offenen Liste hinzu (WENN: begehbar, nicht schon in offener/geschlossener Liste)
    38. foreach (Point p in aktuell.getWalkableNeighbors(karte))
    39. {
    40. Knoten ktn = new Knoten(new Vector2(p.X, p.Y));
    41. ktn.vorgaenger = aktuell;
    42. // Wenn nicht in geschlossener Liste
    43. if (!ktn.isInList(closedList))
    44. {
    45. // Wenn nicht in offener Liste
    46. if (!ktn.isInList(openList))
    47. {
    48. openList.Add(ktn);
    49. }
    50. // Wenn in offener Liste
    51. else
    52. {
    53. // WENN G-Wert für dieses Quadrat (ktn) wenn wir vom aktuellen dort hingehen [z. B. Recht und dann Hoch]
    54. int alterGWert = ktn.G_GesamtFeldkosten;
    55. int neueGWert = aktuell.G_GesamtFeldkosten + aktuell.getDirectionalCostOver(ktn);
    56. // Weg über (aktuell) wäre kürzer:
    57. if (neueGWert<alterGWert)
    58. {
    59. // Wir ändern den Vorgänger von ktn auf das aktuelle Quadrat
    60. ktn.vorgaenger = aktuell;
    61. // Berechnen die G-Kosten mit dem neuen Vorgänger sowie die neuen F-Kosten
    62. ktn.G_GesamtFeldkosten = ktn.vorgaenger.G_GesamtFeldkosten + ktn.getDirectionalCostBasedOnPredecessor();
    63. ktn.F_StartZumZielUeberHierKosten = ktn.G_GesamtFeldkosten + ktn.H_geschaetzteKosten;
    64. }
    65. }
    66. }
    67. }
    68. }
    70. List<Knoten> _path = new List<Knoten>();
    71. int indexOfZiel = zielKnoten.getIndexBasedOnPosition(closedList);
    72. Knoten tempKnoten = closedList[indexOfZiel];
    73. while (tempKnoten.vorgaenger != null)
    74. {
    75. _path.Add(tempKnoten);
    76. tempKnoten = tempKnoten.vorgaenger;
    77. }
    79. return _path;
    80. }

    Extensions

    C#-Quellcode

    1. static class MyExtensions
    2. {
    3. public static Knoten getLowestF(this List<Knoten> list)
    4. {
    5. Knoten kMitMinFKosten = list[0];
    6. for (int x = 0; x < list.Count - 1; x++){
    7. if (kMitMinFKosten.F_StartZumZielUeberHierKosten > list[x].F_StartZumZielUeberHierKosten){
    8. kMitMinFKosten = list[x];
    9. }
    10. }
    11. return kMitMinFKosten;
    12. }
    14. public static void removeWithPosition(this List<Knoten> list, Vector2 position)
    15. {
    16. for (int x = 0; x < list.Count - 1; x++)
    17. {
    18. if (list[x].position == position)
    19. {
    20. list.RemoveAt(x);
    21. }
    22. }
    23. }
    24. }


    Artentus
    @Artentus: Seit gestern ist doch noch ein andere "getDirectionalCost" hinzu gekommen, deswegen hab ich es wieder zur Funktion gemacht.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Eistee“ ()

    Also ich hätte das ja anders realisiert. Ein Knoten (warum eigentlich Deutsch?) sollte seine Nachbarn speichern, zusammen mit der Distanz zu ihnen. Das macht zwar den Speicheraufwand größer, erleichtert dir aber den Rest ungemein und verringert die benötigte Rechenleistung.

    Ich habe es nicht getestet, allerdings vermute ich in den Extensions einen Fehler:

    VB.NET-Quellcode

    1. For x As Integer = 0 To list.Count - 2

    Ich schätze dir geht ein Knoten durch die Lappen, vllt klappt es so besser

    VB.NET-Quellcode

    1. For x As Integer = 1 To list.Count - 1


    Edit: In C# wäre mir das nicht aufgefallen xDDD

    Ne, das kommt nicht vom Converter:

    Quellcode

    1. for (int x = 0; x < list.Count - 1; x++)

    ist gleichbedeutend mit

    VB.NET-Quellcode

    1. For x As Integer = 0 To list.Count - 2


    Und damit prüfst du das letzte Element in der Auflistung nie, dafür aber das Erste doppelt.

    @FreakJNS: Das erste wird doch nicht doppelt getestet?

    @Eistee: Ich nehme an, dass der Fehler war, dass du

    VB.NET-Quellcode

    1. list.Count - 1
    als

    C#-Quellcode

    1. list.Count - 1
    übernommen hast... Durch Converten ist dann halt -2 rausgekommen ^^

    Quellcode

    1. public static Knoten getLowestF(this List<Knoten> list)
    2. {
    3. Knoten kMitMinFKosten = list[0];
    4. for (int x = 0; x < list.Count - 1; x++){
    5. if (kMitMinFKosten.F_StartZumZielUeberHierKosten > list[x].F_StartZumZielUeberHierKosten){
    6. kMitMinFKosten = list[x];
    7. }
    8. }
    9. return kMitMinFKosten;
    10. }


    In Zeile 3 wird kMitMinFKosten auf das erste Element gesetzt. In der Schleife wird es im ersten Durchlauf dann mit sich selbst gegengeprüft, weil die Schleife eben von 0 anfängt. In VB sind Arrays 0-Basiert und da die For-Schleife bis zum letzten Index durchläuft muss man .Count-1 schreiben. In C# reicht ein x < .Count - da muss man nichts abziehen, weil da "kleiner als" steht und nicht "kleinergleich".