Wenn ich wieder Zeit habe werde ich versuchen dicemans _NoCornerCuts() zu implementieren.
Da ich noch am aktuellen Code arbeite will ich zumindest mal meinen (ersten) unoptimierten Code zeigen.
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