A grid based layout game and removing items

Let's say I got a collection (simple grid) of invaders:

In this image, only invader type C can shoot.

Shots are fired, an invader gets destroyed:

Now, invader type B in the third column in the second row can fire as well. Note that there can only be three random invader shots on the screen at the same time. So only three of the invaders in the set {C, C, B, C, C, C} can shoot.

How would I go about implementing this? I am thinking of two solutions:

1. Use an array of arrays [][] (or [,]). When an invader get shot, the place where the invader was gets set to null. Then, when it's time for the invaders to fire, there's a loop going over the first row. Encountering a null makes it check the space above the null. Is it null? Then do the same for the space above that. Is the space in the uppermost row null? Go to the next column in the first r开发者_JS百科ow.

2. Each invader type has a position (I use Point for that). Assign to each position the row number (the collection used will be some sort of dictionary). So, when looking at the image, all C's get a 1, all B's get a 2, and all A's get a 3.

   

   In this picture, C at position (2, 2) is destroyed. It should then subtract 1 from it the Y value of the point, which will be (2, 1). If there's a position like that in the collection, then assign the invader at that position (2, 1) to the position of the invader that got destroyed (2, 2).. Like this, I don't have to have a jagged array containing a bunch of nulls.

My thoughts about how it should look like -> when the game starts the first set is {C C C C C C} and then it will be {C C B C C C}. From this set, three will be randomly chosen to fire.

So, any thoughts?

I disagree with Mirkules. I would suggest you not keep a separate data structure for only the invaders that can shoot. In general it's always a good idea to stick to the DRY pattern to prevent logic issues later on. For a simple application where you can keep the entire program in your head, it's probably not a big deal. But when you start working on larger projects it becomes more difficult to remember that you need to update multiple data structures whenever you modify any one of the associated structures.

Premature optimization is the root of all evil. You probably don't even need to worry about an optimization on such a miniscule level. It is my experience that when you spend a great deal of time working on these types of issues, you end up with good code, but you don't have much to show for it. Instead, I prefer to spend time getting my app to do what I intend, and then refactor it at a later date. Seeing my app work properly gives me the motivation to continue writing more code.

Good luck with your game. Xna is so much fun to write games in!

In game development, especially in a managed language like C# and especially on the Xbox 360, in general your first priority should be to avoid allocating memory while the game is running. Saving memory and reducing operation count is a secondary concern.

A null (in 32-bit, which XNA runs in) is just four bytes!

A 2D array ([,]) containing pointers to your invaders seems entirely appropriate. Especially as it allows you to make the location of each invader implicit by its location in the data structure. (Do you even need to create individual invader objects and point to them? Just use a number which indicates what "type" of invader they are.)

Looping through that data structure (in the manner you suggest) is going to be so amazingly fast that it may well be a "free" operation. Because the processor itself can process the data faster than you can bring it into the cache anyway.

AND you're not even doing it every frame - only when your invaders fire! I am willing to bet that it would be slower to calculate and store that data whenever an invader is destroyed and then load it when your invaders fire.

(Basically what you are proposing is caching/pre-computing that data. A useful performance optimisation technique - but only when it's actually necessary.)

You should be a lot more worried about costs that happen each frame, than ones that are only triggered occasionally by timers and user input.

Do not use a jagged array ([][]). This is basically an array of arrays. It uses more memory and involves an additional layer of indirection which in turn also has the effect of potentially reducing the locality of your data (meaning your data might not end up in the cache in a single hit - this is the "slow bit"). It also increases the number of objects the GC has to think about. Do not use a Dictionary for the same reasons.

In game development it helps to keep this kind of performance stuff at least in-mind when you work (anywhere else this would be completely premature optimisation).

But, for something as simple as Space Invaders, you can pretty much do whatever you like! So do the simplest thing that could possibly work.

I would keep a 2D array of all invaders. In addition, it would be a lot faster if you maintained a separate data structure with pointers only to the invaders that can fire instead of having to loop through the entire array each time you have to fire (causing your program to be really slow in the beginning since there will be a lot more invaders). So in your first diagram, your data structure would contain all "C", and in the second diagram {C, C, B, C, C, C}. When it comes time to fire, you just have to reference this data structure, get their pointers and then only call "fire()" on any of those invaders.

You didn't quite explain how the three invader that can fire are selected, so my guess is it's randomly chosen -- in this case, all you would have to do is pick a random number between 0 (inclusive) and n-1 (where n is the number of invaders in your data structure, in this case 6).

Finally, when it comes time to destroy an invader, if you have the 2D array and you know the position, it will be really easy to pop the killed invader off the "firing squad" data structure, and assign the one above him to the firing squad (i.e. invaderArray[KilledInvader.row-1][KillerInvader.column])

Hope this makes sense.

Can an invader change column? And can it pass an invader that's in front of it?

Assuming that the answer to both questions is no, I would maintain a Queue/List for each column. Then, the set of invader that can fire is the first element in each Queue. When an invader is destroyed, you would just pop it off the queue. Again, assuming only the front row can be destroyed.

Each invader would have to maintain a position for updating and drawing purposes.