Algorithms

Flashback to my time at university. The Sedgewick was the most popular algorithms book among students, being both cheaper and translated to German. Myself, I was using the CLRS Introduction to Algoritms.

This book was found when we were rummaging through stuff that was going to be thrown away at work, and I couldn’t let that happen. I could have used it last week when I was implementing patricia tries. Why is there no good C implementation of them on the ‘net? Anyhow, the question of how to delete an element from a patricia trie isn’t addressed in Sedgewick, so it wouldn’t have helped. I found out, so it wasn’t important, but still, you look up one thing in a classic like this and it’s not in there? How sad.

Optimization potential

The battle in Partôr during week 510 provides an excellent opportunity to do some profiling on Eressea. The whole turn took at least twice as long as usual, and gprof blames a single function for it. I knew this function was bad. The problem is, it really needs to be called this much.

I looked really hard at the usage pattern for the function this morning, and I think I can build a small cache with some information and reuse it for subsequent calls. Anyone dying in the battle invalidates the cache, but still, I figure I might be able to save some 75% of the actual work. Man, I’ve looked at this one at least twice in the past and never seen this!

[Listening to: Battle 22 – Ugress]

Continue reading

I need a good linux IDE

I admit it: In the choice between emacs and vi, I choose “none of the above”. I want a C++ IDE. I’ve grown up with Borland Pascal, then used the Visual Studio IDE, and I’ve never used anything without a good integrated debugger.

Switching from Visual Studio to emacs + gdb is something I’m no longer able to do. So this weekend, I had a look at some of the IDE offerings that Linux had. It’s not a happy tale.

First there’s eclipse. Many people (Java people) swear by this, and as they point out repeatedly, it isn’t a Java IDE, it’s an IDE for anything you want. Sort of like Visual Studio is (if what you want is a MS language). I downloaded the CDT, and I like the way that’s all done from inside the IDE. But then… I tried to create a managed makefile from the Eressea sources, because if I’m going away from commandline make, I’d like to also go away from makefiles, thank you. very much. Not possible, though. It seems Eclipse has a weird conception of projects being everything that is in one folder, no more, no less. If I have the sources for my library and two executables all in the same folder, for example, I can’t make eclipse build a library and two executables. Instead it tries to mush all of it together. But really, that is academic, because I couldn’t even get it to do that – Eclipse + CDT crashed every 5 minutes. All I get is some java exception, no option to save my work, and then it’s gone and I’m back to square one.

Code::Blocks was my next candidate, because many people on the Ogre3D forums are raving about that. I installed it on Windows from the binaries, and while not pretty, it looked close enough to what I want. So.. debian packages? No dice. No packages for any distribution, actually. Build it from the sources, they say. But even that isn’t easy. It comes without a configure script, and requires me to install automake, but not the automake I had, no, that other version of automake please, and then it would bitch about something or other and completely refuse to do anything at all. No dice. I didn’t even get a configure script. Screw this.

There’s still kdevelop left to test. Like Obi Wan, it is my only hope to run linux on the desktop. Yes, my web browser and office suite run on linux, too, but without an IDE, I have to stick with Windows as my OS, because programming is what I do 90% of the time I’m at the computer.

Speed!

Yesterday I checked out a 3 year old version of Eressea and compared it to today’s code. In those three years, the game has gotten almost four times faster! The old code took 10:20 minutes to run a turn, and the one I use today was done after 2:50. This had to be done on an old data file, smaller than the one we have today.

I knew I had been doing the occasional optimization – run the code with gprof, fix the worst offenders, rinse and repeat – but I had no idea the gains were that big. I’m sure that 3 years ago I considered the code pretty compact and fast…

I wonder what it will be like in three years.

[ media | Creedance Clearwater Revival – Fortunate Son ]

Making Wrong Code Look Wrong

Here’s a very good article by Joel Spolsky that you should read. It talks about why hungarian notation is a Good Thing, and how almost everyone uses it in a Bad Way.

I was rewriting the recruiting-rules for Eressea last weekend, and the rule there is that “for each peasant in a hex, players can recruit one person, except orcs, which can recruit 2 orcs per peasant, up to a limit of peasants/20, and if players want to recruit more, then the peasants in the hex are distributed evenly”.

The codes ends up looking a bit like when you’re trying to split your bills and you’ve been paying with 3 different currencies… I had a bug in that code, and only found it after I prefixed all my variables with p for numbers that represented peasants, o for numbers that represented orcs and d for numbers that represented the demand of a player – suddenly you see that you assign between them without the proper conversion.

New PBEM

I’ve been hacking away at a part-time project for the last few days. It’s an implementation of a tabletop game we used to play as teenagers called Armageddon (aka Das Ewige Spiel). It probably needs to be adapted a little for PBEM play.

The idea is to make a PBEM version of it, and try to come up with some new programming techniques if I can. Also, I’m using boost a lot more than I usually would, and dipping into more of their libraries.

The game will have a separate server and client, which exchange their data as xml files (orders going one way, a status report going the other way). I currently have no plans for the client (I write input files by hand), except that I want it to either be portable (Java or C++ with a portable graphics library) or a web interface, which would make it a web game rather than a PBEM. Or all of the above.

The server is written in C++, with libxml2, boost and luabind. The latter is mostly used for setting up the game and modifying the game state – I like having scriptable access to the game world, and I’ve had very positive experiences with lua for Eressea.

Currently, the server knows factions, simple units, regions (but no terrain or levels) and has two commands: one to move a unit and one to swap two units’ places. It can save and load the gameworld, and read orders from an XML file as well as write a simple XML report. That does not sound like a lot, but I’ve built the foundation on which I can build to add more features fast. My short-term TODO list contains terrain types (especially ocean), terrain levels, buildings, more unit types and recruitment/construction orders. It all depends on the weather this weekend, I’d say.

I’ll try to keep track of my progress and the stuff I learn on the blog, if I have the patience for it.

Eressea und luabind

Für die neue Vinyambar-Partie habe ich mir den Spaß gemacht, Lua-bindings für Eresseas wichtigste Funktionen zu machen. Das bedeutet, ass man jetzt den Server aus lua heraus skripten kann. Der Server ist in dem Sinne nicht mal mehr strikt ein Server, er kann auch für programmatische Änderungen am Datenfile benutzt werden. Das ist cool, und sieht z.B. so aus:

function process(infile, outfile, orders) if read_game(infile)~=0 then print("could not read game") return -1 end read_orders(orders) process_orders() write_passwords() write_reports() if write_game(outfile)~=0 then print("could not write game") return -1 end end

Das ist eine normale Auswertung: Datenfile laden, Befehle lesen, Befehle abarbeiten, Passworte schreiben, Reports schreiben, Datenfile wieder speichern.

Für WdW müssen wir haufenweise Parteien in Allianzen einordnen, Aussetzen, und eine Menge Einheiten mit Startitems für jede der Parteien machen. Da die Daten dafür in der Datenbank stecken, generiere ich mir einfach ein kleines lua-skript daraus:

alliance = add_alliance(13, "Einwohner von Lummerland") position = get_position(13) faction = make_faction(position, alliance, 5, "bla@fasel.de", "Dämonen") ... for faction in factions() do local u = add_unit(faction, position) u:set_skill("magic", 3) u:add_item("money", 1000) end

Das ist nur beispielhaft, das wirkliche Skript ist 200 Zeilen lang.

Das schöne ist, sowas kann ich beliebig weitertreiben. Ich brauche eine Datei, in der der aktuelle Spielstand steht? Kein Problem, einfach eine lua-funktion gemacht, die den in eine Datei rausschriebt.

Das gute daran ist, dass man verschiedene Skripte für verschiedene Vinyambars (oder Eressea) benutzen kann, aber alles den gleichen Server benutzt. Der spielbezogene Teil muss nicht neu kompiliert werden, weil die Skripte zur Laufzeit interpretiert werden.

Das ist toll. Ich kann jedem, der ein eigenes PBEM schreibt, nur empfehlen sich einer Skriptsprache zu bedienen, zumindest um die Kern-Funktionen seines Programmes steuern zu können.

Als Tool benutze ich dazu [url=http://luabind.sf.net]luabind[/url], das erlaubt es sehr einfach, C und C++ Code nach lua zu binden. Dafür ist der ganze Eressea-Server jetzt C++-verträglich geworden (schon vor einer Weile). Der luabind-code sieht in etwa so aus:

void bind_region(lua_State * L) { module(L)[ def("regions", &get_regions, return_stl_iterator), def("get_region", &findregion), class_<struct region>("region") .property("name", &region_getname, &region_setname) .property("info", &region_getinfo, &region_setinfo) .property("terrain", &region_getterrain) .def_readonly("x", &region::x) .def_readonly("y", &region::y) .def_readwrite("age", &region::age) .property("units", &region_units, return_stl_iterator) .property("buildings", &region_buildings, return_stl_iterator) .property("ships", &region_ships, return_stl_iterator) ]; }

Ja, das ist [b]wirklich[/b] reines C++, auch wenn es nicht so ausschaut. Habe ich auch erst nicht glauben können 🙂

Writing XML with libxml and iconv

In the past, I’ve always hacked my own XML output functions. The result wasn’t always good XML, and it took a lot of fprintf()-massaging.

Then I needed a DOM parser for C (not C++ or C#), and the only one I really liked was libxml. It’s got the proper license for me to use it, it’s simple to use, and has botth DOM and SAX parsers.

Here’s a libxml example of how to make your own xml output, taken from the Eressea II sources (you’ll find examples for making your own parser everywhere):

#include <libxml/tree.h> int main(int argc, char** argv) { xmlDocPtr doc = xmlNewDoc(BAD_CAST "1.0"); xmlNodePtr node = xmlNewNode(NULL, BAD_CAST "eressea"); xmlNewProp(node, BAD_CAST "game", xml_s("Ümläutß")); xmlAddChild(node, xmlNewNode(NULL, BAD_CAST( xmlDocSetRootElement(doc, node); xmlKeepBlanksDefault(0); xmlSaveFormatFile(argv[1], doc, 1); xmlFreeDoc(doc); }

That BAD_CAST is just a macro to convert char* into (xmlChar*), and you write it whenever you think that your input is already good UTF-8 and are too lazy to convert. Please see Joel’s article on Unicode first. For places where I don’t have that guarantee, my code uses iconv, a character conversion library to convert the internal char* to UTF-8. Here’s an iconv example for the xml_s function used above:

#include <iconv.h> iconv_t utf8; xmlChar* xml_s(const char * str) { static char buffer[1024]; /* it's enough */ const char * inbuf = str; char * outbuf = buffer; size_t inbytes = strlen(str)+1, outbytes = sizeof(buffer); iconv(utf8, &inbuf, &inbytes, &outbuf, &outbytes); return (xmlChar*)buffer; } int main(int argc, char** argv) { utf_8 = iconv_open("UTF-8", ""); puts(xml_s("ä߀")); iconv_close(utf8); }

That’s so much more fun than fprintf-wrangling.

lua bindings for eressea

I’ve always wanted to have a scripting language in Eressea, for all kinds of reasons. The GM tool could really do with a console, for example. And monsters could be scripted without having to change the C code every time. Eressea is really pretty backwards in terms of technology.

So today, I made the old C code C++-clean (added a lot of extern “C” around them), and made lua bindings with luabind and I’m exposing a subset of the region and unit classes to lua. First script (apart from Hello world) listed all the regions by name and coordinates, it’s not much, but it’s a start.

It was actually easier to write small C++ wrapper functions (especially a wrapper template for the Eressea linked lists) and then use luabind (which is a C++ library) than to export the C structures directly though lua’s API. I really like luabind. I found 2 small bugs while I was working on this, but if they haven’t been fixed already, I’m sure they will be soon. The iterator support is rather fresh, after all.