size of arrays?
Blitz3D Forums/Blitz3D Programming/size of arrays?
| ||
| how big can arrays be before problems occur? I have an array for my path finding system, const MaxNodes = 10000 tPath.tPath(MaxNodes-1,MaxNodes-1) and the type is like this type tPath field VisData field PathSize field bank;holds the bank in a bank when it is created end type If i use the path from 'a to b' for 'b to a' then it could be cut down to just 10000 elements but then paths for hills etc would be same up or down. i have had no issues so far and memory consumption is low, anyone offer any advice? ps im using the djekstra algo for the pathfinding with loads of shortcuts, tricks and optimisations thrown in and am trying to use it for a large scale map with intelligent pathfinding for ai. |
| ||
| Arrays can be as big as the memory allows them to be :o) As for speed, it's hard to tell, and depends on how fast your memory and CPU are. |
| ||
Dim tPath.tPath(MaxNodes-1,MaxNodes-1) Wow. 100,000,000 elements? It takes 20 seconds just to initialize the array on my machine! What kind of crazy algorithm needs that much RAM? |
| ||
| I've never heard of the 'djekstra' algorithm but that size of array seems pretty unnecessary. If possible, I think the A* algorithm would be much more efficient for pathfinding. |
| ||
| Dijkstra is very similar to the A*, it just uses a different approach (going from start point always processing the connection that leads to the smallest total distance). But the size of the array for sure is too large. dijkstra will never be able to finish its path calculation on that array if you do not make totally unpassable areas. If you really have a that large map you should consider using waypoints for general movement and when they reach an acceptable waypoint switch to a "zone" like thing in which dijkstra is going to operate. As you see, the array has 100 Mio entries ... if you use types the whole thing means 100MB * sizeof(Type) ... It is just to large to fit in regular RAM amounts ... I have no idea how you come to think that you have a low ram usage ... |
| ||
| You can store paths for commonly followed routes (i.e. connecting 2 cities) but storing every path is a bit too much. A* can be used for seperate grid sizes. Superb article ... A* relating to Blitz plus two-tiered The waypoint method is commonly used in 3D FPS type games... terrain reasoning |
| ||
| thanks guys, i was doing it that way for testing purposes, just to see how many nodes i can place and how long calculations would take. Before, i was storing each path for each node in the array(10000,10000) so the path for nodeA to NodeB would be seperate from NodeB to NodeA now they use the same path. Im using a visibility function so if a node is visible to another node then that is the path instead of working the path through the links. It takes about 2millisecs to work out a path on a 100*100 grid from node0 to node9999 with obstructions etc which is pretty fast when each node has upto 8 links, when i add in a visibility test it cuts it down to 0m depending on the map and obstructions. ps. Its the first time i've done any pathfinding stuff so its all new to me. |
   |