[DGD] Sparce Matrix

[Kevin Carpenter]

Ludger -

I appreciate the help!

What I'm trying to do is create a 3d space management system that
insures that no two objects exist or overlap in space.  This 
system would take into account that container objects like rooms
and bag define their own space regions.

An example usage would be to map rooms so that no two room exist
or overlap the same location.

To do this, I envisioned maintaining a sparce 3D matrix structure.  
A structure element would contain the coordinates of the lower left
hand corner or an object and a pointer to the object.

I suspect the most efficient way of doing this is with nested
mappings, although I'm very open to suggestions.  One problem with
this approach is resolving the location spanning issue:  e.g.  If
I want to place an object at location 10:50:5, how do I determine
who the closest other object is?  If an object existed at, say,
8:48:5, and it was 3:2:1 in size, there would be a conflict since that
object would logically exist in space 8-10:49-50:5-5.  Once I located
the object at 8:48:5, querying its size and determining an overlap is
easy.  The problem then becomes one of locating the object in the first
place.

If I stored my structure as a nested mapping, I could extract the
indexes each time I need to do a check (fortunetly, this won't happen
often for the larger mappings), and binary search the results.  However,
if I need to do that index extract each time, I might be better off just
doing my own array maintenance and represent the sparce matrix that 
traditional way.

So, to answer your question, I need help in your second & third catagories,
although I'm open to anything I might not know about in first <grin>.

Thanks,

Kevin C.

balduin at uni-paderborn.de write:
> 
> Hello Kevin !
> 
> Sorry I somehow lost your email where you describe your
> problem again. So I contact you this way to see if I
> can help you. 
> 
> 1) Please describe what you have in mind to do.
> 2) Please give me a hint on wich level you need help.
>    - Do you need help with lpc, e.g. a description of
>      the use of basic lpc types.
>    - Do you need algorithms and abstract datastructures
>      to solve your problems. (if not you can refer to
>      many commonly known problems by name. I have a good
>      library at hand.) And such knowledge is handy to
>      make suggestions about implementation details.
>    - Do you need very dgd-specific information, as to
>      estimate wich implementation can be expected to be
>      most performant.
> 
> regards 
> Ludger
> (balduin at uni-paderborn.de)
> 


-- 
Kevin Carpenter
Kevin's Home Page: http://www.monrou.com/kevinc
(Expressing his comments from home in St. Louis, where this message originated)

List config page:  http://list.imaginary.com/mailman/listinfo/dgd