Tuesday, October 28, 2008

One of those days...

The collision bug I mentioned last time turned out to go deeper than I'd realized. At the lowest levels of my swept ellipsoid tests, I transform the ellipsoid into a unit sphere and transform each triangle in each collision mesh into the same space as this sphere. It sort of normalizes and simplifies the math. So then I sweep this sphere against the plane of the triangle, and if there's an intersection, test that point for containment in the triangle. That was where I thought things were going wrong before, but it was actually because of bad results from the sphere-plane sweep. It took me several hours trying various permutations of potential fixes on a half page of code before I finally rewound, started fresh, and ended up with a fix that I swore was one of the first things I had tried.

That's the frustrating side of programming. Hard-to-debug problems without obvious causes, where there's nothing to do but keep hypothesizing about why it's broken, applying a patch based on that theory, and then hammering on it to see if it holds. Fortunately, days like that aren't as common as the good, fun days where everything just works. Sometimes, though, we just have to dig in and fix nasty bugs. That's what really separates a good program from a bad one, regardless of the programmer. It's still pretty satisfying when it's finally fixed; in this case, I can walk through the 3D world and trust that it's solid again. That's a nice feeling.

Sunday, October 26, 2008

Weekend SVN Logblog, (Oct. 26, 2008)

Last week I played Fable II. The end.

Okay, maybe my productivity this past week wasn't that bad, but it sure feels like it. Maybe a review of my recent checkins will prove me wrong.

------------------------------------------------------------------------
r905 | Administrator | 2008-10-26 00:38:40 -0700 (Sun, 26 Oct 2008) | 3 lines

Fixed a bug with point-in-triangle testing (I wasn't checking that the point was in the plane).


I posted a pre-alpha build of Strange Visit on the TIGSource forums, and at least one user called me out on the collision bugs. I knew they were there, but I was trying to pretend they weren't that big of a deal. Of course, it was--worst case, the player could become completely stuck in the geometry of a map and be unable to move. I eventually tracked it down to a point-in-triangle test that was giving false positives because I wasn't first ensuring that the point was actually in the triangle's plane. This is was happens when I copy algorithms wholesale from other sources and don't fully grok their proofs. Lesson learned.

------------------------------------------------------------------------
r901 | Administrator | 2008-10-25 15:50:58 -0700 (Sat, 25 Oct 2008) | 2 lines

Bunch of work on SV exterior.
Fixed endless recursion bug in sector traces.


Most of this week was spent blocking out the level for Strange Visit, and it's finally at a decent state. Working on it has continued to reveal bugs relating to sectors and portals; in this case, a stack overflow when a ray was traced through more than one portal such that it ended up back in a sector it previously traversed. This is why it's important that I'm finally making a "real" level instead of just simple test cases.

Sunday, October 19, 2008

The Weekend SVN Logblog (Oct. 19, 2008)

It was a busy week for my hobby projects. I made some substantial performance improvements to the engine and started a small side project that has been shaking out bugs like crazy. Let's take a look:

------------------------------------------------------------------------
r858 | Administrator | 2008-10-14 00:40:52 -0700 (Tue, 14 Oct 2008) | 1 line

Big particles refactoring, so that particle systems don't allocate and create new vertex buffers every frame. Sadly, locking and copying doesn't seem much faster.


I've been worried about the performance of my engine for a little while now; I was only getting 20-30fps in Release mode, and the rates in Debug were almost unplayable. Profiling suggested that particle systems were to blame, so I looked into it and realized that I had left particles in a very hacky state, intending to come back and clean it up if performance started to degrade. Every frame, for every particle system, I was allocating new vertex arrays and creating new Direct3D vertex buffers from them. I rewrote it to reuse a persistent vertex array (updated each frame) and to lock and modify a dynamic Direct3D vertex buffer for each particle system. As the changelog suggests, it wasn't actually a great performance gain, but it helps a bit and I feel better about the code. I still hate having to deal with dynamic Direct3D objects when resetting the device, though.

------------------------------------------------------------------------
r860 | Administrator | 2008-10-14 22:57:51 -0700 (Tue, 14 Oct 2008) | 1 line

Added some HTTP socket stuff for eventually doing leaderboards, stat tracking, whatever.


Inspired by J. Kyle's leaderboard solution for Arc, I decided to dig into WinSock and get some communication going with my web server. I found it surprisingly easy to establish the connection and send HTTP requests, and before long, I had a sample program sending a POST request to a Python CGI script and getting back a meaningful response. I'll have to revisit some of this when it comes time to actually write the leaderboard code, because I'm not actually parsing the response yet, but for a first pass at something I had no prior experience with, I was very satisfied with the time it took to get something running.

------------------------------------------------------------------------
r862 | Administrator | 2008-10-15 06:14:38 -0700 (Wed, 15 Oct 2008) | 1 line

Added core of a new profile system. None of the UI is started yet, and profiles can't be deleted, but the folder structure and config files are all working as intended.

------------------------------------------------------------------------
r866 | Administrator | 2008-10-15 18:30:50 -0700 (Wed, 15 Oct 2008) | 1 line

Short of finding and fixing bugs, profile system is done.


A profile system is something I've been thinking about for a while now, but I kept debating its usefulness. Basically, it provides a named container for saved games and player options, so that multiple players sharing a computer can have their own personal configurations. The leaderboard concept (coupled with a sick day that gave me hours and hours to work at home) finally provided the catalyst for doing this, because I wanted to have a constant user name available instead of making the player type a name every time he submitted a score. Despite it being a fairly significant chunk of work, I managed to finish the bulk of the profile system in just over twelve hours on Wednesday, with a last few fixes coming in just before midnight.

------------------------------------------------------------------------
r871 | Administrator | 2008-10-16 19:52:25 -0700 (Thu, 16 Oct 2008) | 1 line

Added typed EIDs.


This is a small one, but significant for code readability and type safety. I previously just used unsigned integers (EIDs, or Entity IDs) as handles to game entities. It's a simple abstraction trick: these EIDs are used as keys to look up the Entity pointers in a map, so a deleted object will return NULL and I avoid dangling pointers. In the past, I would simply static_cast the returned Entity* to whatever type I knew the handle was meant to represent, but I was never happy with that solution. Now I have a small TypedEID class, templated on the type of Entity it refers to. This class mostly just wraps the basic EID functionality, but it returns a pointer to the correct type (just static_cast still) and also has a slightly more expensive checked accessor that returns NULL if the actual type of the entity does not match the class template. (This requires run-time type information, but I've previously rolled my own RTTI implementation, so that was free.)

------------------------------------------------------------------------
r881 | Administrator | 2008-10-18 16:45:22 -0700 (Sat, 18 Oct 2008) | 1 line

Some initial work on the Commonplace Compo map.


I've been trying to get involved in the indie games scene a bit more, and to that end, I'm entering the TIGSource Commonplace Book Competition. It's a very casual competition: no entry fees, no prizes--mostly just a deadline so people actually get things done. The theme is H. P. Lovecraft's "commonplace book," a journal in which he jotted down ideas and story fragments that might eventually have been developed into fuller stories. I chose the following quotation to base my game upon:

30 Strange visit to a place at night--moonlight--castle of great magnificence etc. Daylight shews either abandonment or unrecognisable ruins--perhaps of vast antiquity.

Strange Visit, as I'm calling it, will be a small game built on the engine I've already got. Because I don't have any real gameplay systems yet, it will about atmosphere, exploration, and discovery instead of rules of play. Developing a real level has uncovered some latent bugs that were hiding in my engine (especially with regard to sectors and portals), but I've been steadily squashing those as they arise.

I expect that the next few weeks will be consumed almost entirely with content development for Strange Visit. I'll return to programming around Thanksgiving, after the competition deadline, and finally start developing some gameplay systems (weapons, inventory, AI, etc.).

Friday, October 17, 2008

Don't Be Stupid!

I'm in the process of changing web hosts, so this won't post until probably a few days from now. Midphase was recommended to me, and their basic web hosting package looked like a really good deal, so I took the plunge. Their service has been prompt so far and the controls are way better than my last provider, so I'm happy. On a side note, I still hate the way domain names (and in this case, the transferring thereof) are handled.

But that's not why I'm writing this. No, today I learned an important lesson: don't be stupid.

I have this nifty little "configuration variables" system in my engine. It primarily lets me define key-value pairs in a config file (just like an INI) and access those values by name at runtime, like so:

float Foo = ConfigManager::GetFloat( "Foo" );

There's many reasons why data-driven values are preferred to hard-coded "magic numbers" in games, and I get quite a lot of use out of this system. In fact, as performance on my game began to decline, I suspected it might be due to my rampant use of config vars all over the code base.

What happens when this config var is accessed? The name ("Foo") is passed down to the accessor function, where it is converted into a hashed value (that is, reduced from a string of letters to an integer). That hash can be quickly compared against all the hashed names in the massive table of config vars to find the requested variable. If it is found in the table, the function asserts that the config var is the type that was requested (in this case, a floating-point value) and returns that value to the caller if it's valid. A default value may be used in case the value was not found or was of the wrong type.

A metaphor for non-programmer types: You go to pick up your jacket from the dry cleaners. You supply the clerk with some information about your jacket, and they go and find it on the racks and bring it back to you. But imagine that instead of handing the clerk a stub with a number that matches the tag they left on your jacket, you hand them a piece of paper on which you've written a riddle. When solved, the riddle reveals the number that matches the tag on your jacket. You can still go and get your jacket from the dry cleaners just like before, but now the clerk spends all her time solving riddles. When a flood of customers starts arriving, she's so backed up solving the riddles that she can't deliver everyone's garments in the expedient fashion to which they're accustomed.

Back to programmer land. Solving the riddle is a metaphor for the hash function. If the system is using small, simple hashed values to find the requested items, why are we giving it big, long strings? These are just riddles that it needs to solve before it can do the task that it was meant to do.

So, bringing it all back to that important lesson: don't be stupid. You would never expect the dry cleaners to solve a riddle to find your jacket, and it was just as stupid of me to be hashing strings inside the config var accessor functions instead of just using a hashed value as the given key.

A conclusion! It was an epic two-hour refactoring job to actually fix this in my game. Every case where I used a string literal (like "Foo" in the earlier example) was replaced with a static hashed name so that it would only have to be computed once. This one simple fix doubled my frame rate in Release mode. Don't be stupid.

Monday, October 13, 2008

Rant

I realize that EA/DRM anger is so last month, but I recently came across an interesting case that makes me question the honesty of EA's promises to the Spore community.

In an interview with MTV Multiplayer, an EA representative promised that:

If we were to ever turn off the servers on the game, we would put through a patch before that to basically make the DRM null and void. We’re never walking away from the game and making it into a situation where people aren’t going to be able to play it.

This is a decent way to pacify a very real concern amongst gamers, that the products they buy might be remotely deactivated at some arbitrary time in the future. This will surely happen eventually, and nothing is ever lost on the internet, so the remaining Spore players will hold EA to this. Whether EA keeps their word (or are even around anymore, or can find developers to make the patch, etc.) remains to be seen. But there's a way EA can really secure the faith of gamers, today.

Patch your games from ten years ago.

Show your concern by fixing the DRM-related problems that plague older games. Off the top of my head, I can name two EA-published games from several years ago that no longer run properly because of the existing copy protection: System Shock 2 and Clive Barker's Undying. I know, because I've recently tried to play both and been thwarted by SafeDisc protection that won't validate on my newer machine even though I own a legitimately-purchased copy.

Of course, there are illegal ways to circumvent the problem. There are several SafeDisc cracker programs that will get me playing my old games in no time. But that's not the point. The point is that, right now, there are games published by EA that I purchased but cannot legally play because of DRM measure. If EA wants anyone to take their new promises seriously, they need to first fix the problems from years ago.

The Weekend SVN Logblog

So I'm going to try something new that I've been meaning to do for a couple of weeks now. Every weekend, I'll post comments regarding interesting developments on my hobby project from the previous week. I should have posted this last Friday or Saturday, so I'm off to an auspicious start.

------------------------------------------------------------------------
r845 | Administrator | 2008-10-06 22:00:09 -0700 (Mon, 06 Oct 2008) | 1 line

Early work on behavior trees.
------------------------------------------------------------------------
r853 | Administrator | 2008-10-08 23:05:51 -0700 (Wed, 08 Oct 2008) | 1 line

Finished the fundamental composite behavior tree tasks.


(Yes, I log in as Administrator. What of it?)

So my big accomplishment last week was doing a first-pass implementation of behavior trees for AI decision-making. I spent a while debating what I would use for behaviors in this project. I had prior experience with Goal-Oriented Action Planning, but I didn't anticipate needing the benefits of a planner. Behavior trees seemed more useful for this game (a fairly straightforward shooter), and it gives me a chance to learn something new. I'm following pretty close to behavior trees as defined in AlexJC's articles (at AiGameDev and in the latest AI Wisdom book), and I've finished implementing the basic composite tasks (Sequences, Parallels, and Selectors) that will be the core of every tree. I've also implemented a very simple movement task as a proof of concept, so I now have a non-animated, faceless, blocky character proxy turning and navigating through my world. It's uncanny.

------------------------------------------------------------------------
r848 | Administrator | 2008-10-07 23:07:37 -0700 (Tue, 07 Oct 2008) | 1 line

Added option to toggle vibration. Changed all visible instances of the word "rumble" to "vibration" (because rumble is a Nintendo-specific term).


I think I'm right about this, but...? It can't hurt, anyway.