A*-Algorithmus

  • VB.NET

Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von buettner123.

    Ja es geht. Und ganz zufällig gibt es eine Klasse namens "List". Also einfach "Openlist" und "Closedlist" als Typ "list" deklarieren und die Knoten des Suchbaums hinzufügen. Wie A* funktioniert steht ja in Wikipedia.

    Andere Methode wäre eine Liste, wobei jeder Eintrag mit einem Tag gekennzeichnet wird, ob der Eintrag "closed" oder noch "opened" ist.

    Danke :) Ok dann stehe ich jetzt vor dem nächsten Problem... wie füge ich die Knotenpunkte in die liste? (... ich hätte auch ein bild, wo man alle "knoten" sehen kann)
    nur halt wie müssen die dann in die liste....?

    die funktion ansich bekomme ich dann anhand des wiki artikels zusammengebaut... nur das einordnen in die Liste nicht, da ich keine Ahnung habe, wie das gehen soll...

    Das kommt darauf an wie du die Knoten definierst. Treffenderweise nimmt man dafür eine Klasse oder Structure.
    Jeder Knoten besitzt also ein paar Informationen, wie bei A* die Priorität, also der heuristische Schätzwert.

    Damit sollte der Knoten etwa wie folgend aussehen:

    VB.NET-Quellcode

    1. '
    2. Public Class Knoten
    3. Public Priorität As Integer ' heuristischer Schätzwert
    4. Public Ebene As Integer ' "Generationsindex", also auf welcher Ebene der Knoten sich im Baum befindet
    5. Public Vater_Index As Integer ' Ganz wichtig bei Suchalgorithmen. Mit diesem Index lässt sich später der Lösungsweg zurückverfolgen
    7. ' ... Hier die Variable(n) für deine Suche (zB Position auf einem Spielfeld)
    8. End Class


    So jetzt baust du dir ganz einfach die beiden Listen (closed und opened) auf und die dazu gehörenden Methoden, wie zum Beispiel:

    VB.NET-Quellcode

    1. '
    2. Private Closed_List As List(Of Knoten)
    3. Private Opened_List As List(Of Knoten)
    5. Public Sub Initialisiere_Knotenlisten()
    6. Closed_List = New List(Of Knoten)
    7. Opened_List = New List(Of Knoten)
    8. End Sub
    10. Public Sub Füge_Knoten_hinzu(ByVal _Knoten As Knoten)
    11. Opened_List.Add(_Knoten)
    12. End Sub
    14. Public Sub Expandiere_Knoten(ByVal Index As Integer)
    15. ' Hier die Kinder-Knoten des Knoten mit dem Index, also "Opened_List(Index)", erstellen
    16. ' siehe dafür A* von Wikipedia
    20. ' Am Ende ist der expandierte Knoten "closed", er wird also aus opened_list gestrichen und der closed_list hinzugefügt
    21. ' Achtung! Wenn ein Item aus einer Liste "gelöscht" wird, werden die anderen Items wie im Stack aufgeschoben.
    22. ' Die Indizes werden also auch verändert, was im Konflikt mit "Vater_Index" steht
    23. ' Daher belasse ich es mal bei "Nothing"
    24. Closed_List.Add(Opened_List(Index))
    25. Opened_List(Index) = Nothing
    26. End Sub
    28. ' usw...




    Generell favorisiere ich das ganz mit einer Liste zu handhaben. Also Closed und Opened Knoten in einer Liste.
    Dazu erhält die Knoten-Klasse einen Booleanwert (zB "Expandiert" oder "Closed"), der angibt ob ein Knoten closed ist oder eben nicht.

    Viel Spaß! :)


    PS:
    Ein wenig mehr Informationen über dein Vorhaben schaden nie. :whistling:

    Wow, danke schonmal für deine Mühe, ich hoffe sie war nciht vergebens und mein vorhaben lässt sich damit wirklich umsetzen...Also
    ich habe ein Progrämmchen geschrieben, was ein Spiel spielt, und dafür will ich nun sozusagen ein Navigationssystem einbauen... d.h. man sagt ihm auf welcher Map es arbeiten soll, und es fliegt dorthin. (dafür will ich mit dem A* Algorithmus den kürzesten Weg dahin berechnen)

    www3.pic-upload.de/04.04.10/ujqxttn4krvs.png

    das ist das Kartensystem, zudem ich meine Listen erzeugen will, und nun soll das programm z.b. von der Map 3-1 (rechts unten) den schnellsten Weg nach 2-4 (rechts mitte) finden (mir also den weg über die einzelnen Jumpportale ausgeben), der schnellste weg wäre hier über 3-2 nach links oben auf 3-4 dann auf 3-3 und nach 2-4.

    Ich hoffe das macht mein Vorhaben etwas klarer...

    So... Hab den Thread irgendwie vergessen. Ich war im Urlaub. Sorry^^

    Ich muss sagen, ich versteh dein Vorhaben nicht wirklich.
    In deinem Beispiel ist der schnellste Weg doch auch gar nicht:
    3-2 nach links oben auf 3-4 dann auf 3-3 und nach 2-4.
    sondern

    3-2 => 3-3 => 2-4.
    Könntest du das vielleicht nochmal genauer erklären? :)

    die grauen striche stehen nicht für die entfehrnung... nur die maps ansich gelten...
    aber ohje ja du hast recht ^^ dann entschuldige ich mich für diesen fehler ;) und jetzt weist du wofür ich diesen algorythmus auch noch brauch (selber bin ich auch nicht auf den schnellsten wegen unterwegs ^^)

    wäre es möglich das mit dem A* ausrechnen zu lassen?

    Hier gibt es also letztendlich nur ein Straßennetz, jedoch kann meiner Meinung nach kein wirklicher Schätzwert errechnet werden (weil keine Entfernungen, zB Luftlinie gegeben sind).

    Es sollte also auch statt der A*-Suche auch eine ganz simple Dijkstra-Suche reichen. Die A*-Suche ist nämlich eine "Mischung" aus Dijkstra-Suche und Besten-Suche.
    Diese Dijkstra-Suche beachtet NUR den bereits zurückgelegten Weg. Das heißt, sie findet in JEDEM Fall den kürzesten Weg (was A* nicht von sich behaupten kann).

    In diesem Fall ist der Weg zwischen den Maps immer gleich lang (korrigieren wenn ich falsch liege ^^) , also zum Beispiel 1. Daher bilden die Kosten ganz einfach die Anzahl der Vorgänger, also die Ebene.

    Der Lösungsansatz wäre also:
    Es muss eine Liste erstellt werden in die alle nötigen Informationen des Kartensystems müssen.
    Dazu zählt:
    • Welche Maps gibt es und wie ist ihr "Name" (zB. "3-1")?
    • Mit welchen Maps sind die jeweiligen Maps verbunden?

    Dazu sollte eine Klasse aufgebaut werden, zB so:

    VB.NET-Quellcode

    1. Public Class Map
    2. Public Name As String
    3. Public Connected_Names() As String
    5. Public Sub New(ByVal _Name As String, ByVal ParamArray _Connected_Names() As String)
    6. Name = _Name : Connected_Names = _Connected_Names
    7. End Sub
    8. End Class


    Jetzt muss das Kartensystem als Liste gefüllt werden. Das muss natürlich hier von Hand gemacht werden.
    Da ich gerade Langweile habe, hab ich das mal gemacht. Am besten guckst du dir es nochmal durch:

    VB.NET-Quellcode

    1. Private MapSystem As New List(Of Map)
    2. Public Sub Initialise_MapSystem()
    3. MapSystem.AddRange(New Map() _
    4. {New Map("1-1", "1-2"), _
    5. New Map("1-2", "1-1", "1-3", "1-4"), _
    6. New Map("1-3", "1-2", "1-4", "2-3"), _
    7. New Map("1-4", "1-2", "1-3", "4-1", "3-4"), _
    8. New Map("2-3", "1-3", "2-2", "2-4"), _
    9. New Map("4-1", "1-4", "4-2", "4-3"), _
    10. New Map("3-4", "1-4", "4-3", "3-3", "3-2"), _
    11. New Map("2-2", "2-3", "2-4", "2-1"), _
    12. New Map("4-2", "4-1", "4-3", "2-4"), _
    13. New Map("4-3", "4-1", "4-2", "3-4"), _
    14. New Map("3-2", "3-4", "3-3", "3-1"), _
    15. New Map("2-1", "2-2"), _
    16. New Map("2-4", "2-2", "2-3", "3-3", "4-2"), _
    17. New Map("3-3", "2-4", "3-4", "3-2"), _
    18. New Map("3-1", "3-2")})
    19. End Sub



    Der Lösungsweg wird wie folgt berechnet:

    VB.NET-Quellcode

    1. Public Sub Solve(ByVal Start_Name As String, ByVal End_Name As String)
    2. Dim Search_Tree As New List(Of Node)
    3. Dim Is_Solved As Boolean = False
    5. ' Baue den Knotenbaum mit dem Startknoten auf
    6. ' Der Startknoten liegt auf Ebene 0 und besitzt keinen Vater-Knoten (daher "-1")
    7. Search_Tree.Add(New Node(MapSystem.Where(Function(m As MapItem) m.Name = Start_Name).First, 0, -1))
    10. Do
    11. ' Finde des Knoten mit geringsten Kosten
    12. Dim min_Kosten As Integer = Integer.MaxValue
    13. Dim Index_of_min_Kosten As Integer = -1
    15. For i As Integer = 0 To Search_Tree.Count - 1
    16. If Search_Tree(i).Expandiert = False AndAlso Search_Tree(i).Get_Kosten < min_Kosten Then
    17. min_Kosten = Search_Tree(i).Get_Kosten
    18. Index_of_min_Kosten = i
    19. End If
    20. Next
    22. ' Expandieren dieses Knotens
    23. Search_Tree(Index_of_min_Kosten).Expandiert = True
    24. ' Für jede verbundene Map wir ein Kind-Knoten aufgebaut
    25. For Each name As String In Search_Tree(Index_of_min_Kosten).Map.Connected_Names
    26. Dim temp_Node As New Node(MapSystem.Where(Function(m As MapItem) m.Name = name).First, Search_Tree(Index_of_min_Kosten).Ebene + 1, Index_of_min_Kosten)
    28. ' Achtung! In einem Knotenbaum darf niemals ein Knoten mehrmals vorkommen
    29. Dim Is_Valid As Boolean = True
    30. For Each n As Node In Search_Tree
    31. If n.Map.Name = temp_Node.Map.Name Then
    32. Is_Valid = False
    33. End If
    34. Next
    35. If Is_Valid Then
    36. Search_Tree.Add(temp_Node)
    37. End If
    39. ' Prüfen ob der Ziel-Knoten erreicht wurde
    40. If Search_Tree.Last.Map.Name = End_Name Then
    41. Is_Solved = True
    42. Exit For
    43. End If
    44. Next
    45. Loop Until Is_Solved
    47. ' Der Weg wurde gefunden. Er muss nur noch bis zum Startknoten zurückverfolgt werden. Der letzte Knoten ist der Zielknoten.
    48. Dim Lösungsweg As New List(Of String)
    49. Dim temp_Index As Integer = Search_Tree.Count - 1
    50. Do
    51. Lösungsweg.Insert(0, Search_Tree(temp_Index).Map.Name)
    52. temp_Index = Search_Tree(temp_Index).Vater_Index
    53. Loop Until temp_Index = -1
    55. ListBox1.Items.Clear()
    56. ListBox1.Items.AddRange(Lösungsweg.ToArray)
    57. End Sub


    Der Lösungsweg wird hier in Schritten in die Listbox1 geschrieben, wenn du Start und Ziel angibtst. Also zum Beispiel "3-1" und "2-4".

    Ohmann ich hab echt zu viel Zeit. :rolleyes:


    Hier sogar noch das Projekt. (Es hat mich gerade auch sehr interessiert) :D
    Dateien

    • Map-Wegsuche.rar

      (63,69 kB, 124 mal heruntergeladen, zuletzt: )

    oO wow wow wow oO
    danke :) ich schaus mir direckt mal an... muss es dann nur noch so umbauen, das er mir sagt, welche jumpgates ich da benutzen muss... (die kleinen Jx anzeigen) denn diese hab ich von der "aktuellen map" in einer list of dictionary... d.h. ich hab davon die koordinaten...
    Ich müsste dann die verknüpfungen herstellen, welches gate zu welcher map führt...

    und dann muss das programm nur dorthinfliegen und jumpen usw (diese funktionen habe ich schon...)

    naja jetzt muss ich deinen code erstmal verstehn und mich da einarbeiten :) aber echt: DANKE :)

    EDIT:
    hab mich mal damit beschäftigt, und noch das andere kartensystem was es gibt hinzugefügt... den algorithmus ansich hab ich noch nicht so ganz verstanden, aber das wird noch ;)

    --> hab mir jetzt mal auf dem papier ein kleines system entwickelt, mitdem ich sehe welche gates ich anfliegen muss... bin gerade dabei das alles in mein Programm einzubauen :) dauert noch, aber wenn das fertig ist, werd ich ein video uploaden, das die funktion davon demonstriert... (link kommt dann hier rein)

    ps: dein code ist schon eingebaut und funktioniert wunderbar :) da muss ich jetzt nur noch den rest drumrumbauen ^^


    EDIT#2:
    So habe nun alles so gebaut wie ich mir überlegt hatte, und es klappt wunderbar ;) noch ein paar design sachen, dass alles in das programmbild passt und dann werde ich das video machen....
    Danke nochmal :)

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „buettner123“ ()

Facebook
Telefonspende