Need help: find the exit of the laberinth code!
Blitz3D Forums/Blitz3D Programming/Need help: find the exit of the laberinth code!
| ||
| 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 |
| ||
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'. |
| ||
| 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... |
| ||
| A simple lookup table would suffice. |
| ||
| If there is no path then the value will be zero. Chroma - this snippet generates the lookup table (above) |
| ||
| just take a look at the a*pathfinding algorithm here: http://www.blitzbase.de/2c.htm |
| ||
| yay for a* |