Skip navigation

Tag Archives: software development

Since I spent some time tweaking the AI in Freekick 3, I thought I should write down some of the implementation details for future reference.

The AI has quite a simple general structure. Apart from the special cases like restarts, goalkeeper AI etc. the main gameplay AI consists of three states: defensive AI, offensive AI and the AI when the agent is about to kick the ball. Whether a player is in the defensive or offensive state depends on the match situation (where the ball is, who has the ball) and the team tactics (agent’s position).

The defensive state is basically a decision “where should I stand to make the opponent’s offensive difficult”. There are a few options: try to take the ball from the opponent, try to block an opponent’s pass or shot or guard some area or opponent. The AI simply assigns scores to each action and picks the action with the highest score. (This, I suppose pretty standard AI technique, seems to be inspired by utility functions and is used throughout the Freekick 3 AI.)

The offensive state is even simpler than the defensive state: either the player tries to fetch the ball or tries to place himself in the best possible supporting position, which should be somewhere that can be passed to, far away from opposing players, and a good shot position. (The AI builds a kind of an influence map that is also affected by some soccer-specific things such as the offside rule.)

Probably the most important decision the AI has to make is what to do when the agent has the ball. Again, like with the defensive state, the AI has a few different possible actions, and it assigns scores to all of them and simply picks the action with the highest score.

The possible actions are Pass, Shoot, Long Pass, Clear, Tackle and Dribble. I’ll start with the Pass action.

When deciding the pass target, the AI loops through all of the friendly players and keeps track of the best option. For each player that’s not too far or too close, the AI considers either passing directly to the player or trying a through-pass. The base score for the pass is highest for players nearer the enemy goal, and then decreased for each opponent player that is seen as a possible interceptor.

The Shoot action score is basically a function of distance to the opponent’s goal and the distance from the opponent’s players (especially the goal keeper) to the possible shot trajectory.

The Long Pass action is actually a composite of Shoot and Pass – it checks for the Shoot and Pass action scores of the friendly players and chooses to make a long pass (or cross) to the player with the highest score. As with other actions, the score is multiplied by a team tactics coefficient, allowing the coach to influence the team’s playing style.

Clear and Tackle are basically emergency brakes that the AI can pull in a situation where the ball needs to be kicked away from the own goal or the opposing players.

With Dribble, the AI creates a few possible rays at regular angle intervals around the agent as possible dribble vectors and assigns scores to each of them. Similar to shooting, the score is higher near the opponent goal, but decreased by opponent presence.

So, in the end, the AI is composed by several rather simple techniques. It’s all heuristics without any algorithms providing optimal solutions (if any can even be used in soccer AI). It uses some simple seeking behaviors (arrive at a position, chase the ball). There’s one simple state machine, with state transitions decided mostly by the ball position. The top level AI is built around simple if-then-else-statements (I suppose you could call them decision trees). Lots of the decision making uses some sort of fuzzy logic, even though it’s not really structured like that (instead the code itself is fuzzy). Still, the AI manages to seem smart in most cases, it plays rather well and presents a challenge for the human player (for me, at least).

There are still quite a few standard AI techniques that I haven’t implemented which might make sense for Freekick 3. For example it might be interesting to experiment with adding some kind of learning ability to the AI, which should be possible using reinforcement learning, or adding a more complicated planning process with the use of a decision network. A useful first step would be to extract all the used generic concepts like decision trees and fuzzy logic to their own code pieces, which would enable experimenting with things like learning a decision tree.

My conclusion is that there are lots of different game AI techniques, many of which are quite simple, and the key to creating a fun AI is to find out which techniques to use for which problem and how to combine the techniques. The techniques are often intuitive but can be also described mathematically, so that when reading up on game AI, you may, depending on the material, get an impression that game AI is either very non-scientific or very mathematical (and therefore difficult), while I think it can be either, depending on how you look at it.

For the interested, the ~500 lines of Freekick 3 AI that make up the core can be found at GitHub.

Those of you who’ve been checking out my projects might have noticed that I wrote my latest one in C++. The two previous projects I had written in Haskell. So why the switch? I’ll write down a small summary of the pros and cons of the both languages that influenced my decision.

I’ll start with the things that spoke for Haskell.

  • Haskell, in general, allows a lot more abstract, safer, higher level way of programming. Of course, you already knew this, but it’s still worth mentioning.
  • Hackage has tons of useful packages which makes using libraries and all the associated bureaucracy really simple. (Hackage is basically a repository consisting of almost all open sourced Haskell programs and libraries.) Combine this with cabal, which downloads, compiles and installs the dependencies for you automatically.
  • C++ compile times, especially with Boost, are abysmal.

And now for the cons, or, put in a more positive light, pros for C++.

  • It’s much easier to reason about performance in C++ than in Haskell. This is given, I guess, and the simple solution is to become a Haskell champion who can spot a space leak a mile away, but it bothers me nevertheless. There was a nice post and thread at Haskell cafe a while back about this.
  • Writing portable code in Haskell is not as easy as with C++. With portable I mean 1) code that runs on x86 across operating systems (Windows, Linux and Mac), and 2) code that runs across architectures (x86, ARM, MIPS, etc.). While portability is not as trendy anymore as it once was, I still have the twisted opinion that high quality code in a higher level language absolutely must be portable, otherwise it’s not high quality, and the Haskell ecosystem currently has limited support for writing portable code. Portable across operating systems is relatively simple with Haskell using GHC (although there are exceptions), but portable across architectures is a pain. GHC, the defacto standard Haskell compiler, actively supports only x86 and doesn’t cross compile. Some of the other Haskell compilers do compile across architectures, but they don’t support all the GHC extensions (which are used by a lot of Hackage packages) and often have a huge performance gap with GHC, which leaves me with zero Haskell compilers I’m 100% happy with. Don’t get me wrong, I still appreciate GHC and think it’s magical, but there’s room for improvement.
  • The Haskell libraries are in a constant flux. I’ve been writing Haskell code for a couple of years now, and each time a new GHC version came out, the old code broke. Usually the libraries included with GHC are updated and the interface was changed. Or GHC behaves a bit differently regarding some minor points and the code breaks. Or cabal, which has its main releases together with GHC, has some new features and the code breaks. There are plans for fixing the libraries once and for all (I can’t find the link now), which I think is a great idea, but when they do (and until they do), there’ll be breakage again.
  • Cabal, while great in general, has its problems, namely what cdsmith felicitously dubbed Haskell’s own DLL hell.

As can be seen from the list, the negative issues I see concerning Haskell are mostly not about the language itself but the infrastructure. That makes sense, I guess; Haskell, although it has a great community, is a less used language, especially in the industry, which makes it more difficult to establish an infrastructure that can compete with the one of, say, C++. The problems I have with C++, on the other hand, concern the language itself, which, although useful, is not really what one might consider the crown jewel of language design.

The infrastructure is at least something that can be fixed.

Behold, Kingdoms 0.1.0 has been released. Kingdoms is a hobby project of mine I’ve been working on for the past couple of months. It’s a strategy game, where you lead a nation from stone age until the bittersweet end – in other words, a Civilization-like game. I’ve been wanting to write one for a long time, and I’m glad to see it’s doable.

It borrows features from all Civilization games I’ve played: graphics from Civ 1 (because I’m no artist), the configuration file type from Civ 2 (back when it was simple), strategic resources and culture from Civ 3 and (part of) the combat system from Civ 4. By the way, that’s also the reason why I wanted something else than FreeCiv: I find it’s too similar to Civ 2, which was never my favorite Civ game.

Here are some screenshots:

Babylonians vs. Aztecs

A map editor is included

You can get Kingdoms from its web page – there’s the source as well as the Windows binary. There are still quite a few features I wanted to implement but haven’t had the time yet, so if something bugs you, let me know.

If you’re planning on writing 3D software in Haskell, here are some tips.

A few months ago I was planning on programming a 3D game in Haskell and was browsing the options for a 3D library. In general, there are a couple of low-level APIs (OpenGL and Direct3D) and a few higher-level libraries built on top of those low-level APIs (OGRE, Irrlicht, and more).  Using a low-level API has the known advantages (fine-grained control) and disadvantages (lots of code to write).

It turned out that limiting the programming language to Haskell is quite restrictive; almost all higher-level libraries are intended for using with C++ (Panda3D being an exception with Python as the intended language; the library itself is written in C++, though). So what you need is Haskell bindings for the libraries. There’s a Haskell binding for OpenGL, which is used for (apparently) all 3D games written in Haskell. A few months ago it was the only option and, if you’re doing anything more complicated than rendering a few models in a scene, it still is.

The problem is that binding a C++ library is rather complicated and basically boils down to either writing C code to wrap the C++ interface and then interfacing the C code in Haskell using FFI or automatically generating the C interface (as well as the Haskell FFI code that wraps it). The latter option was chosen for at least the GUI widget libraries wxHaskell and qtHaskell.

However, a few Haskell bindings for 3D libraries have appeared. There’s a very primitive binding to OGRE written by the author of this post (with examples) as well as at least a start of a binding to Irrlicht by Peter Althainz.  So there appears to be a bit of activity regarding the use of higher-level 3D libraries in Haskell, which is good news, I guess.

One more note regarding the Haskell bindings for Ogre: you can do some simple things like adding models and a camera, and moving them around, but that’s about it, since I haven’t really had the motivation or need to provide support for anything else. The bindings are relatively simple to extend, though, so if you use the bindings and miss a feature, go ahead and let me know.

In this blog post, I list some gem-like web pages that are worth reading if you want to become a better software developer. They’re not simply some sites where you can read about the hype of the week, instead they include insightful material that actually makes you see software development from a whole different perspective.

The need for mentioning the following sites arises from the fact that most web sites and blogs I find in the net usually make me think the writer either tells me some basics about programming I learned years ago or tries to convince me to use some new, brilliant technology which usually involves XML and/or Java. I often get the feeling I’m not part of the target audience and look for things that do a better job on motivating me. As it is quite difficult to find such sites, I’ll spend the few minutes to list some of the sites I’ve found interesting.

Some time ago I stumbled upon a web site called Joel on Software. It’s basically a blog by an experienced software developer, with interesting stories about our industry for us all to read about. It was actually the first software related web page I had found in a long time that managed to inspire me. My favorite article is “Can your programming language do this?“. As another example, if you’ve ever wondered about the Hungarian notation – or cursed at the coding guidelines that force you to use it, even if you can’t see the usefulness behind it, go read what Joel has to say about its history and things may become more clear, although not necessarily less frustrating.

I was glad to find such a page and was hoping to find more. Later I stumbled upon the page of Paul Graham. He shares some similarities with Joel – they both have founded a start-up company and written a lot of nice texts about software development. As a programming language enthusiast, I especially find the essays by Paul Graham involving Lisp interesting.

Some days ago I was looking for a new book on software development to buy and came across Clean Code by Robert Martin. I haven’t bought the book – yet – but searched for some related material and stumbled upon a presentation by Robert Martin titled “What Killed Smalltalk Could Kill Ruby, Too” as well as a blog post drawing parallels between the aforementioned languages and functional languages, namely Lisp and Haskell. The presentation seems very insightful and makes me not only want to learn more about the history of programming languages but also get a copy of the book.

Gaining interest on the new, modern software development techniques I read about TDD and BDD. And when you read about acronyms as these you can’t help coming across the webpage of Martin Fowler sooner or later. Here I also found an interesting text about DSLs, which I feel is an increasingly important – and interesting – topic.

Sites like these help me learn about the new developments in our industry and also make me a better, more efficient developer while still preserving the fun factor. Keep it up!

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.