Skip navigation

Time for a small update again. The last time I wrote I mostly reviewed the work done last year, wrote about the tools used and spent some time comparing Haskell with C++ as I had been busy rewriting the Freekick server in C++. So what’s been going on in the past month? Well, some of the points mentioned in “things to do next” part of the last post have been worked on, while others aren’t. Also, as I have now been using C++ for a few months there have been some signs of the need to wander off to another – hopefully better and shinier – programming language again, just like one would expect. This time I’m not thinking of Haskell though, but Python.

I’ll first let you know what’s new with Freekick core development. There’s been a lot of small improvements – I’ve added some server functionality such as allowing human players to play along or goal detection, but the most important update is that the OGRE client now has the ability to control a player and kick the ball around. This actually makes Freekick a soccer game that can be played. This doesn’t mean, however, that it would actually be fun to play the game – the relatively silly AI makes sure we’re not quite there yet. Another thing that makes the game less fun is that the clubs aren’t really there; the players have no differences in skills or personality, there are no kits or club names or tournaments.

The next thing for me to do is try and eliminate these two problems: first, the AI needs to be made better. At the moment it’s not really that bad – they pass the ball and try to score – but they only have a few actions which makes the match seem repetitive, and the goalkeepers are horrible. Second, the soccer match needs to have a menu around it, including creating and viewing tournaments, lineups, league tables – the whole deal. Actually I’ve already started work on that, which brings me to Python.

You see, working with C++ the whole time with Freekick core was not bad, but after you’ve seen something like Haskell in action, sooner or later you start to wonder if everything really needs to be so complicated. I’m talking about the sheer amount of time spent typing the code in, the loops, the iterators, the classes and headers and declarations, the curly brackets…

As Freekick was designed with modularity in mind and was split to multiple processes from the beginning on, the question of using Python for the game menu arose. After poking around with PyQt for a while the first drafts of the game menu were already finished. I had had my doubts about dynamic languages and duck typing before, but now, after having written a few small applications with Python I’m slowly starting to see the advantages such a dynamic high-level language can bring. I was amazed how fast you could actually write a simple-looking Python script that does the same thing as an application you could spend weeks writing in C++.

Encouraged by my Python adventures, I played around with the idea of solving the other problem – AI – with Python. Since I don’t really fancy writing all the Freekick client side logic in Python, I thought about using Boost.Python to export the C++ classes into Python. Doing the experiment was interesting, but the unfortunate truth is that exporting the classes still seems like too much work, even with the excellent library, especially with the page-long error messages and the fact that the STL containers would apparently also be have to exported manually. The other way would be embedding Python in C++, but I’d still have to export the data structures to Python and back, which makes me think it’s probably faster just to stick with C++ after all.

The GUI part is still far from ready – the only event that starts a match at the moment is a friendly match, and the GUI-match interface is non-existent at the moment – but the base is there and will be expanded when the time is ready. At the moment I think improving the soccer match itself is more important, since there is really no good reason to start a match if playing it isn’t fun, which brings me back to C++ and the AI. I’ve been reading the book “Programming Game AI by Example” by Mat Buckland again, which really is quite an inspiring work, but I think it will still take a while for me before the AI code is in a state where it both seems halfway smart and is easily extensible.

Luckily there are still a couple of mini projects for me to do in case writing AI gets boring. First of all there’s the GUI with all the tournament and schedule creation to do, but I think the time is also slowly getting ready for another Freekick client, this time with ncurses as the “graphics” library. I’ve been wanting to get my hands dirty with ncurses for a while now, and I’m all for minimalistic software, so hey, why not. Other fun things include creating a TV style soccer camera in OGRE and taking player skills into account on the server side. I’ll keep you posted.

New year, new tricks. In this post I’ll explain what Freekick has been doing for the last two months. The main events include rewriting Freekick in C++ so that it finally matches the Haskell version feature-wise, as well as gaining a bit of experience in using the associated tools and libraries. Before I get to that, let me first write down a brief summary of the last year, and of the blog thus far.

In April I wrote the first post announcing the beginning of the project, wondering which language and graphics library to use. The decision was in the end to go for C++ and Ogre. I was also preparing CEGUI as the GUI library. The build system was make, the version control system used was Subversion (if any).

In May I got to physics libraries and decided to look at ODE instead of Bullet. Soon after that I’d let the physics and graphics digest for a while and learn Haskell instead as a tool for AI programming.  Back then, there was no real code written for the project yet.

In June I had learnt the basics of Haskell and was using it to program some of the first things in Freekick.

In July the very basic design of Freekick was slowly getting clear. The plan was (and is) to split the game to different processes and use a server-client model. I went on programming the server and the AI in Haskell and played with the thought of writing the client in Python. I also started getting VCS conscious and mentioned darcs for the first time.

By August I had gotten as far as programming some multithreaded networking in Haskell, as well as doing some nice experiments and tests with neural networks. While the networking part was directly a part of Freekick at the time, I haven’t integrated the concept of neural networks with the project yet.

In September the very basic structure of Freekick, including the server, AI and a client, was finished in Haskell and the version 0.0.1 was released. The client was written using SDL, the primitive physics for the server was done without external libraries and the AI was a simple decision tree.

In October the negative sides of Haskell were starting to become clear, mainly being problems with the performance and problematic use of C++ libraries. The decision was to write a new client in C++ that uses Ogre for graphics. Implementing the data structures (classes) in C++ for the client also makes writing the server in C++ not such a big step.

In November the new client was finished. As it became clear that the performance problems had more to do with the Haskell server than with the client, the decision was to rewrite the server in C++.

In December I didn’t have the time to write about it, but I was busy rewriting the server in C++. This included updating the protocol between the server and the client as well as learning object oriented design.

And now, in January, it’s time for a post again. The C++ server is running, and the preliminary AI is finished too. As there were some updates to the Freekick protocol that broke the backwards compatibility; the old Haskell programs (server, SDL client, AI client) would have to be updated to match the new protocol in order to be able to work with the newer software (maybe I’ll get to it on some rainy day).

As there are some difficulties finding a public code hosting site for darcs repositories (and darcs seems to have some other problems too), I went for another RCS, namely git. I too am one of those who don’t want to go back to centralized SCM after seeing the other side, and git seems to fit my needs perfectly. The Freekick code can be found at GitHub by the way, at http://github.com/anttisalonen/freekick/tree/master. If you want to compile and run it though, there are some external dependencies (notably Bullet and Ogre) and the build script probably isn’t portable yet. If you run into problems, drop me a note.

As a side note, I also wondered which build tool to use for the C++ version of Freekick (for Haskell, Cabal is the excellent build tool, while C++ has a lot more options). The two strongest candidates were CMake and SCons, and in the end I went for the latter. The build tool for Freekick has the seemingly complicated task of compiling and managing a few libraries and applications, preferably comfortably configured in one configuration file. By now, my SCons build script (SConstruct) has become about 150 lines, but it does everything I want it to and how I want it to. The level of documentation for SCons is also excellent.

Now, a few words about implementing Freekick. First of all, even though C++ is more comfortable than I previously thought, it’s still far away from Haskell. My impression is that, thanks to the Boost libraries, you can use most of the nice things that Haskell has (e.g. tuples, lambdas), and everything will run slightly more efficiently than in Haskell, but there’s a lot more code to write and the code is a lot less elegant and a lot more verbose than in Haskell. I guess the better control of CPU cycles and bytes of RAM is worth it.

An interesting thing to note is that it took for both Haskell and C++ about three months to implement the basic functionality of Freekick. The comparison is unfair; I had just learnt Haskell when I started programming Freekick with it, while I’ve had previous (albeit now rather obsolete) experience with C++. Also, when I programmed Freekick the first time, the basic structure and design was only barely clear to me. With Haskell I had to program my own primitive physics engine, with C++ I used Bullet (which was about just as troublesome). The Haskell graphical client was easily done in SDL, while the Ogre client was a bit more work (though using Ogre is actually quite fast, easy and fun – signs of an excellent library). However, in the end the difference in development times wasn’t drastic, which shows to me that C++ really seems to do the job of evolving to a higher level language with time pretty well.

This was also the first time that I’ve actually done some object oriented design. It’s actually quite fun. The constant shuffling around with the header and cpp-files and the verbosity of it all is something I wouldn’t miss with Haskell, and the generic programming and code reuse that OOP offers is still light years away from the level you can find in a functional programming language. Still, C++ is on any account usable and I really need those cycles and bytes. Hopefully in a few years I can use a language that is as elegant as Haskell, while still maintaining the perceived efficiency of C++.

The next things to do with Freekick include relatively small improvements to the server (better compliance with the rules of the game), to the AI (it’s really quite primitive at the moment) as well as to the client (controlling a player and some small graphical enchancements). After that the next task is to go and implement the bigger plan, i.e. the game around the match – organizing the matches into cups and leagues.

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…

It’s time for a small post again. I haven’t updated my blog for a while, but for a reason: there hasn’t really been anything interesting to write about lately. Don’t worry, I’ve been working on my project, but rather implementing it than designing it. The last time I wrote about AI and mentioned it’d be the next thing to implement for Freekick. Well, the basics of AI are there, as well as the basics of everything else (server + client + the organizatory part). I’ve spent the last month writing the AI, writing a client (i.e. a window to the soccer pitch) and making sure the thing doesn’t crash by itself. Sounds like a 0.0.1 release, doesn’t it? Yeah, we’re that far already.

To the disappointment of neural network fans I haven’t implemented them at all in Freekick AI, not yet. The basic structure of the AI is slowly coming together, and when I can concentrate on the details, I’ll try and make some use of neural networks. At the moment, however, the AI follows simple logic for decision making that will be refined later. Having a simplified AI at this stage is helpful because it lets me concentrate on figuring out the bigger picture of the AI functionality.

The current AI is roughly split into two parts, one that defines the possible actions and another that compares these actions with each other and chooses between them. Here, defining the possible actions also includes a set of helper functions such as for finding the best spots on the pitch for scoring or the chances of a successful pass to a teammate.

Splitting the AI code like this makes maintaining it easier than if it was one bloated, monolithic monster. Improving the code should also be simpler in the long run, because if the two parts only communicate via clearly defined interfaces, one part could be swapped or reworked without interfering with the other part. This way I can first make things run with simple logic and when the AI starts to seem too stupid replacing parts of it with, say, neural networks shouldn’t be a big problem. At the moment, though, the AI code is rather transparent (with 10 files and 400 lines of Haskell code), but when the code grows, it will be necessary to make this division even clearer.

I then went on to write an SDL client for Freekick. It’s actually a bit early to call it a client, since there is no single player (nor multi player) mode and the client doesn’t control a player but merely spectates the match, but for now it’s enough to see what the AI is doing. A simple single player mode with some awkward controls will be added later. The client is very ugly, though, and thereby reflects my artistic skills rather perfectly. Here’s a screen shot.

Soccer in all its beauty.

Soccer in all its beauty.

Here it probably starts to become clear for everyone why I wanted Freekick to be so modular. The client is just a client, its duties are merely receiving the match status from the server and displaying it as it sees fit, as well as taking input from the player. It can be exchanged or rewritten in another language without the need to touch the rest of the game logic. I’m also planning on writing an ncurses client for use in non-graphical environments (as if the SDL client wasn’t ugly enough).

As for the server (i.e. the code that handles the network, communication, enforces soccer rules and world physics), it’s running with no major problems. Minor problems include network code that has problems handling disconnecting clients and relatively inaccurate physics, but for now it’s adequate. Probably the biggest thing that differentiates Freekick from a real alpha version of a very ugly spectator only soccer game is (along with the fact that the match actually never ends) that there is actually no connection between the “organizatory part” (i.e. choosing two clubs that play a friendly game against each other, or starting a knockout tournament) and the actual, viewable match.

This all means there is still some more work to do before Freekick could be considered usable. But in the spirit of “Release early, release often” I’m giving you the code (written in Haskell as usual) already anyways. If you have darcs, the easiest way to the code is “darcs get http://code.haskell.org/freekick/”, but there are also tarballs of the code as well of a binary version (x86, Linux) at http://finder.homelinux.org/freekick/files/. With enough playing around one might be able to start the thing, but I’ll write here the way it’s supposed to work anyway. First you start the server (“physics”) with a matchdata file (“matchdata.md”) as parameter. Then you start both the client and the AI, which both connect to the server. AI interprets the information from the server and sends the desired player actions to it. The client displays the players in all its SDL glory. And voila, you’re witnessing a soccer AI experiment.

From the issues mentioned above, the ones I’ll be concentrating on in the near future will be the ability to actually play the game and control a player, finishing up the match flow (i.e. ending the match at some point), and tying the organizatory part together with the match part. After these steps, it’s probably time for some polish, like a main menu, configuration options and a prettier client. As for the 0.0.2 release, it’ll be available, soon. I’ll keep you posted.

In my last post I described the high-level architecture of my software, how the soccer match part is divided into a client that does the work on showing the graphics and receiving input, a server that actually has all the match info and the AI process that actually acts as a client but controls more players at once. I also said my next task would be to write a small working piece of code for each task to get me started. Well, I’m still there; the main physics part is done. As an exercise to working with the BSD sockets interface in another language than C I did the physics part in Haskell, which was fun. Fun, but not easy.

Basically the difficult part was that I wanted the server to establish connections with many clients, send them some information about the match during connection and then broadcast the match data to all clients simultaneously. For this, of course, you need concurrency and threads, though the fact that Haskell as a purely functional language already threads everything confused me a bit. The answer is Control.Concurrent.forkIO and, for the more complicated stuff (i.e. communication between threads) Control.Concurrent.STM. For tutorials on how to program servers with Haskell, a nice, light introduction can be found at http://metavar.blogspot.com/2007/03/simple-socket-programming.html while a bit more difficult but certainly as interesting article is at http://sequence.complete.org/node/258. For a client, check out http://www.haskell.org/haskellwiki/Roll_your_own_IRC_bot. But I digress. Actually I wanted to write about AI.

So, after finishing my physics server (actually it’s not completely finished, it has no soccer rules yet, but it’s a server with some physics understanding after all), I went on to do the AI part. Since it can get quite complicated, I thought about doing some exercises on AI first. Now, the way how to start designing and programming AI was not really clear for me. I have the book “Programming Game AI by Example” by Mat Buckland, (a very nice book by the way) which has installed the relatively simple scheme of state machines in my head. I was not all sure, however, if a state machine would really be enough for soccer players, so I went on to do some more research.

I then stumbled upon neural networks, a topic about which I had only briefly read in the past – they seemed interesting but I never had the patience to sit down and try to grasp the theory. I finally went through the basics about them on a few sites including Wikipedia, but noticed none of those sites really showed any practical examples. I finally came upon two web sites that really explained how to use neural networks in detail. The first one is actually in German and describes the use of neural networks in a Counter-Strike bot, see http://johannes.lampel.net/bll137.html. It was a very interesting read, but for grasping the details you’d need to dive in the source code. The second site can be found at http://www.ai-junkie.com/ann/evolved/nnt1.html; this one is a very very practical introduction to neural networks, it helped me a lot and it’s also by Mr. Buckland, who keeps surprising me how simple it can be for some to make difficult things seem simple. His tutorial trains the networks with genetic algorithms, for which he also wrote a great tutorial (http://www.ai-junkie.com/ga/intro/gat1.html). The code, like all code from Mat, seems to be written for a less standards compliant compiler such as Visual Studio 6.0 or similar, which means you have to tweak it a bit if you want it to compile on a compiler that follows a C++ standard, but it’s doable.

Encouraged by the theory and these practical tutorials, I went on translating Mat’s Minesweepers into Haskell. During this process I also realized why almost all of the tutorials and the theory of artificial neural networks didn’t show any practical examples; my neural network code itself is merely about 50 lines of active code and contains mostly just the mathematical formulas to the networks. The applicaton of neural networks, however, is nearing 200 lines of code (huge, isn’t it?) and basically describes the whole learning and using process of the brain, err, neural network.

What I learned was that how the neural networks work is basically just a few formulas that don’t really say much about the application; in the end the network is really just a black box that you don’t really know, but it just “magically” gives you the correct values. The difficult part when applying neural networks to a problem is designing the way they’re used and figuring out how to make them learn as well and fast as possible. (I haven’t figured out any of the other ways of getting networks to learn (like simulated annealing and whatnot), i.e. providing positive feedback to them than genetic algorithms, but for now it seems good enough.) I also realized how the whole process was based on randomness, and while I thought that was quite funky, I did have my moments of despair trying to figure out if the thing had actually learnt something or not. (If in doubt, wait.)

Well, in the end it worked, though the minesweepers weren’t rolling around the screen like in the Windows/C++ counterpart, but the path of a minesweeper is drawn into a SVG file instead, as in http://finder.homelinux.org/haskell/Mines-0.1/svg_sample/gen400.svg. In this picture, you can actually see a minesweeper (the line) going for the mines nearby (the dots). Oh, want to take a look at the code? That can be found at http://finder.homelinux.org/haskell/Mines-0.1/.

That being cleared out, the next thing to do would be to actually finally implement a simple soccer AI. And, well, if I actually did it like I originally planned, with the locations of all the players and the ball and the player skills and personality as input, action including the direction and power of the action (let it be running, kicking the ball etc.) as output, it would probably end up being a pretty big neural network. The time to train it would probably also be pretty long, I guess.

The solution I’m trying to come up with includes state machines, neural networks, decising trees and maybe an occasional Markov decision process. (I also need to finally get my hands on the book “Artificial Intelligence: A Modern Approach”, which I’ve managed to miss… until now.) The basic principle is the same one as discussed in my last post – breaking everything into smaller parts, with state machines or decision trees to assist with the splitting, while using neural networks for the smaller, more limited problems. Probably my next post will still be on AI, but when that’s done (or at least the skeleton of it), and the AI players are kicking the ball, the only bigger thing missing is a client that actually shows us the action…

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.

It’s been quite a while (a month, actually) since my last post. That is not a sign of laziness, however, on the contrary; I’ve been busy playing around with Haskell and Python lately. In the last post I wrote about taking a break from Ogre to see what this thing called functional programming actually means. I think I’ve come closer to figuring that out in the past month.

Haskell really is quite an interesting language. (There’s a little tutorial showing some very nice aspects about Haskell here.) I started learning it by going through the tutorials available at haskell.org, and especially walking through Yet Another Haskell Tutorial, a mighty PDF book that explains all the major aspects of the language. I really had problems figuring out how to simulate state within Haskell, and the State monad didn’t really make it seem much easier. After going through the source code of some Haskell projects such as Frag (a 3D shooter) and LambdaHack (a roguelike), I finally started to slowly understand how a bigger project in Haskell could look like. So, to start from the bottom and work my way up, I made a blackjack and a video poker game. They’re text based but helped me figure out how to program some simple things in Haskell. (If you’re interested, you can find the sources + binaries here, MIT licensed.)

After finishing those two little cute things, I wanted to tackle the real prob– project, my soccer game wannabe. So I figured out how to read XML files in Haskell to serialize some data. As can be seen from my card games code above, I didn’t quite understand all of the monad concept (and still don’t), which turns out to be a pretty serious drawback when using Haskell to program in a bigger project. As Haskell is a purely functional programming language (one cannot emphasize that enough, I guess), doing something like file I/O without monads is impossible, and without advanced use of monads very tricky once things start to go wrong. The result is that if there is an error somewhere in the XML file to be parsed (my program doesn’t do any validation at the moment) or a bug in a function parsing the XML file, the bughunt may prove to be a very wiery task. So the next thing to do before I go on programming with Haskell is to learn more about monads. Luckily there are a lot of tutorials to the subject on Haskell.org. After that, the smartest thing for me to do would be a rewrite of my XML serializer.

My XML serializer could handle some data, but as I wrote the few XML files manually to test with I realized there is still a lot to design regarding the structure of my soccer game. And in order to see if my design would work, I needed some test scripts to create some XML files that should be able to work with each other. Since creating XML files by parsing text files and adding more or less random data to them is quite an I/O intensive thing to do and since I just wanted to quickly have some scripts that would do the job for me, I decided to do the job in Python instead.

Now, I wasn’t very experienced in Python (to be precise, I had programmed about 20 minutes in Python before this), but I still had somehow had the idea that programming in Python would be extremely fast and easy, especially for such not-very-large programs. After a few days of fooling around with Python and working with the excellent Python lxml library my scripts were finished and it seems I have proved myself correct. Even though my creations look quite terrible (if a Python fan saw my code he’d probably get his eyes hurt) and are written in a procedural fashion reminding me of my BASIC times (maybe Djikstra had a point after all) they do get the job done in the end and I think I can even understand the code.

There are some things I don’t like about Python (mainly the dynamic typing and the fact that is interpreted) and it surely doesn’t fit well for CPU intensive code, but for my XML creation scripts it’s perfect. Python also seems to be very easy to learn (just like Guido wanted it), and my scripts are a living (working) proof for that. I still keep learning Haskell (of course) since it seems even more elegant, faster and is purely functional, but the small Python excursion showed me I should keep clinging to the “right tool for the job” paradigm.

So, what now? Well, there’s the topic of monads to look at. After that I should do a rewrite of my XML serializer. (As boring as it may sound.) Then, well, I should be able to go on with my soccer game project, but with monads this time… We’ll see how it goes.

In my last post I was writing about dynamic animation. I was researching the topic a bit and made a small plan on how to actually implement the technique. As it basically boils down to three steps – ragdoll without any muscles, ragdoll with joints and an ability to move the body parts with them, actual animation by defining the movements using these joints and muscles – I started with the first step, which is my own ragdoll class. However, after working with the subject for some time I got tired of it and decided it was time for something else. I often feel like having an overdose of some particular subject, where I have the feeling it’s for the best to give the problem some time and rather concentrate on something else.

So I will be returning to dynamic animation at some point, but for the past week or two I’ve been going for something completely different. Luckily I’m going for a soccer game, which means there are a lot of construction sites to work on. Basically the game is divided to two parts – the actual soccer game on the pitch, and everything around it including the managerial and organisatory things like creating and updating league tables, calculating the results of the matches not shown etc. So I decided to take a look at the latter side of my project for some time.

In my first post I was wondering about which programming language to use with my project. I can’t remember if I wrote anything about functional programming languages back then, but ever since I realised how handy they can be when working with lots of arrays or lists (such as league tables) and AI (both the player and the manager AI) I’ve been wondering about using a functional programming language in my project. The problem is, I don’t have any experience in programming with them and they seem to have a reputation of being not so easy to learn once you’ve gotten used to the imperative style.

The good thing is that I’m willing to learn from my project. That was why I also went for Ogre and ODE; I didn’t choose them thinking I’d master them in a week, instead I was willing to make the effort and learn them because they’re effective, even if they’re not the easiest libraries to use. And since my past programs with AI haven’t really ended up as I wanted, I wanted to take a look at the world of functional languages. I decided I’d take the time to try and learn Haskell, a lazy, purely functional programming language. While I won’t go to details in explaining what that means (you can go check it out at Wikipedia or Haskell website), the point is that the code written in Haskell is supposed to be shorter, easier to read and to maintain and contain less bugs… If you know how to program in Haskell. So I’ve been going through some tutorials on Haskell (and will be going through them for a long time from now on, I think) and I’m quite impressed with it.

In my next post I’ll hopefully be able to explain a bit about how to use Haskell and how it could be used in my project. (At the moment I’m still too shocked about the new way of thinking to comprehend how I could actually program something with the language.) While I think I have a long way ahead of me with Haskell, I also have a feeling I won’t regret it. After all, I’m already now seeing programming somehow in a whole new way, so that I even see programming in C from a whole new perspective, a perspective filled with pure functions, lists and pattern matching… That can’t be such a bad thing, right?

Time for a small blog entry again. I’ve been going through the Ogre tutorials and after feeling more confident with the whole graphics rendering I decided it was time for the next step: integrating physics with the graphics. Ogre lets (or, as the critics put it, forces) the developer choose a physics engine suitable for his needs. I checked Wikipedia and the Ogre Wiki for some available engines and came to the conclusion that I’d have to choose between Bullet and ODE (I’d rather avoid commercial and closed source engines). Being impressed with the ODE documentation and the list of ODE users, I decided for the latter.

There are wrappers between Ogre and physics engines that make the life of the developer easier. The problem with integrating the two types of engines is basically that both Ogre and the physics engines have their own formats or classes for basic mathematical elements such as vectors, degrees and matrices and the wrapper has to convert them. Moreover, things like the Ogre timing system, nodes and entities have to be integrated with the physics engine. Since OgreODE, the ODE wrapper for Ogre, does not quite describe its functionality with as much detail as ODE I thought for a moment about just skipping the wrapper and using ODE directly with Ogre, doing the aforementioned conversions by myself – but after seeing the work needed I decided to go for OgreODE after all. The source code should be enough documentation anyways… Right?

After messing around with OgreODE a bit and trying out a couple of tutorials it does seem to work pretty well after all. My first test scenes involved the typical boxes bouncing onto the floor and each other, but soon I wanted to go and try out some physics that would really be useful for my game project, namely rag dolls and dynamic (procedural) animation.

I’ll explain quickly what dynamic animation is. First of all, there’s a nice video showing the technique at Youtube (link), the original thread at Ogre forums can be found here. (But don’t click on the links if you’re arachnophobic…) Basically it means the movements are not preanimated but calculated physically instead, and the characters move their joints themselves by applying forces on them with their muscles. This may sound complicated, but in the end it’s just a rag doll with enough intelligence to move itself. They can, however, be hugely flexible and can do anything without making the player feel bored. In other words, a character can really interact with the surrounding world with its limbs, i.e. when a soccer player gets tackled he falls realistically based on the angle from where the tackle came instead of simply doing a preanimated sequence.

The flexibility that dynamic animation offers is not the only reason I want to implement it. As some well known developers have said, a good developer has to be lazy. Manually animating all the sequences that a dynamically animated character is capable of would be way too much work. On the other hand, if only x animation sequences were to be animated, like a few sequences for the kicking, jumping and tackling actions (which would already be a tremendous amount of work), it wouldn’t really be any easier nor less work to make that look realistic in a soccer game than with dynamic animation. If I teach the players to do the actions with their muscles instead of animating them, I save the work on animating the falling down sequences (I just let them fly over as they simply follow the laws of the physics) and instead of doing the animation the traditional way I have to define the forces, vectors and angles for moving the bones and the joints, therefore having a lot of mathematical work instead of artistic work (after all, I’m a programmer, not an artist, and when in doubt, stick with what you can, right?).

The only problem with the technique is that there isn’t really that much reference for me to look for. There are a lot of scientific papers written about it (just google for procedural animation) and some code as well, but since I haven’t (yet) found anything about it for Ogre or Ode, it seems like this will be my first test to see if I’ve learnt enough about the APIs to create a solution to a “real” problem. So in the next few days (weeks, months?) I’ll be going through the theory of procedural animation and try to come up with a way of combining the Ogre meshes with ODE joints and motors to create a real, dynamically animated character.