The Road Traveled Again -- An Unexpected Point of Failure
Akake on 2009/08/17 15:46
of Raster Blaster
The frame rate tanked, falling from 30 to around 5 with just five entities on-screen. :-(
It seems that separating axis collisions are much, much more intensive than rect ones. I knew that, but I underestimated just how much more time it takes.
I can't really salvage this one. There isn't really anything I can trim off of it to make it go faster. It's a shame, because I had high expectations for it.
On the bright side, my spatial hash worked beautifully, and with minimal bug-fixing. :-)
The performance clearly varied depending on how many entities were on the screen, running fine with none, and deteriorating as the number grew.
I've learned a few things from the experience, as well.
I've learned to not underestimate the cost of techniques that I haven't used before, and also that I enjoy making minimalist pixel sprites.
I came into this knowing that failure was possible, and it seems to be that it occurred.
----
Rabbit Hunt -- Post-Mortem
Rabbit Hunt began with minimal progress, but quickly grew into a functional platformer.
I made terrain sprites, but they looked really awful, so I eventually scrapped them.
I only wound up with the sprites for the player and a ! icon that mobs would have displayed when they detected something interesting.
The collision detection was fairly easy to work with, but proved to be too much for the game to easily handle.
I initially wanted entities to check for collisions a few times every frame to keep the speed up while minimizing the amount of that bouncing that separating axis seems to cause when collisions effect velocity, and the tendency to fall through things that entities seem to have when non-tile systems are used.
This created staggering performance hits with only the player entity, so I moved on, changed it to one collision check per frame, and put in a load of test entities.
After hitting my world cells with a hammer a bit, they worked beautifully. The only problem was that the performance hit from having more than one collision check per frame reared its ugly head again.
This did not prove to be fixable, and seems to be a characteristic of separating axis when used with highly sub-divided terrain.
Attempts to group terrain into larger chunks would likely only mitigate the problem somewhat, and would not have helped significantly with a full environment, where there would have been numerous entitities, and complex terrain that could not be reliably sub-divided.
Ultimately, I've learned that if I'm dealing with numerous entities, I should use rect-based collisions, because they are simpler and much, much faster.
Separating axis was a joy to work with, though. I will certainly use it in future projects.
Projects with fewer entities. :-P
Lessons Learned:
* Complex collision systems take lots of processor time in Python
* World hashes greatly improve performance, and are fairly easy to implement
* Minimalist pixel art lends a game a graceful look that even an art-impaired programmer like me can create
* New techniques should be tested for performance impact before a project is fully underway, to determine whether something simpler would be a better option.
* SVN is a very handy way to back up code, as I discovered a few times during development
Overall, the experience was a good one. It was the first project I've had in a while that I could detach myself from healthily that was more than just a super-simplistic shmup.
It was fun, and I'm satisfied, even though I ultimately failed.
---Akake
(log in to comment)
Comments
Akake on
2009/08/17 18:22:
I understand your point about optimization in general, as well. I'm definitely going to keep it in mind.
Not that I think of it, probably the best lesson I learned from this project it that I can handle doing something I haven't before. It won't always succeed, but it's always more fun than the same old thing. ^_^
Besides, failure is always an option!
I've already begun on my next project, but I'm not going to share anything until I have a demo ready.
It's something I haven't done before, though, to be sure. :-)
Again, thanks for the advice. It's very helpful to me, and I'll definitely remember it for future projects.
---Akake
There are two techniques for optimising collision detection which I've found useful.
The first is fast failure. By this I mean quickly identifying objects that are definitely not colliding, which will likely be the majority of tests. You can do this by using simple bounds tests (either rectangles or circles work well) first, and then going on to more expensive methods like separating axis or pixel collisions only in the case where the bounds overlap.
The second method is to avoid performing collision tests in the first place. The fastest code is always the code which isn't executed. Instead of looping over all objects when testing collisions, just loop over the objects which are possible colliders, even if identifying these is slightly more work. Especially in the case where you have a large number of static objects such as terrain, you can preprocess these into an efficient data structure for identifying those which might collide with a given object.
Optimisation is rarely about trimming off bits to make things go faster. The big wins generally come from smarter code that doesn't do any more work than it has to, rather than simpler code that does the work it has in slightly less time.