Need help: find the exit of the laberinth code!

Blitz3D Forums/Blitz3D Programming/Need help: find the exit of the laberinth code!

Dimas(Posted 2006) [#1]
I need a bit of code, but I am unable to do it... I know it is sometype of recursive code...

I have a map of Europe, with 500 cities. Each city has upto 10 links to surrounding cities "city_links(number,links)".

Every city can be Axis or Allied "city_nation(n)"

I need a function "function linked(start,destination)" able to find a road between 2 cities of the same countries, true or false.

I would love the one who makes me such function... I dont need it to be fast.

If you want to know about my program, check at http://www.ampostata.org/The_HC_Game/The_HC_Game.zip


Matty(Posted 2006) [#2]
something like this is what you would want:

Dim NodePathArray(255,255) 
Dim NodeVisArray(255,255)
Dim NodeSearchedArray(255)
Dim BestNodePath(255)
type NodeObject
Field x,y,id
end type

;okay these steps come first:

;calculate the nodes which are 'visible' or 'adjacent' to each other.  I say visible because I am using this system in a game that takes place in an interior environment

;this assumes there are 255 different nodes.  In your system you would replace all instances of '255' with '500'.
;
;so store in the array NodeVisArray(CityN,CityM) a single value which is either 1 or 0, where 1 = adjacent/visible and 0 = not adjacent/not visible.

;then call 'CalcNodePaths'.  This will cause the array 'NodePathArray' to be populated.  At each element it will store the 'next' node to travel to to get from city A to city B.  

;finally store the calculation in a file with WriteNodePathArray("filename.txt")




Function CalcNodePaths()

For Node.NodeObject=Each NodeObject
	For OtherNode.NodeObject=Each NodeObject
		Distance=0
		For i=0 To 255
			NodeSearchedArray(i)=255
			BestNodePath(i)=0
		Next
		LeastDistance=255
		If Handle(node)<>Handle(othernode) Then
		
			If NodeVisArray(Node\ID,OtherNode\ID)=1 Then
			 NodePathArray(Node\ID,OtherNode\ID)=OtherNode\ID 
			Else
		
			NextNodeToDestination(Node.NodeObject,OtherNode.NodeObject,0)
			If LeastDistance<255 Then 
				NodePathArray(Node\ID,OtherNode\ID)=BestNodePath(1)
			EndIf 		
			
			
			EndIf 
		EndIf 
	Next 
Next







End Function

Function NextNodeToDestination(CurrentNode.NodeObject,FinalNode.NodeObject,NodeCount)
NodeSearchedArray(CurrentNode\ID)=NodeCount
If NodeCount>=255 Then Return 255

If Handle(CurrentNode)=Handle(FinalNode) Then Return NodeCount

For OtherNode.NodeObject=Each NodeObject
If Handle(CurrentNode)<>Handle(OtherNode) Then 
	If NodeVisArray(OtherNode\ID,CurrentNode\ID)=1 Then 
		If NodeCount<NodeSearchedArray(OtherNode\ID) Then 
			NodeDist=NextNodeToDestination(OtherNode.NodeObject,FinalNode.NodeObject,NodeCount+1)
			If NodeDist<LeastDistance Then 
				LeastDistance=NodeDist
				BestNodePath(NodeCount)=CurrentNode\ID
				
			EndIf 
		EndIf 		
	Else
	
		
	EndIf 
EndIf 
Next


Return 255
End Function


Function WriteNodePathArray(Filename$)

outfile=WriteFile(filename$)
For i=0 To 255
For j=0 To 255
WriteByte outfile,NodePathArray(i,j) you want to replace this with writeshort outfile,NodePathArray(i,j) because you have 500 cities which is more than 255
Next
Next



CloseFile outfile

End Function




This system precalculates all paths, stores them in a file and can then be used as a 'lookup' for the AI to get from point A->Z by returning the best 'next node' to go to to get from A->Z. So if the path was ABCDZ then the value of NodePathArray(A,Z) would be 'B', and the value of NodePathArray(B,Z) would be 'C'.


Dimas(Posted 2006) [#3]
I understand how to fill nodevisarray:

City 1 has links with cities 3,5 and 240, so

nodevisarray(1,3)=1 : n..(1,5)=1 : n...(1,240)=1, correct?
and so with all cities.

Now I call "calcnodepaths" and I want to know if there is a path between cities 1 and 150 (note that there is no direct link between 1 and 150!)

Lets asume that the best next node to go from 1 to 150 is 5... where to do I find this 5? at nodepatharray(1,150)?

I am correct, I have to check nodepatharray(5,150) to find next step on the path...

And what do I get if there is no path between 1->150? (In my game, it could be possible, if a city or a few of them are isolated!)

BTW, MANY thanks for your help...


Chroma(Posted 2006) [#4]
A simple lookup table would suffice.


Matty(Posted 2006) [#5]
If there is no path then the value will be zero.

Chroma - this snippet generates the lookup table (above)


bytecode77(Posted 2006) [#6]
just take a look at the a*pathfinding algorithm here:
http://www.blitzbase.de/2c.htm


smilertoo(Posted 2006) [#7]
yay for a*