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* |