1
\$\begingroup\$

I'm developing something similar to Galaga and I'm not entirely sure how to "manage" the bullets i.e. what data structures/algorithms/approaches to use when rendering them on the screen. Let's forget collision detection for now. The way I'm thinking of implementing this is:

  1. When the application starts, create an array of bullets. Make sure this is at least as big as the total number of bullets you want to have on the screen at any given time. Initialize all the bullets to some default settings. Also create a list of the bullets that are on the screen at any time. Obviously this will be empty initially.
  2. When the user shoots, get an element of the array and add it to a list of bullets that are currently rendered.
  3. When drawing, iterate the list of bullets and render each of them. If a bullet gets out of the screen (say y > 1.0f) then remove it from the list and reset it to default position.

Is this a sensible approach to the problem? Are there alternatives I should consider?

P.S. This question is language/framework (etc) agnostic, but if you think it makes a difference, I'm using OpenGL ES 2 on Android.

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ the approach is ok. The explosion happening on collision can be part of bullet's behaviour. \$\endgroup\$ – tp1 Mar 23 '14 at 0:15
2
\$\begingroup\$

There are two problems with storing game objects in arrays.

  1. You set a limit on how many game objects you can have. Sure, you could set some astronomically high amount which you are sure you will never reach, but then your data structure will always need the maximum amount of memory.
  2. When game objects are removed, you get holes in the array.

A better data structure would, for example, be a linked list. A linked list has the advantage that it can shrink and grow dynamically. Its maximum size is only limited by RAM, it never takes more space than necessary and you can remove items from the middle of it without causing holes in it.

When a new object is created, you append it to the end of the list. When you iterate the objects and notice that the object needs to be removed (leaves screen, hits a target or whatever), you can just remove it from the list by linking the predecessor to the next element and freeing the current node.

The downside is that it is less efficient than an array. It requires additional memory and the constant memory reallocation when you create and remove elements leads to memory fragmentation which can be detrimental to performance. But these issues are unlikely to be a problem in the case of a simple 2d shot-em-up.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 1. It doesn't need to be an astronomically high number. Something like 30 will be more than enough for such a game, especially if my bullets move fast and, as a result, leave the screen fairly quickly. \$\endgroup\$ – async Mar 23 '14 at 7:50
  • \$\begingroup\$ 2. I will use a separate list that holds the items that are currently rendered, not the array. I can freely add and remove items from that list without affecting the array. The purpose of the array is to have all the necessary bullets already initialized and ready to use at the beginning of the game. I won't need to create any other bullet throughout the game, just use one of those already stored in the array. \$\endgroup\$ – async Mar 23 '14 at 7:52
  • \$\begingroup\$ @user16547 30 will be enough? \$\endgroup\$ – Philipp Mar 23 '14 at 10:42
  • \$\begingroup\$ I'm afraid I don't understand that screenshot, nor your point. The number of bullets on the screen at any point is entirely dependent on how many times the user taps the screen - basically, if the user taps the screen, the ship will fire. The bullet is also fairly quick. I thought it was a fair assumption that the user won't be fast enough to tap the screen more than 30 times in a very short time such that no bullet gets out of the screen. \$\endgroup\$ – async Mar 23 '14 at 19:01
  • 2
    \$\begingroup\$ These days when people talk about arrays, assume they mean dynamic arrays, so your first problem doesn't apply. Also the problem of holes is very cheap to fix by moving the rest of the array to fill the hole; these days CPU prefetch is so much faster than memory that the random access of list structures is going to dominate any costs associated with contiguous arrays. I encourage you to do some benchmarks to see for yourself. \$\endgroup\$ – congusbongus May 22 '14 at 3:24
1
\$\begingroup\$

The only suggestion I would make to your approach is to keep away from linked-lists. Try to always keep the bullets in arrays, they are far more efficient when it comes to CPU cache. For more info on the subject, read this excellent article on Data Locality.

So for item 1 of your list, when you create a new "alive" bullet and move it from the global pool to a live bullets set, make this set an array and copy the whole structure to it. This way you keep a sequential array of alive bullets that is going to be super fast to iterate and cache efficient. It may seem like a dumb thing to copy the whole structure into another array, but chances are that the gained cache efficiency will outweigh the copy cost.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.