Skip navigation

Category Archives: software design

I wanted to start typing down some things as notes I’ve learnt during the development of Freekick until now before I forget all about them. The first article in the series is about one of the most important things that are different between Freekick and my previous hobby projects: modularization in software.

I first started to understand the importance and the benefits of modularity as I read the great book “The Art of Unix Programming” by Eric S. Raymond, a book I can recommend to every software developer, even those who’ve never used or programmed on Unix. Lacking modularity in my programs was the biggest reason why I had to abandon them sooner or later – I’ve ended up in such horrible situations where tweaking the AI creates a bug in the main menu, for example.

As mentioned in the book, managing complexity is one of the most crucial (and difficult) jobs when developing software. Basically, as long as you can simplify the tasks of the software into more and more smaller, simpler sub-tasks, and organize them so that you always know which parts of the software should be talking to each other and how the talking is done (interface design), you have no problem. If you lose the overview half-way to the project but go on writing code, you probably won’t get it finished.

From a developer’s point of view, some programming languages encourage designing the software top-down, always breaking problems into smaller pieces, and then implementing the software bottom-up. I take FORTH as an example, in which it is near to impossible to write even slightly complicated software without designing it thoroughly in a top-down fashion first. Most languages, such as Java or C, don’t really force you to manage complexity in any way, but merely provide you with the tools.

There are a lot of ways to bind all your software components so tightly together that there’s soon no way to take them apart anymore. One way is having a so called “god class“, a class usually aptly called something like “World” that ends up having most of the code in the project. Other popular ways include global variables, static variables or simply functions that are 1000 lines long, with multiple static variables that are conditionally used for different purposes in the beginning, middle and end of the function. Here are some small hints how such misfortunes can be avoided.

One thing to keep in mind is that each class, function and module should have exactly one well defined task to do. When I put it that way it sounds almost trivial, but it’s still sometimes forgotten. Another problem that I often see are confusing interfaces: when designing the interface, don’t have functions InitTaskX(), BeginTaskX() and StartTaskX(), where StartTaskX() internally calls InitTaskX() and BeginTaskX() in sequence. Instead rather decide on one option that the one using the interface will need (even when it’s “future you” – in a few weeks you’ve forgotten what you meant with all the weird functions anyway) and stick to it.

Another thing I wanted to use to increase modularity in Freekick was to split the whole application in multiple processes. There’s one process for doing all the non-soccer-match stuff – menus, league tables, transfers, etc. and other processes for the actual match. When the main menu process starts a match, it creates an XML file for the match server, then starts the server and passes this XML file to it, then starts the other match-related processes (client and AI). This allows me to be 100% sure that I can change anything in the menu part of the application and not break the actual match, as long as I don’t change the XML file which serves as the interface between the two.

The server itself handles the physics, rules and the match state, while the clients display the state received by the server and send user input to the server. As a nice bonus adding multiplayer capability is relatively easy, even though it was something I hadn’t originally planned. Another positive thing about it is that I can use different programming languages for different processes; I’m currently writing the menu part in Python and the actual match part in C++. There are also more sophisticated libraries for accomplishing a similar task, such as D-Bus, but I felt it would’ve been an overkill for this one.

As for the server and the clients, they communicate over a simple, clearly defined Freekick protocol that works over network sockets. This allows me to change the way the client displays the match, for example, without me being able to break the functionality in the server. In Freekick, the AI is a client as well, which allows me to reuse much of the client code while still having clear limits on what code belongs to the client that the player sees, what is only relevant for AI and what code is used by both of them.

Splitting the game into a server and a client is what FreeCiv did as well, by the way. That’s why there exist multiple clients for FreeCiv that do the same thing but look different. Freekick has two clients now as well, one that shows the match  in 3D and another where all the graphics are text based, using Curses. In the end they both same exactly the same soccer match with the same AI, logic, state and rules, only the way of displaying it and receiving input from the user different.

As for the internal structure of the server itself, I’ve also tried to keep things as independent from each other as possible. There’s the Physics class, which is a facade to the whole physics subsystem. Then there’s Rules, a class that is responsible for calculating the changes in the current rules status of the match. Physics can be subscribed to, implementing the visitor pattern, and is subscribed by Rules. Rules receives all updates from Physics (where the ball is at the moment, which player touched the ball, etc.) and updates the rules state correspondingly.

Rules can be subscribed as well, and both of these classes are subscribed by Dispatcher, a class that sends both kinds of updates, rules and physics, to the clients. How does Dispatcher know who the clients are? There is the class ServerManager, which accepts incoming connections and adds them to the list, which the Dispatcher has a pointer to. There are also classes ClientEventListener that receives the input from the clients and InputMonitor, which validates the data before passing it on to Physics.

Freekick is using Bullet for physics simulation. While Bullet is an excellent library, I can’t be sure Freekick will be using it forever (who knows what kind of open source physics libraries we have in five years). To make sure the physics engine can be exchanged in the future as easily as possible, I wrote an interface that should correspond my needs and no more – functions like addStaticObject(form, position) and simulate(timestep) – a wrapper. The interface is then implemented by the BulletPhysicsEngine class using the sometimes not-so-clear Bullet interface.

These are some ways to add modularity in software – of course, there are more and maybe better ways to do it, but these have made it rather easy for me to continue implementing Freekick, even as the code base has gotten bigger with time. For the interested, the Freekick code itself can be browsed here.

A few weeks ago I wrote I’d try and write a new Freekick client using OGRE3D and C++. The reasons for this seemingly dramatic language switch from Haskell were manifold; the top one being the jittery feeling in the old SDL client, apparently resulting from some timing issues regarding my thread management in Haskell I wasn’t able to sort out. Another thing that greatly influenced the decision was that I had split the whole project in multiple processes already during the design; since the processes communicate with each other via sockets, reimplementing one part (even in a different programming language) is relatively easy.

The first version of the OGRE client is now finished, and it has about the same functionality as the very first version of the SDL client: the user is doomed to be a spectator as there is no way to control a player, the only controls available are merely for moving the camera around. I personally found it very interesting to see the functionality of both the server and the AI through a different client; of course the rest of the functionality has stayed the same and the AI is as stupid as usual, but now it’s robots instead of red and blue squares kicking the ball.

Oh, here are some screenshots of the new client. Obviously, there a lot to be done (more than the pictures can describe), but it’s a start.

OGRE client
Top-down look

Another thing I find rather exciting is how easy it is to produce software these days that has features I could only dream about five years ago. Back then, programming multi-threaded networking or 3D scenes with custom meshes and lighting (including shadows) was a nightmare (for me at least), but nowadays (especially with the aid of such terrific libraries as Boost or OGRE) I can spend more time programming the essential things.

A few words on the design of the new OGRE client. I wanted it to have three distinct parts which communicate with each other via simple interfaces (true to Rule of Modularity) – networking, graphics, and match state. The basic idea is that the networking part receives information about the match state from the server and writes it in the state part. The graphics part renders the scene and reads the information for this from the state part, so the state acts as a kind of broker between networking and graphics. As only one part writes and the other one reads the mutable, shared data there shouldn’t be big problems arising with multi-threading, either (I hope).

The question is, then, is the jittery feel from the SDL client gone with the OGRE client? The answer is (to my surprise) no. Last time I wrote about the timing problems in the networking code between the server and the client; specifically, even though the server was set to send the player positions every 20 milliseconds and the client should draw them every 20 milliseconds, the jitter was clearly noticeable. My conclusion at the time was that the client wasn’t updating the graphics fast enough and that I’d need to write a new client in C++ as a remedy.

Now, as the new client is functional enough to show the jitter, I investigated the problem more and, using the Date_time library from Boost I measured the frequency with which the server actually updates the client. It turned out that instead of sending an update every 20 milliseconds, the client receives a scene update only every 250 milliseconds, which obviously is much too slow.

I actually measured the interval between updates before I started writing the new client and came up with the said 20 milliseconds. The difference is, back then I measured the interval on the server side, not on the client side – which means that some obscure bug in either the thread management code or in the network code kept the data on the server before it was actually sent.

I also tried implementing a very primitive client side prediction on the OGRE client as a test, but the interval of 250 milliseconds is still too much for a smooth scene. I also came across some very interesting resources by Valve regarding multiplayer network programming, and while I’m not so sure I’m willing to implement entity interpolation like they did or if doing that would even work so well in a soccer game, the article still gave me some hints what could be done better on the server side.

The last time I wrote I’d consider rewriting the server again using Bullet as the physics engine, and now that I’ve discovered the problems regarding the network code on the server side as well my next task seems pretty clear. I could try to fix the issues in the Haskell server code, but it seems a bit too much at the moment, and I’m already looking forward to getting my hands dirty on Bullet. That means (to the disappointment of the fellow Haskellers) that soon the only part written in Haskell (not counting the older, yet very usable client) will be the AI, which also needs to be improved a lot in the future. I still think Haskell is a great language though and I’ve learnt unbelievably much from it (as Simon Peyton Jones says, “Even if you’re going to go back to C++, you’ll write better C++ if you become familiar with functional programming”), but I’m afraid it’s not the best tool for this job.

For those of you who are interested, I haven’t yet uploaded the code for the new client in any repository. It wouldn’t be suitable having the code on haskell.org, and I don’t know of any other public source code repositories for darcs, which makes me look for other revision control systems. After my experiences with darcs I’m determined to stick with a distributed RCS, and git seems like a good option, but before making the final decision I’ll check out the other options (e.g. Mercurial). Once I have the URL I’ll let you know.

Following the 0.0.1 release of Freekick and an update to 0.0.2, I started noticing some problems in the implementation that showed a need for code refactoring. There were certain issues that implied I should find out about the internal workings of Haskell, as in, trying to figure out how the language and the implementation I use (Glasgow Haskell Compiler) works in general, especially with regards to threading, scheduling and performance.

The first issue I ran into was about my physics engine. I had defined a maximum velocity for my players of 8 m/s, but after some measurements I found out they were instead quite a bit slower. (A tip for the future: implement a debug panel for having such information when you need it. Measuring something like that shouldn’t be necessary.) This implies that the physics engine has serious flaws. I improved the engine slightly and it works slightly better now (but still not as well as it should), but the improvements lead not only to faster players, but also to strange twitching, a flicker-kind of effect on my SDL client.

To figure out what causes the flicker, I needed to check the code for networking. The way my networking code works at the moment is that the server (physics engine) only sends the positions of the players to the clients but no velocity or acceleration, and my SDL client doesn’t calculate the velocity of the player but only places the player where the server tells the client to. This is the simple method used in Quake that lead to problems back in 1996 when 56k baud modems were fast: with a lag of 200 milliseconds and occasional packet loss the client would spend most of the time not knowing where the moving objects (a.k.a. targets) were exactly located. The remedy that id came up with (a technique that was also used in Duke Nukem 3D) was brought to life in QuakeWorld, where the client would “assume” where the players would be located in based on their current/last known position and velocity. This made Quake playable (and a huge online success) even with slower connections (at the time I had a mere 14.4k modem). The technique is called client side prediction and there’s a small section written about it in Wikipedia.

Now, since I don’t expect a crowd of modem using people starting to play Freekick over the Internet, I didn’t implement client side prediction. Since I have the Freekick server and client running on the same computer lag shouldn’t be the cause for twitching anyways. But to make sure the client was receiving updates about the match state fast enough, I raised the server refresh rate, that is, the frequency with which the physics engine sends the match data to the client(s). The delay between refreshes was 40 milliseconds (using threadDelay), which should actually be enough, but I dropped it to 20 milliseconds for testing. Now, with the lightweight threads that Haskell offers (using forkIO) the refresh rate went up indeed, but the flicker stayed. I tried compiling with the “-threaded” parameter, which made the situation only worse, as the minimum thread delay time using “threadDelay” went up to 40 milliseconds on my computer. In the end I stayed with the lightweight threads, which doesn’t really affect my single core anyways, but this points out a problem when optimising the engine for multiple cores.

However, the problem persisted. Since my CPU was still nowhere near 100%, I figured the problem has something to do with how Haskell handles high precision timing. I’ve tried Frag (a 3D shooter written in Haskell) on my computer, and while I was overall impressed by the game, it was hard not to notice how Frag was twitching with regular intervals as well. As I don’t know if there exists a remedy for the problem, nor if the cause indeed is something Haskell specific or just some obscure bug in SDL or in my client, I wanted to go for a completely different approach.

That’s where C++ comes into play. I’ve actually had quite negative opinions about object oriented programming as well as C/C++ in the past, but on the other hand there are some rather impressive and useful libraries available where bindings to Haskell don’t exist and can only be implemented with a lot of work. The library that I thought of first was OGRE, the massively powerful 3D graphics library written in C++. There are actually a couple of articles about calling C++ functions from Haskell (see here and here), but binding a library like OGRE to Haskell using the described methods is not really something I’d like to spend my free time with.

I know that using OGRE for the client side would

a) make the client run faster and with no flicker, and

b) maybe even look a bit nicer

than the current client implementation using SDL, Haskell and 2D pixel-by-pixel drawing methods. The middle way would be to use the apparently very well written Haskell bindings to OpenGL, but I didn’t really enjoy OpenGL very much the last time I used it five years ago and after seeing OGRE in action and realising using OGRE is actually easier than using OpenGL I don’t really have the motivation. Of course, the biggest reason to use OpenGL would be that I could keep on writing the client in Haskell, but in the end it’s probably easier and more effective using C++ and OGRE.

That being decided, the next thing to do was to freshen up my C++ knowledge. I actually never had much of formal education to C++, instead I was using it much like “C with classes”. Even though that was the primary objective of C++ in the beginning, modern C++ is a completely different subject that I somehow had failed to miss until now. So I went and got me the book The C++ Programming Language by Bjarne Stroustrup and studied it through. I can imagine that a lot of people who have no or very little experience with C or object oriented programming find the book confusing, but for me as someone with good knowledge in C and some idea what C++ is about the book was perfect: it explained all the ways C++ can be used to make programming more efficient and less error prone.

I think it’s time for a small analysis about programming languages. After using C and assembly language I’ve gotten a pretty good picture about what the lower-level job of compilers is: shuffling around with the registers, allocating and keeping track of memory, testing for bits and so forth. Languages like C build on top of this, making the whole resource and control flow management easier to write and read.

On the other hand, Haskell approaches the problem from the other side. Haskell is designed from a mathematical point of view while trying to improve the efficiency of the programmer without clinging to the requirements and constraints of the machine, making Haskell code elegant and robust. To me, writing code in Haskell is almost like using a perfect programming language. Between C and Haskell, there’s C++. My impression about C++ was originally (unsurprisingly) that it is not far away from C, but after seeing how C++ improves on C and adds language features that allow the use of completely new programming paradigms (to C), C++ seems more and more Haskell-like to me.

With Haskell I learned to love the fundamental functional programming features that first seemed a little strange to me (like currying, higher order functions, lambdas etc.). I thought with C++ I’d be giving them away in exchange for pointer arithmetic, buffer overflows and unsafe typing, but fortunately I couldn’t have been more wrong. Nearly all of the C features that don’t seem to fit to modern software development are completely unnecessary in C++, and a lot of functional concepts and other features I’d miss from Haskell are brought in either as built-in C++ features (e.g. safer typing, better mutability control), the standard library (lists, currying, higher order functions) and Boost libraries (smart pointers for memory management, lambdas, serialization).

If you check out the Programming Language Shootout, you’ll see that C++ is (as expected) usually faster than Haskell (but the difference is not tremendous). As is also very well known, there exist about ten thousand times more libraries for C++ than for Haskell. In my opinion, those are pretty much all the aspects where C++ is “better” than Haskell. On the other hand, Haskell code is easier to reason about, significantly shorter and therefore easier to read (in my opinion, at the very least) and the concept of type classes is something C++ and the templates still have a lot to learn from, making generic programming far easier and simpler in Haskell than in C++. However, when writing a client for Freekick, performance as well as external libraries do play an important role in the end, and therefore I’ll go for C++. I’m glad I’ve seen Haskell as the finest example on how elegant code can be written, and I’m also glad it’s easy to use the same concepts in C++.

The next thing I’m going to do is read some more about object oriented design (I’ve got Design Patterns waiting for me) and then go and implement a simple Freekick client using OGRE. For that I need to reimplement the Freekick library in C++ as well, which is a nice exercise for OO design (you should plan to throw the first one away anyway, right?). Having the library in C++ would in theory also make it possible to rewrite the server part in C++, in which case I could use a top notch physics library like Bullet as well. But first we’ll see how the client turns out…

I’ve been tinkering with my project in the past week so much that it’s time for a small update again. The last time I wrote I was starting to get to know Haskell better. I also wrote some Python scripts to create some XML data to be parsed and serialized by my Haskell code. Since then I’ve written a small Haskell program that reads in the XML data (with a slightly improved XML serializer) and creates small soccer cups. Since the results are generated randomly, the next steps for my project would be both simulating match outcomes in a more realistic way and programming the actual soccer match.

This is where I have to think some more about the actual software architecture of my game. The ones who played Sensible World of Soccer may remember how the game seemed to have two major modes, the “organisatory” mode with menus and league tables, and the “match” mode with the actual, well, match. (Later soccer games probably have a same kind of division.) I’ve been playing with the idea of dividing my game to two separate processes, one for the organization and other for the match. In the past few days I’ve been reading The Art of Unix Programming (a book I sincerely recommend, even if you’re programming for other OSes), which inspires me regarding modularity in software even more.

The basic principle I’ve been thinking of is that the organizational part creates a temporary file with the data about the clubs that will play against each other, time, place, etc. and starts the match process with this file as a parameter. Match process then reads in the file and plays the match based on the data. After the match is finished, the match process writes another file describing the result and maybe possible player injuries (if I ever get that far). The reason for this is simply making the programming work easier; I can fiddle around with one part without being able to break the other one, and I can even program the two parts in different languages without problems.

While planning the architecture I actually went even a bit farther than that. When the match starts, I’ll have more than one process doing the work. Simply following the Rule of Modularity, I’ll have a small server-client structure, with the server having the information about the match and doing all the AI, and client drawing the match and handling the controls as well as other user interface.

And that’s not even enough modularity for me. The server process should have a frontend that actually communicates with the client and handles the physics and player movements based on the input from the client(s) and from the other part of the server – the AI process, which calculates the AI actions and passes the AI “input” to the physics part of the server. I actually wanted to go as far as dividing the client to two processes, one process handling user input and another drawing graphics, but that would probably make the implementation too difficult.

So, in a nutshell, the server part consists of two processes, AI and physics. The client part sends input to the server (physics part) and draws the match. The physics part of the server receives input from the clients and AI process and calculates the player positions as well as the rest of the match data, sending the data to both clients and the AI process.

At this point a reader might wonder why make it so complicated. Well, I want it to be modular, and I don’t think a plugin architecture would really be enough. I want the game to be easily customizable, so that one can e.g. write his own AI component and use it with the rest of the game, as long as he follows the protocol. Or, put another way, the client side I will program will probably be ugly as hell, and if someone wants to make it better he can just exchange that part without having to reprogram the whole game. The architecture also makes the game playable on older hardware, if a lightweight client is implemented as well. (I’m thinking of ncurses.) In the end it’s basically the same principle as in Freeciv, with the server having the game data and client displaying it (but with even more modularity).

The other reason why to divide the game in processes is that I want to make using several programming languages as easy as possible. That way, people wanting to hack with the game are not restricted to the programming language(s) I’ve chosen. For example, I’ve done a bit of programming AI in C in the past and I started to get the feeling that a linearly increasing complexity of the AI makes the code exponentially complex. Still, I’m sure there are people that can program better AI in C than what I can do in Haskell, and it might as well be that I’ll decide to use C later after all. I also don’t think I want to program everything in e.g. Haskell (which seems to fit well for AI), especially the client side. (There are SDL and OpenGL bindings for Haskell though.) In the end, I will probably use quite weird programming language combinations and I don’t want to mess with foreign function interfaces too much, so separating everything into processes feels like a good idea.

One may also wonder how badly the performance of the game is hit when it is divided to so (relatively) many processes. I looked at Beej’s Guide to Unix Interprocess Communication (my game should be cross-platform in the end, though), and it seems like the most efficient way to do this is through shared memory. Since I’m not really sure if that plays well with higher programming languages like Haskell or Python that I also planned on using on my project and since I thought having the communication streamed would be the easiest way I decided to go for good ol’ BSD sockets. They seem reasonably fast and another bonus with them is that the possible inclusion of multiplayer in the game would be smaller hassle.

Another point from the book mentioned above I also want to follow is first getting the program to work, then getting it to work well. Probably the biggest reason why the software I’ve written until now was never really ready to be released is that I always wanted to make it huge from the start. (Actually, if you look at this project, I’m still doing it.) Dividing the project to so clearly dividable modules makes it possible for me to actually try to program each module in a quick and dirty way just to get a prototype done, and improve each module separately later.

In other words, the next step in my project is to write small functionality for each part of my project and make them work with each other. Since I’m lazy, I thought about doing the client side either with Pygame (the SDL bindings to Python) or just reusing the C++/SDL code I made a couple of months ago that displays a simple soccer pitch with some triangles as players. I’d like to do the AI part with Haskell, since I can imagine how pure functions and lazy evaluation make that task easier. And besides, I think it’s a great language (once you get the hang of it). The third process of my project involves physics, i.e. moving the ball and the players depending on their actions, which may not be a very difficult thing to accomplish and I might as well program it in C.

Of course, another difficult thing is getting the parts work well with each other and designing the protocols between them. That means I still have some planning ahead before I actually get to writing the code, but when I do, I hope it actually doesn’t take forever before I have something to show. When I do have something finished (whenever that may be), I’ll set up a (darcs) repository for the readers to have a look. In any case, when I have some new design or code to write about, I’ll keep you posted.