• Advertisement

Archived

This topic is now archived and is closed to further replies.

Three dimensional Linked List's?

This topic is 5064 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m looking for information on three-dimensional linked-lists. I''ve been looking for a while but can''t seem to find much; mostly stuff on complex rendering techniques and chemistry. I''ve found a few places that say they use them, but nothing that describes them. If anyone has any links to articles, which discuses three-dimensional linked-list -anything- it would be much appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Thanks, but I've already had most of what is on offer through google.

Most of what I find define a three dimensional list as a linked-list with a linked-list with a linked-list.

Another question that I have just remembered; If a linked-list, where nodes have 3 connections (next, previous, child), is defined as being a triply linked-list, can a linked-list with 4 connections be defined as being a quaternary / quarterly linked-list? And if so, can a linked-list, where nodes have 6 connections, be called a hexagonally linked-list?



[edited by - crakinshot on April 10, 2004 3:55:35 PM]

Share this post


Link to post
Share on other sites
When I think three dimensional linked list, I think octree. Is that what you mean?

Share this post


Link to post
Share on other sites
a) I needed something to do my dissertation on. I'm basically trying to assess the advantages or disadvantages of three-dimensional listed-lists in the context of engine design, specifically object management. Good or bad it’s something interesting to do my dissertation on.

b) I concieve a 3D linked-list as being a list where each element has 6 connections; next, previous, parent, child, layer_above, layer_below. Basically I have a picture in my mind of two-dimensional lists layered on-top of each other; which would look three-dimensional. I think I have probably done it wrong; but I focused on making the actual “Node” three-dimensional.

There's not really much to it, more of a cosmetic than anything; having the menu items on the layer above the game objects (menu renders after game objects). You can make do with 2D lists, but like my tutor said; "If the idea is bad, and you can argue it is bad; it should make for a good dissertation."

I’ve already done my implementation and most of my research; I only posted this to make sure I had covered all bases and not missed something.


[edited by - crakinshot on April 10, 2004 4:29:17 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by crakinshot
b) I define a 3D linked-list as being a list where each element has 6 connections; next, previous, parent, child, layer_above, layer_below. Basically I have a picture in my mind of two-dimensional lists layered on-top of each other; which would look three-dimensional. I think I have probably done it wrong; but I focused on making the actual “Node” three-dimensional.
I thought so.

There''s a good reason why there isn''t much data on three-dimensional linked lists as you define them: they have virtually no practical applications. Oh, sure, the abstract model is useful, but maintaining the literal structure is too tedious and inefficient to be helpful. Even the example you give...
quote:
having the menu items on the layer above the game objects (menu renders after game objects)
...barely makes sense. The menu has a relationship to the screen - to the final rendered image of game objects, not the game objects themselves.

quote:
I’ve already done my implementation and most of my research; I only posted this to make sure I had covered all bases and not missed something.
As far as I can tell, you''re inventing the bases. And nobody else will be covering them for a long, looooong time (if ever).

Share this post


Link to post
Share on other sites
I really see no practical application whatsoever of this. Between k-D trees, octrees, nested linked lists, and multidimensional arrays, data structures for 3D space are more or less covered. The only potential advantage I can see is the ability to add a plane of elements in O(n2) normal to any axis, but I''d be hard pressed to think of even a contrived example where this would be needed.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Don''t forget hash tables indexed by ordered triples, hB trees and grid files.

But to be fair, there has been one class of applications that I know of that have been structured as a multi-dimensional linked lists: the classic text adventure games. Remember those? Every room could potentially lead to another room north, south, east, west, up, or down. And at least one game that I''ve seen the source code to structured the actual data to reflect that.

Share this post


Link to post
Share on other sites
quote:
Original post by Oluseyi
quote:
having the menu items on the layer above the game objects (menu renders after game objects)
...barely makes sense. The menu has a relationship to the screen - to the final rendered image of game objects, not the game objects themselves.



Well it’s more of an ordering of tasks. By putting the game objects on one layer and the menu object on a layer above the head game-object, and because of the nature of the Iterater, the game-layer will get messages first and then the menu-layer afterward.

It is a pretty lame example, but along with different options for an Iterater (how it travels), it is the best I have so far... I know you can do the exact same thing with 2D list and in all honesty I can''t find any good reason why you would want to use 3D lists. But if I can prove that you can do most things game related with 2D lists instead of 3D lists, my dissertation should be okay. I hope...

It does work at least; my implementation... hehe...

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
Don't forget hash tables indexed by ordered triples, hB trees and grid files.

But to be fair, there has been one class of applications that I know of that have been structured as a multi-dimensional linked lists: the classic text adventure games. Remember those? Every room could potentially lead to another room north, south, east, west, up, or down. And at least one game that I've seen the source code to structured the actual data to reflect that.


Nice example; better than anything I have.

[Edit]

I said I was looking into three-dimensional linked-list specifically for object management, which isn't the case. In my example program I have 3 layers; Services, game and menu - in that order. The services layer has a few simple interfaces to systems such as the renderer, window manager, etc, the game layer has all the game objects and the menu layer evidently has the menu items.

All I need do is send an update message and a run-once message to the first node of the entire hierarchy and everything updates, draws, what-ever in the correct order, systems update first, then the game objects update from the services and so too the menu items after the game objects.

The only thing that resembles this, which I have found, is an article by Scott Patterson entitled "An Object-Composition Game Framework" in Game Programming Gems 3. It's basically the same idea; layering tasks (well it seems related).


[edited by - crakinshot on April 10, 2004 6:22:20 PM]

Share this post


Link to post
Share on other sites
Good luck coming up with sane generic traversal algorithms. I suppose depthfirst traversal would be one.

Share this post


Link to post
Share on other sites

  • Advertisement