Bullet List Hell

Monday 06 December 2010 at 8:36 pm.

So, mainly just to see what sort of performance I would get with it, I decided to throw together the sample code from a thread on the XNA forums about bullet management for a danmaku (bullet hell) game. Taking the first of the two example codes on there, I whipped together a good test example that, if I kept all the bullets on the screen, would get ~12,000 on screen on the XBox, and ~20,000 on screen on my XPS before there were any dipping below 60 FPS.

The problem, however, came when I tried to remove them from the screen instead of bouncing them around. The boundary check was not the problem, of course, because it was doing that for every node every frame (way more than it should need to anyway) in the first place. But when I started deleting them, it began to lag after 100+ bullets on the screen, progressively worse for each additional bullet drawn, while still apparently reporting that it was running at "60 FPS". 

Now the entire point of the thread itself was managing draw order so newer bullets would always be on top of older ones, so there are two extra sets of information in addition to the actual set of bullets themselves: a sorted list of bullets, plus a list of all the empty slots in the static array to hold all the possible bullet slots. What didn't make sense to me, though, was that the sorted list, instead of being singly-linked like I was expecting it to be (because there's really no need to step backwards through it), they decided to go with a doubly-linked list for whatever reason. Now, doubly-linked lists I had hated from back when I took AP Computer Science in High School, but had forgotten, so I just ran with it, despite regular lists making more sense for this situation and their test numbers sporting good framerates.

That in itself was the problem. Not ever having used them before in C#, I had to look up their functions, and from what I could find in MSDN I could find no way to drop a node other than the Remove() function on the list itself. And this is where the performance was taking a hit, because as it had to drop a node, it always had to start at the beginning again because of the way a dual-linked list works (instead of simply jumping to an index number with a singly-linked list), delete it, then jump back to the beginning and iterate again. So the more and more bullets there would be, any time one single one dropped there was more the crawler had to go through.

A simple switch to a regular List and simply iterating through it in an index loop, and - with the velocity settings I have set right now since its all entirely random for this experiment - I'm sitting pretty at ~350 bullets on screen at any one time right now at ~1200 FPS. Buch better, much faster, and much more sane.

No comments


Title: Bullet List Hell
Date posted: 06 12 10 - 20:36
Next entry:   » Deconstructing The Sp…
Previous entry: « It's Safer Here!