I can do engineering, me!

On Google's internship recruitment process

2011-11-16T12:45:00.012+01:00

I've recently been into their internship program and I get asked about this a lot, so I'll just wrap it up in a blog post for everyone to see how it works. I'll mostly let the Google employees' emails describe the thing.

UPDATE: Due to some concerns about the classification of the emails I quoted, I temporarily removed them. I'm awaiting Google's response on the subject, hopefully they'll allow me to put them back up again.

First Contact

It all started with LinkedIn (if you work in IT and don't have an account there, I strongly suggest you to get one!) - a Google recruiter stumbled upon my profile (email date, so that you can get an idea of the timeline: March 2, 2011):

[here was an email inviting me to take part in Google's full-time engineer recruitment]

Huh? You can imagine my surprise upon receiving this email. Anyway, I replied with something along the lines of "I'm flattered by your offer, but I've still got 2 years until graduation, yadda yadda." I thought that'd be the last time I heard from her, but then (March 2, 2011):

[here was an email offering me to go for an internship instead]

Hmm. Hell, I thought, it's nothing binding, bring it on. Besides, I didn't really expect them to actually contact me. And, guess what... I was wrong again! May 11, 2011 brings me this email:

[here was an email giving an overview of the internship and detailing the initial requirements - CV, education, going back to university after the internship etc., also stating that if I want to go for the 2011 tour, I need to decide quickly, the other option being waiting a few months and contacting again later for a 2012 tour]

The Email Exchange

We arranged to wait until autumn 2011 for further contact. In September I emailed Frida again with another inquiry and received further information about the entire program, and got a response on September 15:

[here was an email detailing how the recruitment process works (2 to 3 phone interviews + an informal chat with the project manager once you're assigned to one) and a list of information you need to provide - preferred languages, interesting projects you've recently taken part in, areas of interest, university GPA, possible internship time spans and preferred Google office locations (you need to work on site)]

After submitting this information, Frida arranged my first interview. In the meantime I received some tips for preparation. The following came in on the 23rd of September.

Warning - a pretty lengthy read ahead! It's not all relevant though, you can safely skip to the next non-indented paragraph.

[here was an email that they allegedly usually send to full-time applicators only, but the recruiter thought it'd be useful to me; it's a lengthy list of tips on how to prepare for the interview, mostly stuff that's good to know, including the basics of algorithms and data structures, networks, computer graphics, maths etc., together with some suggestions on how to brush your skills]

The Interviews

The interviews take the form of a phone call (Google pays) with a Google Document shared between you and the interviewer (who is a Google engineer) and lasts from 45 minutes to 1 hour. A hands-free phone set, a broadband Internet connection and sufficient power supply (for the phone and/or the laptop) are needed for the basic comfort. Every interview begins with a short chat about your background - your work, university, areas of interest, then you go on to solving some programming problems, coding inside the Google document. After completing the task, you are asked to evaluate the algorithm complexity and, if possible, offer ideas for optimizations.

In the first interview I was tasked with coding a non-uniform random number generator - I had an array of numbers that were supposed to be returned and a corresponding array of probabilities.

In the second one, I were given 2 strings, and was supposed to return the first, minus the characters from the second one; as a second task, I was asked to find the maximum sum of a subsequence in a finite sequence of numbers.

In the third one, the interviewer started by asking me to explain, what exactly happens from the moment a user types in a URL into the address bar of a web browser to when the website actually appears on the screen. A few more questions about DNS and routing followed, and then we moved on to a programming task - a reader of a very simple image format (1 bit per pixel, black & white) together with a unit test.

After each interview there is a bit of time when you can ask any questions you might have about how Google works.

The Resolution

And that's how I got where I am currently - after a positive resolution (I received word on the November 11) of the feedback gathering process you are asked to once again reconfirm your areas of interest, preferred Google office locations and availability. It should take 4 to 6 weeks for them to find a project that matches your profile.

And that's pretty much all there is to it!

Thoughts on cheating in online gaming

2011-04-28T17:57:00.005+02:00

And now for something completely different. I've written this short analysis of the cheating phenomenon in multiplayer first person shooter games as a preface to my C++ university project report. It summarizes my thoughts on the subjects from the past few years, and I'm posting it here to use it to save my breath/keyboard strokes when explaining the weakness of the PunkBuster anticheat model (or any of its clones) to those who still believe it will protect their server from cheaters.

Problem definition

Multiplayer games, akin to sports, have been plagued by cheaters almost since their inception. While in the latter case the community struggles against artificial, biochemical augmentation of the players' bodies (doping), in digital competition we are running up against digital "skill boosters".

Narrowing the problem down to FPS (first-person shooter) games, we can define the two basic cheat classes:

those that augment the player's motor skills and reaction time and aid them in aiming at enemies and pulling the trigger - these are called aimbots,
and those that augment the player's perception by revealing the location of enemies and/or important gameplay objects, using various means (turning walls transparent, giving text or audio hints to the player etc.) - we'll put them under the umbrella term of a wallhack.

There is also the speedhack class of cheats, which we are not considering here. They exploit the fact that most popular engines' player locomotion code utilizes client clock for movement physics; older game engines, when fed with client input data at a double rate, would also move the player around the game world at double the speed. The reason we are not dealing with them is that they can be easily denied existence by well thought-out game logic alone, which is the case with practically all modern technologies.

Traditional countermeasures and their weaknesses

The traditional approach to combating cheats is to use methods similar to antivirus software: scanning the client systems for violations of game code and content integrity and/or traces of cheater programs, and sending the scan results over the network to the server. However, this method is fundamentally flawed - since the entire system relies on the honesty of the client component, which is beyond any reliable control of the server, a smart hacker may create a cheating program which will be able to either modify the anticheat system's transmission to send false negatives, or spoof the system entirely, claiming to be the actual anticheat client. Alternatively, having full, physical control of the client machine, the hacker can opt to sandbox the anticheat scanner (i.e. run it in a contained environment, intercepting and manipulating all of its system calls that perform the actual scanning etc.), effectively concealing the presence of the cheater program from it. Surely, it requires the hackers to present a remarkable level of skill; there are numerous examples, however, where this has been done, and it will be done even more frequently in the future, as e-sports tournaments and leagues gain prestige and real-world profits from gaming become involved.

This should leave you with no doubt that these vulnerabilities render the traditional model completely useless. Dependence on client-provided data is unsafe and should be discarded in favour of an untrusted approach: it should actually be assumed, from the very start, that the client is in fact attempting to cheat.

Proposed solution

When an experienced player spectates another person's performance in game, they are well capable of reliable recognition whether that person is playing honestly or they're using a cheat; especially when they're equipped with appropriate means, e.g. a wallhack of their own, which enables them to see what a cheating player would see, and connect the cheater's actions with gameplay events. I assume, then, that it is also possible to teach a computer to do just that. I'm trying to develop a scanner which will not be prone to these flaws, as it follows an entirely different principle, based on heuristics. My solution will run server-side only, which will eliminate the risk of spoofing and the clients feeding us false negatives. Machine learning will be utilized to teach the decision algorithms to tell cheaters from honest players via the means of behaviour analysis alone.

The project is in active development, even though it still has a long way to go.

HOWTO: Running MASM 6.11/6.14 in Linux

2011-03-05T23:25:00.010+01:00

OK, let me start with an explanation why I'm trying to run this 19 years old antique. Yeah, you guessed it right - we're using it at the university to learn x86 assembly. Sheesh.

Anyway, I'm positive I don't want any Windoze crap on my laptop, so the only option for me to use this piece of software is to emulate its native environment. Starting with Dosbox, I easily got MASM 6.11 to work. But then I applied the 6.14 patch (which is supposed to enable support for CPUs newer than 486) and suddenly the build process started failing. I checked the build logs and guess what - the actual assembler in 6.14 is in fact a Windows app! What the hell?!

So I thought, OK, let's try Wine. And guess what? While the assembler works fine, the WorkBench (the IDE) complains about the environment being too small. Damn it!

But hey, I'm a hacker! I came up with the following idea: write a fake Dosbox command that launches the assembler in Wine and redirect all output back to Dosbox. And I put the idea into code. Here's a little HOWTO.

Disclaimer
This is a quick and ugly hack. It's about as makeshift as it can possibly be, so please don't go flaming me about its quality and the awkwardness of steps you need to take to get it working.

You have been warned.

Prerequisites

Dosbox source code - grab it from the SVN or download a tarball from their Sourceforge page.
Installed Wine - any version that can run the 6.14 ML.EXE, preferably from your distro's packages.
MASM 6.11 with the 6.14 patch, either an already set-up install or the installation files.
My patch for the ML.EXE cross-emulation hack. ;)

How it works
The hack simply registers a Dosbox virtual command, ML.EXE. When run, the command opens a pipe and executes the real assembler in Wine, grabbing its stdout output and sending it back to Dosbox. When NMAKE tries to build your project, it simply runs the virtual command instead of the compiler. As simple as that!

Setup
OK, so we're going to use a separate build of Dosbox just for the sake of MASM development. Here are the steps:

Get your Dosbox source tree up and compiling. Don't apply the patch yet, just make a vanilla build.
Use the build created in the first step to install MASM 6.11 and the 6.14 patch.
Rename BIN/ML.EXE and BIN/ML.ERR to something else, e.g. MLREAL.EXE. This step is absolutely crucial, otherwise the locally-found ML.EXE will be run instead of the virtual command.
Make sure Wine can reach the MASM installation (e.g. by creating a symlink for the MASM611 directory from Dosbox's C: directory to Wine's).
Before applying the patch, open it in your favourite text editor and change the lines at the top with the MLReal and BINR constants, according to your own setup.
Apply the patch (e.g. $ patch -p0 < masmhack.diff).
Rebuild Dosbox.

Voilla! If you now run WorkBench in our custom Dosbox build, it should be able to compile our code with the 6.14 assembler, no problem. It might just be a little slow, though, because Wine takes a while to start up, but since I won't be using it much (just the first 2 classes of the x86 assembly course), I'm okay with it.

There, hope this helps someone. If anything's not clear enough, feel free to shoot a question in the comments.

Yakuake/Tilda-style console in Windows (bonus: unix shell with MSYS!)

2011-02-22T11:20:00.005+01:00

So I decided a yakuake-style shell would be useful at work. After googling around a bit I got it to work:

I came up with the following software combination:

AutoHotkey
Console2
(optional - if you want the GNU bash shell) MSYS

Cutting straight through the bullcrap, here's the AutoHotkey script I used (binding the console to the F12 key):

f12::
DetectHiddenWindows, on
IfWinExist ahk_class Console_2_Main
{
   IfWinActive ahk_class Console_2_Main
   {
       WinHide ahk_class Console_2_Main
       WinActivate ahk_class Shell_TrayWnd
   }
   else
   {
       WinShow ahk_class Console_2_Main
       WinActivate ahk_class Console_2_Main
   }
}
else
   Run c:\console2\console.exe
DetectHiddenWindows, off
return

And the Console2 configuration file (console.xml), which gives me my favourite settings - transparent background, Ctrl+Shift+T for a new tab and the GNU bash shell:


<?xml version="1.0"?>
<settings>
 <console change_refresh="10" refresh="100" rows="25" columns="80" buffer_rows="500" buffer_columns="0" shell="C:\msys\1.0\bin\sh.exe --login -i" init_dir="C:\msys\1.0\bin" start_hidden="0" save_size="1">
  <colors>
   <color id="0" r="0" g="0" b="0"/>
   <color id="1" r="0" g="0" b="128"/>
   <color id="2" r="0" g="150" b="0"/>
   <color id="3" r="0" g="150" b="150"/>
   <color id="4" r="170" g="25" b="25"/>
   <color id="5" r="128" g="0" b="128"/>
   <color id="6" r="128" g="128" b="0"/>
   <color id="7" r="192" g="192" b="192"/>
   <color id="8" r="128" g="128" b="128"/>
   <color id="9" r="0" g="100" b="255"/>
   <color id="10" r="0" g="255" b="0"/>
   <color id="11" r="0" g="255" b="255"/>
   <color id="12" r="255" g="50" b="50"/>
   <color id="13" r="255" g="0" b="255"/>
   <color id="14" r="255" g="255" b="0"/>
   <color id="15" r="255" g="255" b="255"/>
  </colors>
 </console>
 <appearance>
  <font name="Courier New" size="10" bold="0" italic="0" smoothing="0">
   <color use="0" r="0" g="0" b="0"/>
  </font>
  <window title="Console" icon="" use_tab_icon="1" use_console_title="0" show_cmd="1" show_cmd_tabs="1" use_tab_title="1" trim_tab_titles="20" trim_tab_titles_right="0"/>
  <controls show_menu="0" show_toolbar="0" show_statusbar="0" show_tabs="1" hide_single_tab="1" show_scrollbars="1" flat_scrollbars="0" tabs_on_bottom="1"/>
  <styles caption="0" resizable="0" taskbar_button="0" border="0" inside_border="2" tray_icon="0">
   <selection_color r="255" g="255" b="255"/>
  </styles>
  <position x="0" y="0" dock="0" snap="0" z_order="1" save_position="1"/>
  <transparency type="1" active_alpha="230" inactive_alpha="230" r="0" g="0" b="0"/>
 </appearance>
 <behavior>
  <copy_paste copy_on_select="0" clear_on_copy="1" no_wrap="1" trim_spaces="1" copy_newline_char="0"/>
  <scroll page_scroll_rows="0"/>
  <tab_highlight flashes="3" stay_highligted="1"/>
 </behavior>
 <hotkeys use_scroll_lock="1">
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="83" command="settings"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="112" command="help"/>
  <hotkey ctrl="0" shift="0" alt="1" extended="0" code="115" command="exit"/>
  <hotkey ctrl="1" shift="1" alt="0" extended="0" code="84" command="newtab1"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="113" command="newtab2"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="114" command="newtab3"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="115" command="newtab4"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="116" command="newtab5"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="117" command="newtab6"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="118" command="newtab7"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="119" command="newtab8"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="120" command="newtab9"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="121" command="newtab10"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="49" command="switchtab1"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="50" command="switchtab2"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="51" command="switchtab3"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="52" command="switchtab4"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="53" command="switchtab5"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="54" command="switchtab6"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="55" command="switchtab7"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="56" command="switchtab8"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="57" command="switchtab9"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="48" command="switchtab10"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="9" command="nexttab"/>
  <hotkey ctrl="1" shift="1" alt="0" extended="0" code="9" command="prevtab"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="87" command="closetab"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="0" code="82" command="renametab"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="1" code="45" command="copy"/>
  <hotkey ctrl="1" shift="0" alt="0" extended="1" code="46" command="clear_selection"/>
  <hotkey ctrl="0" shift="1" alt="0" extended="1" code="45" command="paste"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="stopscroll"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollrowup"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollrowdown"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollpageup"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollpagedown"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollcolleft"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollcolright"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollpageleft"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="scrollpageright"/>
  <hotkey ctrl="1" shift="1" alt="0" extended="0" code="112" command="dumpbuffer"/>
  <hotkey ctrl="0" shift="0" alt="0" extended="0" code="0" command="activate"/>
 </hotkeys>
 <mouse>
  <actions>
   <action ctrl="0" shift="0" alt="0" button="1" name="copy"/>
   <action ctrl="0" shift="1" alt="0" button="1" name="select"/>
   <action ctrl="0" shift="0" alt="0" button="3" name="paste"/>
   <action ctrl="1" shift="0" alt="0" button="1" name="drag"/>
   <action ctrl="0" shift="0" alt="0" button="2" name="menu"/>
  </actions>
 </mouse>
 <tabs>
  <tab title="Console2" use_default_icon="0">
   <console shell="" init_dir="" run_as_user="0" user=""/>
   <cursor style="0" r="255" g="255" b="255"/>
   <background type="0" r="0" g="0" b="0">
    <image file="" relative="0" extend="0" position="0">
     <tint opacity="0" r="0" g="0" b="0"/>
    </image>
   </background>
  </tab>
 </tabs>
</settings>

So, this. Now I have an easily accessible unix shell at work, yay!

X41 tablet screen rotation script

2011-02-13T12:16:00.003+01:00

I bought an IBM Thinkpad X41 tablet/laptop recently. I won't go into details, just dump a little script I wrote to handle screen rotation:

#!/bin/sh
xmessage -buttons 0:0,90:3,180:2,270:1 -center Clockwise rotation
dir=$?
xrandr -o $dir
case "$dir" in
"0") w="NONE";;
"1") w="CCW";;
"2") w="HALF";;
"3") w="CW";;
esac
xsetwacom --set cursor Rotate $w

Simply dump this code in a shell script, chmod +x it and there you go - you'll get a nice little window asking you which direction you want it to rotate.

The AC-130 is in the air

2010-06-12T00:25:00.004+02:00

So I turned my C programming project in earlier today. It got full marks, and the teacher was so impressed he didn't even take the test results into account when giving me my final mark in the subject. Even though it's not finished yet (i.e. it basically doesn't have gameplay yet), I'm quite proud of it!
Despite the performance problems on ATI/AMD GPUs, the renderer works very well on most hardware, and both it and the content generator (oh yeah, did I mention that almost everything in the above screenshot is generated procedurally?) use some interesting techniques. There's some technical babble on them (large terrain rendering, pseudo-instancing in OpenGL, Perlin noise etc.) in the report I've written for the project, if you're interested.

Well, the main reason for this post, however, is the fact that the game's begun a life of its own. This game has potential, despite its simplicity, so I created a SourceForge.org project for it to continue its development. You can see the source code and download the preview release (the one I turned in at the university) there. When I find the time, I'll finish the game, giving it proper collision detection, ground troops with AI and a sound rendering engine.

Oh, the link:
http://ac130.inequation.org/

Multi-window OpenGL rendering

2010-05-29T00:04:00.006+02:00

Here's a little lesson from two weeks ago: if you try to share the resources (display list spaces) between two GL contexts (e.g. when doing multi-window rendering), remember to check the return values. You might spend a week trying to debug the problem while in reality you've just been sending NULL as one of the arguments. Sheesh.

On a side note, my university assignment project is nearing completion. You can have a look at the source code here:
http://www.assembla.com/code/iqpk/subversion/nodes/ac130
And it looks a little something like this:
Yes, Modern Warfare connotations are relevant.

I'll move it to a SourceForge repository once it's finished. Hopefully it will start a life of its own and I can focus on the OIIO development I'm supposed to do as part of Google Summer of Code. Oh, right, I haven't announced it yet! So yeah, I got in this year. I'm supposed to finish my DDS plugin and then write another one for the DPX and Cineon formats (they're in use by the film industry).

So, yeah. There.

Perlin cloud noise

2010-03-21T00:43:00.006+01:00

Note to self: here's how to do obtain Perlin cloud noise:

Generate a Perlin noise map.
Double the frequency, generate another map, half its values, add to the first one.
Repeat step 2 two more times.

It took me half a day today to figure out how to do it properly. Sheesh.

C# lessons

2010-03-17T21:52:00.003+01:00

Phew! I've been working at The Farm 51 for over a week now, and it's been an ultimately interesting experience. I probably shouldn't be writing about this here as I've signed an NDA, but since what I'm working on isn't exactly connected to any of the confidential stuff that TF51 is doing, I will share some of my thoughts.

Have you noticed that game developers are attempting to make their products more and more film-like? My job has a direct connection to this fact - the so-called cutscenes (or cinematic sequences) have become a key device of any modern game, used to advance the storyline. In the past, they usually had to be programmed in a scripting language, which required the cinematic artist to either learn the basics of coding (with miserable results, usually - have a look at the Medal of Honor Allied Assault single player map scripts to see some unbelievably poor programming practices), or work closely with a programmer, or combine the roles of the artist and the programmer. Obviously, this didn't work too well, so a few years ago together with the advent of WYSIWYG game editors (I think Crytek's Sandbox for Far Cry was the first of the kind), cutscene creation has been brought to a different level. Nowadays, most engine toolsets contain a piece of software designed specifically for this purpose. And due to the similarities of the process to filmmaking, they closely resemble the software tools of the latter trade (especially non-linear video editors).

The technology that TF51 is about to use, however, does not contain such a tool. So, here I am, trying to fill the gap! This kind of a task called for RAD (Rapid Application Development) visual design, so even though I'm strongly prejudiced against Microsoft and their technologies, I decided to pick up C# and use it for the development of the tool. I've written about 1,5k lines of code so far in this language, so I think I have something of value to say.

First off, the language, its syntax and design is... Well, it's definitely organized and intuitive, but there are some constructs and conventions that I can't help but question. For instance, the idea of everything being a reference to an object and the way of creating new instances. Sure, it is intuitive, it is quite easy to write something usable in it very quickly, without a lot of thought put into the design. This has some unpleasant implications, though. My impression is that it's plagued by the same issue as Delphi - its ease of use encourages disorganisation and mess. If something just works if you put minimal effort into it without thinking it through, then why try to engineer and improve it? I've already bade the MVC design model farewell in my application because of this - the idea to integrate UI elements that represent the abstract objects with the objects themselves is just too tempting. This provides for extremely messy code that I'll probably have to spend a lot of time refactoring in the future.

While the language itself is bearable, its realization is utter horror to me. It's a performance nightmare! Not only is the executable actually half-interpreted, but also many of the linguistic luxuries come at an enormous performance cost. For instance, the whole "everything is a reference" model implies that a garbage collection mechanism must be put in place. Some of the language constructs, such as the foreach loop, require some additional memory allocations. When drawing custom controls, you often won't be arsed to cache the resources you use to draw, because it's easier to create new instances of them (this also contributes to the messiness of the code that I mentioned earlier). As a faithful follower of C, it is unthinkable for me trade the performance for a bit of the programmer's comfort by emulating (at a huge cost) concepts which are totally artificial to the hardware layer. And just as I've always been curious about how stuff is really done internally, C# leaves me with the feeling that the less I know about the "magic" behind it, the better I'll sleep.

The last paragraph, however, will not be bitching! Actually, as much as I hate the M$ guys and their ideas, I'm quite impressed by WinForms. It has very clean and streamlined design, it's documented well enough (it had pretty much everything I needed so far to create all the custom UI controls for the track editor) and the APIs are very easy to use. There are many similarities to Borland's VCL, which as far as I can remember (mind you that I haven't done anything in visual RAD ever since I dropped Delphi some six years ago to pursue more serious development tools) was a soddy mess, but as I said, it's much better designed, starting even from control names.

Whoa, I didn't expect this post to be this long. Anyway, if anyone reads all of this, thank you for your attention and I hope my insight is worth anything.

Address migration

2010-03-01T18:47:00.003+01:00

Whoa! Almost a year of inactivity! Well, it appears it ends now.

I bought myself a domain, yay! It'll be a place for me to put various interesting stuff I make and/or find, like university projects etc. Plus this blog has moved to blog.inequation.org.

In other news, I'll be applying for GSoC again this year (more successfully than last year, I hope), and I've just been accepted as a programming intern at The Farm 51! :) So, I'm on my way to becoming a real game developer, woohoo!

IneQuation out.

Summer of Code

2009-04-20T22:01:00.001+02:00

It's over! I haven't made it. Good luck to everyone that did! :)

Lighter2: Spot- and directional lights support in CS trunk!

2009-04-14T10:27:00.000+02:00

My patch (ticket #644) has been merged into the Crystal Space trunk as of revision 32304. :)

OIIO: Revision of views on DDS support and a patch for ICO

2009-04-12T23:47:00.000+02:00

ICO support patch chucked out. It's still a bit work-in progress, but core functionality is there.

Working on it enabled me to take a good look at OIIO's architecture and API, and now I can see that it actually won't pose any problem at all to achieve the features I considered tricky at the time of writing of my original proposal. Since both volumetric and multi-image formats are supported, there won't be any problem with 3D textures, cubemaps and mipmaps (well, maybe apart from the resulting layout of the subimages, but I'm sure it can be overcome, perhaps with a convention and by putting additional info in the attributes), or describing the compression type (attributes again), or retrieving native DDS data (same way raw JPEG coefficients are retrieved). There are no further obstacles I can see, and I'm estimating I could actually code stable DDS support in within two weeks at most.

Should I manage to finish Targa and DDS support before GSoC time is up, well, there's plenty of other formats that need supporting. :)

Once I get down with ICO support, I'll start coding the Targa loader.

Lighter2: Directional light issues

2009-04-12T23:41:00.000+02:00

Not without a spectacular slip-up, but I managed to chuck out a patch that adds spot- and directional light support to lighter2, yay! While the spotlight works all right, the problem with the directional one is that shadows aren't cast if not all of its direction vector's components are non-zero (sic!). To me it looks like a possible bug in the raytracer, but I'd better spend some more time on this. Going to have to figure out how to use the occlusion ray debugging feature.

Regarding my education and eligibility for GSoC

2009-04-11T12:30:00.001+02:00

Just to clarify some things. I'm a Polish citizen, age 19, and since April 24th I'm formally no longer a high school student, but practically I still am until I'm done with the Matura exams in May. After this summer I hope to go to university.

GSoC's requires a student to be at least 18 years of age and be formally enrolled in their school on April 20th, 2009 [1]. GSoC's program manager Leslie Hawthorn has also updated (after several questions regarding the issue [2]) the FAQ to state that it's OK for high school students to apply, as long as they conform to other requirements.

Hope this helps. :)

References:
[1] Google Summer of Code Frequently Asked Questions: Eligibility
[2] Google Summer of Code Discuss newsgroup: Are highschool students eligible for applying as students?

Lighter2: Further observations and a patch

2009-04-08T18:32:00.001+02:00

OK, my timing observations from the previous post were influenced by the fact I wasn't compiling directional lightmaps for bump-mapping. After turning this feature on, it becomes perfectly clear that sampling indeed is the most time-consuming part of the lighting process.

In other news I've been working in my non-occupied-by-school-work time on a patch to add spot- and directional lights support to lighter2. As far as I can tell, spotlights are done, now I'm awaiting clarification of some doubts from the crystal-devel mailing list.

Lighter2: Timing observations

2009-04-08T18:28:00.000+02:00

This is an update originally posted on April 5th.

Having run lighter2 a couple of times I noticed that it isn't the sampling that takes longest to complete, at least in the castle-staticlit demo map - kd-tree generation needs a while, too, and the stage described as "Initialize objects: Lightmaps" is also pretty time-consuming (actually, it stops at 30% task 19% total and stays that way for a minute or two, then proceeds). These results, however, might be influenced by a possible bug that I sent an email to cs-main about. Let's see what this resolves to.

Google Summer of Code

2009-04-03T18:53:00.000+02:00

Phew! It's over, we're past the application deadline for this year's Summer of Code. I've done the best I could, now it's all in the hands of the mentors. I've left myself a kind of an open back door, though - linked to the two preceding blog posts in my proposals.

I've applied to work with OpenImageIO (TGA and DDS support) and Crystal Space (lighter2 multithreading), hope one of them gets picked up. I'm a bit worried, though, because OIIO's lead developer doesn't seem to take me seriously (I'm a high school student; he seemed doubtful of my eligibility for the program, but I made sure I am with Leslie Hawthorn, GSoC's manager), but perhaps a patch for ICO support can convince him I'm capable of getting the job done.

I was also thinking of trying BZFlag, Thousand Parsec and Battle for Wesnoth, but I played the former two and honestly, I disliked them. And in the latter there was a regular dev team member applying to work on the only idea that was within my grasp, so with the obvious advantage that he has (he knows the game's internal workings well), I don't think I stood any chance of being accepted.

That's it for now. Let's see how it turns out.

Targa and DDS support: Appendix

2009-04-03T18:44:00.001+02:00

Hello!

The most up-to-date text of the proposal is available here.

I decided to somewhat reorganize my GSoC updates - now they're separate posts, appropriately tagged. You can now find them here.

Lighter2 multi-threading: Appendix

2009-04-03T18:42:00.000+02:00

Hello!

The most up-to-date text of the proposal is available here.

I decided to somewhat reorganize my GSoC updates - now they're separate posts, appropriately tagged. You can now find them here.

Fast sine and cosine approximation

2008-12-27T14:58:00.000+01:00

Time for a pseudo-scientific publication. Yay!

Some background: I needed to calculate the sine of an angle in a little MoHAA (Medal of Honor Allied Assault) gameplay modification for one of the features to work properly. However, the game's scripting engine doesn't provide trigonometric functions. My initial solution was to use a Taylor expansion implementation ported to the MoHAA scripting language by my good friend and former mentor Jeroen Vrijkorte. It provided pretty accurate values, however, I thought that its computational complexity is a tad excessive. So I went on to create my own approximation.

I noticed that the sine in half its period strongly resembles a parabola of a quadratic function. After a little experimentation I found 2 quadratic equations whose plots almost overlap that of a sine:So, how does it work?

Basically, we have 2 quadratic functions:

First we normalize the x to fall within the <0;2π> range, then apply the corresponding equation. As simple as that. Here's an implementation in MoHAA's scripting language (similar to C):

sin local.x:
 // normalize the input
 //local.x = local.x / 3.14159265358979323846
 local.x = local.x * 0.31830988618379067154    // 1/pi, because multiplication is faster than division
 // calculate the value relative to period
 if (local.x < 0.0)
     local.x += float(int(-local.x * 0.5))) * 2.0
 if (local.x > 2.0)
     local.x -= float(int(local.x * 0.5)) + 1) * 2.0
goto _sin_normalized    // moved to a separate label so that this part of the code can be shared between sin and cos

cos local.x:
 // normalize the input
 local.x = 0.5 + local.x * 0.31830988618379067154    // move the plot by a half to the left to achieve cosine
 // calculate the value relative to period
 if (local.x < 0.0)
     local.x += float(int(-local.x * 0.5))) * 2.0
 if (local.x > 2.0)
     local.x -= float(int(local.x * 0.5)) + 1) * 2.0
goto _sin_normalized    // moved to a separate label so that this part of the code can be shared between sin and cos

_sin_normalized:
 // fast special case
 if (local.x == 0.0 || local.x == 1.0 || local.x == 2.0)
     end 0.0
 // pick range and calculate result
 if (local.x < 1) {
     local.x -= 0.5
     end ( -4.0 * local.x * local.x + 1.0)
 }
 local.x -= 1.5
end (4.0 * local.x * local.x - 1.0)

The normalization process performs 3 multiplications and 1 or 2 additions/subtractions, while the actual quadratic function solving performs 2 multiplications and 2 additions/subtractions. Branching is also very limited, which makes for a nice, efficient algorithm, which is less computationally expensive than a Taylor expansion and doesn't have the memory cost of a lookup table.

As you can see in the plot above, the error (the blue curve; calculated as a(x) - sin(x), where a(x) is the approximation) ranges from 0 to about 0.06, which is unnoticeable in most non-scientific application (e.g. computer games). However, if further precision is required, the error can be reduced by several orders of magnitude down to an omittable value, as it can quite easily approximated with a 3rd degree polynomial. With the error subtracted from the quadratic equations we're getting polynomials which are still relatively cheap to solve and produce very accurate results.

Hope anyone finds this useful.

P.S. If you use this method, please drop me a line. It's just nice to know. ;)
P.P.S. I really wouldn't mind if this was known as the "Godlewski sine approximation" in my own honour. :P

GPU terrain in OpenGL tutorial - part 2

2008-11-05T16:47:00.000+01:00

This post contains the actual tutorial. For an introduction and some theoretical background on it, see the previous post.

First off, if you just want to see an exemplary working implementation of the method, check out the Destination engine source code. The code related to terrain resides in the class terrain, which is declared in v_local.h, and its implementation spans across files v_assets_world.cpp (procedural creation of terrain patch data and uploading it to buffer objects) and v_scene_world.cpp (actual drawing).

For the purposes of this tutorial I will assume that the reader has intermediate knowledge of C/C++ and OpenGL. Also, the entire terrain mesh should be square to avoid singularities, which of course can be resolved, but they're out of this tutorial's scope.

Let's start with creating some data for our to-be terrain renderer to show. L3DT is a very nice piece of software for designing large terrains. It runs in Windows and also in Linux via Wine (flawlessly, I should say). Go along with the built-in tutorial and create your terrain maps.

When all your maps are calculated, export the heightfield as a 16-bit unsigned raw image: select RAW from the drop-down list, then open the Options dialog and change the top-most option to "16-bit unsigned (metres)".

Export your texture map, too. Save it to a single image, the bigger in size the better. Choose the format to your preference, i.e. the easiest for you to load into your application.

Let's get rolling with the code! First, let's declare a couple of constants:

#define TERRAIN_PATCH_SIZE 17
#define TERRAIN_NUM_VERTS (TERRAIN_PATCH_SIZE * TERRAIN_PATCH_SIZE + TERRAIN_PATCH_SIZE * 4 - 4) // plus skirt verts at each edge minus duplicated corners
#define TERRAIN_NUM_BODY_INDICES ((2 * TERRAIN_PATCH_SIZE + 2) * (TERRAIN_PATCH_SIZE - 1))
#define TERRAIN_NUM_SKIRT_INDICES (2 * (TERRAIN_PATCH_SIZE * 2 + (TERRAIN_PATCH_SIZE - 2) * 2) + 2)
#define TERRAIN_NUM_INDICES (TERRAIN_NUM_BODY_INDICES + TERRAIN_NUM_SKIRT_INDICES)

These will be used to avoid redundant typing and calculations.

Then, load your heightmap and textures into texture units 0 and 1:

glActiveTexture(GL_TEXTURE_0);
glBindTexture(heightmapID);
glTexImage2D(GL_TEXTURE_2D,
0,
GL_LUMINANCE8_ALPHA8,
heightMapWidth, heightMapHeight,
0,
GL_LUMINANCE_ALPHA,
GL_UNSIGNED_SHORT,
heightMapData);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);

glActiveTexture(GL_TEXTURE_1);
glBindTexture(textureID);
glTexImage2D(GL_TEXTURE_2D,
0,
GL_RGBA8, // set according to your texture's format
texWidth, texHeight,
0,
GL_RGBA,
GL_UNSIGNED_BYTE, // set according to your texture's format
texData);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);

Note that for the heightmap, we're setting the texture parametres to clamp texture coordinates (this is to avoid ugly skirt seam artifacts) andthe nearest filtering mode (increases hardware compatibility). Also, the internal format parametre for the heightmap is GL_LUMINANCE8_ALPHA8. This usually means a grayscale image with an alpha (transparency) channel, but here it's a hack to enable us to use full 16-bit precision of the heightmap. Of course, there's also the GL_LUMINANCE16 format available. You might have heard, though, that it's not supported by all hardware. This is true. Thus the hack. It will be explained in detail once we get to the shaders.

Next, let's generate our buffers:

GLuint bufferIDs[2];

glGenBuffers(2, bufferIDs);

// vertices
glBindBuffer(GL_ARRAY_BUFFER, bufferIDs[0]);
float vertices[TERRAIN_NUM_VERTS * 3];
fillVerts(vertices);
glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

// indices
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, bufferIDs[1]);
unsigned short indices[TERRAIN_NUM_INDICES];
fillIndices(indices);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(indices), indices, GL_STATIC_DRAW);

Then, we fill the buffers with data:

void terrain::fillVerts(float *verts) {
int i, j;
const float invScaleX = 1.f / (TERRAIN_PATCH_SIZE - 1.f);
const float invScaleZ = 1.f / (TERRAIN_PATCH_SIZE - 1.f);
float s, t;

// fill patch body vertices
float *v = verts;
for (i = 0; i < t =" i" j =" 0;" s =" j" j =" 0;" s =" j" i =" 1;" t =" i" p =" indices;" i =" 0;" j =" 0;" i =" 0;" i =" 1;" i =" TERRAIN_PATCH_SIZE">= 0; i--) {
*(p++) = i + TERRAIN_PATCH_SIZE * (TERRAIN_PATCH_SIZE - 1);
*(p++) = i * 2 + TERRAIN_PATCH_SIZE * TERRAIN_PATCH_SIZE + 1;
}
// -X edge
for (i = TERRAIN_PATCH_SIZE - 2; i >= 1; i--) {
*(p++) = i * TERRAIN_PATCH_SIZE;
*(p++) = i * 2 + TERRAIN_PATCH_SIZE * (TERRAIN_PATCH_SIZE + 2);
}
*(p++) = 0;
*(p++) = TERRAIN_PATCH_SIZE * TERRAIN_PATCH_SIZE;
assert(p - indices == TERRAIN_NUM_INDICES);
}

Some parts of it may seem enigmatic. Basically, we're creating a so-called triangle strip to cut on memory usage. Hopefully these 2 diagrams showing vertex indices will explain things. The first diagram also shows the l and d segments, which were described in the previous post and we will use later on.

The second diagram shows the skirt. Starting at the last patch body vertex #288 (marked with the red dot), the arrows show the skirt indexing order, in the repeating sequence red-green-blue.

The terrain's dimensions in its basic form will span from (0, 0) to (1, 1), with its centre at (0.5, 0.5). This is not what we want. Let's move it so that its centre is at (0, 0) and scale it up to make 1 heightmap texel equal 1 space unit. To achieve this, we need a special model view matrix:

float terMVMat[16];

void terrainSetMatrix(void) {
// create an OpenGL matrix to centre the terrain at (0, 0, 0) and scale it
// up to its full dimensions
// we can put all of this stuff together in 1 matrix because we're not
// applying any other transformations
terMVMat[0] = heightMapWidth;
terMVMat[1] = 0.f;
terMVMat[2] = 0.f;
terMVMat[3] = 0.f;
terMVMat[4] = 0.f;
terMVMat[5] = 1.f;
terMVMat[6] = 0.f;
terMVMat[7] = 0.f;
terMVMat[8] = 0.f;
terMVMat[9] = 0.f;
terMVMat[10] = heightMapWidth;
terMVMat[11] = 0.f;
terMVMat[12] = -(heightMapWidth / 2);
terMVMat[13] = 0.f;
terMVMat[14] = -(heightMapWidth / 2);
terMVMat[15] = 1.f;
}

We need to set one more parametre (the starting level for quadtree recursion) before we can proceed:

void terrainCalcMaxLevels(void) {
int pow2 = (m_heightMapWidth - 1) / (TERRAIN_PATCH_SIZE - 1);
terrainMaxLevels = 0;
for (int i = 1; i <>

After the buffers have been created, we can move on to setting up the shaders. Write the code for creating and compiling the vertex and fragment shaders and linking the program (a nice OpenGL shaders tutorial can be found here). Then, request uniform parametres:

GLint biasID, scaleID;
if ((biasID = glGetUniformLocation(programID, "bias")) == -1) {
// handle error here
}
if ((scaleID = glGetUniformLocation(programID, "scale")) == -1) {
// handle error here
}

Also, post texture unit indices (0 and 1) to variables heightMap and tex, respectively.

Time for the shaders! Here's the vertex processing code:

uniform sampler2D heightMap;
uniform vec2 bias;
uniform float scale;

vec2 scaleBiasPos(vec2 pos) {
return vec2(pos.x * scale + bias.x, pos.y * scale + bias.y);
}

void main() {
vec4 pos = gl_Vertex;
pos.xz = scaleBiasPos(pos.xz);
vec4 c = texture2D(tex0, pos.xz);
pos.y *= c.x * 255.0 + c.a * 65280.0;
gl_Position = gl_ModelViewProjectionMatrix * pos;
gl_TexCoord[0].xy = pos.xz;
}

Note the part in bold. This is the actual hack for using full 16-bit precision of the heightmap. By uploading it as GL_LUMINANCE8_ALPHA8, we fooled OpenGL into thinking this is a grayscale image with transparency. Thus, for each pixel, it read the first byte as the grayscale component, and the second as the alpha channel. Now, OpenGL converts all colour values to normalized floating point variables (i.e. in the range 0..1). This line of code does approximately the same work as the following (except on floating point numbers, as opposed to integers):

unsigned short in = 12345; // some random number
unsigned short out;
unsigned char *p = (unsigned char *)∈
// getting the result from unsigned chars
out = p[0] + (p[1] << face="courier new">// getting same result from normalized floats
// note that (x << face="courier new">// 2^8 = 256
// (x << face="courier new">float x = p[0] / 255.f;
float a = p[1] / 255.f;
out = x * 255.f + (a * 255.f) * 256.f;
// 255 * 256 = 65280
out = x * 255.f + a * 65280.f;

Of course, there is some precision loss due to conversions, but the value of out after the last line should be close enough to 12345 for our purposes.

And the fragment shader:

uniform sampler2D tex; // colour map

void main() {
gl_FragColor = texture2D(tex, gl_TexCoord[0].xy);
}

Now, on to the actual rendering part. Start the recursion like this:

// use our shaders
glUseProgram(programID);
// apply our model view matrix
glPushMatrix();
glLoadMatrixf(terMVMat);
// set up geometry buffers for rendering
glBindBuffer(GL_ARRAY_BUFFER, bufferIDs[0]);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, bufferIDs[1]);
glEnableClientState(GL_VERTEX_ARRAY);
glVertexPointer(3, GL_FLOAT, 0, 0);

// recurse - call for the entire terrain mesh first
terrainRender(0.f, 0.f, 1.f, 1.f, terMaxLevels, 1.f);

// restore previous state when we're done
glPopMatrix();
glBindBuffer(GL_ARRAY_BUFFER, 0);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
glDisableClientState(GL_VERTEX_ARRAY);

These 2 functions make up the terrain renderer's core:

void terrainRender(float minU, float minV, float maxU, float maxV, int level, float scale) {
float halfU = (minU + maxU) * 0.5;
float halfV = (minV + maxV) * 0.5;

if (!noCull) { // global variable to control frustum culling
float bounds[2][3] = {
{(minU - 0.5) * heightMapWidth, 0.f, (minV - 0.5) * heightMapWidth},
{(maxU - 0.5) * heightMapWidth, 65536.f, (maxV - 0.5) * heightMapWidth}
};
if (frustumCullBBox(bounds)) // patch out of view frustum?
return;
}

float d2 = (maxU - minU) * heightMapWidth / (TERRAIN_PATCH_SIZE_F - 1.f);
d2 *= d2;

float v[3] = {(halfU - 0.5) * heightMapWidth, terMVMat[5] * 0.5, (halfV - 0.5) * heightMapWidth};
VectorSubtract(v, camera, v); // vector operation: v = v - camera

// use distances squared to avoid expensive square roots
float f2 = VectorLength(v) / d2;

if (f2 > C * C || level <>

For a graphical explanation of l (actually, VectorLength(v)) and d, check out the second diagram in the picture above.

And that's it! Consolidate all of this in your project and you should get a nice, fast-rendering terrain. Enjoy!

And as I said - for a working implementation, check out the Destination engine.

GPU terrain in OpenGL tutorial - part 1

2008-11-05T15:10:00.000+01:00

This post provides some theoretical background. If you want to go straight to the tutorial, check out the next post.

Terrain rendering is one of the most important things in an outdoor game engine like Destination. It makes for the better part of all the triangles drawn in a scene, so the method employed must be as efficient as possible, while maintaining reasonable flexibility. The performace criteria essentially means simplifying the terrain mesh (i.e. reducing the number of triangles it is comprised of).

I have evaluated several terrain simplification algorithms and while some of them provided remarkably good results (like the Realtime Optimally-Adapting Meshes or Peter Lindstrom's Terrain Simplification Simplified), they all had two disadvantages:

the calculations are performed by the CPU, which is undesirable, as a lot of CPU power is required for physics simulation
the number of triangles and vertices was not constant, which made memory usage optimizations difficult.

I was just about to go with Lindstrom's algorithm when I remembered I have a copy of the book Game Programming Gems vol. 6 by Mike Dickheiser. There, in the chapter 5.5, Harald Vistnes describes an alternative method, which turns out to be perfect for my application.

You see, historically, due to 3D hardware's poor performance (in relation to CPUs) it was more feasible to reduce the geometry before rendering - calculate very accurate Potentially Visible Sets (a perfect example of this approach is the id Tech 3 a.k.a. Quake 3 engine's Binary Space Partition system) and simplify complex meshes, as geometry throughput was the main determinant of performance. Nowadays, with the unified shading processor-based GPUs and high bandwidth buses (PCIe) at our disposal, it actually makes more sense to compute less accurate PVSs and to move as much rendering-related calculations load from the CPU to the GPU in order to save time for physics and AI.

In accordance with this, Harald Vistnes suggests a method, which doesn't include any complex mesh simplification (well, apart from LODing). The idea is to divide the terrain in patches and do the following:

Generate vertex and index buffer objects and fill them with data for a single flat, square 17x17 vertices patch of ground (other sizes are also possible, but it turned out 17x17 provides most consistent performance across different sizes of the entire terrain grid), plus the so-called skirt - a vertical border going around the terrain patch expanding along the negative Y axis that covers up cracks between patches at differents levels of detail.
Upload the terrain's heightmap to video memory as a grayscale texture.
Use a vertex shader that uses the Vertex Texture Fetch technique to offset the terrain's vertices along the Y axis according to the heightmap.
To draw, recurse the terrain mesh in a quadtree-like manner. Start with a patch covering the entire terrain grid:
1. Calculate the level of detail criteria: f = l/d, where l is the distance of the current patch's centre from the camera and d is the size (width) of a single quad in the patch.
2. If f > C, where C is a constant that determines the terrain rendering quality (must be chosen via trial and error), or we've reached the bottom of the tree, draw the current patch and return.
3. Else divide the current patch in 4 subpatches and go back to point 4.1 for each of them.

The drawing of each individual subpatch is realized by drawing the contents of the buffer objects, providing a proper model view matrix and 2 uniform shader parametres (describing horizontal displacement and scale, respectively). Nice and simple, isn't it?

One main point is that Harald Vistnes's implementation is based on DirectX. In the next post I will describe how to achieve the effect in OpenGL.

Destination

2008-09-25T18:15:00.000+02:00

...is the name of my very own game technology. Yeah, a game engine. It's called "Destination" as a mockery of Valve Software's Source engine. It's free software under the GNU GPL. Its coded in object-oriented C++ and its design is mostly inspired by the id Tech family of engines (a.k.a. Quake engines), in particular by id Tech 3 and id Tech 4 (Quake 3 and Doom 3/Quake 4, respectively). The first game based on the technology will be Mobile Arena (not much more than a playable technical demo, actually):

mobilearena.sourceforge.net

The engine is devloped simultanously with this game. After Mobile Arena is finished, I will move on to new projects utilising the engine.

The project is still in its infancy, but it already compiles and produces working executables, has a console to interface with the user etc. It doesn't draw anything in 3D as of yet, but that is about to change in the next couple of days.

OpenGL 2.1 is cool.

Nasza-klasa.pl mutual friend finder

2008-09-14T01:24:00.000+02:00

As promised, I wrote a small proof-of-concept C app to download the contact lists of 2 people and find their mutual friends. It uses CURL for HTTP handling. Here goes the code (it's quite lengthy, actually - much lengthier than I had expected; the parsing part could probably be shortened, but I couldn't be arsed to refine it):

http://www.pastebin.ca/1202182

Going to give a Pidgin plugin for NK.pl support a shot soon.

Also, I would like to mention that you'll need to provide a user agent header in any HTTP requests to the NK.pl server (any random blah will do), otherwise it'll keep returning 403 errors and irrelevant content (won't let you log in either). Plus the version parameter in the friends list request seems insignificant - it would accept any number I gave it.

Nasza-klasa.pl's AJAX friend list protocol

2008-09-08T23:13:00.001+02:00

Update: Szymon Gruszecki of the Cracovian University of Technology found out that nasza-klasa.pl changed the way the friends list JSON file is accessed and contributed a description.

OK, time for my first finding. What's nasza-klasa.pl? To quote the Wikipedia:

nasza-klasa.pl (Our Class) is a large social networking platform for people in Poland, a social networking site bringing together former students from the same schools. People are able to keep and maintain a personal page containing information about their name, age, study subjects, interests and courses. Apart from many discussion forums it allows to share photos. It does not require an invitation from anyone of the members to register. The leader of the project is Maciej Popowicz from Wrocław.

The portal has recently received significant functionality enhancements, based on AJAX, including an improved friends list browser and an instant messenger-like contact list and messaging centre. I'm actually quite surprised there hasn't been a surge yet in data mining software based on it, like what happened with Audioscrobbler (Last.fm) - you know, programs that calculate your musical taste's mainstreamness rating, generate tag clouds etc. Given the field in which nasza-klasa.pl operates, I find it even more surprising, as it seems that much more interesting conclusions can be drawn using the data available from it than what can be achieved with Last.fm.

So, as a little research project, I'm going to try and write a piece of software to compare the contact lists of two persons and find mutual friends. Then I might possibly write a Pidgin plugin to support the messaging centre as an instant messenger protocol.

I spent a couple of minutes trying to discover how the contact list works. The server requires you to be logged in as a nasza-klasa.pl user. The lists are located at URLs using the following pattern:

http://nasza-klasa.pl/friends_list/target_ID/flags/version/t=basic_auth

Where:

target_ID is the ID of the user whose contact list we're looking at,
flags is a bit field that tells the server which parts of the friends' profiles to return; possible values (can be ORed together):

UID: 1,
first name: 2,
last name: 4,
avatar (main photo thumbnail): 8,
friends count: 16,
location (city): 32,
messaging centre status: 64,
messaging centre status description: 128,
"artificiality" (whether or not the person in the account is a fictitious one or a real one): 512,

version - a string in the form number1/number2; note: it appears to be different for every account, in order to get it right you must download the contacts subpage first and use the value of MY_VERSION in the FRIENDS_CONFIG object,
basic_auth - the value of the basic_auth cookie that nasza-klasa.pl creates on login.

The server returns a JSON file (MIME type application/json) of a name which seems to be a random number sequence. Or perhaps a Unix timestamp, haven't really made an effort to check. Anyway, it's irrelevant. It starts with a BOM - a sequence of 3 bytes that serves as an indication that the data that follows is UTF-8-encoded: EF BB BF (thanks Deathplanter and maverix). Then, ASCII-encoded with escaped UTF-8 characters (\uXXXX format) text data follows. Punctuation marks make it extremely easy to parse. Here is an exemplary output of the URL "http://nasza-klasa.pl/friends_list/14646653/3/5289" (retrieve UIDs and first names only; it's my friends' band's account - cheers, dudes!), with the 3 leading bytes stripped:

({"VERSION":{"LAST_ADD":"1219583764","FRIENDS_COUNT":40},"UID":[3053592,3583955,14442691,219291,2579249,4381854,5288144,3725481,3123442,5993186,1696561,3684784,3969330,4334375,7098585,4276143,5140616,4245903,6725224,2023542,3724862,6445366,6509887,4984429,1584950,6496380,7960261,3563520,8182916,10758767,3236560,6462111,2975713,4771329,4084833,3350043,2613772,16211826,14143543,3017104],"FIRST_NAME":["Mateusz","Micha\u0142","Jumanji","Piotr","Micha\u0142","Alicja","Katarzyna","Anka","\u266bZosia","Zuzanna","Kuba","Gosia","Magda","Adam","Sebastian","Paulina","Aleksandra","Krzysztof","Dawid","Leszek","Aleksandra","Monika","Mateusz","Helena","Agnieszka","Agnieszka","\u266bRafa\u0142","Maciek","Ewa","Agata","Agata","Bartek","Madzia","Kajtek","Aleksandra","Patrycja","Anna","Ola","Oskar","Tomek"]})

With input data like this it should pose no problem to produce all kinds of interesting output.

In the next post I'll examine the messaging centre.

Hello World!

2008-09-08T23:07:00.000+02:00

I have promised myself time and time again I'll never ever start a blog, but here I am doing this. I have an excuse, though. I'm not going to write about my personal life, but rather about various things I feel the need of sharing with the world that puzzle and intrigue me. They're mostly related to software development, but you'll also find some Linux tricks and quirks and hardware hacks here.

My name's Leszek, I'm a high school student from Poland, an aspiring software (especially games!) developer and an amateur musician.

Guess this does it for now.