Damn you, Thief! …And spatial hashing collision detection

Thief 2013

Well there went about 10 days of my time play Thief when I could have been coding. Actually, that isn’t entirely a true statement. I have actually got around to cleaning up some of my code. You know, that maintenance stuff that puts you in good stead for going forward. Well, at least that’s what I’m telling myself.

Thief is a pretty good example of a AAA title done reasonably well. I don’t know if its mechanics and its story worked as seamlessly as Far Cry 3 or Dishonoured but it was certainly a good game and a good story. The stealth element with outbursts of pure mayhem certainly worked well for me. Oh, and the visuals are just amazing. The Victorian, Gothic & Steampunk city is amazing to look at and explore.

Anyhow, Some of the clean-up work I got done on Mutants 2014 involves my collision detection routine. I decided back around the first week of February that I don’t want to brute force check collisions between every object on screen since before you know it, you’ve got a ^2 iteration load to deal with. Rather, I built a simple spatial map of the screen which (for those that don’t know) essentially lowers the resolution of the screen “grid” when checking if objects occupy the same grid and warrant a closer collision check.

I’ve been taking the size of the play-field and dividing it by 4 to make the resolution of this spatial grid. Between sessions of Thief (when the game was just too much to handle in one session), I went back and looked at the collision code in Mutants and discovered a logical flaw in my code. I was dividing the the play-field by four and then another procedure was doing the same operation and dividing the reduced grid by another four! Essentially my spatial grid lost so much resolution that there was far too many collision checks happening. It was as if I turned my lovely spatial map back into a brute force method! Gah! What a waste of CPU cycles and how dumb of me.

It’s not that I can’t afford the CPU cycles, it’s just that I want to try and keep my frame rate up high. I want this game to feel graphically fluid. I even went to the pains of making sure my code used static arrays to hold the collision hash table instead of dynamic memory allocation. My thinking is that the number of objects is unlimitedly finite to allocate memory up-front and therefore avoid the CPU cycle cost of dynamically allocating memory at runtime. “Unlimitedly finite”? – Oxymoron! Well not quite, once there’s more than let’s say, 100 mutants on screen, it’s a safe bet that you’ll be dead before you know it. So the answer has been to avoid dynamic memory allocation for speed and to avoid potential memory leaks. Memory is cheap and in abundance so just grab what you need at the beginning. This isn’t the C64 (64KB) where memory it limited and I’m not writing a huge AAA title where you can chew up RAM like no tomorrow, so I can afford to do it this. Huzzah!

Anyway, the logic is fixed and now the spatial map is at the correct resolution. Collision checks now only occur when there is real potential for a collision. Nice job, Gavin. Now finish that game of Thief, uninstall it, and get back to work!

Leave a Reply