I had an idea for a data structure. Anyone know anything about this
kind of data structure?
It would be used for games, for 2D or 3D collision detection. It
would basically be a double linked list, but a 2d or 3D double linked
list.
So, you might have something like this:
class CloudNode
dim Above as CloudNode
dim Below as CloudNode
dim Left as CloudNode
dim Right as CloudNode
dim x as single
dim y as single
dim w as single
dim h as single
dim VelX as single
dim VelY as single
end Class
So, on each frame, you'd do something like this:
x = x + VelX
y = y + VelY
then you'd check the adjacent CloudNodes, to see if we've passed any,
or intersected any. If we have, then we'll have to perform an action.
Perhaps bounce off of the other object, or destroy it, or some
special action, or push it away, or something.
I thought DataCloud would be a good name, because it's sort of cloud-
like, seeing as like in a real cloud, the droplets don't have to be
in any fixed distance from the other droplets, it could be a dense or
a thin cloud. A node could be a mile or a milimetre from another node!
Also the name "DataCloud" sounds pretty cool.
Would this sort of data structure work? Would it be beset by design
issues making it unusable? Are some games already using it? Does it
have a proper name (not the name I made up for it)? Why isn't
something like this more popular than today's QuadTree collision
detection format as popularised by ID software?
I imagined that it would be quite fast to run, because most of the
CloudNodes, don't actually move. Most will just be scenery, and thus
we don't need to check them on each frame to see if anything has
changed. And even when something does move, we only need to check 2
adjacent nodes per moving node.
If we just had 50 objects that could move on screen, then we only
need to check 50 cloudnodes per frame. We'd probably keep an array of
movable CloudNodes like this:
dim Moveables(-1) as CloudNode
Of course, disposing of this structure would be a nightmare :) Given
RB's cyclical reference problem. This is the sort of thing that would
be easier to do with a plugin, because in fact most nodes don't even
need to be seperate object, you could dump thousands of them into one
malloc'd block.
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://support.realsoftware.com/listarchives/lists.html>
