September 23, 2013

Code of Interplanetary: Can I see some ID, please?

Hello there, dear reader. I'm Riku, you might remember me from that more technical post I wrote about making a GUI with Unity. In addition to blogging about our Unity woes, my task has been programming network functionality for Interplanetary.

The game uses a client-server model, where each game client records what the player on that client does during their turn. When the player ends their turn, the client sends all that information to a server for processing. When the server gets this data from all the players, it combines all the player actions together and then plays out the turn, figuring out the outcome. The clients then get back the results for the turn and display some pretty pretty particles flying around to show their player what happened and who shot who.

From the outset I decided that to implement this, I would give everything a unique ID that would be used by different clients and the server to make sure they are all talking about the same thing when communicating. For instance, whenever a building takes damage, the server takes note of the ID of the building, and then tells every client that building number 5 just took a hit. This way, to keep every client in sync so they are all on the same page, I'd just need to make sure they all use same IDs for each object. This sounded very simple at first, but ended up being a little bit tricky in practice.

Let's examine how a building gets assigned its ID. When a building is being built, it should be assigned an ID right away so it can be found again if it needs to be operated on later on. However, the game clients can not be the ones generating the IDs. Each ID needs to be globally unique, and the clients can really only generate IDs that are locally unique to only that one client. They could end up generating same IDs that some other client is also generating for themselves, at which point there would exists two buildings with the same ID. Let's illustrate this with an example. Imagine that ID is an integer, and generating an ID means using an integer one higher than the previous one used. The first building built would have ID 1, the second one 2 and so on and so forth.

Since clients do not have knowledge about each other, they would end up generating same IDs as everyone else. Then, when the information about these built buildings is sent to the server and combined together, the game world would have multiple buildings with, say, ID 2, and there would be no way to know which building ID 2 would refer to. Any time the server would send the clients a message about building 2 taking damage, the clients could not possibly know for sure which building had actually taken damage. This is why all the IDs need to be generated on the same machine, so there won't be duplicates.

The natural option to use here is to generate all the IDs on the server. However, building the buildings happens on the clients' end. It would be possible to ask the server for an ID every time a building is built, but that would create a waiting period whenever a player would build a building and the client waited for the server's response over a network. It was decided that all network traffic would be centralized at the ends of turns, and communicating with the server during a turn would be avoided whenever possible. Because of this, buildings get their ID assigned to them at the end of the turn during which they are built. When the server notices that a player built a building during their turn, it generates and assigns an ID to it. When other clients receive the information that a building has been built, they get the ID for the building in the same package, along with other data like the position and type of the building.

There is one issue left to solve, however. The ID for the building needs to be delivered to the client who built the building, as well. It does not sound complicated at all, but it has some practical implications. For the other clients, the ID was delivered together with the information on how to build the building. They can, therefore, assign the ID to the building as they build it. The one client who already has the building only gets the ID. When it receives the ID from the server, it needs to know which building to assign it to. Normally, whenever the server sends a client instructions about operating on a building, it refers to the building with its ID. However, at this point in time, the building does not have an ID yet! A solution to this is to use temporary local IDs. When a client builds a building, it does still assign a locally unique ID to it. It is not going to be unique across all clients, but it does not need to, as it is only going to be used temporarily until the global ID assigned by the server arrives to the client. The local ID is sent to the server alongside other information about the built building, basically telling the server: "Yo, I just built a building with local ID 5". The server then assigns a globally unique ID to the building and tells the client: "Your building 5 now has ID 7", at which point the client switches the building's ID from 5 to 7. At the same time, other clients just get information about building 7 being built, being blissfully unaware of 5 having been involved with the building at all.

So far things have been relatively straightforward, and were easy to anticipate and prepare for when I was implementing this system. However, there is one complication left to solve, and I admit overlooked it and did not see it coming before I was at the point where it made things not work. Let's look at what might happen when a client builds some buildings.

There are two buildings built on previous turns and the two clients in the game are synced up to that point. Then they both start building buildings and assign local IDs to them, beginning from 3. One client builds one building, with local ID 3. The other one builds two buildings, with local IDs 3 and 4. The server then gets information about this and assigns globally unique IDs to all the buildings.

The global IDs assigned start from 3 and go up to 5. Now, let's look at the second client receiving instructions to replace its local IDs with the newly assigned global ones. It finds the building with ID 3 and switches that building's ID to 4. It then goes to find the building with ID 4, to replace that building's ID with 5. The problem here is that now there are two buildings with ID 4, because of the previous building 3 that was just updated to have ID 4.

The solution I used for this was to fetch a building that needed its ID updated, store its upcoming global ID with it without actually yet updating the ID, and then repeating this process for each building in a need of an ID update. Then I go through all those buildings again, assigning each the ID that was stored with them. In the above example this amounts to finding the building with ID 3, and telling it "your ID is going to be 4, but not yet", then finding the building with ID 4 and telling it it would have its ID updated to 5, and then telling both the buildings to now switch their current ID to whatever ID they were told to switch into.

That is the essence of how things get their identifications in our game so every computer involved can talk about the world state with each other and are able to keep in sync when it comes to the state of the objects. For different objects than buildings the process of assigning the ID is a little different, but that’s something for another blog post. Stay tuned, and maybe I’ll get assigned to talk about those other things in the next episode!

1 comment:

  1. Instead of reassigning IDs, why not use relational approach? Player has an ID of some sort anyway, so it would be very easy to add a relation to keep track of buildings that the player has without all the ID hassle you have now, provided that you are actually using a relational database on the server side.