Atul Varma - July 29, 2003
Pman is a Pac-Man clone I created over a period of about three weeks of intermittent coding. You can download the source tarball here.
The core game logic and graphics are fully implemented: there's a main menu, hi-score list, and a demo (aka attract) mode; once the game starts, Pac-Man can eat fruits, pellets and power pellets, be killed by ghosts and eat them, win levels to face-off against harder ghosts, and so forth. A scoreboard keeps track of the player's score and lives left. Everything is fully animated, except for Pac-Man's gruesome death.
The game's codebase is platform-independent, and the game has been compiled and run successfully on Windows, Mac OS X, and Linux.
The only third-party code involved in this project was the use of the Simple DirectMedia Layer (libsdl.org), a cross-platform, low-level multimedia API. This library provided basic routines for video access, blitting, and bitmap loading, as well as input and timing functionality. All other code was written by myself. Finite State Machines were researched and implemented to represent the gameplay state and the game agents, and a time-based message routing subsystem allowed them to communicate with each other; integer-based fixed-point math routines were derived and used for real number calculations; drawing algorithms were researched and implemented for the rendering of basic graphics primitives such as lines, circles, and triangles, and these functions were combined to dynamically generate graphics for Pac-Man and the ghosts on-the-fly; shortest-path algorithms were researched and implemented for ghost AI; a basic bitmap font library was coded to draw text to the screen; and a model-view-controller architecture was used to provide for extensible, "pluggable" game modules. This architecture also provided for a framework that semi-decoupled game logic from on-screen rendering (described in more detail below).
Before doing any coding, I sat down and wrote down basic finite state machines for how I thought the game worked. This got me thinking about what the various game tokens were, how they interacted, and so forth. It also gave me a general idea of the complexity of the project, although this turned out to be an underestimation (more on this later).
Modularity.
Unlike previous C code I've written, this program was pretty modular. No global variables were used, and module variables (i.e., static local variables with internal linkage) were kept to a minimum and their data was accessed by other modules using (reasonably) restrictive accessor functions. This kept things pretty understandable at all times, although there were a few instances where I didn't know what module to put a function in (for instance, should the map_fixed_vector_to_direction() function be put in the fixed point vector module, or the drawing module, where directional constants are defined and used?).
Refactoring.
Although code did get pretty messy at times, I tried my best to go back after a few hours worth of work to do some commenting and apply OO-style refactoring principles (a la Fowler, et al.) to this procedural code. "Extract method" was used on functions a lot to consolidate redundant code, "pull up method" was used in the GameAgent class to reuse code shared by pac man, fruits, and the ghosts, "magic numbers" were converted to constants, and sometimes functions were heavily modified to make them more readable. There is still a lot of code that is messy, but it's debatable as to whether it would be productive to refactor it since the project won't really be extended.
Asserts.
For the first time, I used C's assert() macro in my code, which increased readability and helped in bug-squishing without impairing the performance of production-level code.
Finite State Machines.
The finite state machine model described in Steve Rabin's article in Game Programming Gems made coding the behavior for ghosts particularly easy. Its benefits for other game tokens was debatable, however; the FSM model seems to be most useful for tokens that can be in multiple states and behave differently depending on those states, and the message routing model described in Rabin's article is very helpful when a message needs to be processed some amount of time after it is sent. However, these two things weren't extremely prevalent in the rest of the code, so sometimes I wondered if the payoff was worth it; yet I imagine that not using the FSM model would have resulted in tons of global variables and code that would have been far more spaghetti-like than it already is.
However, I did have a few issues with the FSM model, although it was partially because it was the first time I had modeled a moderately complex application using a FSM. For instance, the passing of parameterized information became difficult with the FSM's message routing model; this meant that it was much more cumbersome to send a message using a FSM than it was to simply make a function call, and figuring out which way to go in order to make the code more understandable was a learning experience. Sometimes it was also difficult figuring out which FSM to implement a behavior in, and I'm still confused about this in some cases; for instance, a behavior that seems like it should belong in the game board FSM may actually need to be implemented in the play state FSM because the behavior affects several different game tokens and changes the state of the entire game to some extent. Even the creation of a play state FSM separate from a game board FSM was debatable, although I'm sure this is a conflict I would have run into had I used OO methodologies or even non-FSM based procedural code. In other cases, I sometimes created a new state message type instead of reusing old ones, which felt like it bloated code, although it may have made it a little easier to understand in the long-run, since state messages had names that were very specific to the actual actions they performed.
Semi-decoupling of game logic from drawing.
I borrowed this idea from Game Architecture and Design by Rollings and Morris. The game loop is executed as fast as possible, and the model (game logic) is passed a parameter that indicates how much time has passed since it was last called. (This parameter is in milliseconds and has a maximum value defined in a .h file, which is currently defined as being about 200 milliseconds.) Thus the game always moves at the same speed on all computers (unless the computer is so slow as to play the game at less than 5 frames per second) but it plays smoother depending on how fast the computer is. This ensures that it can play on a wide variety of platforms.
Dirty rectangles.
The screen isn't redrawn anew each frame unless a particular game token says that it should be. In most cases, the screen stays the same and the background behind the game agents' rectangles last frame is just repainted, and the game agents are redrawn again at their new location. This made the game run at about 2300 fps windowed, 3600 fps fullscreen on my P3 800 mhz laptop. If I converted the ghost draws to straight blits of dynamically pre-rendered graphics (which is currently how the Pac-Man sprite is displayed), the game could run faster, and it would probably be even faster if I told the graphics library to put all the surfaces in video memory (which would be extremely efficient, I think, since the game code would never make the CPU modify any bitmap surfaces using non-blitting routines).
The MS Visual Studio IDE.
I managed to wean myself off emacs to try out the MS VS IDE, and it's very useful. Split-screen/pane features are similar to those of emacs, and most useful are the context-sensitive IntelliSense "auto-complete" features that automatically give you a pop-up list of all a structure's data members as soon as you use the dot or arrow operator, show you the parameter list for a function you're calling as soon as you type the opening parenthesis, function and constant name auto-completion at the press of ALT-RIGHT ARROW, and so forth. This saved me a lot of time because it meant I didn't have to go sifting through my code to remember what something was named. Another feature where you can right-click the name of a function or variable in your code and select "Go to declaration" and/or "Go to definition" and be taken to the appropriate point in the appropriate file was also very useful.
The MS Visual Studio Debugger.
In the past, I haven't used a debugger much to debug programs (I've usually resorted to printf() statements), but for this project I learned the basics of the debugger. Setting breakpoints and using step into/over/out of features was very useful for squishing bugs, as was being able to watch variables as they changed.
Knowledge of software requirements.
Because Pac-Man already exists, I had an excellent "blueprint" for the game and was able to find and play with a clone of it to figure out nuances of the game's behavior (although I never looked at anyone else's source code, since that was part of the challenge). Thus playing Pac-Man made the game's software requirements clear for the most part; if I were coding a game that had never been done before and had no such "blueprints" to work off of, I would have had to focus more on writing down the requirements and prototyping the game in a higher-level language like Python.
Platform independence.
I originally coded the game using MS Visual C++. Fortunately, using SDL allowed my multimedia modules to be largely platform-independent. After the codebase was stabilized, I learned how to use the GNU build tools automake and autoconf, using them with Cygwin for Windows (available at www.cygwin.com) to create a cross-platform framework for compiling the game, as well as for modifying and distributing its source code. This made porting the game to other Unix-based platforms extremely simple and straightforward, and it also made it much easier to maintain my software.
I utterly despise this language sometimes. Not that it's bad--it's obviously a godsend compared to assembly, but it leaves much to be desired when it comes to the other programming languages in the market today. Specific areas of frustration in this project included:
Not using standard naming conventions for variables and functions.
Although some care was taken to name variables and functions appropriately, such as prefixing a module variable with g_, and they were named meaningfully (i.e., I didn't call any variables eggsAndSpam), there were some other problems. Firstly, there were some times when a variable wasn't named very accurately but I didn't rename them (e.g., calling a variable curr_nibbloon_kills instead of ghosts_killed_since_last_nibbloon, which would have been more understandable). Also, prefixes should have been given for certain variables; e.g. prefixing a fixed point number with fix_ would have helped make code more understandable. There were also inconsistent naming conventions with functions; most notably, sometimes a structure's "constructor" would be called init(), other times a module's constructor would be called init(); when a module had the same name as a structure (see state.c), the module's constructor was called init() and the structure's constructor was called construct(), which confused things. To make things even more confusing, the shutdown() method was usually the complement of init(), but sometimes it was destroy(). Not actively focusing on naming conventions and their consistency impaired the readability of my code. (As I mentioned in the previous section, though, encapsulation would have helped here, as it effectively gives you namespaces; many of the naming consistency problems here were a result of global namespace collisions, although they still could have been avoided if I'd paid more attention to them.)
Bad programming habits and underestimating the project size.
Although I did refactoring in this project, near the middle of development I started to get a little impatient because the project was taking a lot longer than I thought it would. I had originally anticipated that the game would take a day or two to complete for the core coding and game logic, but the entire thing ended up taking a little over two weeks. This was discouraging; I worried that sometimes I spent so much time refactoring or over-designing the architecture that I was "spinning my wheels" and not spending enough time doing useful coding. Other times I accused myself of the opposite--that I hadn't spent enough time looking ahead, and had to backtrack some of my programming because many of the implementations I had started turned out to be inadequate when I found out that they wouldn't be able to support some aspect of the game's functionality. Other times I simply attributed it to a perceived lack of programming skill.
This frustration was dealt with in positive and negative ways. Sometimes I told myself that I had to keep coding so I could finish the project in a timeframe that I felt was appropriate; this resulted in long hours of sitting in front of a computer, trying to work as quickly as possible so I could get the job done faster, and this usually only resulted in more frustration. Encountering a minor bug resulted in more annoyance, which made me spend time being frustrated instead of actually fixing the code.
Other times, I simply took a break from coding, which helped clear my mind. I would also try to put the situation in perspective: with a few exceptions, the game was actually being implemented in much the same way as it would have been ten or fifteen years ago (in fact, aside from some memory management issues, I wonder how well this game would run on older computers). Pac-Man certainly would have taken a little longer to code than a weekend back then, so I assured myself that the project was just a lot more complex than I thought it'd be because I was doing so much "from scratch" and using a relatively low-level language for implementation.
Sometimes heavy frustration was a result of "bad smells" (to use Mark Fowler's terminology) in the code, and a solution was to refactor the code, which was almost like taking a break from coding because it was so easy. Howver, given some of the frustrations with C noted above, this was sometimes very tedious, which got me annoyed at C and made me wish I was using Java or another language that resulted in more maintainable code.
Ultimately, what I really wish I had was what Extreme Programming calls "pair programming". In my few experiences with pair programming, there was rarely ever a high level of frustration because two people were approaching the problem, which led to better solutions faster, and it also took pressure off both participants because they knew that finding the solution wasn't solely their responsibility--in social parlance, they had "a friend there to back them up", which reduced tension significantly. As the extreme programming philosophy mentions, it's also much harder for two people two code with bad habits, which results in less bugs and cleaner code, which leads to far less frustration in the long run. Pair programming also turns the otherwise solitary activity of coding into a social activity, which makes it incredibly fun and satisfying, which obviously helps reduce potential frustration even more.
Inadequate understanding of the problem space.
It sounds silly, but although Pac-Man was an ideal candidate for a project due to its level of complexity, I've never really liked Pac-Man as a game. Because I don't like it much, I haven't actually played it much, so I don't know much about its internal game mechanics. Late in development, a conversation with a non-programmer friend who has played the game extensively revealed that the ghosts supposedly move on pre-defined paths and don't actually have any dynamic AI, which would have made parts of the game much easier to code (for instance, it would have completely obviated the need for shortest path algorithms). Also, in the middle of development I realized that because the center of the ghost's home base (the code refers to this as the "asylum") wasn't on a "tile boundary", extra code had to be written to deal with this; this extra code complicated the final project and made it harder to read. Had I understood the problem space better, I may have been able to notice this earlier and thus I may have been able to design the architecture to seamlessly support it.
Not writing out the "goals" section of this post-mortem before starting the project.
Although I had thought about the goals before starting the project, I never actually wrote them down until starting this post-mortem. Having a solid, written document of my goals would have helped me in the instances when I felt directionless or overwhelmed by the task at hand (especially goal about developing better programming habits, which I tended to forget from time to time as I got wrapped up in the project). To some extent, this indicates a need for some kind of "programmer bill of rights" or "the seven habits of highly effective coders" (heh, heh) that I can refer to whenever I start getting frustrated with coding so I can stay focused. I may have to write (or find) something like this in the future.
Fixed point math.
I mostly implemented fixed-point math for educational purposes; I realize that many processors are now about as fast (sometimes faster) at floating-point math as with integer math, and of course efficiency isn't even much of a concern with a project as relatively simple as this. While implementing fixed-point math was fun, the problem was that the fixed-point numbers were encoded in integers, and although a typedef was defined for fixed point numbers, C still viewed all fixed point numbers as ints. This made it extremely easy to accidentally pass an int as a fixed-point number and vice versa, as there was effectively no type checking to discriminate between the two types. This led to a number of bugs that were hard to squish. (As mentioned earlier, though, I should have prefixed all fixed-point variables with fix_, which would have helped prevent mistakes.) Addendum: When attempting to compile this using gcc with Apple's Project Manager on OS X, the compiler did treat fixed as a separate type and raised warnings when a fixed was being used as an int and vice versa. I wish the MS VC++ compiler did the same.
Overall, I was satisfied with the outcome of the project. Through coding procedurally, I was able to gain a better understanding of how and why object-oriented methodologies evolved, and hopefully this will help me be a better programmer in the long run. This post-mortem will also help me figure out how to do things better the next time around.