I’m working on a game were creatures will reproduce and die. I need to be able to keep track of them in a container since they will need to be able to find each other.
What I’d like to do is have access to a Linked List class but I haven’t seen one available. Can anyone tell me about what container objects we do have access to in Unity and maybe a suggestion from among those which would most likely be most useful for my application?
Currently I’m looking at ArrayList but it is a bit ugly.
You can also use System.Collections.Generic, so that gives you List, which I think is very elegant. Most generic collection classes are also in mscorlib.dll, so you can even use those in a Web player. Unfortunately, not all of them - the generic stacks and queues are in another assembly, so using those will bloat a Web player.
I guess the implementation of the System.Collections.Generic.List is still some sort of array list in the end, though (but I’m not sure about that). Depending on how many objects you have, the difference between an array list and a linked list might turn out to not so severe.
You might want to have a look at the Mono or .NET API documentation …
The operations I will need to use will be insertion, deletion, and traversing. I also will want to change the size of the container object to hold more objects.
Correct me if I’m wrong, I believe that ArrayList stores the object in an array internally. The ArrayList seems to be similar to the “Vector” object in the C++ STL.
This would work well for traversing, adding, and changing the size of the container. The problem I see is deletion. Deleting an object would require removing the object from the list and then moving all the object behind it down one index. I’m sure that’s built in if I’ve got the class right, but that still is a bit intense to be doing each frame.
Please let me know if I’m wrong, I’d be glad if it is so!
Cool, so you have a LinkedList - be aware, though, that this one’s in System.dll and not in mscorlib.dll. So the following issue applies to this (only relevant to Web players, though):
Btw, I’m not even sure LinkedLists are that much greater concerning deletions. I would assume (not perfectly sure about this), that they internally use arraycopy which I think is a very quick operation, since there’s probably some low-level “memcopy” involved. I haven’t been much into the internals of datastructures recently, but I guess the problem with deletion in LinkedLists is that you first need to iterate to the object you want to delete. So unless it’s the first or last, that might even be slower than deleting from an array.
But as said, I’m currently not an expert in datastructures … but you probably wouldn’t want to create and destroy objects in each frame, or would you?
In my quick testing a while back, I found that typed Dictionaries are actually quite fast. A notable amount faster than Hashtables. I only tested insertion and retrieval, but deletion should follow a similar pattern.
It’s in the System.Collections.Generic NS though, with the issues that Jashan mentioned with size.
Also, you might want to look at creating a SkipList for a bit more speed if you really need to use a Linked List structure.
I checked and MSDN and it says that it stores LinkedList as a doubly linked list.
It’s a class that uses Stucts, typically Node stucts. Each node contains an item, a pointer to a node before it, and a pointer to a node after it (it may also have an int to give it an index). So the LinkedList class just has an int to count the number of nodes and a pointer to point to the first node in the list, as well as, constructors, destructors, etc. that make the class function.
For me this is perfect!! I just need to make two LinkedLists at start up. At run time I can iterate through all of nodes in the two LinkedLists (I’m doing something similar to collision detection but much more primitive), and I can easily remove and add new nodes.
No I won’t be deleting and adding EVERY frame cycle but I will in many. I may also remove multiple objects in the same cycle which could lag if I delete a decent number of objects at once. If I used some sort of array implementation each object would be removed then all behind it shifted, then another object removed then all behind it shifted and this would continue until all had been removed. This is rather inefficient compared to just taking a node and removing it by making the node before it point to the one after it and vice versa.
Are you sure you would need to do that with an ArrayList? A good technique is to null out entries in the container list when you delete them and then keep a second list with the indices of the empty spaces - you just pull the last item from the empty space list when you want to add an item and only grow the container if there are no spaces left.
A linked list is not usually the best option for a simple container on modern CPUs because it tends to defeat the cache. In fact, I suspect the performance penalty during the linked list traversal might be worse even than the time taken to shuffle entries along when deleting from the simple ArrayList. Of course, I don’t know the details of your code, but I would suggest trying both the linked list and the ArrayList for speed before deciding what to use.
I’m using a builtin (JavaScript) array to manage spawns. When an enemy dies it gets destroyed and the slot in the container evaluates to false. I can repopulate it at my leisure, and there’s no danger of a runaway spawn producing a million creatures.
I can also scan the list for stuff that’s far away or no longer interesting and despawn it.
I doubt the cache coherency issues with linked lists has much of an impact on performance but … all of this sounds like premature optimization / overthinking a simple problem. Sometimes a fixed size array is a perfectly good option.
I agree this is most likely me thinking too hard on a problem that may not exist. I’m also taking another class on XNA so it’s made me think about most likely more than I need to.
This project is due for a class on Monday and I’ve had three weeks to put it together so I think I’ve done tons of planning ahead since I don’t really have time for many problems.
So far, The LinkedList has been perfect but we’ll see over the next few days!
I know this is an old thread, but I think some clarification is in order. Graph theory is very important in many different uses, and List’s do not always fit the suitability for any particular graph structure.
Ie. One size does not fit all. Linked lists are not as inefficient as most people think they are, and you can actually generate linked lists using static lists (use one list to collect the objects, and another to allow some form of sorting/insertion/node management).
Its important to have these lists though, because they often provide search systems that are not linear nore key’s but are based on graph structure instead (Red / Black trees as an example).
So… hope this clears its up a bit. And if anyone is interested I can post a LinkedList implementation up here.
… but you probably wouldn’t want to create and destroy objects in each frame, or would you?