[burovalex]

Вот у меня сейчас терраин 64х64 и это так - средненький островок.
Использую я конечно 30-40% суши, НО я сейчас тестил этот пример Астар
и он выдал время обработки 4 мс - вот теперь прикинь что будет допустим 5 шуганутых зверюшек - и комп повесится

вот исходник со встроенным Астаром

Graphics3D 1024, 768, 32, 2
SetBuffer BackBuffer()


;	Create navigation grid
Local rows=64
Local cols=64
	
Dim Graph.NAV_Node(rows, cols)

For col=0 To cols-1
	For row=0 To rows-1
		Graph(col, row)=NAV_CreateNode(col*10, 0, row*10)
		
		;Swap pivot with cube to make node visible
		FreeEntity Graph(col, row)\Pivot
		Graph(col, row)\Pivot=CreateCube()
		PositionEntity Graph(col, row)\Pivot, col*10+Rnd(-2, 2), 0, row*10+Rnd(-2, 2)
	Next
Next

;	Connect nodes
For col=0 To cols-1
	For row=0 To rows-2
		NAV_Connect(Graph(col, row), Graph(col, row+1))
	Next
Next
	
For row=0 To rows-1
	For col=0 To cols-2
		NAV_Connect(Graph(col, row), Graph(col+1, row))
	Next
Next

;	Set camera
Camera=CreateCamera()
PositionEntity Camera, rows*10/2, rows*10, cols*10/2
TurnEntity Camera, 90, 0, 0

;	Pick source and destination nodes

Src.NAV_Node=Graph(0, 0)
Dst.NAV_Node=Graph(rows-1, cols-1)

EntityColor Src\Pivot, 0, 0, 255
EntityColor Dst\Pivot, 255, 0, 0

;	Get search time

time1=MilliSecs()
NAV_FindPath(Src, Dst)
time2=MilliSecs()

P.NAV_Node=Dst\Parent

While P<>Null
	EntityColor P\Pivot, 255, 0, 0
	P=P\Parent
Wend

While Not KeyHit(1)
	UpdateWorld
	RenderWorld
	Text 20, 20, "time: "+(time2-time1)
	Flip
Wend
End

;	NAVIGATION

Type NAV_Node
	Field Pivot
	Field Disabled
	Field Parent.NAV_Node			; for path building
	Field F#, G#, H#
	
	Field FirstLink.NAV_Link
	Field LastLink.NAV_Link
End Type

Type NAV_Link
	Field Node.NAV_Node
	Field Distance#
	
	Field PrevLink.NAV_Link
	Field NextLink.NAV_Link
End Type

Type NAV_OpenedNode
	Field Node.NAV_Node
End Type

Type NAV_ClosedNode
	Field Node.NAV_Node
End Type

Type NAV_Path
	Field StartNode.NAV_PathNode
End Type

Type NAV_PathNode
	Field Node.NAV_Node
	
	Field NextNode.NAV_PathNode
End Type

Function NAV_CreateNode.NAV_Node(X#, Y#, Z#)
	Local Node.NAV_Node=New NAV_Node
	Node\Pivot=CreatePivot()
	PositionEntity Node\Pivot, X, Y, Z
	Return Node
End Function

Function NAV_AddLink(NodeA.NAV_Node, NodeB.NAV_Node)
	Local Link.NAV_Link=New NAV_Link
	Link\Distance=EntityDistance(NodeA\Pivot, NodeB\Pivot)
	Link\Node=NodeB
	
	If NodeA\LastLink<>Null
		Link\PrevLink=NodeA\LastLink
		NodeA\LastLink\NextLink=Link
		NodeA\LastLink=Link
	Else
		NodeA\FirstLink=Link
		NodeA\LastLink=Link
	EndIf
End Function

Function NAV_Connect(NodeA.NAV_Node, NodeB.NAV_Node)
	NAV_AddLink(NodeA, NodeB)
	NAV_AddLink(NodeB, NodeA)
End Function

Function NAV_Heuristic#(Node.NAV_Node, DstNode.NAV_Node)
	Local X#=Abs(EntityX(DstNode\Pivot, True)-EntityX(Node\Pivot, True))
	Local Y#=Abs(EntityY(DstNode\Pivot, True)-EntityY(Node\Pivot, True))
	Local Z#=Abs(EntityZ(DstNode\Pivot, True)-EntityZ(Node\Pivot, True))
	
	Return (X+Y+Z)
End Function

Function NAV_AddToOpened(Node.NAV_Node)
	Local Opened.NAV_OpenedNode
	Local L.NAV_OpenedNode
	Local R.NAV_OpenedNode
	
	L=First NAV_OpenedNode
	
	If L<>Null
		If Node\F<=L\Node\F
			Opened=New NAV_OpenedNode
			Opened\Node=Node
			Insert Opened Before L
			Return
		EndIf
	Else
		Opened=New NAV_OpenedNode
		Opened\Node=Node
		Return
	EndIf
	
	Repeat
		R=After L
		If R=Null Then Exit
		
		If Node\F>=L\Node\F And Node\F<=R\Node\F
			Opened=New NAV_OpenedNode
			Opened\Node=Node
			Insert Opened Before R
			Return
		EndIf
		L=R
	Forever
	
	Opened=New NAV_OpenedNode
	Opened\Node=Node
	
End Function

Function NAV_AddToClosed(Node.NAV_Node)
	Local Closed.NAV_ClosedNode
	Local L.NAV_ClosedNode
	Local R.NAV_ClosedNode
	
	L=First NAV_ClosedNode
	
	If L<>Null
		If Node\F<=L\Node\F
			Closed=New NAV_ClosedNode
			Closed\Node=Node
			Insert Closed Before L
			Return
		EndIf
	Else
		Closed=New NAV_ClosedNode
		Closed\Node=Node
		Return
	EndIf
	
	Repeat
		R=After L
		If R=Null Then Exit
		
		If Node\F>=L\Node\F And Node\F<=R\Node\F
			Closed=New NAV_ClosedNode
			Closed\Node=Node
			Insert Closed Before R
			Return
		EndIf
		L=R
	Forever
	
	Closed=New NAV_ClosedNode
	Closed\Node=Node
End Function

Function NAV_SortNode(Opened.NAV_OpenedNode)

	Local Node.NAV_Node=Opened\Node
	Delete Opened
	
	Local L.NAV_OpenedNode
	Local R.NAV_OpenedNode
	
	L=First NAV_OpenedNode
	
	If L<>Null
		If Node\F<=L\Node\F
			Opened=New NAV_OpenedNode
			Opened\Node=Node
			Insert Opened Before L
			Return
		EndIf
	Else
		Opened=New NAV_OpenedNode
		Opened\Node=Node
		Return
	EndIf
		
	Repeat
		R=After L
		If R=Null Then Exit
			
		If Node\F>=L\Node\F And Node\F<=R\Node\F
			Opened=New NAV_OpenedNode
			Opened\Node=Node
			Insert Opened Before R
			Return
		EndIf
		L=R
	Forever
	
	Opened=New NAV_OpenedNode
	Opened\Node=Node
	
End Function

Function NAV_IsOpened.NAV_OpenedNode(Node.NAV_Node)
	For Opened.NAV_OpenedNode=Each NAV_OpenedNode
		If Opened\Node=Node Then Return Opened
		If Opened\Node\F>Node\F Then Return Null
	Next
End Function

Function NAV_IsClosed(Node.NAV_Node)
	For Closed.NAV_ClosedNode=Each NAV_ClosedNode
		If Closed\Node=Node Then Return True
		If Closed\Node\F>Node\F Then Return
	Next
End Function

Function NAV_FindPath.NAV_Path(SrcNode.NAV_Node, DstNode.NAV_Node)
	Local Node.NAV_Node
	Local Link.NAV_Link
	Local LinkNode.NAV_Node
	Local Opened.NAV_OpenedNode
	Local Closed.NAV_ClosedNode
	
	NAV_AddToOpened(SrcNode)
	
	Local Fail
	
	Repeat
		Opened=First NAV_OpenedNode
		
		If Opened=Null
			Fail=True
			Exit
		EndIf
		
		Node=Opened\Node
		Link=Node\FirstLink
		
		Delete Opened
		NAV_AddToClosed(Node)
		
		While Link<>Null
			
			LinkNode=Link\Node
			If LinkNode\Disabled=False
				If NAV_IsClosed(LinkNode)=False
					Local G=Node\G+Link\Distance
					
					If LinkNode=DstNode
						LinkNode\Parent=Node
						Exit
					EndIf
					
					Local OpenedLinkNode.NAV_OpenedNode=NAV_IsOpened(LinkNode)
					
					If OpenedLinkNode=Null
						LinkNode\Parent=Node
						LinkNode\G=G
						LinkNode\H=NAV_Heuristic(LinkNode, DstNode)
						LinkNode\F=LinkNode\G+LinkNode\H
						NAV_AddToOpened(LinkNode)
					Else
						If G<LinkNode\G
							LinkNode\Parent=Node
							LinkNode\G=G
							LinkNode\F=LinkNode\G+LinkNode\H
							NAV_SortNode(OpenedLinkNode)
						EndIf
					EndIf
				EndIf
			EndIf
			
			Link=Link\NextLink
		Wend
		
		If LinkNode=DstNode Then Exit
	Forever
	
	If Fail=False
		Local Parent.NAV_Node=DstNode
		
		If Parent=Null Then RuntimeError ""
		
		Local PathNode.NAV_PathNode=New NAV_PathNode
		PathNode\Node=Parent
		
		Local NextNode.NAV_PathNode=PathNode
		
		Repeat
			Parent=Parent\Parent
			PathNode=New NAV_PathNode
			PathNode\Node=Parent
			PathNode\NextNode=NextNode
			NextNode=PathNode
		Until Parent=SrcNode
		
		Local Path.NAV_Path=New NAV_Path
		Path\StartNode=PathNode
		
		Delete Each NAV_OpenedNode
		Delete Each NAV_ClosedNode
		
		Return Path								; Finally return path
	Else
		Delete Each NAV_OpenedNode				; ...Or null
		Delete Each NAV_ClosedNode
	EndIf
End Function

Function NAV_NearestNode.NAV_Node(Entity)
	Local MinDistance#=10^38
	Local NearestNode.NAV_Node
	
	For Node.NAV_Node=Each NAV_Node
		If Node\Disabled
			Local Distance#=EntityDistance(Entity, Node\Pivot)
			If Distance<MinDistance
				MinDistance=Distance
				NearestNode=Node
			EndIf
		EndIf
	Next
	
	Return NearestNode
End Function

Function NAV_DeletePath(Path.NAV_Path)
	Local PathNode.NAV_PathNode=Path\StartNode
	Local NextPathNode.NAV_PathNode
	
	While PathNode<>Null
		NextPathNode=PathNode\NextNode
		Delete PathNode
		PathNode=NextPathNode
	Wend
	
	Delete Path
End Function

Function NAV_Clear()
	For Node.NAV_Node=Each NAV_Node
		FreeEntity Node\Pivot
		Delete Node
	Next
	
	Delete Each NAV_Link
	Delete Each NAV_Path
	Delete Each NAV_PathNode
End Function