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.