Dynamic QuadTree - GameCreators Forum

Author

Message

janbo

15

Years of Service

User Offline

Joined: 10th Nov 2008

Location: Germany

Posted: 5th Aug 2018 12:42 Edited at: 5th Aug 2018 12:44

Link

I'm trying me on octrees, They are very usefull for Minecraft type of games or culling algorithms and used for all sort of performance gaining because an Octree is a binary tree with eight nodes and therefore fast to traverse.
You can apply recursion on it, never the less I'm stuck on combining the nodes back together.
If you already have some code for octrees or quadtrees or if you know a good tutorial I'm happy to learn from it.
There is one requirement, I want dynamically add and remove nodes from the tree and I cant wrap my head around adding them back together and removing the unnecessary nodes right now.

Thanks in advance and any comment is welcome

SetWindowTitle( "Octree" )
SetWindowSize( 800, 600, 0 )

SetVirtualResolution( 800, 600 )
SetOrientationAllowed( 1, 1, 1, 1 )
SetSyncRate(0,0)
SetClearColor(0, 193, 255)
SetPrintSize(12)

CameraVectorID=CreateVector3()
PointerVectorID=CreateVector3()
PointVectorID=CreateVector3()

type OctTree_NodeData
	Depth as integer
	MinX# as float
	MinY# as float
	MinZ# as float
	MaxX# as float
	MaxY# as float
	MaxZ# as float
	Size# as float
	ObjectID as integer
	ParentID as integer
	ChildID as integer[7]
endtype

global OcTreeNode as OctTree_NodeData[]
global MaxDepth
MaxDepth=3

OcTree_CreateNode(-1,-1,-1,1,1,1,4,-1)

SphereObjectID=CreateObjectSphere(0.3,16,32)
SetObjectCollisionMode(SphereObjectID,0)
GridX#=0.125
GridY#=0.125
GridZ#=0.125
do
	print("Arrow keys to move the selection sphere and right mouse to remove/add a cube)
	Print(ScreenFPS())
	ControlCamera()

//~ PointerX#=Get3DVectorXFromScreen(GetPointerX(),GetPointerY())
	//~ PointerY#=Get3DVectorYFromScreen(GetPointerX(),GetPointerY())
	//~ PointerZ#=Get3DVectorZFromScreen(GetPointerX(),GetPointerY())
	//~ SetVector3(PointerVectorID,PointerX#,PointerY#,PointerZ#)
	//~ SetVector3(CameraVectorID,GetCameraX(1),GetCameraY(1),GetCameraZ(1))
	//~ GetVector3Multiply(PointerVectorID,9999)
	//~ ObjectRayCast(0,GetVector3X(CameraVectorID),GetVector3Y(CameraVectorID),GetVector3Z(CameraVectorID),GetVector3X(PointerVectorID),GetVector3Y(PointerVectorID),GetVector3Z(PointerVectorID))
	//~ ObjectID=GetObjectRayCastHitID(0)
	//~ RayHitX#=GetObjectRayCastX(0)
	//~ RayHitY#=GetObjectRayCastY(0)
	//~ RayHitZ#=GetObjectRayCastZ(0)

GridX#=GridX#-GetRawKeyPressed(37)*0.25+GetRawKeyPressed(39)*0.25
	GridY#=GridY#-GetRawKeyPressed(34)*0.25+GetRawKeyPressed(33)*0.25
	GridZ#=GridZ#-GetRawKeyPressed(40)*0.25+GetRawKeyPressed(38)*0.25
	SetObjectPosition(SphereObjectID,GridX#,GridY#,GridZ#)
	X#=GridX#
	Y#=GridY#
	Z#=GridZ#

//~ NodeID=OcTree_Exist(0,X#,Y#,Z#)
	//~ print(NodeID)
	//~ if NodeID<>-1
		//~ print("ObjectID: "+str(OcTree_GetObjectID(NodeID)))
		//~ print("Depth: "+str(OcTreeNode[NodeID].Depth))
		//~ print("ParentID: "+str(OcTreeNode[NodeID].ParentID))
	//~ endif

if GetRawMouseRightPressed()=1
		NodeID=OcTree_Exist(0,X#,Y#,Z#)
		if NodeID<>-1
			if GetObjectExists(OcTree_GetObjectID(NodeID))
				OcTree_RemoveNode(NodeID,X#,Y#,Z#)
			else
				OcTree_AddNode(NodeID,X#,Y#,Z#)
			endif
		endif
	endif

for ID=0 to OcTreeNode.length
		print(str(ID,0)+","+str(OcTreeNode[ID].ParentID)+","+str(OcTreeNode[ID].Depth))
	next ID

sync()
loop

function AddCube(Size#,X#,Y#,Z#)
	ObjectID=CreateObjectBox(Size#,Size#,Size#)
	SetObjectPosition(ObjectID,X#,Y#,Z#)
endfunction ObjectID

function RemoveCube(ObjectID)
	DeleteObject(ObjectID)
endfunction ObjectID

function OcTree_CreateNode(MinX#,MinY#,MinZ#,MaxX#,MaxY#,MaxZ#,Size#,ParentID)
	TempNode as OctTree_NodeData

if ParentID=-1
		TempNode.Depth=0
	else
		TempNode.Depth=OcTreeNode[ParentID].Depth+1
	endif
	TempNode.MinX#=MinX#
	TempNode.MinY#=MinY#
	TempNode.MinZ#=MinZ#
	TempNode.MaxX#=MaxX#
	TempNode.MaxY#=MaxY#
	TempNode.MaxZ#=MaxZ#
	TempNode.Size#=Size#
	TempNode.ParentID=ParentID
	TempNode.ObjectID=AddCube(Size#*0.5,(MaxX#+MinX#)*0.5,(MaxY#+MinY#)*0.5,(MaxZ#+MinZ#)*0.5)

for ChildID=0 to 7
		TempNode.ChildID[ChildID]=-1
	next ChildID

OcTreeNode.insert(TempNode)
endfunction OcTreeNode.length

function OcTree_SplitNode(NodeID)
	TempNode as OctTree_NodeData
	TempNode=OcTreeNode[NodeID]
	HalfSize#=TempNode.Size#*0.5
	X#=GetObjectX(TempNode.ObjectID)
	Y#=GetObjectY(TempNode.ObjectID)
	Z#=GetObjectZ(TempNode.ObjectID)
	TempNode.ChildID[0]=OcTree_CreateNode(TempNode.MinX#,TempNode.MinY#,TempNode.MinZ#,X#,Y#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[1]=OcTree_CreateNode(X#,TempNode.MinY#,TempNode.MinZ#,TempNode.MaxX#,Y#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[2]=OcTree_CreateNode(X#,TempNode.MinY#,Z#,TempNode.MaxX#,Y#,TempNode.MaxZ#,HalfSize#,NodeID)
	TempNode.ChildID[3]=OcTree_CreateNode(TempNode.MinX#,TempNode.MinY#,Z#,X#,Y#,TempNode.MaxZ#,HalfSize#,NodeID)
	TempNode.ChildID[4]=OcTree_CreateNode(TempNode.MinX#,Y#,TempNode.MinZ#,X#,TempNode.MaxY#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[5]=OcTree_CreateNode(X#,Y#,TempNode.MinZ#,TempNode.MaxX#,TempNode.MaxY#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[6]=OcTree_CreateNode(X#,Y#,Z#,TempNode.MaxX#,TempNode.MaxY#,TempNode.MaxZ#,HalfSize#,NodeID)
	TempNode.ChildID[7]=OcTree_CreateNode(TempNode.MinX#,Y#,Z#,X#,TempNode.MaxY#,TempNode.MaxZ#,HalfSize#,NodeID)
	RemoveCube(TempNode.ObjectID)
	OcTreeNode[NodeID]=TempNode
endfunction

function OcTree_RemoveNode(NodeID,X#,Y#,Z#)
	if OcTreeNode[NodeID].Depth>=MaxDepth
		RemoveCube(OcTreeNode[NodeID].ObjectID)
	else
		OcTree_SplitNode(NodeID)
		for ChildID=0 to 7
			if OcTree_InsideNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)=1
				OcTree_RemoveNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)
				exit
			endif
		next ChildID
	endif
endfunction

function OcTree_UniteNode(NodeID)
	TempNode as OctTree_NodeData
	TempNode=OcTreeNode[NodeID]

for ChildID=0 to 7
		RemoveCube(OcTreeNode[TempNode.ChildID[ChildID]].ObjectID)
	next ChildID

ParentNode as OctTree_NodeData
	ParentNode=OcTreeNode[TempNode.ParentID]
	OcTree_CreateNode(ParentNode.MinX#,ParentNode.MinY#,ParentNode.MinZ#,ParentNode.MaxX#,ParentNode.MaxY#,ParentNode.MaxZ#,ParentNode.Size#,NodeID)

OcTreeNode[NodeID]=TempNode
endfunction

function OcTree_FullParent(NodeID)
	ParentID=OcTreeNode[NodeID].ParentID
	for ChildID=0 to 7
		if OcTreeNode[ParentID].ChildID[ChildID]=-1 then exitfunction 0
	next ChildID
endfunction 1

function OcTree_Combine(NodeID)
	if OcTree_FullParent(NodeID)=1 and OcTreeNode[NodeID].Depth>1
		MaxX#=OcTreeNode[NodeID].MaxX#
		MaxY#=OcTreeNode[NodeID].MaxY#
		MaxZ#=OcTreeNode[NodeID].MaxZ#
		MinX#=OcTreeNode[NodeID].MinX#
		MinY#=OcTreeNode[NodeID].MinY#
		MinZ#=OcTreeNode[NodeID].MinZ#
		Size#=OcTreeNode[NodeID].Size#
		Depth=OcTreeNode[NodeID].Depth
		ParentID=OcTreeNode[NodeID].ParentID
		ObjectID=OcTreeNode[NodeID].ObjectID
		OcTreeNode.remove(NodeID)

//~ OcTreeNode[ParentID].ChildID[ChildID]=-1

//~ OcTree_CreateNode(MinX#,MinY#,MinZ#,MaxX#,MaxY#,MaxZ#,Size#,ParentID)
		for ChildID=7 to 0 step -1
			ID=OcTreeNode[ParentID].ChildID[ChildID]
			//~ OcTreeNode[ParentID].ChildID[ChildID]=-1
			DeleteObject(OcTreeNode[ID].ObjectID)
			OcTreeNode.remove(ID)
		next ChildID
		OcTree_Combine(ParentID)
	endif
endfunction

function OcTree_AddNode(NodeID,X#,Y#,Z#)
	if OcTreeNode[NodeID].Depth>=MaxDepth
		OcTree_Combine(NodeID)
	else
		for ChildID=0 to 7
			if OcTree_InsideNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)=1
				OcTree_AddNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)
				exit
			endif
		next ChildID
	endif
endfunction

function OcTree_Exist(NodeID,X#,Y#,Z#)
	for ChildID=0 to 7
		if OcTreeNode[NodeID].ChildID[ChildID]<>-1
			if OcTree_InsideNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)=1
				ID=OcTree_Exist(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)
				if ID<>-1 then exitfunction ID
			endif
		endif
	next ChildID
	if OcTree_InsideNode(NodeID,X#,Y#,Z#)=1 then exitfunction NodeID
endfunction -1

function OcTree_InsideNode(NodeID,X#,Y#,Z#)
	if NodeID<=OcTreeNode.length
		if X#>=OcTreeNode[NodeID].MinX# and X#<=OcTreeNode[NodeID].MaxX#
			if Y#>=OcTreeNode[NodeID].MinY# and Y#<=OcTreeNode[NodeID].MaxY#
				if Z#>=OcTreeNode[NodeID].MinZ# and Z#<=OcTreeNode[NodeID].MaxZ#
					exitfunction 1
				endif
			endif
		endif
	endif
endfunction 0

function OcTree_GetObjectID(NodeID)
endfunction OcTreeNode[NodeID].ObjectID

function ControlCamera()
	global startx#
	global starty#
	global angx#
	global angY#

speed#=40*GetFrameTime()

// move the camera with keys
	if GetKeyboardExists()=1
		if(GetRawKeyState(87)) then MoveCameraLocalZ(1, speed# )
		if(GetRawKeyState(83)) then MoveCameraLocalZ(1, -speed# )
		if(GetRawKeyState(65)) then MoveCameraLocalX(1, -speed# )
		if(GetRawKeyState(68)) then MoveCameraLocalX(1, speed# )
		if(GetRawKeyState(81)) then MoveCameraLocalY(1, -speed# )
		if(GetRawKeyState(69)) then MoveCameraLocalY(1, speed# )
	else
		JoystickSize#=GetVirtualHeight()*0.25
		SetJoystickScreenPosition(GetScreenBoundsLeft()+JoystickSize#*0.5,GetScreenBoundsBottom()-JoystickSize#*0.5,JoystickSize#)
		MoveCameraLocalZ( 1, -GetJoystickY() * speed# )
		MoveCameraLocalX( 1, GetJoystickX() * speed# )
	endif

// rotate the camera
    if GetPointerPressed()=1
        startx# = GetPointerX()
        starty# = GetPointerY()
        angx# = GetCameraAngleX(1)
        angy# = GetCameraAngleY(1)
    endif

if GetPointerState()=1
        fDiffX# = (GetPointerX() - startx#)
        fDiffY# = (GetPointerY() - starty#)

newX# = angx# + fDiffY#
        if ( newX# > 89 ) then newX# = 89
        if ( newX# < -89 ) then newX# = -89
        SetCameraRotation( 1, newX#, angy# + fDiffX#, 0 )
    endif
endfunction

+ Code Snippet

SetWindowTitle( "Octree" )
SetWindowSize( 800, 600, 0 )

SetVirtualResolution( 800, 600 )
SetOrientationAllowed( 1, 1, 1, 1 )
SetSyncRate(0,0)
SetClearColor(0, 193, 255)
SetPrintSize(12)

CameraVectorID=CreateVector3()
PointerVectorID=CreateVector3()
PointVectorID=CreateVector3()

type OctTree_NodeData
	Depth as integer
	MinX# as float
	MinY# as float
	MinZ# as float
	MaxX# as float
	MaxY# as float
	MaxZ# as float
	Size# as float
	ObjectID as integer
	ParentID as integer
	ChildID as integer[7]
endtype

global OcTreeNode as OctTree_NodeData[]
global MaxDepth
MaxDepth=3

OcTree_CreateNode(-1,-1,-1,1,1,1,4,-1)

SphereObjectID=CreateObjectSphere(0.3,16,32)
SetObjectCollisionMode(SphereObjectID,0)
GridX#=0.125
GridY#=0.125
GridZ#=0.125
do
	print("Arrow keys to move the selection sphere and right mouse to remove/add a cube)
	Print(ScreenFPS())
	ControlCamera()

	//~ PointerX#=Get3DVectorXFromScreen(GetPointerX(),GetPointerY())
	//~ PointerY#=Get3DVectorYFromScreen(GetPointerX(),GetPointerY())
	//~ PointerZ#=Get3DVectorZFromScreen(GetPointerX(),GetPointerY())
	//~ SetVector3(PointerVectorID,PointerX#,PointerY#,PointerZ#)
	//~ SetVector3(CameraVectorID,GetCameraX(1),GetCameraY(1),GetCameraZ(1))
	//~ GetVector3Multiply(PointerVectorID,9999)
	//~ ObjectRayCast(0,GetVector3X(CameraVectorID),GetVector3Y(CameraVectorID),GetVector3Z(CameraVectorID),GetVector3X(PointerVectorID),GetVector3Y(PointerVectorID),GetVector3Z(PointerVectorID))
	//~ ObjectID=GetObjectRayCastHitID(0)
	//~ RayHitX#=GetObjectRayCastX(0)
	//~ RayHitY#=GetObjectRayCastY(0)
	//~ RayHitZ#=GetObjectRayCastZ(0)

	GridX#=GridX#-GetRawKeyPressed(37)*0.25+GetRawKeyPressed(39)*0.25
	GridY#=GridY#-GetRawKeyPressed(34)*0.25+GetRawKeyPressed(33)*0.25
	GridZ#=GridZ#-GetRawKeyPressed(40)*0.25+GetRawKeyPressed(38)*0.25
	SetObjectPosition(SphereObjectID,GridX#,GridY#,GridZ#)
	X#=GridX#
	Y#=GridY#
	Z#=GridZ#

	//~ NodeID=OcTree_Exist(0,X#,Y#,Z#)
	//~ print(NodeID)
	//~ if NodeID<>-1
		//~ print("ObjectID: "+str(OcTree_GetObjectID(NodeID)))
		//~ print("Depth: "+str(OcTreeNode[NodeID].Depth))
		//~ print("ParentID: "+str(OcTreeNode[NodeID].ParentID))
	//~ endif

	if GetRawMouseRightPressed()=1
		NodeID=OcTree_Exist(0,X#,Y#,Z#)
		if NodeID<>-1
			if GetObjectExists(OcTree_GetObjectID(NodeID))
				OcTree_RemoveNode(NodeID,X#,Y#,Z#)
			else
				OcTree_AddNode(NodeID,X#,Y#,Z#)
			endif
		endif
	endif

	for ID=0 to OcTreeNode.length
		print(str(ID,0)+","+str(OcTreeNode[ID].ParentID)+","+str(OcTreeNode[ID].Depth))
	next ID

	sync()
loop

function AddCube(Size#,X#,Y#,Z#)
	ObjectID=CreateObjectBox(Size#,Size#,Size#)
	SetObjectPosition(ObjectID,X#,Y#,Z#)
endfunction ObjectID

function RemoveCube(ObjectID)
	DeleteObject(ObjectID)
endfunction ObjectID

function OcTree_CreateNode(MinX#,MinY#,MinZ#,MaxX#,MaxY#,MaxZ#,Size#,ParentID)
	TempNode as OctTree_NodeData

	if ParentID=-1
		TempNode.Depth=0
	else
		TempNode.Depth=OcTreeNode[ParentID].Depth+1
	endif
	TempNode.MinX#=MinX#
	TempNode.MinY#=MinY#
	TempNode.MinZ#=MinZ#
	TempNode.MaxX#=MaxX#
	TempNode.MaxY#=MaxY#
	TempNode.MaxZ#=MaxZ#
	TempNode.Size#=Size#
	TempNode.ParentID=ParentID
	TempNode.ObjectID=AddCube(Size#*0.5,(MaxX#+MinX#)*0.5,(MaxY#+MinY#)*0.5,(MaxZ#+MinZ#)*0.5)

	for ChildID=0 to 7
		TempNode.ChildID[ChildID]=-1
	next ChildID

	OcTreeNode.insert(TempNode)
endfunction OcTreeNode.length

function OcTree_SplitNode(NodeID)
	TempNode as OctTree_NodeData
	TempNode=OcTreeNode[NodeID]
	HalfSize#=TempNode.Size#*0.5
	X#=GetObjectX(TempNode.ObjectID)
	Y#=GetObjectY(TempNode.ObjectID)
	Z#=GetObjectZ(TempNode.ObjectID)
	TempNode.ChildID[0]=OcTree_CreateNode(TempNode.MinX#,TempNode.MinY#,TempNode.MinZ#,X#,Y#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[1]=OcTree_CreateNode(X#,TempNode.MinY#,TempNode.MinZ#,TempNode.MaxX#,Y#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[2]=OcTree_CreateNode(X#,TempNode.MinY#,Z#,TempNode.MaxX#,Y#,TempNode.MaxZ#,HalfSize#,NodeID)
	TempNode.ChildID[3]=OcTree_CreateNode(TempNode.MinX#,TempNode.MinY#,Z#,X#,Y#,TempNode.MaxZ#,HalfSize#,NodeID)
	TempNode.ChildID[4]=OcTree_CreateNode(TempNode.MinX#,Y#,TempNode.MinZ#,X#,TempNode.MaxY#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[5]=OcTree_CreateNode(X#,Y#,TempNode.MinZ#,TempNode.MaxX#,TempNode.MaxY#,Z#,HalfSize#,NodeID)
	TempNode.ChildID[6]=OcTree_CreateNode(X#,Y#,Z#,TempNode.MaxX#,TempNode.MaxY#,TempNode.MaxZ#,HalfSize#,NodeID)
	TempNode.ChildID[7]=OcTree_CreateNode(TempNode.MinX#,Y#,Z#,X#,TempNode.MaxY#,TempNode.MaxZ#,HalfSize#,NodeID)
	RemoveCube(TempNode.ObjectID)
	OcTreeNode[NodeID]=TempNode
endfunction

function OcTree_RemoveNode(NodeID,X#,Y#,Z#)
	if OcTreeNode[NodeID].Depth>=MaxDepth
		RemoveCube(OcTreeNode[NodeID].ObjectID)
	else
		OcTree_SplitNode(NodeID)
		for ChildID=0 to 7
			if OcTree_InsideNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)=1
				OcTree_RemoveNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)
				exit
			endif
		next ChildID
	endif
endfunction

function OcTree_UniteNode(NodeID)
	TempNode as OctTree_NodeData
	TempNode=OcTreeNode[NodeID]

	for ChildID=0 to 7
		RemoveCube(OcTreeNode[TempNode.ChildID[ChildID]].ObjectID)
	next ChildID

	ParentNode as OctTree_NodeData
	ParentNode=OcTreeNode[TempNode.ParentID]
	OcTree_CreateNode(ParentNode.MinX#,ParentNode.MinY#,ParentNode.MinZ#,ParentNode.MaxX#,ParentNode.MaxY#,ParentNode.MaxZ#,ParentNode.Size#,NodeID)

	OcTreeNode[NodeID]=TempNode
endfunction

function OcTree_FullParent(NodeID)
	ParentID=OcTreeNode[NodeID].ParentID
	for ChildID=0 to 7
		if OcTreeNode[ParentID].ChildID[ChildID]=-1 then exitfunction 0
	next ChildID
endfunction 1

function OcTree_Combine(NodeID)
	if OcTree_FullParent(NodeID)=1 and OcTreeNode[NodeID].Depth>1
		MaxX#=OcTreeNode[NodeID].MaxX#
		MaxY#=OcTreeNode[NodeID].MaxY#
		MaxZ#=OcTreeNode[NodeID].MaxZ#
		MinX#=OcTreeNode[NodeID].MinX#
		MinY#=OcTreeNode[NodeID].MinY#
		MinZ#=OcTreeNode[NodeID].MinZ#
		Size#=OcTreeNode[NodeID].Size#
		Depth=OcTreeNode[NodeID].Depth
		ParentID=OcTreeNode[NodeID].ParentID
		ObjectID=OcTreeNode[NodeID].ObjectID
		OcTreeNode.remove(NodeID)

		//~ OcTreeNode[ParentID].ChildID[ChildID]=-1

		//~ OcTree_CreateNode(MinX#,MinY#,MinZ#,MaxX#,MaxY#,MaxZ#,Size#,ParentID)
		for ChildID=7 to 0 step -1
			ID=OcTreeNode[ParentID].ChildID[ChildID]
			//~ OcTreeNode[ParentID].ChildID[ChildID]=-1
			DeleteObject(OcTreeNode[ID].ObjectID)
			OcTreeNode.remove(ID)
		next ChildID
		OcTree_Combine(ParentID)
	endif
endfunction

function OcTree_AddNode(NodeID,X#,Y#,Z#)
	if OcTreeNode[NodeID].Depth>=MaxDepth
		OcTree_Combine(NodeID)
	else
		for ChildID=0 to 7
			if OcTree_InsideNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)=1
				OcTree_AddNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)
				exit
			endif
		next ChildID
	endif
endfunction

function OcTree_Exist(NodeID,X#,Y#,Z#)
	for ChildID=0 to 7
		if OcTreeNode[NodeID].ChildID[ChildID]<>-1
			if OcTree_InsideNode(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)=1
				ID=OcTree_Exist(OcTreeNode[NodeID].ChildID[ChildID],X#,Y#,Z#)
				if ID<>-1 then exitfunction ID
			endif
		endif
	next ChildID
	if OcTree_InsideNode(NodeID,X#,Y#,Z#)=1 then exitfunction NodeID
endfunction -1

function OcTree_InsideNode(NodeID,X#,Y#,Z#)
	if NodeID<=OcTreeNode.length
		if X#>=OcTreeNode[NodeID].MinX# and X#<=OcTreeNode[NodeID].MaxX#
			if Y#>=OcTreeNode[NodeID].MinY# and Y#<=OcTreeNode[NodeID].MaxY#
				if Z#>=OcTreeNode[NodeID].MinZ# and Z#<=OcTreeNode[NodeID].MaxZ#
					exitfunction 1
				endif
			endif
		endif
	endif
endfunction 0

function OcTree_GetObjectID(NodeID)
endfunction OcTreeNode[NodeID].ObjectID

function ControlCamera()
	global startx#
	global starty#
	global angx#
	global angY#

	speed#=40*GetFrameTime()

	// move the camera with keys
	if GetKeyboardExists()=1
		if(GetRawKeyState(87)) then MoveCameraLocalZ(1, speed# )
		if(GetRawKeyState(83)) then MoveCameraLocalZ(1, -speed# )
		if(GetRawKeyState(65)) then MoveCameraLocalX(1, -speed# )
		if(GetRawKeyState(68)) then MoveCameraLocalX(1, speed# )
		if(GetRawKeyState(81)) then MoveCameraLocalY(1, -speed# )
		if(GetRawKeyState(69)) then MoveCameraLocalY(1, speed# )
	else
		JoystickSize#=GetVirtualHeight()*0.25
		SetJoystickScreenPosition(GetScreenBoundsLeft()+JoystickSize#*0.5,GetScreenBoundsBottom()-JoystickSize#*0.5,JoystickSize#)
		MoveCameraLocalZ( 1, -GetJoystickY() * speed# )
		MoveCameraLocalX( 1, GetJoystickX() * speed# )
	endif

	// rotate the camera
    if GetPointerPressed()=1
        startx# = GetPointerX()
        starty# = GetPointerY()
        angx# = GetCameraAngleX(1)
        angy# = GetCameraAngleY(1)
    endif

    if GetPointerState()=1
        fDiffX# = (GetPointerX() - startx#)
        fDiffY# = (GetPointerY() - starty#)

        newX# = angx# + fDiffY#
        if ( newX# > 89 ) then newX# = 89
        if ( newX# < -89 ) then newX# = -89
        SetCameraRotation( 1, newX#, angy# + fDiffX#, 0 )
    endif
endfunction

Move the camera with W,A,S,D, there is a sphere inside the cube which you can control with the arrow keys and remove/add a cube.

Back to top

Profile PM Email Website

puzzler2018

User Banned

Posted: 5th Aug 2018 17:21 Edited at: 5th Aug 2018 17:23

Link

Hi Janbo,

Thanks for this, I can see roughly what its trying to acheive and here is a little more on

Octree (2D) https://www.gamedev.net/articles/programming/general-and-gameplay-programming/introduction-to-octrees-r3529/

Wiki https://en.wikipedia.org/wiki/Octree

and

https://www.omicsonline.org/rendering-for-3d-animation-based-on-octree-jcsb.10000117.php?aid=1289

and

https://castle-engine.io/vrml_engine_doc/output/xsl/html/chapter.octree.html
Hope these help get you started, its a worth while shot at this for the Minecraft one we are doing

Back to top

Profile

Sorry your browser is not supported!

AppGameKit Classic Chat / Dynamic QuadTree