Sort+sweep detection: FINALLY

Okay, so I'm super happy that I've gotten the sort/sweep implementation more or less working for my collision detection. It took me a good long while, but it's working now, and the performance increase is noticeable.

My previous collision detection did the following:
Make a list of everything.
Go through each item on the list.
Test it for collisions with everything.

It's very easy to do and very inefficient. The new algorithm does the following:
Make a list of everything.
Make a new list of the beginning and ending positions on the X axis of each item and sort this list by these X positions.
Go through each item on the list.
Test it for collisions with any objects whose X position is between the start and end positions of this object in the second list.

That's a poor way of putting it. Here's a much better explanation. It even has pictures.

So anyway, it turns a really simple but time consuming problem into a somewhat complicated but much faster problem. I still haven't addressed the major issue for XBox, the mid-game creation of objects, and that will be one of my next major goals. Nevertheless, on my laptop it can go up to 1024 sprites (the most I'm supported at the current time) with virtually no hits to the performance. The video posted is a good deal slower due to the screenshot software.

Also, I don't think I've posted a video since I've made a few changes to the interface. I changed the screen size to 720p, so it's a big taller and a lot longer. I've moved things around a little to account for overscan on my HDTV. Finally, I've made the lives and the score displays a good deal bigger. I think it looks pretty.

Video: Extincathon sort sweep collision detection

Extinctathon: the long road ahead

I've spent the last week preparing my code for broadphase collision detection using a sweep and prune algorithm. I'm working on the actual sweep and prune process now, but getting it to work at a reasonable speed on the XBox seems like it's going to be an uphill battle. I'll be working on it for at least another week, and hopefully by that point I won't have decided to give up and focus solely on the PC.

I read an excellent article by John Wells on the topic of broadphase collision detection particularly geared towards optimizations for the XBox 360 (bit of a refresher: my game currently uses the most naive collision detection algorithm in the universe, checking every object with every other object, i.e. a O(n²) algorithm which absolutely breaks down on the 360 after five or six enemies are present). The two main goals are elimination of cases, i.e. testing the fewest possible number of collisions by implementing some rather simple logic, and the avoidance of garbage. The XBox 360 hates garbage. When you create heap-based objects, it spits in your face. It slows to a crawl. It writes goth poetry. It doesn't like new objects.

The first issue, the elimination of unneccessary cases, is easy enough to do. I'm still working on it, but I can finish it in a day or two. The second part, however, is far more complicated (to me) because it involves lots of C# functions (and even syntax) that I've never before seen. I need to learn how to do it, but it's rather complicated. I'll have to work on it later.

I'll post some more of the details a bit later when I have more time.

Extinctathon: enemy types and collision bugs

Now that the level loading is about halfway where I want it to be (it's independently loading lists of Blocks and Species), I need to do some serious work on the collision detection algorithms. I'll go into more detail in future posts, but here are the basic problems.

• I need to implement per-pixel collision detection. This is most noticeablely an issue with the Snakeocat at the end, which, by virtue of the size of its bounding box, floats in the air a good deal more than the other enemies
  
• I need to do a much better job of processing collisions with enemies once they occur. The player dies in a handful of situations where he shouldn't. Right now, the player dies if he collides with the bottom 3/4 of the enemy. If the player is falling too fast, or the enemy is rising too fast, even when the player hits the enemy from above he dies. What needs to be done is to extract the player from the enemy and then determine if the player was on top, to the side, or underneath.
• Similar fixes need to be done with regards to collisions with blocks. There is a rare bug when the player is between two blocks spaced exactly the width of the player apart that can cause some unusual behavior.
  
• I need to optimize the hell out of it. I deployed to my XBox for the first time this weekend, and anything more than 6 enemies on screen KILLS the performance. We're talking 1 or 2 frames per second. My basic algorithm is as naive as it gets (literally everything is tested with everything, an O(n^2) algorithm), and I need to fix it as soon as possible. It does fine with a couple hundred enemies on my computer, but, of course, that's a lot faster (with certain kinds of operations).
• In addition to optimizing the broad phase of the collision detection, i.e. deciding what should be tested against what, I need to do some serious optimizations on the collision detection itself. I have not yet decided how best to handle this.
• And, finally, I need to make it so that when enemies die by falling off the screen they don't give you points.

That's it for now. I was kind of lazy today and ended up just making a new enemy (the af0rementioned Snakeocat). I'll get to work on the serious stuff tomorrow.

Extinctathon: tiny updatelet

The whole Species content pipeline thing is done (enemy loading and saving, in lay speak), and now I'm going to be updating the Block class to make it more extensible and more geared towards classification via a BlockType enumeration, a method which I've found incredibly helpful with the Species class. I'd like to have more done at this point, but I just picked up Ninja Gaiden II -and- Lost Odyssey, AND I'm at work two days more than what's normal this week. Hopefully I'll catch up on Sunday.

In other, non-Extinctathon news, a friend has passed along some very sciencey Fortran code that models the flight of a frisbee given some initial conditions. Somewhere along the line I'll be turning this into an XNA frisbee simulator, but I really want to keep working at Extinctathon for the time being.

Extinctathon! Current short-term goals

I've got some time today and hopefully more during the week, so I've got a couple of big goals to work towards. The main one is to get the level loading and saving working (level meaning the list of blocks, list of enemies, start point, end point, and a few other bits of info). I was having some trouble, conceptually, with this, but Shawn Hargreaves came to my rescue and explained what all I needed to do. Before I do this, however, I need to make a big change.

Yes, you guessed it....SPRITE SHEETS.

Right now I'm loading 20 different textures and switching between them multiple times per call to Draw(). This is very GPU intensive, so I've heard, and it's much better to load them all into a single image and then draw specific portions of that image onto the screen. The reason I have to do this BEFORE I do the level saving and loading mechanism is that it will replace the lists of sprites that make up the animations of the various characters with lists of rectangles describing where these sprites can be found on the master sheet. This will be a pretty big overhaul, and I forsee spending my whole day (well, up until noon) working on it. Fun.

UPDATE:
I have the sprite sheets working, using the incredibly helpful projects here. I spent most of the morning just adjusting all the draw and bounds-checking calls to work with the new system. I'd say I'm about 20% done with the Level content pipeline system. It's going to take a good deal of work, but I think I can do it. Once that is done, I can work on making a few more enemies, Block types, and a system for implementing power-ups. Once that is done, I can get to work on some serious level editing--after a few much-needed improvements to the level editor, that is. And I still need to get the menus working, either by adapting the examples found here or by rolling my own in some fashion that won't make the code completely unreadable. Either way that seems like a big ordeal.

Extinctathon: new enemies, code maintenance

Not much to say, but I have added a new enemy (bees!) to the game. It's pretty easy to add them, really the only hard part is deciding what they look like and how they behave.

My project for the day is to replace all my C++ and Java-esque accessor methods with the more idiomatically correct C# style get/set methods.

Once again, boring stuff, but stuff that needs to be done. Another thing that needs to be done, seriously, is using sprite sheets instead of using a separate texture for every single frame of every sprite's animation. Switching textures, apparently, is incredibly GPU intensive, so it's better to put groups of sprites into single textures and then drawing portions of the larger textures onto the screen.

UPDATE:
I've finished updating the code using the get/set property style. I moved stuff around to match with the style I've seen in most of Microsoft's projects. I even took a look at the menu and game screen system examples on the XNA site, but it's too much for me to deal with right now.

Source:
Extinctathon (entire project, zipped)