Pathfinding ideas!
Blitz3D Forums/Blitz3D Programming/Pathfinding ideas!
| ||
| Ok, i have grasped what this is all about. Didn't understand it at first as it seemed rather inefficient, but i suppose computers are limited to the way they can do things. ANNNNNNNNNyway... Instead of storing neightbours in an array, do you think it would be easier to store them in types. Using Object/handle to get the next neightbour. Instead of having an array which would be dimensioned to hold the maximum number of links, ie. the number of nodes in the network - 1. I reckon this would use less memory and be quickier. Would i be right by saying this? Additionally, to reduce memory further, i was thinking about chopping up the 32 bit integer into, well, bits... Eg, 1 - 16 bits dedicated for distances the other 16 bits dedicated like so: Bit Description --- ----------- 17 Area lighted? 0-yes(safer) 1-no 18 Terrain description 0-flat 1-hilly 19 Enemies around 0-no 1-yes 20 Populated area-safety- 0-yes 1-no 21 Populated area-crowded-0-no 1-yes 22 etc 23 etc Could get tedius setting up such a system, but you get my drift. The idea being, you'd only need to store one integer, to describe the waypoint better, taking into account different factors. |
| ||
| I don't know if memory will be majorly different, in the global terms of your whole game. With this part of your code speed is a greater concern. |
| ||
| Well, for instance. If i have 50 nodes. I need an array: 50 x 50 = 2500 * 4 = 10,000 roughly 10 KB Now, you'd think most nodes would only have maybe 4 links each, then, using types: 50 nodes * 4 links = 200 * 4 = 800 Bytes I think the more nodes, say you have 100 nodes, the memory difference might be huge. BUT, i see where your coming from. even 100 nodes, only boasts 40 KB of memory usage. Thing is, in a 50 node network, you'd be searching 50 nodes everytime you advance the path. Base that against only searching the number of actual links using a type objects. So, i reckon there's a big difference in size and speed? Would that be correct to say? |
| ||
| I think it's a good idea storing alot of info in a single integer ... a flag so to speak. I use this all the time as it makes it easy to add new factors ... e.g. const F_LIT = 1 const F_HILLY = 2 const F_ENEMIES = 4 const F_POP_SAFETY = 8 const F_POP_CROWN = 16 Where Flag = 13 would mean Hilly, Enemies & Pop Safety. Enemies = ( Flag and F_ENEMIES ) etc.. Hilly = ( Flag and F_HILLY ) I'd be inclined to store the distance separately though. Stevie |
| ||
| Glad to hear man :o) What do you think about the storing of links in type objects, rather than a big array? |
| ||
| I think it'd be fine - you'd have alot of unused pointers if set the max to 50 but I think it will be plenty fast enough. Is this the kinda thing your planning to use ..?
Type Waypoint
field x#, y#, z#
field Flag
field Link.Waypoint[ 50 ]
field NoOfLinks
End type
Function WAYPOINTaddLink( w.waypoint , l.waypoint )
w\Link[ w\NoOfLinks ] = l
w\NoOfLinks = w\NoOfLinks + 1
End function
Function WAYPOINTdoStuffWithLinks( w.waypoint )
for l = 0 to w\NoOfLinks - 1
n.waypoint = w\Link[ l ]
{do stuff with waypoint n }
next
end function
If so I think it'll work well. Stevie |
| ||
I was thinking more along the lines of:Type Waypoint field x#, y#, z# field Flag field firstlink_handle End type Type link field node_number field value field next_link_handle end type Using the object command to retreive the next type object link in the list. Would this work better, or over complicating things? |
| ||
| Yes but what is to say the next link is connected to the original waypoint. How do you plan to traverse the list? |
| ||
| I have an array in the PATH TYPE object, holding the previous node numbers travelled along. Simply compare the nodes number against this array. |
   |