GSoC project: The network for you to play online !

Hello world ! my name is Robin Nicollet, alias hilnius, and I'm a GSoC student working on your favorite open-source game ;) I'm going to present you why I'm here and what I'll try to add to SuperTuxKart.

Abstract

First of all, I'd like to thank STK's mentors for choosing me, it's a great honor to work on that project, and I'll do everything possible to make this game as good as possible. I'd also like to say that the community that I found here is amazing, I feel that everybody is welcome here and that's great to have such a good atmosphere.

Presentation

Me

I'm a french student from Télécom-Bretagne, I just finished my first year in this school (2 more and i'll have a master). I've been programming in C then C++ for about 5 years. I know more programming languages but that's not really relevant for this project.

My project

My project is to bring to this game the main features that allow people to play together online. To be quick, that means:

• Connecting people in LAN (Local Area Networks) or WAN (Wide Area Networks : all over the world).
• Starting games and playing together.

One of the main features to play on WAN is the lag compensation, which I won't tackle here for timing reasons :) .

If you just wanted to know what i'll do, you're down at this stage.

In the next sections, I'll detail how the connection between people will work and explain some things about network that are necessary to understand my solution. I will talk about playing together later in the summer when that will be implemented and working ;)

Connecting people

Situation

You may or may not know, but SuperTuxKart do not own a private server and cannot deploy a proper and classic client-server architecture. That's why we will ask SuperTuxKart's player to host their own games. As a result, we will provide inside the game an accessible interface that will allow you to start a server on your own computer to host races.

NAT issues

In this part i'll explain details about how NAT (Network Address Translation) works so that you will have a better understanding of IP networks and how connection will work.
I will use NAT to name the devices that does the Network Address Translation.

Your local configuration

Your local configuration at home probably looks like this:

You are in the Local Network. You are behind a first NAT (it is probably a box that you either borrowed or bought to your ISP (Internet Service Provider). Then, your ISP has his own network, with a lot of devices. Then he has his own NAT.

You may wonder: what is Network Address Translation ?

Network Address Translation

(If you want a fully detailed answer, you can read the wikipedia article)

Network Address Translation is a process used first to extend the number of available IPv4 addresses. Your three computers probably have IPv4 addresses matching the formats 10.xxx.xxx.xxx, 172.16-31.xxx.xxx or 192.168.xxx.xxx.
This does not identify you uniquely over the internet, thousands of people have the same address. It identifies you uniquely only in the Local Network. You should also know that each interface of a connected device has its own IP. For example, your NAT has at least two interfaces : one in the LAN network, and one in the ISP network. Each one of them has its own IP address.
What your NAT does, is that each time you send a message on internet (get a web page, connect to a server, anything...), it changes the IPv4 address in that message to its own. A quick drawing will help me explain that :

Request

Your computer sends a message (get the google.fr webpage) and puts his own local address. Then all NAT that stands on the way of the message will "translate" this address. That means they will memorize the IP of the sender, and replace it by their own.
So for example, when the message is in the ISP network, the IP address of the sender written inside the message is the one of your Router/NAT. And when the message travels in the public internet, the IP address of the sender written in the message is the one of the ISP NAT.

Response

When the google server receives that request, it answers to the IP written in the request (the one of your ISP NAT).
But the ISP NAT knows who sent that message in the first place (10.2.3.4). So the ISP NAT will send the response to 10.2.3.4. Same for your NAT/Router, which knows that it's you who made the request (and then doesn't send the response to your computers 1 and 3).

Conclusion ?

You can now understand that if google sends a message to your public address (that is the one of your ISP NAT), that ISP NAT won't know that you're the one who should receive the message, and then cannot route the message.
As a result, if you try to send a message to anybody who is not directly in the "public internet", he won't receive your message.
The solution to that is the STUN protocol and will be detailed in the next section

The STUN Protocol

This protocol carries well its name, because STUN means Simple Traversal of UDP through NATs. Our goal is indeed to establish a connection between two users, let's say Alice and Bob, each of who are behind their local NAT and their ISP NAT. You can find a complete RFC of the protocol here.

How stun works

STUN is very simple : there are STUN servers in the public internet. You send a STUN request to one of those servers, and it will send you a STUN response telling you your public address. If you understood well how address translation works, you'll notice that when the STUN server receives your request, the sender's IP address is your ISP NAT's one. In the response, that server will tell you : "you have a public IP address that is A and a public port which is P.".

If you're asking yourself what is a port, you can see it as how the NATs identify you. If you send a message to the STUN server, the ISP NAT will give you a port number and put it in the message. Then the STUN server will respond to the couple (sender's ip, sender's port). The ISP NAT will know that the port has been allocated to you and will send the response to your local NAT.

As you see, NATs use "NAT tables" to have ip:port bindings and know where they have to forward packets.
You can see that the STUN response received by your computer contains the ISP NAT's IP address and port number.
A detail worth mentioning: some NAT, called symmetric NATs, allocate a specific port for each connection, and do not allow this protocol to work. It's basically a security feature. So I'm sad to tell that it's very likely that you won't be able to play SuperTuxKart online in a company environment (symmetric NATs are used usually by companies).

Imagine now, Alice and Bob want to communicate. Alice and Bob obtain their own public address (which is their ISP's NAT IP address). Now Alice calls bob with her phone and says "hi bob, my public address is A-A and the associated port is P-A". Bob answers and says "Hey Alice, my public address is A-B and the associated port is P-B". Then if Alice sends a message to the address A-B on the port P-B, Bob will receive the message, because his ISP NAT will know that this IP:port couple is bind to Bob's local NAT/Router. And Bob's local NAT/Router will know that the message he's receiving from the ISP NAT is meant to be delivered to Bob's computer.
So Bob and Alice can now talk :)

The only difference in the way STK will work is that instead of using phone calls to exchange public IP addresses / ports, we'll use a SQL database.

The connection protocol in SuperTuxKart

So when you'll want to play online, you'll query a STUN server, obtain your public IP address/port, then you will publish that in a SQL database. After that, you will put in that database which server you want to join. You also get the server's public IP address/port from the database and start sending messages to it.
This server will check regularly in the database who wants to join him. When he knows that you want to join him, he will get your public IP address/port, and send messages to it. After both you and the server have sent at least one message to each other, NATs will have the good entries in their NAT tables to allow a UDP exchange between you and the server.

After that setup, you will be connected to the server and you will be able to play races with other players that are connected to this server.

Conclusion

I hope it wasn't too long, and that you have now a good understanding of why this is necessary to work this way, and why people cannot connect directly to each other.
The networking part is designed to allow people to setup game servers on real servers, so I'm glad to announce you that at the end of summer you will probably be able to run your own SuperTuxKart server !!

Bye and see you online ;) !

First graphical two weeks - very progressive, aye?

So, this will be long. Your humble coder will try to make it more interesting by interleaving pictures of cats among the overly technical chitchat.

The roadmap said one should do groundwork, glow/bloom, and a smoothed minimap. All this was done, and in addition, the weather system insulted my pet octopus, so now we have updated rain, snow, and grass (and full wind simulation).

Let's start with the rain. Just as any lvl 30 mage worth their bath salt, the mere presence of me triggered interesting gravitational effects:

The previous rain was done with five cylinders, encircling our player like a Russian matryoshka doll. Each cylinder was set to display both sides, and to use a scrolling rain texture.

While working, this method came with two downsides: it was repetitive (streaks always fell at the same spot), and it was a fillrate killer (ticket 892, among others).

Drawing every pixel on the screen five times, with alpha blending on (= 2x the cost, by having to do a read + write instead of mere write), really hit the weaker, bandwidth-low cards. Integrated ones especially bad, as system memory tends to be slower than dedicated VRAM.

So, for a 1024x768 window, 10 fullscreen draws equals 30mb of traffic. Using an integrated system with DDR2-400 RAM as an example, the system RAM can move 3.2 GB (3.05GiB)/s. If everything were optimally placed (we wish), it would take 9.8ms to draw the rain for one frame. 59% of the 16.6ms allowed budget, if the memory placement were optimal (add 10-20% of overhead to that for a more realistic number). This is also not counting the rain texture read.

Ah, we have a question from the audience: "But it's mostly see-through transparent pixels. Surely those are lighter than colorful pixels in the rain streaks?" - no, they aren't. Even if caught by the alpha test, that would only save the final write, the texture read would still occur, the fragment pipeline would still run. So lighter, but not by that much.

Before - after:

So, what was done? Instead of having five scrolling screens, we now model every raindrop, and it upped the average fps from 30 to 45 on a test setup. Yes, you read that right, every drop. There are about 2500 drops. The simulation is fully done on the GPU, and where each drop falls varies as time passes.

By drawing each drop with a point sprite, we send only one vertex per drop, and overdraw is minimal compared to the previous solution. Updating the rain texture from 512x512 to 32x32 (from covering a wall of rain to a single drop) also did its part, now the texture fits entirely into cache.

The average overdraw should be close to one now. Instead of the previous 10 fullscreen moves, we now move about 2.

The observant reader will note that point sprites are squares, not rectangles, and so there is still half of the space wasted in fully transparent area. This is true, a 16x32 texture with a rectangle billboard would be more efficient fragment-wise. However, it would have four times the vertex load, due to having to send each corner instead of just the center point.

---

Moving to the next topic, snow. Snow was handled as cpu-side particles, but they fell straight down, and always faced the player, giving them an artificial look.

So what was done with these? Nothing more than fixing the two lacking points. Each flake was made affected by the wind (more on it in the grass section), and to spin around randomly.


Making the flakes spin was an effort a little more involved. Irrlicht's particle system only does billboards, that is, squares that always face the player.  They don't rotate, period.

This left yours truly stumped for a few hours, pondering how to work around the limitation. The solution came in the form of texture magic, brought to you by the symmetric nature of the snow flake. By flipping the texture in-place by various amounts, it gives the appearance of actually spinning snowflakes.


The improvement was profound. You'll need to see it in action, the still screenshots don't fully do it justice.

---

The grass, which was made to wave in the as-of-yet-unreleased-level Lighthouse, had some limitations. First, there was no wind simulation, it was a sine wave, very repetitive to the eyes. Second, the wind was applied on one axis only, adding to the repetitiveness.

As the first stop towards summoning Jupiter, a proper wind simulation was implemented, via the scroll of 2D Simplex Noise. It blew in all directions, at all strengths, bringing a.. uhm.. wind-like quality to the uhm.. wind.

Then, the new wind was applied to the grass (and trees, and vines, and...) with a nicer shader. Nothing more to report on this topic, for pictures of Lighthouse see the previous post by Samuncle.

---

Turning our attention to the minimap in the lower-left corner, we notice a certain quality of jagginess. Assuming the player had MSAA enabled, it would look nicer, but with the target group of more casual userbase, not many have the hardware power to do so. Of course, smooth maps are as close to a constitutional right as any, so something had to be done.

After a few rounds of prototyping, the final formula ended up being so: render the minimap at double the original resolution, blur it with a Gaussian blur with a radius of 3 pixels, and make sure it has trilinear filtering enabled.

These steps eliminate most of the jaggies, while keeping the edges sharp enough, giving a nicer look in total.

---

At this point, the remaining items on the checklist were glow and bloom. However, our resident master artist had a request: mipmap level visualization, so that artists can determine which textures are of too low resolution, and which are too high.

The formula and colors are those from Unity, publicized by Aras P. A big set of thanks to him!

The blue means too low resolution, and red means too high. Original color means just perfect. Of course the measurement varies by the user's resolution, and how far is one looking at the object from. Therefore any decisions based on this should be done after looking at multiple resolutions, and getting as close & far as possible from the item in question.

The analysis on Hacienda showed that the rope had a far too high resolution - memory could be saved there - while the ground and the wheels of most karts were of too low resolution.

The implementation differs a bit from that of Aras; it is not done by texture, but entirely in the shader, giving more freedom and making it easier to apply. If we were happy with a DX10 requirement, even the textureSize uniform could be skipped (GL 3.0 introduced a function to query a texture's size inside the shader), but as we have to override the shader anyway to show this, sending the uniform is little additional effort, and enables it to run on GL 2 hardware.

Obviously there is a speed hit caused by calculating the mipmap level in the shader compared to letting the texture hardware handle that, but seeing as this is a debug option for artists, extreme speed is not needed. Ease of implementation, by not requiring the extra texture, was worth more in this case.

---

Next up, bloom. No, not her. The technique.

This one is fairly standard fare; a post-processing light bleed effect. We start by capturing the bright areas of the rendered scene. This bloom picture is then progressively minified to 1/8th the size (1/64 the area) halving the resolution at each step, losing no information.

Indeed, such a progressively minified image is of greatly better quality than if we had rendered the captured bloom to the same size directly. The cost of minification is very small in the total effect.

At the small resolution, we then blur it with a Gaussian blur of radius 6. Blurring at a lower resolution comes with the usual benefit that it looks like a much larger blur applied to the full image, at several times faster speed.

This blurred image is then additively blended on top of the scene. There are some artifacts from bilinear sampling, but they are invisible to the human eye in practise, due to the brightness's effect on the eye.

---

For the final item on today's list, we have glow. There's been some confusion with these terms, so let it be known how I define them: Bloom is a post-processing effect, applied to the whole image, to bleed bright light over, improving the look of sunsets, lava, explosions, and many other parts.
Glow is the object emitting light that is visible without a media - so more of an aura, or a light outline. Glow does not appear on top of the object, but only outside it.

I'm especially happy about the dynamic pink in that last picture. Certainly gives the final finish to any barrel of wheat! (don't be alarmed, the colors are intentionally bad as mentioned in the forum, gently encouraging the more artistic among us to change them ;)

I'm sure everyone is itching to hear how this works under the hood. No? I'll tell you anyway.

At each frame, we build a list of glowing objects and their glow colors. Each object is then drawn to a temporary texture, fully clothed with their given color, updating the stencil along the way for free.

This colorful pastel buffer is then progressively minified, this time to 1/4th resolution. A 6-radius Gaussian blur is applied to spread the glow around the object itself. This glow texture is then given to the list of glowing nodes built earlier.

In order for these glow nodes to behave properly in the scene's depth order, they are drawn by container geometry in the transparent pass. At first I tried to use the objects themselves, scaled to a larger size, but that failed soon enough, as no object was modeled around the origin (!). So the next best thing was used, a small sphere (~20 polys) placed at the object's real origin, not the placed origin.

Why does it not overlay the whole objects then, nobody asked. I'm glad you didn't ask, as this is where the stencil magic comes in. Having marked the stencil earlier for "these spots do not glow", we now ask the stencil to block our drawing to those parts, just for the container nodes.

Altogether, it provides a very nice effect, answering the issue that nitros and other objects were not easily visible in darker levels, such as the sand/egypt track.

Phew, if you made it this far, you're probably too tired to leave a comment. That's ok, I'm too tired to read them until Monday. Have a nice weekend!

"Next gen tracks" sneak preview

Hello my name is Jean-Manuel Clemençon (aka samuncle)
I'm the lead graphics artist.
I have been a contributor for a while but this is my first post.

Graphics is an important aspect in our game and since the last version I worked hard to improve graphics.
I made a new track that shows what I'm planning for the future of supertuxkart and two major improvements.

Old (new) mine

I cleaned up the mesh but the most visible improvement is the new lighting system with several lightmaps (and some dynamic lights). It's also more interactive with a Minecart that can knock the player if he forgot to check the traffic light.

Lighthouse

Lighthouse is a next gen track with around 70 000 poly (the average for a track is 20 000). It's the first track that uses our new vegetation shader for grass animation.

The track has also several animated objects like floating buoys in the sea and a dynamic skybox.

Zen Garden

When I made Zen garden in 2010 supertuxkart didn't support lightmaps. So I added some lights and a sunset. Caves are less empty with little blue fireflies.

 

 I'm not saying any more, you can discover by yourself ;)

Graphics guy saying hi

Greetings all! My name's Lauri (cand), and I'll be working on bringing some graphical improvements to STK this summer.

---

Here's the initial timeline:

Weeks 1-2: Groundwork (such as a wrapper class to ease loading shaders), glow (including bloom, since it's very similar), and smoothed minimap

Weeks 3-4: Lighting, including rim lighting for the karts

Initial plan is to implement a light prepass system.

Weeks 5-6: MLAA, SSAO

Weeks 7-8: God rays, motion blur

Weeks 9-10: Water

This will include screen-space reflections, simulated caustics, and vertex
animation via scrolling textures.

Weeks 11-12: Grass, and wrapping up


If there's some part of STK that's been poking you in the eye, or some effect you absolutely must have, leave a comment - the plan's not set in stone.

After each period, I'll be posting some comparison shots, before and after, of that period's progress.

Signing out.

Google Summer of Code - Students View

After more than 2 weeks of deliberation and discussions among all mentors and admins we have finally reached a conclusion for GSoC. First of all congratulations to the three selected students:

• Hilnius: Network Core for SuperTuxkart - implementing network multiplayer but not lobby or rewind
• Cand: Graphical improvements
• Uni: Networking lobby

It was a very difficult decision for us to make. For each proposed idea to us we usually had at least two students we would have loved to pick. But we had only three slots (which is for a first time GSoC organisation quite high), so we had to choose. Congratulations to Hilnius, Cand, and Uni.

Unfortunately, this means that we disappointed 75 other students. We would have gladly taken 6 or so more (but it would not have been realistic to try to mentor that many students). We hope that next year we might have more mentors and more slots, and will be able to accommodate more proposals. In case that you are interested in some statistics: here are the number of proposals we got for each of our suggestions, and the average ranking in each category (1 to 5). There were 6 proposals suggesting new things (including one that proposed to make a 3d kart racing game where you have powerups ... hello, did you even play SuperTuxKart??)

We won't have time to give individual feedback to all students, but here are some common issues we noticed in various sections. First of all, it certainly helps if you spell the name SuperTuxKart correct - we saw quite a few variations ;)  But otherwise some comments about frequent problems we noticed:

Patches

While most students had no problems with the patches, we noticed that many of the patches were not tested. A simple example is our suggested patch of replacing printf with Log::warn/error etc calls.
Assuming a patch is correct just because it compiled is not really sufficient. In one case a patch would compile on linux, but not on Windows. Reason were missing parameters in function calls - something that is easy to notice if you verify that your patch works. And people did not notice that e.g. Log::warn would already print "[warn]", so any 'Warning:' included in the text is not necessary and should have been removed. But for the record, we did not really exclude anyone because of those problems, since we stated that we mainly wanted to see that using SVN etc. worked. We did rank someone who attached a patch as image (png) ... quite low, since this showed us that the basics of a versioning system were not fully understood, and this is an essential skill any student needs to have.
Some students surprised us by taking on some rather complex bugs that were in our tracker, so we already have quite a few improvements for the next release because of this.

Battle Mode

The most popular proposal. Many proposals were suffering from missing details, e.g. not explaining what information was exported by blender into SuperTuxKart, and how it was used - they just assumed that there would be a graph. Or missing was just how a target kart or target item were selected, how the AI was meant to drive (i.e. could the existing AI code be used). Some proposals were more research oriented - and while I'd love to do more AI research work, for GSoC we had to accept proposals that had in our opinion more chances of success - last thing we want is to have a good student, with an idea that just doesn't work properly.

Race Verifier

That somewhat simple sounding idea proved to be quite difficult. Many people suggested to just include the stk_config.xml file (careful study of the code would show that also all kart.xml files needed to be included). More advanced proposals suggested to encrypt the file, in order to prevent tampering with the data. While this sounds really convincing, they are all missing the point that if you compile your own sources it is trivial to write into that file whatever you want, and use completely different values in-game. Only a few proposals suggested to actually use STK itself to verify if a race is correct, and only one proposal suggested to analyse statistically what items were collected in a race (this suggestion can easily be improved by just storing the random number seed for each box - from that number the sequence of collected items can be reproduced).
Overall, this project idea had the fewest good proposals in the end. I guess that because it could potentially be a stand-alone program many students either underestimated its complexity, or just missed the point.

Rewind

Many proposals ignored that you need to store the user events, e.g. steering, and firing. When you rewind and replay from a previous state, you still need to fire, accelerate and steer at the right time, otherwise the whole point of rewinding is missed. Better proposals suggested to make other use of the replay data, e.g. to use this data to show a slow-motion shot of finishing the race.

Summary

Some general comments to wrap this up: Similar things can be said for almost any proposal. Generally proposals of people who have spoken to us received much higher rankings. Especially in the section of new proposals that was obvious - if it hadn't been for Hilnius's proposal, its average would have been much lower.

One frequently asked question or concern was that many students had no prior experience to open source development. We made a point of reading first the actual proposal before reading the background of students, but still in general people with more practical experience received better scores. Their proposals were just more complete, i.e. thought out every step of the way to the goal. For any student who might be interested in participating in a future GSoC I would strongly recommend to use the time till then to get more experience - and participating in Open Source would be a very good candidate. While I can't speak for all Open Source projects I know many will welcome new contributions, and will be happy to help anyone who wants to learn and is willing to put effort into this.