Aktuelle Zeit: 20.08.2019 18:53

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 47 Beiträge ]  Gehe zu Seite Vorherige  1, 2, 3, 4, 5
Autor Nachricht
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 21.05.2019 20:50 
Offline
Benutzeravatar

Registriert: 06.07.2017 12:24
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.

_________________
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.


Zuletzt geändert von diceman am 21.05.2019 21:07, insgesamt 2-mal geändert.

Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 21.05.2019 21:06 
Offline
Benutzeravatar

Registriert: 25.09.2016 01:42
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.

_________________

Links:
PureBasic Discord
[ENGINE] 2D Engine Nautilus (Win)
[INCLUDE] GLFW 3.3 Library
[MODULE] Bass Library 2.4 (Win)
[LIBRARY] Hexi Binary2Hex (Win)



Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 25.05.2019 18:07 
Offline
Benutzeravatar

Registriert: 25.09.2016 01:42
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:
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

_________________

Links:
PureBasic Discord
[ENGINE] 2D Engine Nautilus (Win)
[INCLUDE] GLFW 3.3 Library
[MODULE] Bass Library 2.4 (Win)
[LIBRARY] Hexi Binary2Hex (Win)



Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 26.05.2019 13:00 
Offline
Benutzeravatar

Registriert: 25.09.2016 01:42
Hab gerade _NoCornerCuts() implementiert :D

Bild

Hier ist meine Variante:
Code:
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

_________________

Links:
PureBasic Discord
[ENGINE] 2D Engine Nautilus (Win)
[INCLUDE] GLFW 3.3 Library
[MODULE] Bass Library 2.4 (Win)
[LIBRARY] Hexi Binary2Hex (Win)



Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 26.05.2019 18:52 
Offline
Benutzeravatar

Registriert: 06.07.2017 12:24
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 08.06.2019 21:18 
Offline
Benutzeravatar

Registriert: 25.09.2016 01:42
Langsam get es weiter :)

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

Bild

_________________

Links:
PureBasic Discord
[ENGINE] 2D Engine Nautilus (Win)
[INCLUDE] GLFW 3.3 Library
[MODULE] Bass Library 2.4 (Win)
[LIBRARY] Hexi Binary2Hex (Win)



Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Isometrische 2D Spiele-Engine
BeitragVerfasst: 09.06.2019 06:19 
Offline
Benutzeravatar

Registriert: 06.07.2017 12:24
Impressive, most impressive. 8)

_________________
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 47 Beiträge ]  Gehe zu Seite Vorherige  1, 2, 3, 4, 5

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye