I have a little coding puzzle that I can't solve

Blitz3D Forums/Blitz3D Programming/I have a little coding puzzle that I can't solve

GIB3D

(Posted 2010) [#1]

I'm trying to make my own pathfinding system but am stuck because of this. I can't wrap my mind around this one. How would you do this in code?

The first number is the starting pathnode

1,1,1
1,2,1
1,3,1
1,1,2
1,2,2
1,3,2
1,1,3
1,2,3
1,3,3

The size of that will depend on how many nodes there are. Each number is a node_id. Once this puzzle is solved I will be able to make it faster by stopping it from adding on more numbers if there is a duplicate number.

Also, I tried searching on google but I couldn't find anything mainly because I'm not sure what to search for.

Just to show you what I'm working with, here is the code.

;1,1,1
;1,2,1
;1,3,1
;1,1,2
;1,2,2
;1,2,3
;1,3,1
;1,3,2
;1,3,3

Const Size = 3

For n = 1 To Size
	AddNode
Next

Print "NodeCount = " + GetNodeID()
Print "NodeLoops = " + (GetNodeID()^2)

CreatePath(1,1,GetNodeID())
PrintPaths()

Type Node
	Field ID
End Type

Function AddNode()
	Local a.Node = New Node
	
	a\ID = GetNodeID()
End Function

Function GetNodeID()
	Local a.Node
	Local Number
	
	For a = Each Node
		Number=Number+1
	Next
	
	Return Number
End Function


Type Path
	Field Group$
	Field ID
	Field Element$
End Type

Function CreatePath(group$,source_node_id$,dest_node_id$)
	For x = 1 To Size
		Local a.Path = New Path
		
		a\Group = group
		a\ID = GetPathID()
		;a\Element = source_node_id+"->"
	Next
	
	Local Number
	Local n = GetPathID()
	
	For a = Each Path
		
		For x = 1 To Size-1
			Number = Number + 1
			a\Element = AddElement(a\Element,Number)
		Next
		
		a\Element = 1+a\Element
	Next
End Function

Function AddElement$(element$,start_id$)
	element = "->"+start_id+element
;	Repeat
;		If KeyHit(1) End
;		For x = 1 To Size
;			If Not Instr(element,x+"->")
;				element = element+x+"->"
;;				Print element
;;				Delay(300)
;			EndIf
;		Next
;	Until Instr(element,end_id+"->")
	
	Return element
End Function

Function GetPathID()
	Local a.Path
	Local Number
	
	For a = Each Path
		Number=Number+1
	Next
	
	Return Number
End Function

Function PrintPaths()
	Local a.Path
	
	For a = Each Path
		Print a\Element
	Next
End Function

WaitKey
End

Jiffy

(Posted 2010) [#2]

I'm not sure what you're doing, but I think you're going about it the wrong way. You're mapping out an exponential growth in complexity each time you add a node.
You may need to look at the problem differently- or at least find a way to quickly cull invalid nodes.

GIB3D

(Posted 2010) [#3]

Well at the moment I need to be able to make a big list of every possible path an object can take first. Each line would be the Type called Path. Each number within the Path is the Type Element which stores its parent node. Then after I'm able to do that I'll stop it from creating the paths if it finds a duplicate node in the list. What I originally had was 3D but sometimes I have to start fresh so I can try to actually code what I need instead of worrying about how it looks on-screen.

This is partly where I'm getting some of my information http://ai-depot.com/Tutorial/PathFinding.html

The difference between what I'm doing and what they have is Neighbors. None of my nodes are connected because I do not know how to find the Neighbor of a node and connect them dynamically.

Jiffy

(Posted 2010) [#4]

I find that tutorial confusing. I suggest

http://www.policyalmanac.org/games/aStarTutorial.htm

about 7 versions exist here:

http://blitzbasic.com/codearcs/codearcs.php?cat=6

search for 'path'

xlsior

(Posted 2010) [#5]

A full map of possible nodes does get exponentially large -- depending on how you define a 'node' (waypoint? Walkable terrain tile?) the total map could end up being gigabytes in size, or even larger.

GIB3D

(Posted 2010) [#6]

I found that policymanac.org tutorial extremely confusing when trying to change anything in it. It's a grid based system which I don't want and it does some funky Binary Dump stuff that I don't completely understand. I'm wanting the pathfinding system to be more like how Half-Life 2 and Unreal Tournament 3 do it. If you've ever used either of their map editors you would know that they both use User Placed Path Nodes. Without the path nodes, the AI are extremely dumb when it comes to moving around.

Jiffy

(Posted 2010) [#7]

Node paths are artificial & only work on fixed maps with specific game dynamics. Better & faster if that's what you need, but prone to occasional issues & ignorant to new game dynamics. Try spawning a vehicle on a map not designed to have one & block off a path- see what the AI does. I hope it can tell, but I doubt it. UT3 pathing used to be pretty buggy- don't know if it's cleaned up or not.

Anyway, try modifying

http://blitzbasic.com/codearcs/codearcs.php?code=968
or
http://blitzbasic.com/codearcs/codearcs.php?code=1825

as starter waypoint systems. puki did the first one & he's about- maybe he'll answer q's you have about it.

You gonna eat that thing or what?

GIB3D

(Posted 2010) [#8]

I know node paths are on fixed maps and can't be put in later. I also noticed in the Unreal Editor that you can see the node's connections before you even test the map. So in some way, I'm probably going about this wrong because I "need" to connect the nodes. I'll take a look at the links you posted.

Edit:
I took a look at the links. The first one is good, the second one I have already seen but thanks anyways. I'm going to code in a neighbor system now and hopefully I can actually get some good pathfinding working. I guess what I'll do is limit each node to finding Four nodes near it.

Pseudo Code

Type Node
Field T_Neighbor.Node[3]
End Type

I'll just add that into my code and work on it from there and post back here if I get it working.

GIB3D

(Posted 2010) [#9]

:)

It's not much yet but it's a simple neighboring demo. The big red block is literally a block. A LinePick checks if you can safely travel straight to that node without hitting things. The LinePick is also effected by nodes too. Nodes are pickable so that you don't have a lot of nodes in one place being picked.

Use keys 1 through 0 to change which neighbors are displayed.
The 0 key is for the first node. Don't blame me, blame ASCII.

Graphics3D 1024,768,32,2
SetBuffer BackBuffer()
SeedRnd MilliSecs()

Const I_NodeNeighbors = 3

Const Col_Player = 1
Const Col_Block = 2

Collisions Col_Player,Col_Block,2,2


Global DisplayNodeNeighbors
Global NodeID,PathFindingID

CreateLight()

Global Pivot = CreatePivot()

Global Camera = CreateCamera(Pivot)
PositionEntity Camera,0,16,-15
CameraRange Camera,.1,1000
BP_SetCamFOV Camera,70

Global Sphere[1]
For n = 0 To 1
	Sphere[n] = CreateSphere()
	EntityOrder Sphere[n],-1
	EntityColor Sphere[n],180*n+100,1*n+100,10*n+100
	HideEntity Sphere[n]
Next

Global T_Player.TYPE_Player = FUNC_Create_Player(0,0)
Global PathDistance

EntityTexture CreatePlane(),GTexture(256)

CreateNodes(0,4)

Local Font = LoadFont("Impact",22)
SetFont Font

While Not KeyDown(1)
	TurnEntity Pivot,0,(KeyDown(205)-KeyDown(203)),0
	PointEntity Camera,T_Player\E_Point
	
	FUNC_Update_Player()
	
	UpdateWorld
	RenderWorld
	
	FUNC_Node_CameraProject(Camera)
	Color 0,255,120
	FUNC_Path_CameraProject(Camera)
	
	If Handle(T_Player\T_PathFinding) <> 0
		Text 0,0,T_Player\T_PathFinding\S_Group
		Text 0,20,FUNC_PathFinding_GetFullPath(T_Player\T_PathFinding\S_Group)
		Text 0,40,PathDistance
	EndIf
	
	Flip
Wend
End

Function CreateNodes(x,z)
	;[Block] Create block
	Local Block = CreateCube()
	PositionEntity Block,x-1,2.01,z+4
	ScaleEntity Block,3.95,2,.95
	EntityAlpha Block,.4
	EntityFX Block,16
	EntityType Block,Col_Block
	EntityPickMode Block,2
	Local Texture = GTexture(256,200,60,60,4,8,.625,.5625)
	
	SetBuffer TextureBuffer(Texture)
	Color 0,0,0
	Text TextureWidth(Texture)*.5,TextureHeight(Texture)*.5,"B",1,1
	SetBuffer BackBuffer()
	
	EntityTexture Block,Texture
	;[End]
	
	FUNC_Create_Node(x,z)		;1
	FUNC_Create_Node(x-2,z+6)	;2
	FUNC_Create_Node(x+4,z+4)	;3
	FUNC_Create_Node(x-6,z)		;4
	FUNC_Create_Node(x-8,z+8)	;5
	FUNC_Create_Node(x-2,z+10)	;6
	FUNC_Create_Node(x+1,z+12)	;7
	FUNC_Create_Node(x+6,z)		;8
	FUNC_Create_Node(x+6,z+8)	;9
	FUNC_Create_Node(x-2,z+14)	;10
	
	FUNC_Node_AssignNeighbors()
End Function



Type TYPE_Player
	Field E_Point
	
	Field S_PathGroup$
	Field T_PathFinding.TYPE_PathFinding
	Field T_Node.TYPE_Node
End Type

Function FUNC_Create_Player.TYPE_Player(x#,z#)
	Local a.TYPE_Player = New TYPE_Player
		a\S_PathGroup = Handle(a)
		a\E_Point = CreateCube()
		
		PositionEntity a\E_Point,x,1,z
		PointEntity Camera,a\E_Point
		EntityTexture a\E_Point,GTexture(64,10,10,200,1,1)
		EntityType a\E_Point,Col_Player
	Return a
End Function

Function FUNC_Update_Player()
	Local a.TYPE_Player
	Local Yaw#
	Local Key[1]
	
	Key[0] = KeyDown(57)
;	Key[1] = KeyHit(200)
	
	For a = Each TYPE_Player
		If Key[0]
;			If Handle(a\T_Node) <> 0
;				Yaw = DeltaYaw(a\E_Point,a\T_Node\E_Point)
;				TurnEntity a\E_Point,0,Yaw*.05,0
;				MoveEntity a\E_Point,0,0,(1.0/(Abs(Yaw)+.5))*2
				
;				If Handle(a\T_Node)
;					If EntityDistance(a\E_Point,a\T_Node\E_Point) <= 2
;						If Handle(a\T_PathFinding\T_Node) = Handle(a\T_Node)
;							If Handle(a\T_PathFinding)
;								a\T_Node = Null
;								FUNC_Delete_PathFinding(a\T_PathFinding)
;							EndIf
							
	;						a\T_PathFinding = FUNC_FindShortestPath(a\E_Point,Rand(1,6))
							
	;						b = FUNC_PathFinding_GetCurrentNode(a\T_PathFinding)
	;						
	;						If Handle(b)
	;							PathDistance = FUNC_PathFinding_GetDistance(a\T_PathFinding\S_Group)
	;							a\T_Node = b
	;							FUNC_Node_Paint(a\T_Node)
	;						EndIf
						Else
	;						b = FUNC_PathFinding_GetNextNode(a\T_PathFinding)
	;						DebugLog "Next Node " + Handle(b)
	;						
	;						If Handle(b)
	;							PathDistance = FUNC_PathFinding_GetDistance(a\T_PathFinding\S_Group)
	;							
	;							a\T_Node = b
	;							FUNC_Node_Paint(a\T_Node)
	;						EndIf
;						EndIf
;					EndIf
;				EndIf
;			EndIf
		EndIf
		
		Key[1] = GetKey()
		If Key[1] => 48 And Key[1] =< 57
			DisplayNodeNeighbors = Key[1]-47
;			FUNC_Player_FindPath(a,Key[1]-48)
		EndIf
;		If Key[1]
;			FUNC_Player_FindPath(a,10)
;		EndIf
	Next
End Function

Function FUNC_Player_FindPath(a.TYPE_Player,dest_node_id)
;	Local b.TYPE_Node
;	
;	If Handle(a\T_PathFinding)
;		a\T_Node = Null
;		FUNC_Delete_PathFinding(a\T_PathFinding)
;	EndIf
;	
;	DebugLog "FindPath"
;	a\T_PathFinding = FUNC_FindShortestPath(a\E_Point,dest_node_id)
;	
;	If Handle(a\T_PathFinding)
;		b = FUNC_PathFinding_GetCurrentNode(a\T_PathFinding)
;		
;		If Handle(b)
;			;PathDistance = FUNC_PathFinding_GetDistance(a\T_PathFinding\S_Group)
;			a\T_Node = b
;			FUNC_Node_Paint(a\T_Node)
;		EndIf
;	EndIf
End Function


;Select a node to start finding a path on
;Find other nodes but make sure they aren't already selected in this path
;Also, make sure the path doesn't lead into an object by using LinePick

;1. Choose a node to start making a path with
;2. Repeatedly select the next node to branch to
;3. If the branch ends up having the destination node then stop that path
;4. After finding all the branches, calculate which one is the shortest
;If more than one are the shortest, choose the first shortest path

Function FUNC_FindShortestPath.TYPE_PathFinding(entity,dest_node_id)
	DebugLog "FUNC_FindShortestPath dest_node_id = " + dest_node_id
	
	Local a.TYPE_PathFinding = New TYPE_PathFinding
	
	a\S_Group = FUNC_PathFinding_GetNewID()
	a\T_StartNode = FUNC_Node_GetNearest(entity)
	a\T_EndNode = FUNC_Node_GetNode(dest_node_id)
	
	FUNC_Path_CreateBranch(a\S_Group,a\T_StartNode,a\T_EndNode)
	
	Return a
End Function


Type TYPE_Node
	Field E_Point
	Field I_ID
	
	Field T_Neighbor.TYPE_Node[I_NodeNeighbors]
End Type

Function FUNC_Create_Node.TYPE_Node(x#,z#)
	Local a.TYPE_Node = New TYPE_Node
		a\E_Point = CreateCube()
		a\I_ID = FUNC_Node_GetNewID()
		
		EntityPickMode a\E_Point,1
		NameEntity a\E_Point,a\I_ID
		PositionEntity a\E_Point,x,1,z
		ScaleMesh a\E_Point,1,.91,1
		EntityTexture a\E_Point,GTexture(256,200,200,60,1,1,0,0)
	Return a
End Function

Function FUNC_Node_GetNewID()
	NodeID=NodeID+1
	Return NodeID
End Function

Function FUNC_Node_Count()
	Local a.TYPE_Node
	Local Number
	
	For a = Each TYPE_Node
		Number = Number + 1
	Next
	
	Return Number
End Function

Function FUNC_Node_GetNode.TYPE_Node(id)
	Local a.TYPE_Node
	
	For a = Each TYPE_Node
		If a\I_ID = id
			Return a
		EndIf
	Next
End Function

Function FUNC_Node_GetNearest.TYPE_Node(entity,exclusive=0)
	Local a.TYPE_Node
	Local Distance#=99999999,D#,b.TYPE_Node
	
	For a = Each TYPE_Node
		If Handle(a) <> Handle(b)
			D = EntityDistance(a\E_Point,entity)
			
			If D > exclusive
				If D < Distance
					Distance = D
					b = a
				EndIf
			EndIf
		EndIf
	Next
	
	If Handle(b) <> 0 Return b
End Function

Function FUNC_Node_AssignNeighbors()
	Local a.TYPE_Node
	
	For a = Each TYPE_Node
		FUNC_Node_SetShortestNeighbor(a)
	Next
End Function

Function FUNC_Node_SetShortestNeighbor(a.TYPE_Node)
	Local b.TYPE_Node
	Local Distance# = 999999,D#
	
	For y = 0 To I_NodeNeighbors ; Search the shortest distance for each Neighbor node slot
		Distance = 999999
		
		For b = Each TYPE_Node
			If b <> a ; Make sure this node doesn't set itself as a neighbor
				If Not FUNC_Node_NodeIsNeighbor(a,b) ; Make sure the node isn't already a neighbor
					If b <> a\T_Neighbor[z]
						If EntityLinePick(a\E_Point,b\E_Point) = b\E_Point ; Finally, make sure you can go directly from the first node to this node without a collision
							D = EntityDistance(a\E_Point,b\E_Point)
							
							If D < Distance
								Distance = D
								a\T_Neighbor[y] = b
							EndIf
						EndIf
					EndIf
				EndIf
			EndIf
		Next
	Next
End Function

Function FUNC_Node_NodeIsNeighbor(a.TYPE_Node,b.TYPE_Node) ; Checks if the inputed node is already a neighbor
	For n = 0 To I_NodeNeighbors
		If Handle(a\T_Neighbor[n])
			If a\T_Neighbor[n] = b
				Return True
			EndIf
		EndIf
	Next
End Function

Function FUNC_Node_Paint(b.TYPE_Node)
	Local a.TYPE_Node
	
	For a = Each TYPE_Node
		EntityColor a\E_Point,255,255,255
	Next
	
	If Handle(b) EntityColor b\E_Point,255,0,0
End Function

Function FUNC_Node_CameraProject(camera)
	Local a.TYPE_Node
	Local X,Y
	
	For a = Each TYPE_Node
		If EntityInView(a\E_Point,camera)
			Color 255,120,0
			
			CameraProject camera,EntityX(a\E_Point,1),EntityY(a\E_Point,1),EntityZ(a\E_Point,1)
			X = ProjectedX()
			Y = ProjectedY()
			Text X,Y-30,a\I_ID,1,1
			
			If a\I_ID = DisplayNodeNeighbors
				Color 255,10,0
				
				For n = 0 To I_NodeNeighbors
					If Handle(a\T_Neighbor[n])
						CameraProject camera,EntityX(a\T_Neighbor[n]\E_Point,1),EntityY(a\T_Neighbor[n]\E_Point,1),EntityZ(a\T_Neighbor[n]\E_Point,1)
						Line X,Y,ProjectedX(),ProjectedY()
						Text ProjectedX()+30,ProjectedY()-70,n,0,1
					EndIf
				Next
			EndIf
		EndIf
	Next
	
	Color 255,120,0
End Function


Type TYPE_PathFinding
	Field S_Group$
	Field T_StartNode.TYPE_Node
	Field T_EndNode.TYPE_Node
End Type

Function FUNC_Create_PathFinding.TYPE_PathFinding(source_node_id,dest_node_id)
	If source_node_id <> dest_node_id
		Local a.TYPE_PathFinding = New TYPE_PathFinding
			a\S_Group = FUNC_PathFinding_GetNewID()
			
			a\T_StartNode = FUNC_Node_GetNode(source_node_id)
			a\T_EndNode = FUNC_Node_GetNode(dest_node_id)
		Return a
	EndIf
End Function

Function FUNC_PathFinding_GetNewID()
	PathFindingID=PathFindingID+1
	Return PathFindingID
End Function

Function FUNC_PathFinding_GetFullPath$(group$)
	Local a.TYPE_Path
	Local Path$
	
	For a = Each TYPE_Path
		If a\S_Group = group
			Path = Path + a\I_ID + ","
		EndIf
	Next
	
	Return Path
End Function

Function FUNC_PathFinding_GetCurrentNode.TYPE_Node(a.TYPE_PathFinding)
;	Return FUNC_Path_GetNodeByIndex(a\S_Group)
End Function

Function FUNC_PathFinding_GetNextNode.TYPE_Node(a.TYPE_PathFinding)
;	FUNC_Delete_Path_ByCurrent(a\S_Group)
;	
;	Local b.TYPE_Node = FUNC_Path_GetNodeByIndex(a\S_Group,1)
;	DebugLog "GetNextNode = " + Handle(b)
;	Return b
End Function

Function FUNC_Delete_PathFinding(a.TYPE_PathFinding)
	FUNC_Delete_Path_ByGroup(a\S_Group)
	Delete a
End Function


Type TYPE_Path ; Stores a branch group
	Field S_Group$
	
	Field I_ID
End Type

Function FUNC_Create_Path.TYPE_Path(group$)
	Local a.TYPE_Path = New TYPE_Path
		a\S_Group = group
		a\I_ID = FUNC_Path_GetNewID(group)
		
		DebugLog "Path = " + a\S_Group + "(" + a\I_ID + ")"
	Return a
End Function

Function FUNC_Path_CreateBranch(group$,start_node.TYPE_Node,end_node.TYPE_Node)
	Local a.TYPE_Path,b.TYPE_PathElement,c.TYPE_PathElement,d.TYPE_Node,e.TYPE_Node
	
	For d = Each TYPE_Node
		a = FUNC_Create_Path(group) ; Create a new path branch
		b = FUNC_Create_PathElement(a,start_node,Null) ; Since the first element is known, it is placed first
		
		c = FUNC_Path_CheckPlaceElement(a,b)
		
		If Handle(c)
			DebugLog b\T_Node\I_ID+"->"+c\T_Node\I_ID
		Else
			DebugLog "Diggy"
		EndIf
	Next
End Function

Function FUNC_Path_CheckPlaceElement.TYPE_PathElement(a.TYPE_Path,b.TYPE_PathElement)
	Local d.TYPE_Node
	Local Pick
	
	For d = Each TYPE_Node ; Go through all the nodes and place valid nodes into the branch
		If Not Handle(FUNC_PathElement_GetByNodeID(a\S_Group,a\I_ID,d\I_ID)) ; Make sure duplicate nodes are put into the branch
			;Pick = EntityLinePick(b\T_Node\E_Point,d\E_Point)
			
			;If Not Pick ; Checks if there's an object between the parent element and the destination element
				b = FUNC_Create_PathElement(a,d,b)
				Return b
			;Else
			;	DebugLog "BadNodeID = " + d\I_ID
			;EndIf
		EndIf
	Next
End Function

Function FUNC_Path_GetNewID(group$)
	Local a.TYPE_Path
	Local Number
	
	For a = Each TYPE_Path
		If a\S_Group = group
			Number = Number + 1
		EndIf
	Next
	
	Return Number
End Function

Function FUNC_Path_GetDistance#(group$,id)
	Local a.TYPE_Path,b.TYPE_PathElement
	Local Index
	Local Distance#
	
	;Finds the last element in a path and steps backwards to get the distance
	;Each element holds a handle to the parent element it is connected to
	
	a = FUNC_Path_GetByGroup(group,id)
	
	If Handle(a)
		Index = FUNC_PathElement_Count(group,id)
		
		b = FUNC_PathElement_GetByIndex(group,id,Index)
			Repeat
				If Handle(b\T_Parent)
					Distance = Distance + EntityDistance(b\T_Node\E_Point,b\T_Parent\T_Node\E_Point)
					b = b\T_Parent
				Else
					Exit
				EndIf
			Forever
			
		Return Distance
	EndIf
End Function

Function FUNC_Path_GetByGroup.TYPE_Path(group$,id)
	Local a.TYPE_Path
	
	For a = Each TYPE_Path
		If a\S_Group = group
			Return a
		EndIf
	Next
End Function

Function FUNC_Delete_Path_ByGroup(group$)
	Local a.TYPE_Path
	
	For a = Each TYPE_Path
		If a\S_Group = group
			Delete a
		EndIf
	Next
End Function

Function FUNC_Path_CameraProject(camera)
;	Local a.TYPE_Path
;	
;	For a = Each TYPE_Path
;		If Handle(a\T_Node)
;			If EntityInView(a\T_Node\E_Point,camera)
;				CameraProject camera,EntityX(a\T_Node\E_Point,1),EntityY(a\T_Node\E_Point,1),EntityZ(a\T_Node\E_Point,1)
;				
;				Text ProjectedX(),ProjectedY(),a\I_ID,1,1
;			EndIf
;		EndIf
;	Next
End Function


Type TYPE_PathElement ; Stores a piece of a branch in a path
	Field I_ID
	
	Field T_Group.TYPE_Path
	Field T_Node.TYPE_Node
	Field T_Parent.TYPE_PathElement
End Type

Function FUNC_Create_PathElement.TYPE_PathElement(b.TYPE_Path,c.TYPE_Node,parent.TYPE_PathElement)
	Local a.TYPE_PathElement = New TYPE_PathElement
		a\T_Group = b
		a\T_Node = c
		
		a\I_ID = FUNC_PathElement_GetNewID(a\T_Group)
	Return a
End Function

Function FUNC_PathElement_GetNewID(b.TYPE_Path)
	Local a.TYPE_PathElement
	Local Number
	
	For a = Each TYPE_PathElement
		If a\T_Group = b
			Number = Number + 1
		EndIf
	Next
	
	Return Number
End Function

Function FUNC_PathElement_GetNodeByIndex.TYPE_Node(group$,id,index=0)
	Local a.TYPE_Path,b.TYPE_PathElement
	Local Number
	
	a = FUNC_Path_GetByGroup(group,id)
	
	If Handle(a)
		For b = Each TYPE_PathElement
			If b\T_Group = a
				If Number = index
					Return b\T_Node
				EndIf
				
				Number = Number + 1
			EndIf
		Next
	EndIf
End Function

Function FUNC_PathElement_GetByIndex.TYPE_PathElement(group$,id,index=0)
	Local a.TYPE_Path,b.TYPE_PathElement
	Local Number
	
	a = FUNC_Path_GetByGroup(group,id)
	
	If Handle(a)
		For b = Each TYPE_PathElement
			If b\T_Group = a
				If Number = index
					Return b
				EndIf
				
				Number = Number + 1
			EndIf
		Next
	EndIf
End Function

Function FUNC_PathElement_GetByNodeID.TYPE_PathElement(group$,id,node_id)
	Local a.TYPE_Path,b.TYPE_PathElement
	
	a = FUNC_Path_GetByGroup(group,id)
	
	If Handle(a)
		For b = Each TYPE_PathElement
			If b\T_Group = a
				If b\T_Node\I_ID = node_id
					Return b
				EndIf
			EndIf
		Next
	EndIf
End Function

Function FUNC_PathElement_Count(group$,id)
	Local a.TYPE_Path,b.TYPE_PathElement
	Local Number
	
	a = FUNC_Path_GetByGroup(group,id)
	
	If Handle(a)
		For b = Each TYPE_PathElement
			If b\T_Group = a
				Number = Number + 1
			EndIf
		Next
	EndIf
End Function

Function FUNC_Delete_PathElement_ByIndex(group$,id,index=0)
	Local a.TYPE_PathElement
	
	a = FUNC_PathElement_GetByIndex(group,id,index)
	
	If Handle(a)
		Delete a
	EndIf
End Function


Function GTexture(size=64,red=255,green=255,blue=255,scalex#=4,scaley#=4,offsetx#=.25,offsety#=.25)
	Local T = CreateTexture(size,size,1+256)
	
	SetBuffer TextureBuffer(T)
		Color red*.7,green*.7,blue*.7
		Rect 0,0,size,size
		
		Color red,green,blue
		Rect size/2,0,size/2,size/2
		Rect 0,size/2,size/2,size/2
	SetBuffer BackBuffer()
	ScaleTexture T,scalex,scaley
	PositionTexture T,offsetx,offsety
	
	Return T
End Function

Function EntityLinePick(src_ent,dest_ent)
	Local DisX# = EntityX(dest_ent,1)-EntityX(src_ent,1)
	Local DisY# = EntityY(dest_ent,1)-EntityY(src_ent,1)
	Local DisZ# = EntityZ(dest_ent,1)-EntityZ(src_ent,1)
	
	LinePick EntityX(src_ent,1),EntityY(src_ent,1),EntityZ(src_ent,1), DisX,DisY,DisZ,1
	PositionEntity Sphere[0],EntityX(src_ent,1),EntityY(src_ent,1),EntityZ(src_ent,1)
	PositionEntity Sphere[1],PickedX(),PickedY(),PickedZ()
	
	Return PickedEntity()
End Function

I can see the end in sight :D All I have left now is to code it to make it branch out through the neighbors and keep going till it finds the goal node. It will delete any path that finds a node that has already been added because that means it was looping back to a node it has already seen. For example...
Node1 to Node2 to Node3 to Node1

lo-tekk

(Posted 2010) [#10]

Have a look right here: http://www.blitzbasic.com/Community/posts.php?topic=73941#832575

[edit]Sorry, the link has gone. Reuploaded here:

http://www.box.net/shared/kgzoydu3ds

Maybe you can make a good use out of it.

Knight #51

(Posted 2010) [#11]

You should definitely try ordered lists or trees for AI path finding nodes.

GIB3D

(Posted 2010) [#12]

I'm already doing "orderly lists".. or "trees"... I think.. heh. I'm using Types to store all the information. At the moment I have some of it working but I need to seriously debug it because I have done some things wrong but it does work because I before I broke it some more, I saw it work ;)

GIB3D

(Posted 2010) [#13]

I got it working mostly. Sometimes it can't find a path even when there is an obvious route but once again I probably coded a few things wrong.

Controls:
Press a number to find a path to that node
0 = 1
1 = 2
3 = 4
etc...

Left and Right arrow keys turn the camera
Pressing T toggles the info view from seeing Node info to Path info

Sometimes it doesn't show the full path.. no idea why.

There are 10 nodes and more can be added in the CreateNodes() function

Graphics3D 1024,768,32,2
SetBuffer BackBuffer()
SeedRnd MilliSecs()

Const I_NodeNeighbors = 3

Const Col_Player = 1
Const Col_Block = 2

Collisions Col_Player,Col_Block,2,2


Global DisplayNodeNeighbors
Global NodeID
Global NumberOfPathsTried

CreateLight()

Global Pivot = CreatePivot()

Global Camera = CreateCamera(Pivot)
PositionEntity Camera,0,16,-15
CameraRange Camera,.1,1000
BP_SetCamFOV Camera,70

Global Sphere[1]
For n = 0 To 1
	Sphere[n] = CreateSphere()
	EntityOrder Sphere[n],-1
	EntityColor Sphere[n],180*n+100,1*n+100,10*n+100
	HideEntity Sphere[n]
Next

Global T_Player.TYPE_Player = FUNC_Create_Player(-3,0)
Global PathDistance

EntityTexture CreatePlane(),GTexture(256)

CreateNodes(0,4)

Local Font = LoadFont("Impact",22)
SetFont Font

Local ViewToggle

While Not KeyDown(1)
	TurnEntity Pivot,0,(KeyDown(205)-KeyDown(203)),0
	PointEntity Camera,T_Player\E_Point
	
	FUNC_Update_Player()
	
	UpdateWorld
	RenderWorld
	
	If KeyHit(20) ViewToggle = Not ViewToggle
	
	Select ViewToggle
		Case 0
			FUNC_Node_CameraProject(Camera)
		Case 1
			FUNC_Player_CameraProjectPath(Camera)
	End Select
	
	If Handle(T_Player\T_PathFinding) <> 0
		Color 0,255,120
		Text 0,0,"Distance = " + PathDistance
	EndIf
	
	Flip
Wend
End

Function CreateNodes(x,z)
	;[Block] Create block
	Local Block = CreateCube()
	PositionEntity Block,x-1,2.01,z+4
	ScaleEntity Block,3.95,2,.95
	EntityAlpha Block,.4
	EntityFX Block,16
	EntityType Block,Col_Block
	EntityPickMode Block,2
	Local Texture = GTexture(256,200,60,60,4,8,.625,.5625)
	
;	SetBuffer TextureBuffer(Texture)
;	Color 0,0,0
;	Text TextureWidth(Texture)*.5,TextureHeight(Texture)*.5,"B",1,1
;	SetBuffer BackBuffer()
	
	EntityTexture Block,Texture
	;[End]
	
	FUNC_Create_Node(x,z)		;1
	FUNC_Create_Node(x-2,z+6)	;2
	FUNC_Create_Node(x+4,z+4)	;3
	FUNC_Create_Node(x-6,z)		;4
	FUNC_Create_Node(x-8,z+8)	;5
	FUNC_Create_Node(x-2,z+10)	;6
	FUNC_Create_Node(x+1,z+12)	;7
	FUNC_Create_Node(x+6,z)		;8
	FUNC_Create_Node(x+6,z+8)	;9
	FUNC_Create_Node(x-2,z+14)	;10
	
	FUNC_Node_AssignNeighbors()
End Function



Type TYPE_Player
	Field E_Point
	
	Field S_PathGroup$
	Field T_PathFinding.TYPE_PathFinding
	Field T_Node.TYPE_Node
End Type

Function FUNC_Create_Player.TYPE_Player(x#,z#)
	Local a.TYPE_Player = New TYPE_Player
		a\S_PathGroup = Handle(a)
		a\E_Point = CreateCube()
		
		PositionEntity a\E_Point,x,1,z
		PointEntity Camera,a\E_Point
		EntityTexture a\E_Point,GTexture(64,10,10,200,1,1)
		EntityType a\E_Point,Col_Player
	Return a
End Function

Function FUNC_Update_Player()
	Local a.TYPE_Player,b.TYPE_Node
	Local Yaw#
	Local Key[2]
	
	Key[0] = KeyDown(57)
;	Key[1] = KeyHit(200)
	
	For a = Each TYPE_Player
		If Handle(a\T_Node)
			If EntityDistance(a\E_Point,a\T_Node\E_Point) <= 1
				DebugLog "LastNodeID = " + a\T_Node\I_ID
				a\T_Node = FUNC_PathFinding_GetNode(a\T_PathFinding,True)
				
				If Handle(b)
					DebugLog "NextNodeID = " + b\I_ID
					PathDistance = FUNC_Path_GetDistance(a\T_PathFinding\T_Path)
					FUNC_Node_Paint(a\T_Node)
				EndIf
			EndIf
		EndIf
		
		If Key[0]
			If Handle(a\T_Node)
				If EntityDistance(a\E_Point,a\T_Node\E_Point) > 2
					Yaw = DeltaYaw(a\E_Point,a\T_Node\E_Point)
					TurnEntity a\E_Point,0,Yaw*.25,0
				EndIf
				
				;If Abs(Yaw) <= 15
					MoveEntity a\E_Point,0,0,.1
				;EndIf
			EndIf
		EndIf
		
;		If Key[1]
;			If DisplayNodeNeighbors > 0
;				FUNC_Player_FindPath(a,DisplayNodeNeighbors)
;			EndIf
;		EndIf
		
		Key[2] = GetKey()
		If Key[2] => 48 And Key[2] =< 57
			DisplayNodeNeighbors = Key[2]-47
			FUNC_Player_FindPath(a,DisplayNodeNeighbors)
		EndIf
	Next
End Function

Function FUNC_Player_FindPath(a.TYPE_Player,dest_node_id)
	Local b.TYPE_Node
	
	If Handle(a\T_PathFinding)
		a\T_Node = Null
		FUNC_Delete_PathFinding(a\T_PathFinding)
	EndIf
	
	DebugLog "FindPath"
	a\T_PathFinding = FUNC_FindShortestPath(a\E_Point,dest_node_id)
	
	If Handle(a\T_PathFinding)
		b = FUNC_PathFinding_GetNode(a\T_PathFinding)
		
		If Handle(b)
			DebugLog "Node1ID = " + b\I_ID
			PathDistance = FUNC_Path_GetDistance(a\T_PathFinding\T_Path)
			a\T_Node = b
			FUNC_Node_Paint(a\T_Node)
			FUNC_Node_Paint(a\T_PathFinding\T_EndNode,0,255,0,False)
		EndIf
	EndIf
End Function


Type TYPE_Node
	Field E_Point
	Field I_ID
	
	Field T_Neighbor.TYPE_Node[I_NodeNeighbors]
End Type

Function FUNC_Create_Node.TYPE_Node(x#,z#)
	Local a.TYPE_Node = New TYPE_Node
		a\E_Point = CreateCube()
		a\I_ID = FUNC_Node_GetNewID()
		
		EntityPickMode a\E_Point,1
		NameEntity a\E_Point,a\I_ID
		PositionEntity a\E_Point,x,1,z
		ScaleMesh a\E_Point,1,.91,1
		EntityTexture a\E_Point,GTexture(256,200,200,60,1,1,0,0)
	Return a
End Function

Function FUNC_Node_GetNewID()
	NodeID=NodeID+1
	Return NodeID
End Function

Function FUNC_Node_GetNode.TYPE_Node(id)
	Local a.TYPE_Node
	
	For a = Each TYPE_Node
		If a\I_ID = id
			Return a
		EndIf
	Next
End Function

Function FUNC_Node_GetNearest.TYPE_Node(entity,exclusive=0)
	Local a.TYPE_Node
	Local Distance#=99999999,D#,b.TYPE_Node
	
	For a = Each TYPE_Node
		If Handle(a) <> Handle(b)
			D = EntityDistance(a\E_Point,entity)
			
			If D > exclusive
				If D < Distance
					Distance = D
					b = a
				EndIf
			EndIf
		EndIf
	Next
	
	If Handle(b) <> 0 Return b
End Function

Function FUNC_Node_AssignNeighbors()
	Local a.TYPE_Node
	
	For a = Each TYPE_Node
		FUNC_Node_SetShortestNeighbor(a)
	Next
End Function

Function FUNC_Node_SetShortestNeighbor(a.TYPE_Node)
	Local b.TYPE_Node
	Local Distance# = 999999,D#
	
	For y = 0 To I_NodeNeighbors ; Search the shortest distance for each Neighbor node slot
		Distance = 999999
		
		For b = Each TYPE_Node
			If b <> a ; Make sure this node doesn't set itself as a neighbor
				If Not FUNC_Node_NodeIsNeighbor(a,b) ; Make sure the node isn't already a neighbor
					If b <> a\T_Neighbor[z]
						If EntityLinePick(a\E_Point,b\E_Point) = b\E_Point ; Finally, make sure you can go directly from the first node to this node without a collision
							D = EntityDistance(a\E_Point,b\E_Point)
							
							If D < Distance
								Distance = D
								a\T_Neighbor[y] = b
							EndIf
						EndIf
					EndIf
				EndIf
			EndIf
		Next
	Next
End Function

Function FUNC_Node_NodeIsNeighbor(a.TYPE_Node,b.TYPE_Node) ; Checks if the inputed node is already a neighbor
	For n = 0 To I_NodeNeighbors
		If Handle(a\T_Neighbor[n])
			If a\T_Neighbor[n] = b
				Return True
			EndIf
		EndIf
	Next
End Function

Function FUNC_Node_Paint(b.TYPE_Node,red=255,green=0,blue=0,reset=True)
	Local a.TYPE_Node
	
	If reset
		For a = Each TYPE_Node
			EntityColor a\E_Point,255,255,255
		Next
	EndIf
	
	If Handle(b) EntityColor b\E_Point,red,green,blue
End Function

Function FUNC_Node_CameraProject(camera)
	Local a.TYPE_Node
	Local X,Y
	
	For a = Each TYPE_Node
		If EntityInView(a\E_Point,camera)
			Color 255,120,0
			
			CameraProject camera,EntityX(a\E_Point,1),EntityY(a\E_Point,1),EntityZ(a\E_Point,1)
			X = ProjectedX()
			Y = ProjectedY()
			Text X,Y-30,a\I_ID,1,1
			
			If a\I_ID = DisplayNodeNeighbors
				Color 255,10,0
				
				For n = 0 To I_NodeNeighbors
					If Handle(a\T_Neighbor[n])
						CameraProject camera,EntityX(a\T_Neighbor[n]\E_Point,1),EntityY(a\T_Neighbor[n]\E_Point,1),EntityZ(a\T_Neighbor[n]\E_Point,1)
						Line X,Y,ProjectedX(),ProjectedY()
						Text ProjectedX()+30,ProjectedY()-70,n+1,0,1
					EndIf
				Next
			EndIf
		EndIf
	Next
	
	Color 255,120,0
End Function


Type TYPE_PathFinding ; Stores the final outcome of the whole Path searching junk.. basically just gives you want you want to know
	Field T_StartNode.TYPE_Node
	Field T_EndNode.TYPE_Node
	Field T_Path.TYPE_Path
End Type

Function FUNC_FindShortestPath.TYPE_PathFinding(entity,dest_node_id)
	DebugLog "FUNC_FindShortestPath dest_node_id = " + dest_node_id
	
	Local a.TYPE_PathFinding = New TYPE_PathFinding
		a\T_StartNode = FUNC_Node_GetNearest(entity)
		a\T_EndNode = FUNC_Node_GetNode(dest_node_id)
		
		If EntityLinePick(entity,a\T_EndNode\E_Point) = a\T_EndNode\E_Point
			;Checks if you can just go straight to the node without needing to waste time finding a whole path
			a\T_Path = FUNC_Create_Path(a\T_EndNode)
			FUNC_Create_PathElement(a\T_Path,a\T_EndNode,Null)
		Else
			a\T_Path = FUNC_Path_StartFinding(a\T_StartNode,a\T_EndNode)
		EndIf
		
		If Handle(a\T_Path) = 0
			DebugLog "FindShortestPath Path not found"
			FUNC_Delete_PathFinding(a)
		EndIf
	Return a
End Function

Function FUNC_PathFinding_GetNode.TYPE_Node(a.TYPE_PathFinding,delete_last_node=0)
	Return FUNC_Path_GetNode(a\T_Path,delete_last_node)
End Function

Function FUNC_Delete_PathFinding(a.TYPE_PathFinding)
	FUNC_Delete_Path_All()
	Delete a
End Function


;Store the branch groups and then sift through each Path to find the shortest one

Type TYPE_Path ; Stores a branch group
	Field I_Bad
	
	Field T_Last.TYPE_Node
	Field T_EndNode.TYPE_Node
End Type

Function FUNC_Create_Path.TYPE_Path(dest.TYPE_Node)
	Local a.TYPE_Path = New TYPE_Path
		a\T_EndNode = dest
		NumberOfPathsTried = NumberOfPathsTried + 1
	Return a
End Function

Function FUNC_Path_StartFinding.TYPE_Path(source.TYPE_Node,dest.TYPE_Node)
	NumberOfPathsTried = 0
	
	Local a.TYPE_Path = FUNC_Create_Path(dest)
	
	;Starts the first path for checking
	;When it runs into a node that has more than one neighbor it clones the path
	;and the other path now heads on to that other neighbor's neighbor's paths which then ; the double neighbor's neighbor's is supposed to be like that ; a comment to a comment about comment.. lol
	;create more paths
	
	a\T_Last = source
	
	FUNC_Create_PathElement(a,a\T_Last,Null)
	
	DebugLog ""
	DebugLog "Starting"
	
	Repeat
		FUNC_Update_Path(dest)
		
		If FUNC_Path_AllFound()
			Exit
		EndIf
	Forever
	
	DebugLog "Number of paths tried = " + NumberOfPathsTried
	DebugLog ""
	DebugLog "Sifting through paths to find the shortest one"
	a = FUNC_Path_GetShortest()
	
	Return a
End Function

Function FUNC_Update_Path(dest.TYPE_Node)
	Local a.TYPE_Path,b.TYPE_Path
	Local Search
	
	For a = Each TYPE_Path
		Search = True
		
		If a\T_Last = a\T_EndNode
			Search = False
		EndIf
		
		If FUNC_PathElement_FindDuplicates(a)
			a\I_Bad = True
			Search = False
			DebugLog "BadPath " + FUNC_Path_ReturnString(a)
		EndIf
		
		If Search
			Search = False ; Set search to false so the neighbors can be checked if they exist first
			
			For n = 0 To I_NodeNeighbors
				If Handle(a\T_Last\T_Neighbor[n])
					Search = True ; If a neighbor exists then it continues to search
					Exit
				EndIf
			Next
			
			If Search ; Should it continue?
				If Handle(a\T_Last\T_Neighbor[0])
					FUNC_Create_PathElement(a,a\T_Last\T_Neighbor[0],FUNC_PathElement_NodeInPath(a,a\T_Last))
					DebugLog "Continuing the path on Path("+Handle(a)+") PathString " + FUNC_Path_ReturnString(a)
					
					a\T_Last = a\T_Last\T_Neighbor[0]
				EndIf
				
				For n = 1 To I_NodeNeighbors
					If Handle(a\T_Last\T_Neighbor[n])
						b = FUNC_Path_CopyPath(a)
						FUNC_Create_PathElement(b,b\T_Last\T_Neighbor[n],FUNC_PathElement_NodeInPath(b,b\T_Last))
						DebugLog "Copied Path("+Handle(b)+") PathString " + FUNC_Path_ReturnString(b)
						
						b\T_Last = b\T_Last\T_Neighbor[n]
					EndIf
				Next
			EndIf
		EndIf
		
		If a\I_Bad
			DebugLog "Deleting bad path"
			FUNC_Delete_Path(a)
		EndIf
		DebugLog ""
	Next
End Function

Function FUNC_Path_AllFound() ; Returns true if all the paths have found the end
	Local a.TYPE_Path
	
	For a = Each TYPE_Path
		If a\T_Last <> a\T_EndNode
			Return False
		EndIf
	Next
	
	Return True
	DebugLog "FUNC_Path_AllFound"
End Function

Function FUNC_Path_Count()
	Local a.TYPE_Path
	Local Number
	
	For a = Each TYPE_Path
		If Not a\I_Bad
			Number = Number + 1
		EndIf
	Next
	
	Return Number
End Function

Function FUNC_Path_GetShortest.TYPE_Path()
	Local a.TYPE_Path,b.TYPE_Path
	Local Distance#,D#
	
	For a = Each TYPE_Path
		If a = First TYPE_Path
			Distance = FUNC_Path_GetDistance(a)
			b = a
		Else
			D = FUNC_Path_GetDistance(a)
			
			If D < Distance
				Distance = D
				b = a
			Else
				FUNC_Delete_Path(a)
			EndIf
		EndIf
	Next
	
	DebugLog "Paths left after GetShortest = " + FUNC_Path_Count()
	
	Return b
End Function

Function FUNC_Path_GetDistance#(a.TYPE_Path)
	Local b.TYPE_PathElement,c.TYPE_PathElement
	Local Distance#
	
	For b = Each TYPE_PathElement
		If b\T_Path = a
			c = b
		EndIf
	Next
	
	If Handle(c)
		While Handle(c\T_Parent)
			Distance = Distance + EntityDistance(c\T_Node\E_Point,c\T_Parent\T_Node\E_Point)
			c = c\T_Parent
		Wend
	EndIf
	
	Return Distance
End Function

Function FUNC_Path_CopyPath.TYPE_Path(b.TYPE_Path)
	Local a.TYPE_Path = FUNC_Create_Path(b\T_EndNode)
	Local c.TYPE_PathElement,parent.TYPE_PathElement
	Local Number
	
	a\T_Last = b\T_Last
	
	For c = Each TYPE_PathElement
		If c\T_Path = b
			If Number = 0 Number = Number + 1
			
			If Number = 1
				parent = FUNC_Create_PathElement(a,c\T_Node,Null)
			Else
				parent = FUNC_Create_PathElement(a,c\T_Node,parent)
				a\T_Last = parent\T_Node
			EndIf
		EndIf
	Next
	
	Return a
End Function

Function FUNC_Path_GetNode.TYPE_Node(b.TYPE_Path,delete_last_node=0)
	Local a.TYPE_PathElement
	
	If delete_last_node
		For a = Each TYPE_PathElement
			If a\T_Path = b
				FUNC_Delete_PathElement(a)
				Exit
			EndIf
		Next
	EndIf
	
	For a = Each TYPE_PathElement
		If a\T_Path = b
			Return a\T_Node
		EndIf
	Next
End Function

Function FUNC_Path_ReturnString$(b.TYPE_Path)
	Local a.TYPE_PathElement
	Local Elements$
	
	For a = Each TYPE_PathElement
		If a\T_Path = b
			Elements = Elements + a\T_Node\I_ID + ","
		EndIf
	Next
	
	If Elements <> ""
		Elements = Left(Elements,Len(Elements)-1)
	EndIf
	
	Return Elements
End Function

Function FUNC_Player_CameraProjectPath(camera)
	Local a.TYPE_Player = First TYPE_Player
	Local b.TYPE_PathElement,c.TYPE_PathElement
	Local X,Y
	
	If Handle(a\T_PathFinding)
		If Handle(a\T_PathFinding\T_Path)
			For c = Each TYPE_PathElement
				If c\T_Path = a\T_PathFinding\T_Path
					b = c
				EndIf
			Next
			
			If Handle(b)
				Color 0,0,255
				
				Repeat
					If Handle(b\T_Parent)
						If EntityInView(b\T_Node\E_Point,camera) And EntityInView(b\T_Parent\T_Node\E_Point,camera)
							CameraProject camera,EntityX(b\T_Node\E_Point,1),EntityY(b\T_Node\E_Point,1),EntityZ(b\T_Node\E_Point,1)
							X = ProjectedX()
							Y = ProjectedY()
							
							CameraProject camera,EntityX(b\T_Parent\T_Node\E_Point,1),EntityY(b\T_Parent\T_Node\E_Point,1),EntityZ(b\T_Parent\T_Node\E_Point,1)
							Line X,Y,ProjectedX(),ProjectedY()
							
							b = b\T_Parent
						EndIf
					Else
						Return
					EndIf
				Forever
			EndIf
		EndIf
	EndIf
End Function

Function FUNC_Delete_Path(a.TYPE_Path)
	FUNC_Delete_PathElement_InPath(a)
	Delete a
End Function

Function FUNC_Delete_Path_All()
	Local a.TYPE_Path
	
	For a = Each TYPE_Path
		FUNC_Delete_Path(a)
	Next
End Function


Type TYPE_PathElement ; Stores a piece of a branch in a path
	Field T_Path.TYPE_Path
	Field T_Node.TYPE_Node
	Field T_Parent.TYPE_PathElement
End Type

Function FUNC_Create_PathElement.TYPE_PathElement(b.TYPE_Path,c.TYPE_Node,parent.TYPE_PathElement)
	Local a.TYPE_PathElement = New TYPE_PathElement
		a\T_Path = b
		a\T_Node = c
		a\T_Parent = parent
	Return a
End Function

Function FUNC_PathElement_NodeInPath.TYPE_PathElement(b.TYPE_Path,c.TYPE_Node)
	Local a.TYPE_PathElement
	
	For a = Each TYPE_PathElement
		If a\T_Path = b
			If a\T_Node = c
				Return a
			EndIf
		EndIf
	Next
End Function

Function FUNC_PathElement_FindDuplicates(d.TYPE_Path)
	Local a.TYPE_PathElement,b.TYPE_PathElement
	
	DebugLog "FindDuplicates Path Handle("+Handle(d)+")"
	DebugLog "PathString " + FUNC_Path_ReturnString(d)
	
	For a = Each TYPE_PathElement
		If a\T_Path = d
			
			For b = Each TYPE_PathElement
				If a <> b
					If b\T_Path = d
						If b\T_Node = a\T_Node
							DebugLog "Handle1("+Handle(a)+") Handle2("+Handle(b)+")"
							DebugLog "Duplicate found " + a\T_Node\I_ID
							Return True
						EndIf
					EndIf
				EndIf
			Next
			
		EndIf
	Next
	
	DebugLog "Found no duplicates"
	DebugLog "---"
End Function

Function FUNC_Delete_PathElement(a.TYPE_PathElement)
	Delete a
End Function

Function FUNC_Delete_PathElement_InPath(b.TYPE_Path)
	Local a.TYPE_PathElement
	
	For a = Each TYPE_PathElement
		If a\T_Path = b
			FUNC_Delete_PathElement(a)
		EndIf
	Next
End Function


Function GTexture(size=64,red=255,green=255,blue=255,scalex#=4,scaley#=4,offsetx#=.25,offsety#=.25)
	Local T = CreateTexture(size,size,1+256)
	
	SetBuffer TextureBuffer(T)
		Color red*.7,green*.7,blue*.7
		Rect 0,0,size,size
		
		Color red,green,blue
		Rect size/2,0,size/2,size/2
		Rect 0,size/2,size/2,size/2
	SetBuffer BackBuffer()
	ScaleTexture T,scalex,scaley
	PositionTexture T,offsetx,offsety
	
	Return T
End Function

Function EntityLinePick(src_ent,dest_ent)
	Local DisX# = EntityX(dest_ent,1)-EntityX(src_ent,1)
	Local DisY# = EntityY(dest_ent,1)-EntityY(src_ent,1)
	Local DisZ# = EntityZ(dest_ent,1)-EntityZ(src_ent,1)
	
	LinePick EntityX(src_ent,1),EntityY(src_ent,1),EntityZ(src_ent,1), DisX,DisY,DisZ
	PositionEntity Sphere[0],EntityX(src_ent,1),EntityY(src_ent,1),EntityZ(src_ent,1)
	PositionEntity Sphere[1],PickedX(),PickedY(),PickedZ()
	
	Return PickedEntity()
End Function

GIB3D

(Posted 2010) [#14]

I found a nice video for pathfinding. It shows almost the same exact way I'm doing it. http://www.youtube.com/watch?v=WC1Po5rWXr0