Frage für Profis

Anfängerfragen zum Programmieren mit PureBasic.
Antworten
Benutzeravatar
unix
Beiträge: 361
Registriert: 15.02.2005 19:25
Wohnort: Zwischen Coburg und Bamberg :-)
Kontaktdaten:
Kontaktdaten von unix

Frage für Profis

Beitrag 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?
Hier steht normalerweise die Putzfrau drin,
die hat aber Urlaub.
MfG : Unix
Nach oben
Benutzeravatar
Sylvia
verheiratet<br>1. PureGolf-Gewinner
Beiträge: 487
Registriert: 29.08.2004 09:42
Wohnort: Old Europe

Beitrag 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
Basic Pur = PureBasic
Nach oben
Benutzeravatar
unix
Beiträge: 361
Registriert: 15.02.2005 19:25
Wohnort: Zwischen Coburg und Bamberg :-)
Kontaktdaten:
Kontaktdaten von unix

Beitrag 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!
Hier steht normalerweise die Putzfrau drin,
die hat aber Urlaub.
MfG : Unix
Nach oben
Benutzeravatar
Zaphod
Beiträge: 2875
Registriert: 29.08.2004 00:40

Beitrag 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.
Nach oben
DarkDragon
Beiträge: 6291
Registriert: 29.08.2004 08:37
Computerausstattung: Hoffentlich bald keine mehr
Kontaktdaten:
Kontaktdaten von DarkDragon

Beitrag 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.
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Nach oben
Benutzeravatar
Deeem2031
Beiträge: 1232
Registriert: 29.08.2004 00:16
Wohnort: Vorm Computer
Kontaktdaten:
Kontaktdaten von Deeem2031

Beitrag 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.
Bild
[url=irc://irc.freenode.org/##purebasic.de]irc://irc.freenode.org/##purebasic.de[/url]
Nach oben
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag 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!
Nach oben
Benutzeravatar
unix
Beiträge: 361
Registriert: 15.02.2005 19:25
Wohnort: Zwischen Coburg und Bamberg :-)
Kontaktdaten:
Kontaktdaten von unix

Beitrag 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 :-)
Hier steht normalerweise die Putzfrau drin,
die hat aber Urlaub.
MfG : Unix
Nach oben
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag 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
Nach oben
Benutzeravatar
unix
Beiträge: 361
Registriert: 15.02.2005 19:25
Wohnort: Zwischen Coburg und Bamberg :-)
Kontaktdaten:
Kontaktdaten von unix

Beitrag 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?
Hier steht normalerweise die Putzfrau drin,
die hat aber Urlaub.
MfG : Unix
Nach oben
Antworten

Zurück zu „Anfänger“