Hi all, I want to cache the results from various visibility ray traces between objects in my game world. WRT generality and speed, I reckoned it best to use a 2D matrix of bools for object_id vs object_id (i.e. set entry true if visible, else false.) The hard bit (there has to be one) is that there can be hundreds of objects in the world, so I thought a 'sparse matrix' would suit my purposes best here. So... my initial thoughts on implementing one are to have a stl map of maps. Any comments on suitability (space/time efficiency), other thoughts on sparse matrix implementations or thoughts on other solutions to the problem?

I think when most people talk about sparse matrices, they have considerations involving algebraic operations that can be done with matrices like matrix multiplication. For your purpose, you just want to be able to quickly set entries and check if an entry in a boolean matrix is true or false.

Instead of a map of maps, you could also use a map of sets. If an element is present in the set then true, else false. Or a set or map of pairs, although this could result in more unnecessary comparisons. Continuing along that idea, for more efficiency, if there are only hundreds or thousands of objects...if there is some maximum value for object id, create a function that stores a pair of object ids into a unique integer for that pair, and store that integer in a set or hash_set. For example, if an object id is 16 bits, store the first id in the upper 16 bits of a 32 bit word and the second id in the lower 16 bits.

For 'hundreds' (let's say 1024 for simplicity of calculation), just make a bool[1024*1024] and don't bother with sparseness. That's only 1MB, a drop in the ocean with modern RAM.

There are a plethora of different approaches to caching visibility and ray-cast results, all with different performance profiles and memory/speed tradeoffs. What specifically are you trying to accomplish?

@Bob: ah yes - should have mentioned - my Id's are unsigned int's... :o

@Jason: I'm interested in any other approaches. My ray casting binds 3 separate subsystems (heightmap/physics world primitives/per-poly collision system) so isn't the most efficient of operations. I was just hoping to prevent multiple raycasts betw the same objects per frame, and also take advantage of the fact that some rays could have acceptable latency. Another method I thought of was raycast scheduling, but that seems maybe too complex?

@Vorpy: yeah I thought the terminology may confuse ;) I was hoping for an O(1) set/read (tho maps dont give this). My IDs are current U32, but I could maybe limit them to 16 bits - have to think about it.

Hash maps/sets give average O(1) performance, assuming a good hash function is used.

Emmanuel: yeah saw that: it's an implementation for the 'other' (official?) meaning of 'sparse matrix' as Vorpy mentioned - one for linear algebra, rather than just value storage.
Ah well I think I'll go for a map of maps/sets as looking like the best solution.

Thanks all :)