[bb] 3D Pathfinding Lib by 3D [ 1+ years ago ]

BlitzBot · June 29, 2017, 00:28:39

Title : 3D Pathfinding Lib
Author : 3D
Posted : 1+ years ago

Description : Does what it says on the tin

You can download it from here

www.mrpye.com/Blitz

Code :

Code: blitzbasic

Webpage
www.mrpye.com/Blitz/Pathfinding/pathfinding.htm
Download
www.mrpye.com/Blitz/Pathfinding/3DPathFinding1.zip

Comments :

Jeroen(Posted 1+ years ago)

OLD, 404.

3D(Posted 1+ years ago)

There was a problem with the webserver all working again

puki(Posted 1+ years ago)

I'm worried that one day the links will be gone forever.The page is still there: <a href="http://www.mrpye.com/Blitz/" target="_blank">http://www.mrpye.com/Blitz/</a>I've edited the Collision Avoidance demo to use Blitz primitives - so it can run as is.I've renamed the obstacle as 'barrel' rather than 'b' as this might be confusing for a novice - considering the use of the Type 'b' for the bot.I've remarked out the animation and changed the height of the bot.<a href="http://www.blitzbasic.co.nz/logs/userlog.php?user=1673&log=1185" target="_blank">http://www.blitzbasic.co.nz/logs/userlog.php?user=1673&log=1185</a>

Code: BASIC

;==========================
;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(botsMainPiv)
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"
	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 bCActionCount#>0 Then 
		bCActionCancelCount#=bCActionCancelCount#-1;reduce the action count
		If bCActionCancelCount#<-8 Then
			bCActionCount#=0
		End If
	Else
		bCActionCancelCount#=0
	End If
	
	If bCActionCount#>0 Then;see if we are performing an action
		If bCAction=0 Then;turn left
			TurnEntity bMainPiv,0,-TurnSpeedObsticles#,0
		ElseIf bCAction=1 Then;turn rigth
			TurnEntity bMainPiv,0,TurnSpeedObsticles#,0
		End If
		
		;=========================
		;decrease the action count
		;=========================
		bCActionCount#=bCActionCount#-1
		If bCActionCount#<0 Then 
			bCActionCount#=0
		End If
	Else
		;======================
		;see if we hit anything
		;======================
		If result#<>0 Then
			;=========================
			;find out what way to turn
			;=========================
			If DeltaYaw#(bMainPiv,result#)>0 Then 
				bcspeed#=0;stop
				bCAction=0;turn left
				bCActionCount#=Abs(Int(DeltaYaw#(bMainPiv,result#)))*1.5;how long to turn
				If bCActionCount#=<0.1 Then bCActionCount#=45	;make sure it does turn	
			ElseIf DeltaYaw#(bMainPiv,result#)<0 Then
				bcspeed#=0;stop
				bCAction=1;turn rigth
				bCActionCount#=Abs(Int(DeltaYaw#(bMainPiv,result#)))*1.5;how long to turn
				If bCActionCount#=<0.1 Then bCActionCount#=45		;make sure it does turn	
			EndIf
			
			bCActionCancelCount#=0;reset the action cancel
;			AnimateBot b;animate the bot
		Else
			;==============================
			;no collision so move to target
			;==============================
			If DeltaYaw#(bMainPiv,target)>4 Then;0 Then
				TurnEntity bMainPiv,0,TurnSpeedTarget#,0
			ElseIf DeltaYaw#(bMainPiv,target)<-4 Then;0 Then
				TurnEntity bMainPiv,0,-TurnSpeedTarget#,0
			EndIf
			bCAction=3;action is goto the target
;			AnimateBot b		;animate bot
			bcspeed#=bcspeed#+0.1 : If bcspeed#>MAxSpeed# Then bcspeed#=MAxSpeed#;increase speed
		End If
	End If

	MoveEntity bMainPiv,0,0,bcspeed#

End Function

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

;=========================
;function Create Obsticals
;=========================
Function CreateObsticles()
	barrel=CreateCylinder()
	EntityColor barrel,100,100,100 ; line added
;	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
	
	bMainPiv=CreatePivot();create the bot model
	;load the model and setup
	bmodel=CreateCube(bMainPiv)
	EntityColor bmodel,0,0,255 ; line added
	RotateEntity bmodel,0,90,0
	PositionEntity bmodel,0,0,0; he had the height set to -1
	ScaleEntity bmodel,1,2,1
	;set up animation
;	ExtractAnimSeq bmodel,0,30
;	ExtractAnimSeq bmodel,31,100
;	ExtractAnimSeq bmodel,107,107
;	Animate bmodel,1,0.5,1,10
	;set up sensor pivot
	bSenPiv=CreatePivot(bMainPiv);add the sensor pivot
	PositionEntity bSenPiv,0,0,2
	PositionEntity bMainPiv,Rnd(-30,30),0,Rnd(-50,50);random pos
	EntityPickMode bMainPiv,1;set the entity pick
	Return b
End Function


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

psychicbottle(Posted 1+ years ago)

mrpye. i know it been a really long time but i am in the process of bringing blitz3d BACK FROM THE DEAD!

my current game is in need of pathfinding such as the one you have created years ago... i was wondering if you could find it in the good of your heart to contact me and assist me for i am having trouble modifying the code to suit my needs...^i intend to give you full credit by the way, [/i]

Alienhead · February 19, 2022, 18:57:51

Does anyone still have this code ? I'm currently in 3d pathfinding hell and need some examples.

Ty.

EDIT:

Nevermind, found the code on blitzcoder.. it dont work, editor crashes and the code runtimeerrors in the editor.. oh well.

Any advice or examples or a hint in the right direction regarding this topic ? thanks.
And/or has anyone modified the above code so that it actually works outside of the demo he shows ?

I got a node layout editor as shown in the attached pic, what is the prefered method for sorting these 3d nodes for the best path?

Qube · February 20, 2022, 03:41:27

Is this any use for you? - It was originally by Pakz

Code: blitzbasic


Graphics 640,480,32,2
SetBuffer BackBuffer()
Global sx,sy,ex,ey
Global mapwidth = 39
Global mapheight = 29
Global cellwidth = 16
Global cellheight = 16
Dim map(mapwidth,mapheight)
Type ol
        Field x,y,f,g,h,px,py
End Type
Type cl
        Field x,y,f,g,h,px,py
End Type
Type path
        Field x,y
End Type
SeedRnd MilliSecs()
readmap()
 
While KeyDown(1) = False
        Cls
        setcoordinates()
        drawmap()
        tim = MilliSecs()
        findpath()
        tim = MilliSecs()-tim
        drawpath()
        Color 0,0,0
        Rect 0,0,GraphicsWidth(),12,True
        Color 255,0,0
        Text 0,0,"time taken "+tim
        Flip
        Delay 1000
Wend
End
 
Function findpath()
        ; Remove old pathfinding data
        Delete Each ol
        Delete Each cl
        Delete Each path
        ; Move the start position onto the open list
        d.ol = New ol
        dx = sx
        dy = sy
        Local exitloop = False
        Local tx,ty,tf,tg,th,tpx,tpy,newx,newy,lowestf
        While exitloop = False
                ; If the open list is empty then exit loop (path not found)
                If openlistisempty() = True Then exitloop = True
                ; Get the position from the open list with the lowest f value
                lowestf = 100000
                For e.ol = Each ol
                        If ef < lowestf Then
                                lowestf = ef
                                tx = ex
                                ty = ey
                                tf = ef
                                tg = eg
                                th = eh
                                tpx = epx
                                tpy = epy
                        End If
                Next
                ; If the current position is the end position then path is found
                If tx = ex And ty = ey Then
                        exitloop = True
                        f.cl = New cl
                        fx = tx
                        fy = ty
                        ff = tf
                        fg = tf
                        fh = th
                        fpx = tpx
                        fpy = tpy
                        findpathback()
                        Else
                        ; Move the current position to the closed list
                        g.cl = New cl
                        gx = tx
                        gy = ty
                        gf = tf
                        gg = tg
                        gh = th
                        gpx = tpx
                        gpy = tpy
                        ; Remove the current position from the open list
                        removefromopenlist(tx,ty)
                        ; Get the eight positions from around the current position
                        ; and move them to the open list
                        ;
                        For y=-1 To 1
                        For x=-1 To 1
                        newx = tx + x
                        newy = ty + y
                        If newx > -1 And newy > -1 And newx < mapwidth+1 And newy < mapheight+1
                        If isonopenlist(newx,newy) = False Then
                        If isonclosedlist(newx,newy) = False Then
                        If map(newx,newy) = 0 Then
                                h.ol = New ol
                                hx = newx
                                hy = newy
                                hg = tg + 1
                                hh = distance(newx,newy,ex,ey)
                                hf = hg+hh
                                hpx = tx
                                hpy = ty
                        End If
                        End If
                        End If
                        End If
                        Next
                        Next
                       
                End If
        Wend
End Function
 
Function findpathback()
        Local exitloop = False
        x = ex
        y = ey
        While exitloop = False
                For this.cl = Each cl
                        If x = thisx And y = thisy Then
                                x = thispx
                                y = thispy
                                that.path = New path
                                thatx = x
                                thaty = y
                        End If
                Next
                If x = sx And y = sy Then exitloop = True
        Wend
End Function
 
Function drawpath()
        Color 255,255,0
        For this.path = Each path
                Oval thisx*cellwidth+4,thisy*cellheight+4,8,8,True
        Next
End Function
 
Function openlistisempty()
        Local count = 0
        For this.ol = Each ol
                count = count + 1
                If count > 0 Then Return False
        Next
        If count = 0 Then Return True
End Function
 
Function isonclosedlist(x,y)
        For this.cl = Each cl
                If thisx = x And thisy = y Then Return True
        Next
        Return False
End Function
 
Function isonopenlist(x,y)
        For this.ol = Each ol
                If thisx = x And thisy = y Then Return True
        Next
        Return False
End Function
 
Function removefromopenlist(x,y)
        For this.ol = Each ol
                If thisx = x And thisy = y Then
                        Delete this
                        Return
                End If
        Next
End Function
 
Function setcoordinates()
        Local exitloop = False
        While exitloop = False
                sx = Rand(mapwidth)
                sy = Rand(mapheight)
                ex = Rand(mapwidth)
                ey = Rand(mapheight)
                If map(sx,sy) = 0 And map(ex,ey) = 0 Then
                        If sx<>ex And sy<>ey Then
                                exitloop = True
                        End If
                End If
        Wend
End Function
 
Function drawmap()
        Color 0,0,255
        For y = 0 To mapheight
        For x = 0 To mapwidth
                If map(x,y) = 1 Then
                        Rect x*cellwidth,y*cellheight,cellwidth,cellheight,True
                End If
        Next
        Next
        Color 0,255,0
        Oval sx*cellwidth+8,sy*cellheight+8,8,8,True
        Color 255,0,0
        Oval ex*cellwidth+8,ey*cellheight+8,8,8,True
End Function
 
Function readmap()
        Restore level
        For y = 0 To mapheight
        For x = 0 To mapwidth
                Read a
                map(x,y) = a
        Next
        Next
End Function
 
Function distance(x1,y1,x2,y2)
        Return Sqr( ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 ) )
End Function
 
.level
Data 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0
Data 0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0
Data 0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0
Data 0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0
Data 0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0
Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0
Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
Data 0,1,0,1,0,1,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0
Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0
Data 0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0
Data 0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0
Data 0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0
Data 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0
Data 1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1
Data 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
Data 0,0,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
Data 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
Data 0,0,0,1,0,1,1,1,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0
Data 0,0,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0
Data 0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0
Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0
Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0
Data 0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0
Data 0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0
Data 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0

Alienhead · February 20, 2022, 03:57:14

hmm A*. yes I can use that for learning

. That seems to be 2d grid based? im working strictly in 3d non-dynamic, non-quickest path method. More or less a waypoint system that I need to plot paths out of .

For example ( commands ).

GetPath( NodeAt, NodeTo)

this function would return me a tlist of the route to take ... like
node2 > node18 > node19 < TARGETreached

Im just havning no luck in plotting the path based of these numbered nodes in 3d space.

SyntaxBomb - Indie Coders

[bb] 3D Pathfinding Lib by 3D [ 1+ years ago ]

BlitzBot

Alienhead

Qube

Alienhead