PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

Frage für Profis

https://www.purebasic.fr/german/viewtopic.php?t=4257

Seite 1 von 2

Frage für Profis

Verfasst: 04.08.2005 18:54
von unix
Wie sucht eine Einheit in einen Strategiespiel den kürzesten Weg?
Dazwischen ist z.B. ein Fluss oder Berg.

Wie lässt sich so etwas Programmieren?

Verfasst: 04.08.2005 19:15
von Sylvia
Ist das nicht ein hochinteressantes Thema, um sich selbst damit zu beschäftigen ?

Mir hat es Spass gemacht beim (vor-?)letzten Contest von Rob (der mit den
Raumschiffen) die Pfadfinder-Routine zu erstellen. Leider konnte ich aus Zeitgründen
das gesamte Programm nicht mehr beenden. Meinen Code möchte ich dir nicht zur
Verfügung stellen, da ich evtl. noch eine kommerzielle Verwertung dafür habe.

Aber die anderen abgegebenen Wettbewerbsbeiträge könnten dir weiterhelfen. Die
müssen auch eine solche Routine enthalten.
Schau mal hier: http://www.mentaloverflow.de/purecontest/contest03.htm

Verfasst: 04.08.2005 19:19
von unix
Danke Sylvia.

Da es bei meinen Spiel eine unendlich viele Möglichkeiten geben wird (MapEditor) wird das mit learn warscheinlich nicht funcktioniern.
Aber gute Idee!

Verfasst: 04.08.2005 19:23
von Zaphod
der gebräuchlichste algorithmus dafür ist der sogenannte A* (a star) algorithmus. dazu sollte sich viel an tutorials und dokumentation finden lassen.

für nodetable basierende wegfindung würde mir sonst noch der algorithmus von djikstra einfallen.

Verfasst: 04.08.2005 19:31
von DarkDragon
Zaphod hat geschrieben:der gebräuchlichste algorithmus dafür ist der sogenannte A* (a star) algorithmus. dazu sollte sich viel an tutorials und dokumentation finden lassen.

für nodetable basierende wegfindung würde mir sonst noch der algorithmus von djikstra einfallen.
Wollte ich auch grad sagen. Allerdings ist der A* Algorithmus auch für Vectornodes gut zu gebrauchen.

Verfasst: 04.08.2005 19:34
von Deeem2031
Ich hab mal einen relativ alten Code rausgesucht, den ich einfach mal aus Spaß am proggen geschieben habe.

Code: Alles auswählen

Global mapwidth,mapheight
mapwidth = 40
mapheight = 30

Structure node
  x.l
  y.l
  last.l
  ber.l
EndStructure

Dim Map.b(mapwidth-1,mapheight-1)
Dim smap.l(mapwidth-1,mapheight-1) ;Nur für das Beispiel wichtig, kann auch weggelassen werden
NewList node.node()
NewList path.POINT()

Procedure D_Pathfinding4(*start.POINT,*target.POINT) ;gibt die Anzahl der Schritte zurück
  If CompareMemory(*start,*target,SizeOf(POINT)):ProcedureReturn 0:EndIf
  Dim smap.l(mapwidth-1,mapheight-1)
  ClearList(node())
  AddElement(node()):node()\x = *target\x:node()\y = *target\y
  smap(*target\x,*target\y) = 1
  
  Repeat
    noconnection = 1
    cnt = 0
    ForEach node()
      If node()\ber = 0
        cnt + 1
        noconnection = 0
        x = node()\x
        y = node()\y
        node_p = @node()
        node()\ber = 1
        If x = *start\x And y = *start\y:finish = 1:Break:EndIf
        If x+1 < mapwidth
          If smap(x+1,y) = 0
            If Map(x+1,y)
              smap(x+1,y) = 1
            Else
              AddElement(node())
              node()\x = x+1
              node()\y = y
              node()\last = node_p
              smap(x+1,y) = 1
            EndIf
          EndIf
        EndIf
        If x-1 >= 0
          If smap(x-1,y) = 0
            If Map(x-1,y)
              smap(x-1,y) = 1
            Else
              AddElement(node())
              node()\x = x-1
              node()\y = y
              node()\last = node_p
              smap(x-1,y) = 1
            EndIf
          EndIf
        EndIf
        If y+1 < mapheight
          If smap(x,y+1) = 0
            If Map(x,y+1)
              smap(x,y+1) = 1
            Else
              AddElement(node())
              node()\x = x
              node()\y = y+1
              node()\last = node_p
              smap(x,y+1) = 1
            EndIf
          EndIf
        EndIf
        If y-1 >= 0
          If smap(x,y-1) = 0
            If Map(x,y-1)
              smap(x,y-1) = 1
            Else
              AddElement(node())
              node()\x = x
              node()\y = y-1
              node()\last = node_p
              smap(x,y-1) = 1
            EndIf
          EndIf
        EndIf
      EndIf
    Next
    Debug cnt
  Until finish Or noconnection
  If finish
    ClearList(path())
    Length = 0
    Repeat
      Length + 1
      AddElement(path())
      path()\x = node()\x
      path()\y = node()\y
      ChangeCurrentElement(node(),node()\last)
    Until node()\last = 0
    ProcedureReturn Length
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

Procedure D_Pathfinding8(*start.POINT,*target.POINT) ;gibt die Anzahl der Schritte zurück
  If CompareMemory(*start,*target,SizeOf(POINT)):ProcedureReturn 0:EndIf
  Dim smap.l(mapwidth-1,mapheight-1)
  ClearList(node())
  AddElement(node()):node()\x = *target\x:node()\y = *target\y
  smap(*target\x,*target\y) = 1
  
  Repeat
    noconnection = 1
    cnt = 0
    ForEach node()
      If node()\ber = 0
        cnt + 1
        noconnection = 0
        x = node()\x
        y = node()\y
        node_p = @node()
        node()\ber = 1
        If x = *start\x And y = *start\y:finish = 1:Break:EndIf
        If x+1 < mapwidth
          If smap(x+1,y) = 0
            If Map(x+1,y)
              smap(x+1,y) = 1
            Else
              AddElement(node())
              node()\x = x+1
              node()\y = y
              node()\last = node_p
              smap(x+1,y) = 1
            EndIf
          EndIf
        EndIf
        If x-1 >= 0
          If smap(x-1,y) = 0
            If Map(x-1,y)
              smap(x-1,y) = 1
            Else
              AddElement(node())
              node()\x = x-1
              node()\y = y
              node()\last = node_p
              smap(x-1,y) = 1
            EndIf
          EndIf
        EndIf
        If y+1 < mapheight
          If smap(x,y+1) = 0
            If Map(x,y+1)
              smap(x,y+1) = 1
            Else
              AddElement(node())
              node()\x = x
              node()\y = y+1
              node()\last = node_p
              smap(x,y+1) = 1
            EndIf
          EndIf
          If x-1 >= 0
            If smap(x-1,y+1) = 0
              If Map(x-1,y+1)
                smap(x-1,y+1) = 1
              Else
                AddElement(node())
                node()\x = x-1
                node()\y = y+1
                node()\last = node_p
                smap(x-1,y+1) = 1
              EndIf
            EndIf
          EndIf
          If x+1 < mapwidth
            If smap(x+1,y+1) = 0
              If Map(x+1,y+1)
                smap(x+1,y+1) = 1
              Else
                AddElement(node())
                node()\x = x+1
                node()\y = y+1
                node()\last = node_p
                smap(x+1,y+1) = 1
              EndIf
            EndIf
          EndIf 
        EndIf
        If y-1 >= 0
          If smap(x,y-1) = 0
            If Map(x,y-1)
              smap(x,y-1) = 1
            Else
              AddElement(node())
              node()\x = x
              node()\y = y-1
              node()\last = node_p
              smap(x,y-1) = 1
            EndIf
          EndIf
          If x-1 >= 0
            If smap(x-1,y-1) = 0
              If Map(x-1,y-1)
                smap(x-1,y-1) = 1
              Else
                AddElement(node())
                node()\x = x-1
                node()\y = y-1
                node()\last = node_p
                smap(x-1,y-1) = 1
              EndIf
            EndIf
          EndIf
          If x+1 < mapwidth
            If smap(x+1,y-1) = 0
              If Map(x+1,y-1)
                smap(x+1,y-1) = 1
              Else
                AddElement(node())
                node()\x = x+1
                node()\y = y-1
                node()\last = node_p
                smap(x+1,y-1) = 1
              EndIf
            EndIf
          EndIf 
        EndIf
      EndIf
    Next
    Debug cnt
  Until finish Or noconnection
  If finish
    ClearList(path())
    Length = 0
    Repeat
      Length + 1
      AddElement(path())
      path()\x = node()\x
      path()\y = node()\y
      ChangeCurrentElement(node(),node()\last)
    Until node()\last = 0
    ProcedureReturn Length
  Else
    ProcedureReturn 0
  EndIf
EndProcedure


Restore Map
For y = 1 To mapheight
  For x = 1 To mapwidth
    ;Read Map(x-1,y-1)
    Map(x-1,y-1) = Random(1)
  Next
Next

_GT_DevCaps.TIMECAPS 
SetPriorityClass_(GetCurrentProcess_(),#HIGH_PRIORITY_CLASS) 
timeGetDevCaps_(_GT_DevCaps,SizeOf(TIMECAPS)) 
timeBeginPeriod_(_GT_DevCaps\wPeriodMin) 

InitSprite()
OpenWindowedScreen(OpenWindow(0,0,0,mapwidth*20,mapheight*20+20,#PB_Window_ScreenCentered|#PB_Window_SystemMenu,"Pathfinding"),0,0,mapwidth*20,mapheight*20,0,0,0)
CreateGadgetList(WindowID())
ButtonGadget(0,0,mapheight*20,mapwidth*10,20,"DRÜCKEN ;) (4Wege)")
ButtonGadget(1,mapwidth*10,mapheight*20,mapwidth*10,20,"DRÜCKEN ;) (8Wege)")
me.POINT
me\x = Random(mapwidth-1);2
me\y = Random(mapheight-1);2
Map(me\x,me\y) = 0
enemy.POINT
enemy\x = Random(mapwidth-1);37
enemy\y = Random(mapheight-1);28
Map(enemy\x,enemy\y) = 0
Repeat
  Select WindowEvent()
    Case #PB_Event_Gadget
      Select EventGadgetID()
        Case 0
          me\x = Random(mapwidth-1);2
          me\y = Random(mapheight-1);2
          Map(me\x,me\y) = 0
          enemy\x = Random(mapwidth-1);37
          enemy\y = Random(mapheight-1);28
          Map(enemy\x,enemy\y) = 0
          Repeat
            For y = 1 To mapheight
              For x = 1 To mapwidth
                ;Read Map(x-1,y-1)
                Map(x-1,y-1) = Random(4)&1
              Next
            Next
            StartTime = timegettime_()
            r = D_Pathfinding4(@me,@enemy)
            SetWindowTitle(0,"Pathfinding4 ("+Str(timegettime_()-StartTime)+" ms)")
          Until r
        Case 1
          me\x = Random(mapwidth-1);2
          me\y = Random(mapheight-1);2
          Map(me\x,me\y) = 0
          enemy\x = Random(mapwidth-1);37
          enemy\y = Random(mapheight-1);28
          Map(enemy\x,enemy\y) = 0
          Repeat
            For y = 1 To mapheight
              For x = 1 To mapwidth
                ;Read Map(x-1,y-1)
                Map(x-1,y-1) = Random(4)&1
              Next
            Next
            StartTime = timegettime_()
            r = D_Pathfinding8(@me,@enemy)
            SetWindowTitle(0,"Pathfinding8 ("+Str(timegettime_()-StartTime)+" ms)")
          Until r
      EndSelect
    Case #PB_Event_CloseWindow
      quit = 1
    Case 0
      Delay(100)
  EndSelect
  StartDrawing(ScreenOutput())
  For x = 0 To mapwidth-1
    For y = 0 To mapheight-1
      Box(x*20,y*20,20,20,Map(x,y)*255+(smap(x,y)*155)<<8)
    Next
  Next
  ForEach path()
    Box(path()\x*20,path()\y*20,20,20,255<<8)
  Next
  Box(me\x*20,me\y*20,20,20,255<<16)
  Box(enemy\x*20,enemy\y*20,20,20,255<<16)
  StopDrawing()
  FlipBuffers()
Until quit = 1

timeEndPeriod_(_GT_DevCaps\wPeriodMin) 

DataSection
Map:
Data.b 1,1,1,1,1,1,1,1,1,1
Data.b 1,0,1,1,0,0,1,0,0,1
Data.b 1,0,0,0,0,0,1,0,0,1
Data.b 1,0,0,0,1,0,1,0,0,1
Data.b 1,0,0,0,1,0,1,1,0,1
Data.b 1,0,0,0,1,0,0,1,0,1
Data.b 1,0,0,0,1,0,0,0,0,1
Data.b 1,0,0,0,1,0,1,0,0,1
Data.b 1,0,0,0,1,0,0,0,0,1
Data.b 1,1,1,1,1,1,1,1,1,1
EndDataSection
Kurze Erklärung: Wenn man auf den 4 Wege-Knopf drückt wird immer eine Verbindung nach rechts,oben,links und unten gesucht, bei 8 Wege auch diagonal. Im Titel steht auch wie lange er für die Wegsuche gebraucht hat. Das grüne ist der Weg (hättet ihr nicht gedacht oder? ^^), das hellgrüne Feld darum ist das Gebiet, welches er abgesucht hat und der rest ist entweder schwarz (frei) oder rot (nich frei, wand oder so..)

Das Programm erstellt übrigens so lange eine neue Karte bis ein Weg gefunden werden konnte. Wird kein Weg gefunden, oder der Startpunkt ist gleich Endpunkt geben die Proceduren 0 zurück, andernfalls die Anzahl der Schritte zwischen den Punkten.

Hoffe dir hilft der Code, konnte ihn selber noch nicht gebrauchen.

Verfasst: 04.08.2005 21:21
von remi_meier
Hab grad kürzlich einen Dijkstra-Code veröffentlicht :-)
http://forums.purebasic.com/german/view ... t=dijkstra
A* ist ein wenig heuristisch, dafür aber schneller!

Verfasst: 04.08.2005 22:34
von unix
Ok das hilft mit anscheinend

aber kannst du mir sagen wie ich die wegpunkte herausbekomme und was für zahlen Start und Ziel ist?

Also kurz diesen Code musst du mir genau erklären

--> er ist schnell das ist guuut :-)

Verfasst: 04.08.2005 23:36
von remi_meier
Ich hoffe, du meinst mich :)
Also:
StartK und StopK ist der Start-Knoten und der Stop-Knoten, also von welchem
Knoten das Ding startet und bei welchem es ankommen soll. Knoten sind
hier z.B. Kacheln/Tiles/Wegpunkte (Fluss/Berg). Die Punkte werden in form
von Distanzen zwischen den Punkten gespeichert, danach wird die Reihen-
folge der Punkte zurückgegeben, welche das Ding ablaufen muss.

Wenn das Spiel gekachelt ist, sind oft alle Distanzen zwischen den einzelnen
Kacheln = 1, solche Kacheln, die nicht miteinander verbunden sind, bekommen
ein #M, was hier für unendliche Distanz steht. Ausserdem kann man dann
den Code noch kürzen! Verständnis wäre schon empfehlenswert!

Code: Alles auswählen

DataSection 
distanzen: 
Data.l 0, 2, 4, #M 
Data.l 2, 0, 1, 7 
Data.l 4, 1, 0, 3 
Data.l #M,7, 3, 0 
EndDataSection
Das ist das Array, wo die Distanzen zwischen den Knoten eingetragen wurden,
also von Knoten 0 zu Knoten 2 ist D = 4, von 3 nach 2 D = 3 usw., du musst
also nur die Distanzen zwischen den Knoten kennen!

hoffe das reicht und hoffe das es dir hilft!

greetz
Remi

Verfasst: 05.08.2005 17:18
von unix
Es tut mir leid das ich so dumm bin aber warum hat bei dir ein knoten nur eine Dimension?
Ist doch X UND Y oder?
Oder wie machst du das mit den Knotendifinieren?
Alle Zeiten sind UTC+02:00
Seite 1 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de