A Wonderful Life in a Magical Tux

As I wanted to kill some time, I helped BombStrike with his project for Eve Online, a “massive multiplayer online roleplaying space game”.

The part I helped with is about being able to find a “route” from one point to another.

My first attempt was just for fun, a stored procedure for MySQL which did the lookup with the help of 3 temporary tables. This worked quite well, but had serious troubles resolving really long paths (avg. of 7 seconds for a 24 hops search).

So, I finally decided to create a dedicated database format for Eve Online, which would be optimized for lookups.

With this new database, a 95 hops lookup takes an average of 2.25ms. This is fairly acceptable, I’d say.

For those who are interested, the generated database (it took ~3 hours to build it), and some data files are available for download. You can also download the initial MySQL database dump.

The index file is fairly simple, it contains only solar system ids and locations in the main file (4 bytes for little endian solar system id, and 4 bytes for location in main file).

The main data file is a bit more complex. For each solar system we have:

• Solar System ID (4 bytes)
• Solar System Security (4 bytes int, explained soon)
• Number of known solar system when adding this one
• Solar system name length (1 byte)
• Solar system name (variable length)
• Solar system links to other solar systems (size of 9*number of known solar system when adding this one). This list contains:
  • Next hop to reach this solar system (4 bytes)
  • Number of hops remaining to reach it (1 byte)
  • Security level of this route (4 bytes, explained soon)

The security level in Eve Online is a float between -1 and 1. Storing float or double values is a pain, so I converted them to integer with a simple operation: int_value = (float_value + 1) *1000000000.
This way the int_value will be between 0 and 2000000000, and (almost) efficiently use space available on signed 32bits integers.

Creation of the initial file is also pretty simple.

First, we create the various solar systems, based on data from the database.

Next, we insert what we call “level 1″ links (basically, those are all the direct links).

Finally, we enter a for loop starting a 2 and finishing at 255 which will ask to populate links. There the way this is done is easy.
For each solar systems:

• We collect all links which takes one less hop than the current value of the loop (for example for the third iteration, we take all “2 hops” links)
• We “advertise” them to solar systems directly connected to our solar system, saying the “next hop” is us (for example this would lead a solar system directly connected to the current one adding the current solar system as a “3 hops” target for the advertised solar system).

Explaining all that is not easy, I hope I didn’t get anyone lost here.

Anyway have fun with this piece of (maybe) useful code!

The release of PHP 5.3.0alpha3 is soon (planned for December 2nd for now), the main change since PHP 5.3.0alpha2 is the namespace separator, which switches from :: to \.

Other changes should include:

• MySQLnd async queries and other stuff like stream scanning
• ext/mhash removed from main tree, and replaced with ext/hash, which seems better (I believe compatibility function names will be used, eg. ext/hash will provide mhash_* functions aliases)
• OpenSSL will now work with buffers (I’ve been waiting for this one)

Anyway this is most likely going to be the last alpha release of PHP 5.3, as this should mark the last new features added to PHP 5.3. Next test releases should be beta, then RC, for finally getting a final PHP 5.3 out in 2009.

By the way, remember that in France, the PHP 2008 Forum will be held on December 8th and 9th 2008 in Paris, and many people will be there…

Recently I had some troubles finding a good way to let Qt (now owned by Nokia) and PHP communicate.

At first, I tried using QtSoap (part of Qt Solutions), but I was expecting something better for a commercial-only element (the lack of wsdl parsing is the main problem, I guess).

Anyway I finally decided to look at less complex solutions, and found WDDX to be a good idea.
After some tests I wrote a WDDX module for Qt and started doing tests. I was surprised at some point when I saw that the data I was getting from the server appeared to be UTF-8 encoded, and here I found that PHP’s WDDX extension was broken: the documentation stated WDDX functions only accept UTF-8, but the code was clearly showing conversions from ISO-8859-1 to UTF-8…

This led me to write a patch to fix that (along other patches for other features in PHP), and post a lot of stuff to the PHP internal mailing list.

I found out that the Wddx extension was maintained by Andrei Zmievski, and I guess he didn’t have enough time to continue looking after it… anyway he approved my patch, and at this point I became a “php developper”.

Next steps are pretty normal: I discovered again CVS, which I had totally forgotten, I discovered branch management and manual merge because PHP branches are too different, and a lot more stuff which made my time working on Wddx pretty fun.
Thanks to the tests I wrote I could spot two other bugs, one in PHP_5_3 (wddx_add_vars() was ignoring the first passed variable) and one in all versions of PHP (serializing a class providing a __sleep() method with wddx caused this class to be stored without its values, even those __sleep() said we need to store).

Anyway the next thing I’d like to implement in Wddx is packet streaming: the ability to send a packet while building it, allowing creation of really large packets without needing the RAM to store it (and coupled with stuff like mysqli::use_result(), it’s a nice way to stream large SQL data).

Anyway WDDX is a really nice way to serialize data, and it seems JS libraries able to parse WDDX exists (I only use it for communications with Qt, so I didn’t look a lot in this direction, still I guess google could tell you more).

During the week, the 五OS project has been resumed. This project is aimed at creating an OS for end-users with a really fast boot by including all vital parts in the kernel.

Also, in order to make easier for the users, there will be no need to deal with things such as shells, etc… to get the OS installed.

I’ve taken over the USB driver developpement, while BombStrike will work on the process scheduler in order to fix a few glitches that were reported.

While this happens, I’m still working on TuxTelecom althrough the service is now owned by Mutum Sigillum LLC. I get to play with the central while real service will be initiated soon.
The final service will of course include regular phone calls, but it will also include ability to send SMS to the world, and maybe to receive those too (in order to receive SMS you’ll need a special plan. Everyone with credit on their accounts will be able to send messages).

Finally, a new non-open source project I’m working on : libthor (threaded torrent library). This cross-platform library will allow anyone to build applications handling torrents (load a torrent, seed it, etc).

Well, that’s basically everything to this week’s news. See you next week !

Recently I wrote about PHP lessons.

You have until June 1st to register and take part as one of the 10 chosen ones.

All levels of PHP are accepted, however you’ll need basic knowledge of HTML (CSS and JS are a plus).

Lessons will contain many aspects of real-life php programming, ranging from simple charset problems to things like XML generation using DOM.

Each lesson will be available as an exercice, and you’ll be able to unlock parts of the required documentation to get some help. Scoring will be based on amount of documentation you had to unlock, code quality, security aspect, etc…

Everyone will be able to access exercices, however documentation and notation will be reserved to the 10 selected students.

The first exercice will be a pretty simple application. This simple application will have more and more things added as time passes by, and will end as a pretty complete website. This reflects some aspects of PHP programming.

The exercices are made to force you to search for what you’ll need, just giving you basic tips. Searching for documentation helps learning way more than receiving documentation.

Out of the 10 students, the 3 best overall students will win some prizes. Those prizes will change as I get sponsors. It may range from a domain name with webhosting to having the final project bought by a company for cash. Each winner will be free to choose from what’s available at this point. Webhosting isn’t a problem, however I don’t know yet for the code buying thing.

If you wish to participate, you can contact me directly on this contact form.

I’ll be starting PHP lessons for free in a few weeks.

It’ll be limited to 10 people, and the 3 best will get some special prize, I’ll see with them what they want and what I can give them. They will get a SVN repository and a webhosting connected to this repository in order to be able to answer to the subjects.

If you want to participate, I’ll have to talk to you and evaluate your level in order to adjust to everyone’s level and avoid making subjects too boring for you.

As subjects will be made public on this blog, you are also free to participate on your own.

Subjects will be issued in English and in French.

June 1st is the deadline for people who wish to participate directly. First subject will be issued a few days later, once all participants are ready.

Finally, I didn’t write a new blog engine as I initially intended (no time in this world for that), however I switched from DotClear to Wordpress.

This choice was made after I used Wordpress for a while on Porchoman. Anyway stay tuned for more soon !