NewsForumsCodeLogsGallerySpecsSearch

Path finding Ai

Blitz3D Forums/Blitz3D Beginners Area/Path finding Ai

Ben(t)(Posted 2007) [#1]
I have a unit that runs at my character, it points at them and then just runs, but I'm having trouble getting the unit to go around solid objects, right now it just runs in to them


mindstorms(Posted 2007) [#2]
You could implement any one of the pathfinding algorithms on this site, or if the obstacle is simple, you could implement something similar to mrpye´s "Collision Avoidance V2", in which he basically used a thick linepick to "see" what is ahead of the characters.


puki(Posted 2007) [#3]
What "mindstorms" is referring to is collision avoidance - although, it can be combined with pathfinding.

This is the Collision Avoidance V2 code he was referring too - I've amended the code so that you can run it without the external media.

; this internal media version by puki
;;==========================
;Collision Avodance Demo v2
;By Andrew Pye AKA(3D)
;Date: 25/06/2004
;==========================
;=======================================================================
;Well at last I have come up with something that is
;simple and works well.
;The system works by using line pick with a large radius.
;If line pick picks up an entity then based on is pos it make a 
;decision  which way to turn and for how long.
;If there is no entity then head towards the target.
;But you will have to take a look through the code for all the details.
;
;Feel free to use the code in your own projects 
;But if you do just give us a little mention.
;=======================================================================

;=================
;set up enviroment
;=================
Graphics3D 640, 480,16,0
;Graphics3D 800, 600,32,0
light = CreateLight()

;=======
;globals
;=======
;======================
;Play with these values 
;======================
Global BotCount=30;number of bots
Global ObjticlesCount=50;number of obsticles
Global MAxSpeed#=0.5;speed of bots
Global TurnSpeedObsticles#=4;how fast to turn towards obsticles
Global TurnSpeedTarget#=2;how fast to turn towards target
Global SensterWidth#=1.5;how wide to check for collisions

;=====
;Types
;=====
Type Bot
	Field MainPiv,CActionCancelCount,CAction,model,CAnimationTime#
	Field SenPiv,cspeed#,CActionCount#
End Type

;======================
;create our target node
;======================
Global Target=CreateSphere()
EntityColor Target,255,0,0

;===============
;Create the bots
;===============
For i=0 To BotCount
	bots.bot=CreateBot()
Next

;store current view
Global CView

;============================================
;Create camera and attach to last created bot
;============================================
Global camera= CreateCamera(bots\MainPiv)
PositionEntity camera,0,3.6,0;raise a little

;================
;create obsticals
;================
For i=0 To ObjticlesCount
	CreateObsticles()
Next

;==========
;set up fps
;==========
Const FPS=30
period=1000/FPS
time=MilliSecs()-period

;=========
;main loop
;=========
Repeat
			
	;=======================
	;time the frames per sec
	;=======================
	Repeat
		elapsed=MilliSecs()-time
	Until elapsed
	;how many 'frames' have elapsed	
	ticks=elapsed/period
	;fractional remainder
	tween#=Float(elapsed Mod period)/Float(period)
	If KeyHit(16) Then PositionEntity Target,Rnd(-150,150),0,Rnd(-150,150)
	If KeyHit(17) Then 
		If CView=0 Then
			PositionEntity camera,0,30,0
			RotateEntity camera,90,0,0
			CView=1
		ElseIf CView=1 Then
			PositionEntity camera,0,60,0
			RotateEntity camera,90,0,0
			CView=2
		ElseIf CView=2 Then
			PositionEntity camera,0,3.6,0
			RotateEntity camera,0,0,0
			CView=0
		End If
	End If

	
	For k=1 To ticks
		time=time+period
		If k=ticks Then CaptureWorld
		;===============
		;Ai for each bot
		;===============
		For b.bot = Each bot :BotAi b :Next
	Next
	
	UpdateWorld
	RenderWorld tween
	
	Text 1,1,"Collision Avoidance Demo V2 - this internal media version by puki"
	Text 1,15,"BY Andrew Pye"
	Text 1,30,"25/06/2004"
	Text 1,45,"Press (Q) to chage the Target"
	Text 1,60,"Press (W) to chage the View"
	Flip
	
Until KeyHit(1)
End

;======
;bot ai
;======
Function BotAi(b.bot)
	
	;================================
	;test to see if anything in front
	;================================
	result#=TestSensor(b);test sensor
	
	;=====================================
	;Check if to reset the action count
	;=====================================
	If result#=0 And b\CActionCount#>0 Then 
		b\CActionCancelCount#=b\CActionCancelCount#-1;reduce the action count
		If b\CActionCancelCount#<-8 Then
			b\CActionCount#=0
		End If
	Else
		b\CActionCancelCount#=0
	End If
	
	If b\CActionCount#>0 Then;see if we are performing an action
		If b\CAction=0 Then;turn left
			TurnEntity b\MainPiv,0,-TurnSpeedObsticles#,0
		ElseIf b\CAction=1 Then;turn rigth
			TurnEntity b\MainPiv,0,TurnSpeedObsticles#,0
		End If
		
		;=========================
		;decrease the action count
		;=========================
		b\CActionCount#=b\CActionCount#-1
		If b\CActionCount#<0 Then 
			b\CActionCount#=0
		End If
	Else
		;======================
		;see if we hit anything
		;======================
		If result#<>0 Then
			;=========================
			;find out what way to turn
			;=========================
			If DeltaYaw#(b\MainPiv,result#)>0 Then 
				b\cspeed#=0;stop
				b\CAction=0;turn left
				b\CActionCount#=Abs(Int(DeltaYaw#(b\MainPiv,result#)))*1.5;how long to turn
				If b\CActionCount#=<0.1 Then b\CActionCount#=45	;make sure it does turn	
			ElseIf DeltaYaw#(b\MainPiv,result#)<0 Then
				b\cspeed#=0;stop
				b\CAction=1;turn rigth
				b\CActionCount#=Abs(Int(DeltaYaw#(b\MainPiv,result#)))*1.5;how long to turn
				If b\CActionCount#=<0.1 Then b\CActionCount#=45		;make sure it does turn	
			EndIf
			
			b\CActionCancelCount#=0;reset the action cancel
;			AnimateBot b;animate the bot
		Else
			;==============================
			;no collision so move to target
			;==============================
			If DeltaYaw#(b\MainPiv,target)>4 Then;0 Then
				TurnEntity b\MainPiv,0,TurnSpeedTarget#,0
			ElseIf DeltaYaw#(b\MainPiv,target)<-4 Then;0 Then
				TurnEntity b\MainPiv,0,-TurnSpeedTarget#,0
			EndIf
			b\CAction=3;action is goto the target
;			AnimateBot b		;animate bot
			b\cspeed#=b\cspeed#+0.1 : If b\cspeed#>MAxSpeed# Then b\cspeed#=MAxSpeed#;increase speed
		End If
	End If

	MoveEntity b\MainPiv,0,0,b\cspeed#

End Function

;===============
;animate the bot
;===============
Function AnimateBot(b.bot)
	b\CAnimationTime#=b\CAnimationTime#+MAxSpeed#*2.6
	If b\CAnimationTime#>30 Then b\CAnimationTime#=0
	SetAnimTime b\model,b\CAnimationTime#
End Function

;=========================
;function Create Obsticals
;=========================
Function CreateObsticles()
	barrel=CreateCylinder()
	EntityColor barrel,100,100,100 ; line added
	ScaleEntity barrel,2,2,2
;	ScaleEntity barrel,0.1,0.1,0.1
	EntityPickMode barrel,1;set the entity pick
	PositionEntity barrel,Rnd(-100,100),0,Rnd(-100,100);random pos
	Return barrel
End Function

;===================
;function create bot
;===================
Function CreateBot.bot()
	b.bot=New bot
	
	b\MainPiv=CreatePivot();create the bot model
	;load the model and setup
	b\model=CreateCube(b\MainPiv)
	EntityColor b\model,0,0,255 ; line added
	RotateEntity b\model,0,90,0
	PositionEntity b\model,0,0,0; he had the height set to -1
	ScaleEntity b\model,1,2,1
	;set up animation
;	ExtractAnimSeq b\model,0,30
;	ExtractAnimSeq b\model,31,100
;	ExtractAnimSeq b\model,107,107
;	Animate b\model,1,0.5,1,10
	;set up sensor pivot
	b\SenPiv=CreatePivot(b\MainPiv);add the sensor pivot
	PositionEntity b\SenPiv,0,0,2
	PositionEntity b\MainPiv,Rnd(-30,30),0,Rnd(-50,50);random pos
	EntityPickMode b\MainPiv,1;set the entity pick
	Return b
End Function

;==================
;test for collision
;==================
Function TestSensor(b.bot)
	;see if touching anything
	SenObjId=LinePick( EntityX(b\MainPiv), EntityY(b\MainPiv),EntityZ(b\MainPiv),EntityX(b\SenPiv,True)-EntityX(b\MainPiv), EntityY(b\SenPiv,True)-EntityY(b\MainPiv),EntityZ(b\SenPiv,True)-EntityZ(b\MainPiv), SensterWidth#)  
	Return SenObjId
End Function



chwaga(Posted 2007) [#4]
i was wondering how to do that too...the problem with that code is that it's too picky, more than half of it has to be reverse-engineered before adding to a game


Ben(t)(Posted 2007) [#5]
I just need something that will tell a unit to turn out of the way so that it will go the shortest turning distance to find it's target


Ben(t)(Posted 2007) [#6]
I have motion and turning speed already implemented I just need a function (or something) that will tell the bot how to turn


mindstorms(Posted 2007) [#7]
Like I said, you can either generate a list of waypoints and use deltayaw to go toward those, or you can use a linepick and determine what is in front of the bot, then decide what to do.

In my game, I am using a combination of both, using the second method to get to the waypoints, allowing for avoiding moving things without having to update a 'no go' map and the waypoints each frame (as well as making the waypoints farther apart)

Chwaga: I disagree, the only thing that needs to be worked out are the two variables cactionCount and cActionCancelCount, and all they do is make sure that the bot does not get stuck turning one way to avoid something one frame and the next turning back to follow the target...to be more specific, action Count will slowly count down each frame, but if the bot is no longer colliding cancel action count will decrease as well. This means that the bot will turn 8 frames after it stops colliding, giving the bot distance between itself and the barrel.


mindstorms(Posted 2007) [#8]
this is actually closer to what I use, I replaced cActionCount with cDoAction, which is turned on by collisions and turned off by cActionCancel, because cActionCount was redundant.




IPete2(Posted 2007) [#9]
Nice stuff guys, I like your thinking.

IPete2.


Pete Carter(Posted 2007) [#10]
this has helped me a great deal, i need this for my NPCs in my syndicate game when they are walking a path and meet people walking the other direction. the only thing is the i would have to make the diverted character correct his course a bit quicker and not have quite such a big turning circle.


blade007(Posted 2007) [#11]
u can just make him go backwards


Pete Carter(Posted 2007) [#12]
what?