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.

To make the game a lot more interesting, the map will contain objects that are randomly plotted when they are in view. It doesn't matter if a player backtracks to find that the world is changing. That's to be expected.

I can program all that easily, but I don't know which is the best way to store these objects. I expect the majority of time, players will be simply rushing pass these objects without to much effort. Therefore, objects will be added and removed several times a minute.

I was originally going to allocate a large array for these objects and if the engine requested more, it would simply allocate another large block and used that as well. I cannot say how many objects will be active at once as the game's screen size isn't fixed.

So has anyone else created a program that's has a requirement similar to this one? If so, what did you use? Would a linked list be better in this case?

Thanks to any replies.

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.

I'll also code a particle and decal (used for the player's tracks) system for the game eventually which will add be very similar to the object system but will be allocating and freeing at a much faster rate. Should I used linked lists for these to?

Thanks again for your reply.

>>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.
Why don't you try implementing it with linked lists first, see if it's actually slow and then try something else?

> 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?

It's fine that many of them have such a limited lifetime. If you used a buffer with sliding windows some amount bigger than the screen, you could locate them very quickly with an indirect array lookup O(1) to skip the offscreen elements.

>>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.

Instead of removing entries from the middle of the array which is on average O(N), you can swap the item being removed with the last item in the list, and remove the last item. This should have better performance, though it assumes that the order doesn't matter. I presume this no problem for a particle system.

Then, of course, you must find some efficient way of getting them onto the screen. But you'd have to deal with that with linked lists too.

>>7
Surely it would be confusing if the player goes backwards even slightly, to find the world changing mere seconds after he left it. I'd keep two or three screens of objects around (and maybe more memorable objects from further away).

>>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
a limit that you will be going under, so that there isnt a constant amount of objects
also keep a list of ALL available objects
people have enough mem these days to have an enormous list
you can choose to change it after a transition too, ie. grass->desert
(imo a waste of 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".

In terms of performance, once each of the two vectors grows large enough to store the largest number of objects you are likely to have in any given session of gameplay, you have O(1) adding to the list, O(1) removal from the list, and each object can decide its own lifespan. More importantly, the vector of object pointers has strong cache locality, and can be iterated over quickly, and you don't need to allocate/free up any linked list nodes when objects are created or when they die.

Lastly, a factor which may or may not be important to you, objects in the object list are updated in the same order they are added, and when an object creates child-objects, it can decide whether or not those objects should update before or after it by the order in which those objects are added to the backbuffer. This can become very important late into a development cycle, and is a nice feature to have.

As a performance optimisation, if the data defining your objects is small, you may want to store the entire objects themselves instead of pointers to objects allocated elsewhere. This will improve cache locality for both reading and writing tremendously, and the performance savings could completely overwhelm the minor performance hit needed to copy the data for each object. In fact, a smart update routine could even eliminate some copies by writing the results of calculation for things like the updated position / velocity / animation data, etc, into the backbuffer.

This is an especially good paradigm to use for things like particle systems, and can be implemented on a GPU by having a geometry shader accept a particle as input and output any number of particles as output, and stream back and forth between two vertex buffers. This basic premise was used in nVidia's "cascades" demo to allow for fully dynamic water to flow around rocky structures, creating rivers and waterfalls.