3D games usually use 2D pathfinding because at the end of the day, tanks dont fly, if you see what i'm getting at. The point is doing a game in 3D need not complicate your path finding, you can treat it just like 2D.
You're better off writting the pathfinding yourself so that you understand it enough to make it work well for your game, but there's no harm in doing so by learning from existing code examples/libraries.
Path finding is one of the harder things to implement in a game which is why I try to solve it relatively early in the programs development cycle. Better to grin and bear it early than to put it off and never face it.
I usually make my path finding functions in a seperate program using the games actual data but shown onscreen as a 2D map - it helps me tweak the algorythm.
This is a modified A* routine which is quite good for searching routes out of a large heightmap based terrain. You can make extra "blocked" areas for trees & houses simply by painting the colour red(255).
You'll need to change the heightmap file loaded before this sample will run - I last used this for my Paradise Island project so it's trying to load the heightmap from that...
Graphics 512,512,0,2
AppTitle("A*")
Dim mapData(512,512)
Global treeMap=LoadImage("C:\BeckysGames\Paradise Island\Gfx\Terrain\map2.png")
SetBuffer ImageBuffer(treeMap)
For x=0 To 511
For z=0 To 511
GetColor(x,z)
mapData(x,511-z)=ColorRed()
If mapData(x,511-z)=255 Then mapData(x,511-z)=999
Next
Next
SetBuffer BackBuffer()
Type openList
Field x,z
Field parentX,parentZ
Field fSum
Field gCost
Field hGuess
Field mapHeight
End Type
Type closedList
Field x,z
Field parentX,parentZ
End Type
Type AIpath
Field x,z
End Type
sx=256
sz=256
tx=256
tz=256
SeedRnd MilliSecs()
Repeat
strt=MilliSecs()
unit=Rnd(1,5)
route(sx,sz,tx,tz,unit)
time=MilliSecs()-strt
Cls
DrawImage treeMap,0,0
Color 255,255,0
Oval sx,511-sz,3,3,0
Color 0,255,0
Oval tx,511-tz,5,5,0
Color 0,0,255
For n=1 To 5
id=0
For p.AIpath=Each AIpath
id=id+1
If id>1
o.AIpath=Before p
Line p\x,512-p\z, o\x,512-o\z
EndIf
Next
Next
Color 255,255,0
Text 10,10,time+"ms for "+id+" steps"
Flip 0
Repeat
If MouseDown(1)
sX=MouseX()
sZ=512-MouseY()
EndIf
If MouseDown(2)
tX=MouseX()
tZ=512-MouseY()
EndIf
Until KeyDown(17)
;Stop
For clearPath.AIpath=Each AIpath
Delete clearPath
Next
Forever
Function route(sx,sz,tx,tz,id)
node.openList=New openList
node\x=sx : node\z=sz
node\fSum=0 : node\gCost=0
node\hGuess=0
node\mapHeight=mapData(node\x,node\z)
maxNodeRange=(Abs(sx-tx)+Abs(sz-tz))*1.1
searchTime=MilliSecs()+333
Repeat
lowestScore=99999999
nodes=0
For checkNode.openList=Each openList
nodes=nodes+1
If checkNode\fSum<lowestScore
lowestScore=checkNode\fSum
node.openList=checkNode.openList
EndIf
Next
;DebugLog(node\x+"x"+node\z+" = "+node\gCost+" ("+tX+"x"+tZ+") ["+nodes+"]")
;we now have the node to search
If lowestScore=99999999; Or MilliSecs()>searchTime
buildPath=2
Else
If Abs(node\x-tx)<=3 And Abs(node\z-tz)<=3
buildPath=1
Else
For bearing=0 To 359 Step 40
rX#=node\x : rZ#=node\z
range=0
ht=mapData(node\x,node\z)
While range<=5
rX=rX+Cos(bearing)
rZ=rZ+Sin(bearing)
If rX=>0 And rX<=511 And rZ=>0 And rZ<=511
If Int(rX)=tX And Int(rZ)=tZ
range=10
Else
If mapData(rX,rZ)-ht<=4
ht=mapdata(rX,rZ)
range=range+1
Else
range=10
EndIf
EndIf
Else
range=10
EndIf
Wend
sX=rX : sZ=rZ
;*** CORE SYSTEM
If sX=>0 And sX<=511 And sZ=>0 And sZ<=511
If sX<>node\X Or sZ<>node\Z
onClosedList=0
For checkCNode.closedList=Each closedList
If Abs(checkCNode\x-sX)<=1
If Abs(checkCNode\z-sZ)<=1
onClosedList=1
checkCNode.closedList=Last closedList
EndIf
EndIf
Next
If Not onClosedList
onOpenList=0
For checkONode.openList=Each openList
If Abs(checkONode\x-sX)<=1
If Abs(checkONode\z-sZ)<=1
onOpenList=1
If node\gCost+1<checkONode\gCost
If checkONode\mapheight-node\mapHeight<=4
If checkOnode\mapHeight<8 Then cost=10 Else cost=1
checkONode\parentX=node\X
checkONode\parentZ=node\Z
checkONode\gCost=node\gCost+cost
checkONode\fSum=checkONode\gCost+checkONode\hGuess
EndIf
EndIf
checkONode.openList=Last openList
EndIf
EndIf
Next
If Not onOpenList
If mapData(sX,sZ)-node\mapHeight<=4
If node\gCost<maxNodeRange
If mapData(sX,sZ)<8 Then cost=10 Else cost=1
newNode.openList=New openList
newNode\x=sX : newNode\z=sZ
newNode\parentX=node\x : newNode\parentZ=node\z
newNode\gCost=node\gCost+cost
newNode\hGuess=moveHeuristic(sX,sZ,tX,tZ)
newNode\fSum=newNode\gCost+newNode\hGuess
newNode\mapHeight=mapData(sX,sZ)
EndIf
EndIf
EndIf
EndIf
EndIf
EndIf
;*** END CORE SYSTEM
Next
finished.closedList=New closedList
finished\x=node\x : finished\z=node\z
finished\parentX=node\parentX : finished\parentZ=node\parentZ
Delete node.openList
EndIf
EndIf
up=up+1
ms=MilliSecs()
If up=>lastTime-ms
lastTime=ms
up=0
Color 255,255,0
DrawImage treeMap,0,0
For showO.openList=Each openList
Plot showO\x,512-showO\z
Next
Color 0,255,255
For showC.closedList=Each closedList
Plot showC\x,512-showC\z
Next
Color 0,255,0
Oval tx,512-tz,3,3,0
Flip 0
Color 0,0,255
Oval ox,512-oz,5,5,0
EndIf
Until buildPath>0
If buildPath=2
For checkOnode.openList=Each openList
finished.closedList=New closedList
finished\x=checkOnode\x
finished\z=checkOnode\z
finished\parentX=checkOnode\parentX
finished\parentZ=checkOnode\parentZ
Delete checkOnode
Next
nearest=99999999
newTx=tx : newTz=tz
For CheckCnode.closedList=Each closedList
dx#=checkCnode\x-tx
dz#=checkCnode\z-tz
rng=Sqr((dx*dx)+(dz*dz))
If rng<nearest
newTx=checkCnode\x
newTz=checkCnode\z
thisNode.closedList=checkCnode.closedList
nearest=rng
EndIf
Next
path.AIpath=New AIpath
path\x=thisNode\x
path\z=thisNode\z
x=thisNode\parentX
z=thisNode\parentZ
EndIf
If buildPath=1
path.AIpath=New AIpath
path\x=node\x : path\z=node\z
x=node\parentX : z=node\parentZ
Delete node
EndIf
Repeat
For pathnode.closedList=Each closedList
If x=pathnode\x And z=pathnode\z
path.AIPath=New AIPath
path\x=x
path\z=z
x=pathnode\parentX
z=pathnode\parentZ
Delete pathNode
EndIf
Next
Until x=0 And z=0
For clearOList.openList=Each openList
Delete clearOList
Next
For clearCList.closedList=Each closedList
Delete clearCList
Next
End Function
;Function moveHeuristic(sX,sZ,tX,tZ)
; difX=Abs(sX-tX)
; difZ=Abs(sZ-tZ)
; If difX>difZ
; Return difZ+(difX*3)
; Else
; Return difX+(difZ*3)
; EndIf
;End Function
;Function moveHeuristic(sX,sZ,tX,tZ)
; dx#=sX-tX
; dz#=sZ-tZ
; Return Sqr((dx*dx)+(dz*dz))
;End Function
Function moveHeuristic(sX,sZ,tX,tZ)
Return (Abs(sX-tX)+Abs(sZ-tZ))*2
End Function
|