NewsForumsCodeLogsGallerySpecsSearch

Obstical Avoidance

Blitz3D Forums/Blitz3D Programming/Obstical Avoidance

Dicon(Posted 2013) [#1]
I seem to be unable to get my brain around the method to make a character walk/move around objects to a target on the screen. Can anyone suggest a method. It's not like I am asking for the code ( which would be nice ) but an approach to the problem.
Dicon


Omnicode(Posted 2013) [#2]
You're referring to 'AI', entity movement and control. I suggest using nodes that can be followed in a path.

Perhaps create an Array of nodes per object that can function as pivots, once the 'character' has reached the desired position it simply switches to the next node in the array in which to travel to.

Now, positioning those nodes in order to navigate complex obstacles is really the issue.

Mainly id recommend doing some sort of 'pick' to figure out the obstacle or issue to the character's path and then position the nodes accordingly in real time and once the player reaches a new node it does yet another 'pick'. Hope it helps.

There's A LOT of ways to do this, this method may not be the fastest nor have i tested it. I use more 'freeworld' types of AI. Whereas the only obstacles may be a tree or rock or water. Rather than many walls or buildings.

Concept Displayed here:


But it really depends on what kind of effect you're looking for, if you're looking for a more like 'if i click here, i wanna move there' kinda deal and still do those things, that's probably much easier. As it involves less math.


Omnicode(Posted 2013) [#3]
Here, i put this together to perhaps assist you in your understanding, this is FAR from perfect but it works about 70% of the time.

It's accuracy is slightly off but it still works.
Being that i spent about 15mins making it.
Free to use, its whatever you make of it.

The funny part is, is that i completely misunderstood the usage of 'linepicks' and yet it still created this result.

Graphics3D 800,600,32,2
SetBuffer BackBuffer()

Global AI_METHOD=1,PICK=0

Type Character
	Field Entity,X,Y,Z,Node[99],Modulus
	Field Target,Status$,Destination,CurrentNode,CurrentNodesNeeded
End Type

Type Obstacle
	Field Entity,x,y,z
End Type

Global Plane=CreatePlane()
EntityPickMode Plane,2
MoveEntity Plane,0,-1,0

Global Light=CreateLight()
RotateEntity Light ,45,45,0

Global Camera=CreateCamera()

Global C.Character=New Character
C\Entity=CreateCube()
C\Target=CreateSphere()
C\CurrentNode=1
ScaleEntity C\Target,2,2,2
EntityColor C\Target,10,10,10
HideEntity C\Target
EntityColor C\Entity,255,0,0
ScaleEntity C\Entity,1,2,1
MoveEntity C\Entity,0,1,0

PositionEntity Camera,0,60,27.5
RotateEntity Camera,90,0,0

For obx=1 To 10
	For oby=1 To 10
		Obs.Obstacle=New Obstacle
		obs\entity=CreateCube()
		EntityColor obs\entity,Rand(255),Rand(255),Rand(255)
		ScaleEntity obs\entity,1,5,1
		PositionEntity obs\entity,obx*10-(27.5*Rnd(1,3)),0,oby*Rnd(1,25)
		Obs\x=EntityX#(Obs\entity)
		Obs\y=EntityY#(Obs\entity)
		Obs\z=EntityZ#(Obs\Entity)
		EntityPickMode Obs\Entity,1
		EntityRadius Obs\Entity,2
	Next
Next

For nodes=1 To 99
	C\Node[nodes]=CreateCube()
	EntityColor C\Node[nodes],255,0,255
	HideEntity C\Node[nodes]
Next

UpdateWorld

While Not KeyDown(1)
	Cls
	TranslateEntity Camera,0,-MouseZSpeed()*2,0
	If MouseHit(1)=True
		If CameraPick(Camera,MouseX(),MouseY())<>0
			ShowEntity C\Target
			PositionEntity C\Target,PickedX(),PickedY(),PickedZ()
			C\Destination=C\Target
			For nodes=1 To 99
				PositionEntity C\Node[nodes],0,0,0
				HideEntity C\Node[nodes]
			Next
			EntityPickMode C\Target,2
			C\CurrentNode=1
			C\CurrentNodesNeeded=1
			EntityPickMode Plane,0
			OBSTACLE=LinePick(EntityX(C\Entity),EntityY(C\Entity)+1,EntityZ(C\Entity),EntityX(C\Target),EntityY(C\Entity)+1,EntityZ(C\Target),2)
			If OBSTACLE<>0 And OBSTACLE<>C\Destination
				AI_METHOD=2
				C\CurrentNodesNeeded=NodesNeeded(C\Entity,C\Target)
				PositionEntity C\Node[C\CurrentNodesNeeded+1],EntityX(C\Target),EntityY(C\Entity),EntityZ(C\Target)
			Else
				AI_METHOD=1
			EndIf
			EntityPickMode Plane,2
		EndIf
	EndIf
	
	If KeyHit(205)=True Then AI_METHOD=AI_METHOD+1
	If KeyHit(203)=True Then AI_METHOD=AI_METHOD-1
	
	If AI_METHOD<1 Then AI_METHOD=1
	If AI_METHOD>2 Then AI_METHOD=2
	
	For nodes=1 To C\CurrentNodesNeeded+1
		ShowEntity C\Node[nodes]
	Next
	
	
	If C\Destination<>0
		Select AI_METHOD
			Case 1
				If EntityDistance(C\Destination,C\Entity)>2
					PointEntity C\Entity,C\Destination
					RotateEntity C\Entity,0,EntityYaw(C\Entity),0
					MoveEntity C\Entity,0,0,2
				Else
					RotateEntity C\Entity,0,EntityYaw(C\Entity),0
					C\Destination=0
				EndIf
			Case 2
				If EntityDistance(C\Destination,C\Entity)>2
					If C\CurrentNode<1 Then C\CurrentNode=1
					If C\CurrentNode<=99
						If EntityDistance(C\Entity,C\Node[C\CurrentNode])<2
							C\CurrentNode=C\CurrentNode+1
							If C\CurrentNode>C\CurrentNodesNeeded+1 Then C\CurrentNode=C\CurrentNodesNeeded+1
						Else
							PointEntity C\Entity,C\Node[C\CurrentNode]
							TurnEntity C\Entity,0,DeltaYaw#(C\Entity,C\Node[C\CurrentNode]),0
							MoveEntity C\Entity,0,0,.2
						EndIf
					EndIf
				Else
					RotateEntity C\Entity,0,EntityYaw(C\Entity),0
					C\Destination=0
				EndIf
		End Select
	EndIf
	UpdateWorld
	RenderWorld
	Color 0,0,0
	CameraProject Camera,EntityX(C\Entity),EntityY(C\Entity),EntityZ(C\Entity)
	Text ProjectedX(),ProjectedY(),"Player"
	Text 0,0,"USING METHOD:"+AI_METHOD+" Nodes:"+C\CurrentNode+"/"+C\CurrentNodesNeeded
	
	For Nodes=1 To C\CurrentNodesNeeded
		CameraProject Camera,EntityX(C\Node[nodes]),EntityY(C\Node[nodes]),EntityZ(C\Node[nodes])
		Local X1#=ProjectedX() : Local Y1#=ProjectedY()
		CameraProject Camera,EntityX(C\Node[nodes+1]),EntityY(C\Node[nodes+1]),EntityZ(C\Node[nodes+1])
		Local X2#=ProjectedX() : Local Y2#=ProjectedY()
		Line X1#,Y1#,X2#,Y2#
	Next
	
	Flip 0
Wend
End


Function NodesNeeded(obs,dest)
	Local NodeUsed=1,NodePick
	EntityPickMode Plane,0
	obs=LinePick(EntityX(C\Entity),EntityY(C\Entity)+1,EntityZ(C\Entity),EntityX(dest),EntityY(dest),EntityZ(dest),5)
	If obs
		If obs=dest
			EntityPickMode Plane,2
			UpdateWorld 0
			Return 1
		EndIf
		PositionEntity C\Node[NodeUsed],EntityX(obs),EntityY(obs),EntityX(obs)
	Else
		PositionEntity C\Node[NodeUsed],EntityX(C\Entity),EntityY(C\Entity),EntityX(C\Entity)
	EndIf
	EntityPickMode Plane,0
	Repeat
		NodePick=LinePick(EntityX(C\Node[NodeUsed]),EntityY(C\Node[NodeUsed]),EntityZ(C\Node[NodeUsed]),EntityX(dest),EntityY(dest),EntityZ(dest),1)
		If NodePick
			If NodeUsed+1<100
				Local NX#=EntityX(NodePick)
				Local DX#=EntityX(dest)
				Local DELX#=(DX#-NX#)
				
				Local NZ#=EntityZ(NodePick)
				Local DZ#=EntityZ(dest)
				Local DELZ#=(DZ#-NZ#)
				PositionEntity C\Node[NodeUsed+1],EntityX(NodePick),EntityY(NodePick),EntityZ(NodePick)
				If DELX#>0
					MoveEntity C\Node[NodeUsed+1],-3,0,0
				Else
					MoveEntity C\Node[NodeUsed+1],3,0,0
				EndIf
				If DELZ#>0
					MoveEntity C\Node[NodeUsed+1],0,0,-3
				Else
					MoveEntity C\Node[NodeUsed+1],0,0,3
			    EndIf
				NodeUsed=NodeUsed+1
			EndIf
		Else
			EntityPickMode Plane,2
			Return NodeUsed
		EndIf
	Until NodeUsed>=99
	EntityPickMode Plane,2
	Return 0 ;Can't resolve it.
End Function



Omnicode(Posted 2013) [#4]
Hi, here's a greater version of this earlier code. Now Works much faster and works about 99% of the time.
Graphics3D 800,600,32,2
SetBuffer BackBuffer()

Global AI_METHOD=1,PICK=0

Type Character
	Field Entity,X,Y,Z,Node[99],Modulus
	Field Target,Status$,Destination,CurrentNode,CurrentNodesNeeded
End Type

Type Obstacle
	Field Entity,x,y,z
End Type

Global Plane=CreatePlane()
EntityPickMode Plane,2
MoveEntity Plane,0,-1,0

Global Light=CreateLight()
RotateEntity Light ,45,45,0

Global Camera=CreateCamera()

Global C.Character=New Character
C\Entity=CreateCube()
C\Target=CreateSphere()
C\CurrentNode=1
ScaleEntity C\Target,.5,.5,.5
EntityColor C\Target,10,10,10
HideEntity C\Target
EntityColor C\Entity,255,0,0
ScaleEntity C\Entity,1,2,1
MoveEntity C\Entity,0,1,0

RotateEntity Camera,90,0,0

For obx=1 To 10
	For oby=1 To 10
		Obs.Obstacle=New Obstacle
		obs\entity=CreateCube()
		EntityColor obs\entity,Rand(255),Rand(255),Rand(255)
		ScaleEntity obs\entity,1,5,1
		PositionEntity obs\entity,obx*10-(27.5),0,oby*10
		Obs\x=EntityX#(Obs\entity)
		Obs\y=EntityY#(Obs\entity)
		Obs\z=EntityZ#(Obs\Entity)
		EntityPickMode Obs\Entity,1
		EntityRadius Obs\Entity,2
	Next
Next

For nodes=1 To 99
	C\Node[nodes]=CreateCube()
	EntityColor C\Node[nodes],0,128,255
	ScaleEntity C\Node[nodes],.5,.5,.5
	HideEntity C\Node[nodes]
Next

UpdateWorld

While Not KeyDown(1)
	Cls
	TranslateEntity Camera,0,-MouseZSpeed()*2,0
	PositionEntity Camera,EntityX(C\Entity),120,EntityZ(C\Entity)
	If MouseDown(1)=True
		If CameraPick(Camera,MouseX(),MouseY())<>0
			ShowEntity C\Target
			PositionEntity C\Target,Ceil(PickedX()),EntityY(C\Entity),Ceil(PickedZ())
			C\Destination=C\Target
			For nodes=1 To 99
				HideEntity C\Node[nodes]
			Next
			EntityPickMode C\Target,0
			C\CurrentNode=1
			C\CurrentNodesNeeded=0
			EntityPickMode Plane,0
			OBSTACLE=LinePick(EntityX(C\Entity),EntityY(C\Entity),EntityZ(C\Entity),EntityX(C\Target)-EntityX(C\Entity),EntityY(C\Entity),EntityZ(C\Target)-EntityZ(C\Entity),1)
			If OBSTACLE<>0
				AI_METHOD=2
				C\CurrentNodesNeeded=NodesNeeded(C\Entity,C\Target)
				PositionEntity C\Node[1],EntityX(C\Entity),EntityY(C\Entity),EntityZ(C\Entity)
				PositionEntity C\Node[C\CurrentNodesNeeded+1],EntityX(C\Target),EntityY(C\Entity),EntityZ(C\Target)
			Else
				AI_METHOD=1
			EndIf
			EntityPickMode Plane,2
		EndIf
	EndIf
	
	If KeyHit(205)=True Then AI_METHOD=AI_METHOD+1
	If KeyHit(203)=True Then AI_METHOD=AI_METHOD-1
	
	If AI_METHOD<1 Then AI_METHOD=1
	If AI_METHOD>2 Then AI_METHOD=2
	
	
	If C\Destination<>0
		Select AI_METHOD
			Case 1
				If EntityDistance(C\Destination,C\Entity)>2
					PointEntity C\Entity,C\Destination
					RotateEntity C\Entity,0,EntityYaw(C\Entity),0
					MoveEntity C\Entity,0,0,.2
				Else
					RotateEntity C\Entity,0,EntityYaw(C\Entity),0
					C\Destination=0
				EndIf
			Case 2
				If EntityDistance(C\Destination,C\Entity)>2
					If C\CurrentNode<1 Then C\CurrentNode=1
					If C\CurrentNode<=99
						If EntityDistance(C\Entity,C\Node[C\CurrentNode])<1
							C\CurrentNode=C\CurrentNode+1
							If C\CurrentNode>C\CurrentNodesNeeded+1 Then C\CurrentNode=C\CurrentNodesNeeded+1
						Else
							PointEntity C\Entity,C\Node[C\CurrentNode]
							TurnEntity C\Entity,0,DeltaYaw#(C\Entity,C\Node[C\CurrentNode]),0
							MoveEntity C\Entity,0,0,.2
						EndIf
					EndIf
				Else
					RotateEntity C\Entity,0,EntityYaw(C\Entity),0
					C\Destination=0
				EndIf
		End Select
	EndIf
	UpdateWorld
	RenderWorld
	Color 0,0,0
	CameraProject Camera,EntityX(C\Entity),EntityY(C\Entity),EntityZ(C\Entity)
	Text ProjectedX(),ProjectedY(),"Player"
	Text 0,0,"USING METHOD:"+AI_METHOD+" Nodes:"+C\CurrentNode+"/"+(C\CurrentNodesNeeded+1)
	
	For Nodes=1 To C\CurrentNodesNeeded
		If nodes>=C\CurrentNode-1
			ShowEntity C\Node[nodes]
			CameraProject Camera,EntityX(C\Node[nodes]),EntityY(C\Node[nodes]),EntityZ(C\Node[nodes])
			Local X1#=ProjectedX() : Local Y1#=ProjectedY()
			CameraProject Camera,EntityX(C\Node[nodes+1]),EntityY(C\Node[nodes+1]),EntityZ(C\Node[nodes+1])
			Local X2#=ProjectedX() : Local Y2#=ProjectedY()
			Line X1#,Y1#,X2#,Y2#
		Else
			HideEntity C\Node[nodes]
		EndIf
	Next
	
	Flip 0
Wend
End


Function NodesNeeded(obs,dest)
	Local NodeUsed=2,NodePick
	EntityPickMode Plane,0
	PositionEntity C\Node[NodeUsed],PickedX(),EntityY(C\Entity),PickedZ()
	MoveEntity C\Node[NodeUsed],PickedNX()*4,0,PickedNZ()*4
	Repeat
		NodePick=LinePick(EntityX(C\Node[NodeUsed]),EntityY(C\Node[NodeUsed]),EntityZ(C\Node[NodeUsed]),EntityX(dest)-EntityX(C\Node[NodeUsed]),EntityY(dest),EntityZ(dest)-EntityZ(C\Node[NodeUsed]),1)
		If NodePick
			If NodeUsed+1<100
				Local NX#=EntityX(NodePick)
				Local DX#=EntityX(C\Entity)
				Local DELX#=(DX#-NX#)
				
				Local NZ#=EntityZ(NodePick)
				Local DZ#=EntityZ(C\Entity)
				Local DELZ#=(DZ#-NZ#)
				PositionEntity C\Node[NodeUsed+1],Ceil(EntityX(NodePick)),EntityY(C\Entity),Ceil(EntityZ(NodePick))
				MoveEntity C\Node[NodeUsed+1],PickedNX()*4,0,PickedNZ()*4
				NodedPick=LinePick(Ceil(EntityX(NodePick)),EntityY(C\Entity),Ceil(EntityZ(NodePick)),Ceil(EntityX(NodePick+1))-Ceil(EntityX(NodePick)),EntityY(C\Entity),Ceil(EntityZ(NodePick+1))-Ceil(EntityZ(NodePick)),1)
				UpdateNormals C\Node[NodeUsed+1]
				NodeUsed=NodeUsed+1
			EndIf
		Else
			EntityPickMode Plane,2
			Return NodeUsed
		EndIf
	Until NodeUsed>=99
	EntityPickMode Plane,2
	Return 0 ;Can't resolve it.
End Function