# Which data structure should I use for dynamically generated platforms?

I'm creating a platform type of game with various types of platforms. Platforms that move, shake, rotate, etc. Multiple types and multiple of each type can be on the screen at once. The platforms will be procedural generated.

I'm trying to figure out which of the following would be a better platform system:

1. Pre-allocate all platforms when the scene loads, storing each platform type into different platform type arrays( i.e. regPlatformArray ), and just getting one when I need one.

2. The other option is to allocate and load what I need when my code needs it.

The problem with 1 is keeping up with the indices that are in use on screen and which aren't.

The problem with 2 is I'm having a hard time wrapping my head around how I would store these platforms so that I can call the update/draw methods on them and managing that data structure that holds them. The data structure would constantly be growing and shrinking. It seems there could be too much complexity.

I'm using the cocos2d iPhone game engine.

Anyways, which option would be best or is there a better option?

## 1 Answer

There's a few data structures that meet your requirements: growth, adding, removing, iterable.

1. Linked lists (doubly linked). Easy to implement, easy to iterate to perform operations on each node. Not as fast for selecting a specific element, since you have to step through.

2. Dynamic array. Easy to implement, easy to iterate to perform operations on each node, fast for indexing. Not so good for adding and removing items in the beginning or end.

3. Binary search tree (balanced) Fairly easy to step through. Average for "indexing", adding and removing.

Which one to choose depends on your game. For example, if it were side scroller and you're always just adding platforms on the end and removing them from the beginning (as you scroll), the linked list would work great for that. If you always have a small number of platforms in memory < 100. Any of these structures will work just fine. You can always just pick on, and if it doesn't work out it should be simple to swap out for a more efficient structure.

If you're having trouble wrapping your head around these structures, I suggest you check out some free online courses for computer science. The introduction courses will introduce basic data structures. The MIT Opencourseware site is a good resource for this.