SyntaxBomb - Indie Coders

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 :
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>;==========================
;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]

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? 

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


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


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.