I'm currently creating a game which is the first time I've needed to create a map that didn't use an array of tiles.
The game's map will be infinite in both width and height. Player's will simply unnoticeable teleport to the other side of the map if they spend enough time traveling.
Since you are going to insert and delete a lot of stuff, a linked list is what you need.
>>2
Thanks. I've heard that malloc() is an expensive function though (in terms of performance) and should be used as little as possible. Also I expect a single game object to be only a few bytes in length. In my first version they'll only use ten bytes and I don't expect that they'll grow any larger in later versions.
>>3 Have you considered how you will locate all of the elements to display?
Travelling through the entire list to find it would be awful slow.
> Travelling through the entire list to find it would be awful slow.
What are you talking about? Linear search is O(N) in both lists and arrays.
If the elements can be ordered (if order matters) in some way, you can consider using a B-tree, but it just seems too much for me for a normal game. O(N) is not that much.
> What are you talking about? Linear search is O(N) in both lists and arrays. ... you can consider using a B-tree,
Binary search is O(log N). Binary trees are O(N log N). Sparse fields are O(1). Hashed/sparse fields are O(k). None of these algorithms apply to lists, which is why I asked Have you considered how you will locate all of the elements to display?
>>4
Order doesn't matter and every object that's allocated should be on screen (if not, just a few pixels off). While I'm sure an array would be faster, I don't think looping through a linked list would be "awful slow".
>>3
Using linked lists for a particle system is probably not a good idea, especially with respect to locality of reference. I'd probably go for a resizable array, and avoid having to call malloc/free.
>>3 you only malloc something like that once, unless youre a dumbass
make space, reuse it
keep a set limit to how many objects can be in a view at one time
Just use malloc and free. If they turn out to be a bottleneck, you can optimize them later. Trust me, an API that consists of three calls (malloc, realloc, free) won't be a difficult thing to tear out and replace.
Ignore everybody on here. The correct data structure to use in this case is a double-buffered list.
If you are using C++, you can achieve this with two std::vector<T*>, we'll call them primary and backbuffer, where T is the class/struct containing your objects. On every frame, you first call "backbuffer.clear()". Then, iterate through your primary buffer. For each object in the list, you should call an update() function and pass it the backbuffer of objects. Your object can update itself, and then use "push_back()" to place itself into the backbuffer. Alternatively, if the object is too far away, has been destroyed, or some other condition is true which means you want to get rid of it, have the object delete itself and not use "push_back()". If the object needs to spawn any new objects (bullets, explosions, new enemies, items), it can do so and use "push_back()" to add them to the backbuffer. Once all objects have been updated, you can add any additional new objects you want for that frame to the backbuffer, again using "push_back()". Finally, you call "primary.swap(backbuffer)", which will cause the contents of the primary and backbuffer to switch, and executes in constant time (it amounts to swapping three pairs of pointers). Now, for any rendering work, you simply iterate over "primary".