Isometrische 2D Spiele-Engine

Spiele, Demos, Grafikzeug und anderes unterhaltendes.
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Re: Isometrische 2D Spiele-Engine

Beitrag von diceman »

Hier übrigens der originale Artikel mit der gesamten Theorie hinter der A*-Pfadsuche, welcher mich umgehend inspiriert hat, dieses programmiertechnisch (damals noch für BlitzBasic) umzusetzen:
https://www.raywenderlich.com/3016-intr ... athfinding
Der ganze Modus Operandi wird hier sehr gut und zugänglich erklärt.
Mijikai hat geschrieben:Ich vermute das der Aufruf des Macros nach dem Check der Closed List stattfindet?
Das Macro checkt die Felder um das momentane Feld und entscheidet ob es berücksichtigt wird?
This.
Wenn die Routine die umliegenden Felder checkt, wird jedesmal ein "Bonus-Check" ausgeführt, ob beim Betreten dieses Feldes die Ecke eines diagonal liegenden Blockes abgeschnitten würde.
Wenn dies der Fall ist, wird das Feld übersprungen und direkt zum nächsten übergegangen (tileOkay = 0).
Ich habe den jeweiligen Teil des Codes nur aus Gründen der Übersichtlichkeit als Macro ausgelagert, damit klar wird, daß es sich hier gänzlich um eine optionale Angelegenheit handelt. Default-mäßig wird "tileOkay" immer auf 1 gesetzt ... allerdings hat das Macro die Erlaubnis, "tileOkay" zu überschreiben, und so den Check für dieses Feld gänzlich zu verbieten.
Zuletzt geändert von diceman am 21.05.2019 21:07, insgesamt 2-mal geändert.
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Benutzeravatar
Mijikai
Beiträge: 754
Registriert: 25.09.2016 01:42

Re: Isometrische 2D Spiele-Engine

Beitrag von Mijikai »

diceman hat geschrieben:Hier ist übrigens der originale Artikel mit der gesamten Theorie hinter der A*-Pfadsuche, welcher hat mich umgehend inspiriert hat...
Gutes Tutorial,
so hab ich das auch umgesetzt - hab mich nach meinem ersten
kläglichen Versuch brav an die Vorgaben gehalten :)
diceman hat geschrieben:
Mijikai hat geschrieben:Ich vermute das der Aufruf des Macros nach dem Check der Closed List stattfindet?
Das Macro checkt die Felder um das momentane Feld und entscheidet ob es berücksichtigt wird?
This.
Wenn die Routine die umliegenden Felder checkt, wird jedesmal ein "Bonus-Check" ausgeführt, ob beim Betreten dieses Feldes die Ecke eines diagonal liegenden Blockes abgeschnitten würde.
Wenn ja, wird das Feld übersprungen und direkt zum nächsten übergegangen (tileOkay = 0).
:allright:
Dann versuch ich das mal bei mir mit einzubauen.
Benutzeravatar
Mijikai
Beiträge: 754
Registriert: 25.09.2016 01:42

Re: Isometrische 2D Spiele-Engine

Beitrag von Mijikai »

Hab gerade meinen Astar-Algorithmus optimiert :)
Wenn ich wieder Zeit habe werde ich versuchen dicemans _NoCornerCuts() zu implementieren. :coderselixir:

Da ich noch am aktuellen Code arbeite will ich zumindest mal meinen (ersten) unoptimierten Code zeigen.

Code:

Code: Alles auswählen

EnableExplicit

;ASTAR PATHFINDING
;Version: Alpha
;Author: Mijikai

Structure ASTAR_OFFSET_STRUCT
  x.i
  y.i
EndStructure

Structure ASTAR_MAP_STRUCT
  *buffer
  size.i
  width.i
  height.i
EndStructure

Structure ASTAR_NODE_STRUCT
  id.i
  *parent.ASTAR_NODE_STRUCT
  offset.ASTAR_OFFSET_STRUCT
  cost_g.i
  cost_h.i
  cost_f.i
EndStructure

Structure ASTAR_STRUCT
  *map.ASTAR_MAP_STRUCT
  start.ASTAR_OFFSET_STRUCT
  stop.ASTAR_OFFSET_STRUCT
  stop_id.i
  *node.ASTAR_NODE_STRUCT
  List open.ASTAR_NODE_STRUCT()
  List closed.ASTAR_NODE_STRUCT()
EndStructure

Global *dummy
Global *astar_map
Global astar_start.ASTAR_OFFSET_STRUCT
Global astar_stop.ASTAR_OFFSET_STRUCT
Global astar_offset.ASTAR_OFFSET_STRUCT

Procedure.i astarMapTest(*Map.ASTAR_MAP_STRUCT,*Offset.ASTAR_OFFSET_STRUCT)
  Protected *test.Byte 
  If *Offset\x > -1 And *Offset\x < *Map\width
    If *Offset\y > -1 And *Offset\y < *Map\height
      *test = *Map\buffer + *Offset\x + (*Offset\y * *Map\width)
      If *test\b = #Null
        ProcedureReturn *test
      EndIf 
    EndIf
  EndIf
  ProcedureReturn #Null
EndProcedure

Procedure.i astarMap(*Buffer,Width.i,Height.i)
  Protected *map.ASTAR_MAP_STRUCT
  *map = AllocateStructure(ASTAR_MAP_STRUCT)
  If *map
    *map\buffer = *Buffer
    *map\size = Width * Height
    *map\width = Width
    *map\height = Height
  EndIf
  ProcedureReturn *map
EndProcedure

Procedure.i astarMapFree(*Buffer)
  FreeStructure(*Buffer)  
EndProcedure

Procedure.i astarHeuristic(*Astar.ASTAR_STRUCT,*Offset.ASTAR_OFFSET_STRUCT)
  ProcedureReturn (Abs(*Offset\x - *Astar\stop\x) + Abs(*Offset\y - *Astar\stop\y)) * 10
EndProcedure

Procedure.i astarSteps(*Astar.ASTAR_STRUCT,*Offset.ASTAR_OFFSET_STRUCT)
  ProcedureReturn Abs(*Offset\x - *Astar\stop\x) + Abs(*Offset\y - *Astar\stop\y)
EndProcedure

Procedure.i astarNodeOpen(*Astar.ASTAR_STRUCT,*Node.ASTAR_NODE_STRUCT,X.i,Y.i,Cost.i,*Error.Integer)
  Protected node_id.i
  Protected node_cost_g.i
  Protected node_cost_h.i
  Protected node_cost_f.i
  Protected offset.ASTAR_OFFSET_STRUCT
  offset\x = *Node\offset\x + X
  offset\y = *Node\offset\y + Y
  node_id = astarMapTest(*Astar\map,@offset)
  If node_id
    ForEach *Astar\closed()
      If *Astar\closed()\id = node_id
        ProcedureReturn #Null
      EndIf 
    Next 
    node_cost_g = *Node\cost_g + Cost
    node_cost_h = astarHeuristic(*Astar,@offset)
    node_cost_f = node_cost_g + node_cost_h  
    ForEach *Astar\open()
      If *Astar\open()\id = node_id
        If node_cost_f < *Astar\open()\cost_f
          *Astar\open()\cost_g = node_cost_g
          *Astar\open()\cost_h = node_cost_h
          *Astar\open()\cost_f = node_cost_f
          *Astar\open()\parent = *Node
        EndIf
        ProcedureReturn #Null
      EndIf 
    Next
    If AddElement(*Astar\open())
      *Astar\open()\id = node_id
      *Astar\open()\offset\x = offset\x
      *Astar\open()\offset\y = offset\y
      *Astar\open()\parent = *Node
      *Astar\open()\cost_g = node_cost_g
      *Astar\open()\cost_h = node_cost_h
      *Astar\open()\cost_f = node_cost_f
      ProcedureReturn *Astar\open()
    Else
      *Error\i = #True
    EndIf
  EndIf
  ProcedureReturn #Null
EndProcedure

Procedure.i astarNodeEntry(*Astar.ASTAR_STRUCT,*Offset.ASTAR_OFFSET_STRUCT)
  If AddElement(*Astar\open())
    *Astar\open()\id = astarMapTest(*Astar\map,*Offset)
    *Astar\open()\offset\x = *Offset\x
    *Astar\open()\offset\y = *Offset\y
    *Astar\open()\cost_f = astarHeuristic(*Astar,*Offset)
    ProcedureReturn *Astar\open()
  Else
    ProcedureReturn #Null
  EndIf
EndProcedure

Procedure.i astarNodeClosed(*Astar.ASTAR_STRUCT,*Node.ASTAR_NODE_STRUCT)
  If AddElement(*Astar\closed())
    CopyMemory(*Node,*Astar\closed(),SizeOf(ASTAR_NODE_STRUCT))
    ChangeCurrentElement(*Astar\open(),*Node)
    DeleteElement(*Astar\open())
    ProcedureReturn *Astar\closed()
  EndIf 
  ProcedureReturn #Null
EndProcedure

Procedure.i astarCreatePath(*Map.ASTAR_MAP_STRUCT,*Start.ASTAR_OFFSET_STRUCT,*Stop.ASTAR_OFFSET_STRUCT,Diagonal.b = #False,Steps.i = #Null,Nodes.i = #Null)
  Protected *astar.ASTAR_STRUCT
  Protected *node.ASTAR_NODE_STRUCT
  Protected current.ASTAR_NODE_STRUCT
  Protected error.i
  Protected count.i
  Protected stop_id.i
  If Not (*Start\x = *Stop\x And *Start\y = *Stop\y)
    If Steps
      If astarSteps(*Map,*Start) > Steps
        ProcedureReturn #Null
      EndIf
    EndIf
    stop_id = astarMapTest(*Map,*Start)
    If astarMapTest(*Map,*Stop) And stop_id
      *astar = AllocateStructure(ASTAR_STRUCT)
      If *astar
        *astar\map = *Map
        *astar\stop\x = *Start\x
        *astar\stop\y = *Start\y
        *astar\start\x = *Stop\x
        *astar\start\y = *Stop\y
        *astar\stop_id = stop_id
        *node = astarNodeEntry(*astar,@*astar\start)
        If Diagonal
          Repeat
            *node = astarNodeClosed(*astar,*node)
            If *node
              If *node\id = *astar\stop_id
                *astar\node = *node\parent
                ProcedureReturn *astar  
              EndIf   
              astarNodeOpen(*astar,*node,-1,0,10,@error)
              astarNodeOpen(*astar,*node,-1,-1,14,@error)
              astarNodeOpen(*astar,*node,0,-1,10,@error)
              astarNodeOpen(*astar,*node,1,-1,14,@error)
              astarNodeOpen(*astar,*node,1,0,10,@error)
              astarNodeOpen(*astar,*node,1,1,14,@error)
              astarNodeOpen(*astar,*node,0,1,10,@error)
              astarNodeOpen(*astar,*node,-1,1,14,@error)
              count + 8
              If error
                Break 
              EndIf
              If Nodes
                If count > Nodes
                  Break
                EndIf
              EndIf
              SortStructuredList(*astar\open(),#PB_Sort_Ascending,OffsetOf(ASTAR_NODE_STRUCT\cost_f),#PB_Integer)
              *node = FirstElement(*astar\open())
            Else
              Break
            EndIf
          Until *node = #Null 
        Else
          Repeat
            *node = astarNodeClosed(*astar,*node)
            If *node
              If *node\id = *astar\stop_id
                *astar\node = *node\parent
                ProcedureReturn *astar  
              EndIf   
              astarNodeOpen(*astar,*node,-1,0,10,@error)
              astarNodeOpen(*astar,*node,0,-1,10,@error)
              astarNodeOpen(*astar,*node,1,0,10,@error)
              astarNodeOpen(*astar,*node,0,1,10,@error)
              count + 4
              If error
                Break 
              EndIf
              If Nodes
                If count > Nodes
                  Break
                EndIf
              EndIf
              SortStructuredList(*astar\open(),#PB_Sort_Ascending,OffsetOf(ASTAR_NODE_STRUCT\cost_f),#PB_Integer)
              *node = FirstElement(*astar\open())
            Else
              Break
            EndIf
          Until *node = #Null
        EndIf
      EndIf 
    EndIf
  EndIf
  FreeList(*astar\open())
  FreeList(*astar\closed())
  FreeStructure(*astar)
  ProcedureReturn #Null
EndProcedure

Procedure.i astarPath(*Astar.ASTAR_STRUCT,*Offset.ASTAR_OFFSET_STRUCT)
  If *Astar\node
    *Offset\x = *Astar\node\offset\x
    *Offset\y = *Astar\node\offset\y
    *Astar\node = *Astar\node\parent
    ProcedureReturn #True
  EndIf 
  ProcedureReturn #False
EndProcedure

Procedure.i astarPathFree(*Astar.ASTAR_STRUCT)
  FreeList(*Astar\open())
  FreeList(*Astar\closed())
  ProcedureReturn FreeStructure(*Astar)
EndProcedure

*astar_map = astarMap(?mask,4,4)

If *astar_map

  astar_start\x = 0
  astar_start\y = 0
  astar_stop\x = 3
  astar_stop\y = 3
  
  *dummy = astarCreatePath(*astar_map,@astar_start,@astar_stop)

  While astarPath(*dummy,@astar_offset)
    Debug "->"
    Debug astar_offset\x
    Debug astar_offset\y
  Wend   
    
  astarMapFree(*astar_map)
EndIf  
  
DataSection
  mask:
  !db 0,1,0,0 
  !db 0,1,0,0 
  !db 0,0,0,0
  !db 0,1,1,0
EndDataSection
Benutzeravatar
Mijikai
Beiträge: 754
Registriert: 25.09.2016 01:42

Re: Isometrische 2D Spiele-Engine

Beitrag von Mijikai »

Hab gerade _NoCornerCuts() implementiert :D

Bild

Hier ist meine Variante:

Code: Alles auswählen

Macro astarPathNoCorners(a,b,c,d);*path x y cost
  a\node_skip = #False
  If d = 14;are we going diagonal?
    If astarMaskTest(a\mask,a\current\offset\x + b,a\current\offset\y);is offset valid?
      a\node_skip = a\mask\table(a\current\offset\x + b,a\current\offset\y);check for corner
    EndIf
    If a\node_skip = #False;if node is still usable check the other corner
      If astarMaskTest(a\mask,a\current\offset\x,a\current\offset\y + c)
        a\node_skip = a\mask\table(a\current\offset\x,a\current\offset\y + c)
      EndIf
    EndIf
  EndIf 
EndMacro
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Re: Isometrische 2D Spiele-Engine

Beitrag von diceman »

Top! :allright: :allright: :allright:
Hast die _NoCornerCuts()-Abfrage auch noch etwas knapper hinbekommen als ich.
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Benutzeravatar
Mijikai
Beiträge: 754
Registriert: 25.09.2016 01:42

Re: Isometrische 2D Spiele-Engine

Beitrag von Mijikai »

Langsam get es weiter :)

Musste den grafischen Teil nochmal umkrempeln (optimiert + Bugs beseitigt).
Jetzt heißt es wieder testen.

Bild
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Re: Isometrische 2D Spiele-Engine

Beitrag von diceman »

Impressive, most impressive. 8)
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Antworten