How to Design the Data Structure for a Turn Based Game

Published August 26, 2015 by David Xicota, posted by David Xicota
Do you see issues with this article? Let us know.
Advertisement
One of the recurring questions I get is how to exactly make a turn-based game that has a coherent data structure. Because you're already great coding features for your games, all you may need is a little guidance on how to organize your design to make the things you want actually work. When you see the following example, you'll see how easy it is.

Stuff needed to build a turn-based game

To keep things simple, let's say you want to build a classic tic-tac-toe game. What features should be expected from a game like this?
  • Multiple simultaneous games. Players should be able to have multiple games with different opponents taking place at the same time.
  • Different game status. Every game should have a status that indicates what to expect. Waiting, created, running, finished or cancelled.
  • Play with listed friends. You could have the option to challenge your friends to a game or add new friends to the list.
  • Play with random users. You may want to play with people you don't know.
  • Play same skill users. You might want to play against random players that have a similar skill as you do.
Luckily, making a game with all these features is quite easy! All you need to know is how to lay out the features to make them work like you want. Here are a few questions you should be able to answer.

#1 How are you going to store data?

In this case, I assume a NoSQL database. There, game data is stored in collections, which is like a table in an SQL database. There are some differences though. In a collection you store objects with a similar concept, but they don't need to have the same number of "columns". In fact, in a collection, objects have attributes instead of columns.
  • How many collections does the tic-tac-toe game need?
  • What information should we store in every object?
  • How does every process work inside the game?
To know these, first we have to determine the data structure of a game (match).

Designing the game structure

Our "games" will be objects stored inside a collection we can name GAMES. Every "game" object has these features:
  • It is shared by two (or more) players
  • Allows players to make moves only on their turns
  • It has a winning condition
  • It has a winner
  • All players in it can update the "game" object
We'll store all these features in GAMES collection, which must be readable and writeable by any player so they can work properly.

#2 How will the game structure look like?

Obviously it will depend on the kind of game you'd like to make, but in the tic-tac-toe example we're doing you'll need:
  • Users. Players involved in each game.
  • Status. Whether it is a waiting, created, running, finished or cancelled "game".
  • Current turn. In tic-tac-toe, there will be a maximum of six turns between both players.
  • Current user. Which player has the active turn and can make a move.
  • Movements. List every move, which must be ordered by turn and has to contain the information about:
    • User who made the move
    • Position occupied on the board {x,y} when the move is made
how-design-data-structure-for-turn-based This is how the structure of a turn based game looks like. Most games will have a more elaborate board than we're dealing with in this example, so you'll need a complex matrix of coordinates, and so on. But for this example, the board can be represented by a simple array of positions. Let's see our board of coordinates so we can represent movements in the "game". 0,2 1,2 2,2 0,1 1,1 2,1 0,0 1,0 2,0 The format of the objects used here is JSON, so every "game" will have this structure: { 'users':{ // 'user1': id_of_user1 '1': 55448343d3655, '2': 33129821c1233 }, 'status': 'running', 'currentturn': 3, 'currentuser': '1', 'movements': { '1': {'user': 55448343d3655, 'position':[0,0]}, '2': {'user': 33129821c1233, 'position':[0,1]} }, }

#3 How will you manage the users?

Regardless of the method any user starts a session with (email, Facebook, silent) he or she will always need a profile. Every user has to be assigned a unique user id for the profile, where you can store any additional info you need. Important notice. This profile is public for every other user that asks for it. You should create a collection for "Users", and store there all their profile information for your game.

User public information

In the user profile we are going to store the following information that can be seen by the rest of users:
  • Nickname. The name the user wants to be listed as.
  • Avatar. The name of the image she is using as avatar. The fastest method is referencing an image already in the game package. The alternatives are URL of the file, or ID of the downloadable file in you storage.
  • Friend list. The list of user id's that are in the friend list.

Adding new users to the friend list

We'll have to create a screen flow that allows the players to search for other players in the game and add them to their friend list. The best way to add a new user to the friend list would be to store the user id of the entity, not the nickname, not the avatar, or any other concepts. Important notice. Every object stored should have been assigned a unique id, which is what you should use to look for the whole entity information when you need to challenge friends.

#4 How to play with random users of same skill?

Players will be able to play with random players around the world. Or, to be precise, players in your game database. Now you know all these you're ready to create any asynchronous game you want. How can we make two players find each other and play a game? The most common solution would be to create a collection named "random", or "randomqueue" and make it readable and writeable by all users: Own(er) users and Other users. When a user wants to play with a random opponent we will need him to create an object on that collection indicating he is "waiting" for another user to join. Besides, we'll need to store specific data that lets the user who wants to join the game decipher whether she is an opponent of same skill. This is what you should store for this tic-tac-toe example:
  • User id. Object id of the waiting user because the opponent must be able to download the whole profile if needed.
  • Nickname. So it can be shown on screen easily.
  • Avatar. To have the picture shown on screen easily.
  • Skill. To find the right opponent and offer a balanced gameplay.
Should we create a new object every time a user wants to play random opponents? Not really! The algorithm to implement should be something like this:
  1. Make a search on the "random queue" collection looking for
    • a user that is not me, and
    • whose skill is close to my skill rating
  2. If the result is empty, create my own object on the queue for which I will be waiting
  3. If there are results:
    • pick one
    • create a game
    • send a notification to the opponent via server script

Calculate the user skill rating

In order to foster a balanced matchmaking system, it might be a good idea to have players of similar skill play each other. One way to calculate the skill level of a user is to design a system similar to an Elo rating system. With a system like this, you can have a more balanced gameplay.

#5 How to notify users about their turn?

There are different ways to create a notification mechanism to alert users it is their turn to move or any other game event. Our preferred method are push notifications, though you may want to have an alternative mechanism just in case push are blocked by the user.

Push notifications

To let users know it's their turn, we'll create a server hook post-save script for the collection GAMES. This means every time a user creates or modifies a "game" object the script will run on the server side to send that notification. The script we'll add does a very simple thing:
  1. If the match status is waiting:
    • Pick the current user id
    • Send the user a push saying "It's your turn"
  2. If the match status is created:
    • Pick the user who doesn't Own (didn't create) the match
    • Send the user a push saying "Mary is challenging you"

Alternatives to notify users

How can you notify users it's their turn if they blocked push notifications? One option you have is to create a pulling system. This is how it'd work: If your game detects push notifications are blocked, you can ask the server about your "games" status with an established frequency. You can do this by searching the GAMES collection or by creating a custom script that returns the information you need. If changes to the "game" are found, you can update the scene, and if there aren't the player can continue playing.

To sum up

You have to determine a few key things to build your turn-based game:
  • How to store data
  • How to structure a game
  • How to manage users
Now you know all these you're ready to create any basic asynchronous game you want. Are you using the same techniques to make your own turn-based games? Or something entirely different? Please, post questions or your techniques in the comments section!

This was originally posted in Gamedonia blog.

Cancel Save
0 Likes 0 Comments

Comments

Nobody has left a comment. You can be the first!
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Advertisement