Handling simultaneous, interdependent, game loop updates

[cpolymeris]

This is more of a general game programming than an SFML question, but I still thought you might have some insight:

Say, I was going to implement "The Game of Life". As you probably know this game consists of an infinite two dimensional grid of square "cells" that live under very simple rules. Each iteration of the game, each cell can be "born", can "continue living" or can "die". This only depends on the number of adjacent cells that are alive.

Something like this:

class Cell : public bool
{
public.
  void update(int numberOfLiveNeighbors)
  {
    *this = numberOfLiveNeighbours == 3 || (numberOfLiveNeighbours == 2 && *this);
  }
};
 

Now, if I was to follow the standard implementation recommended by most game tutorials, my naive game loop would look something like this:

for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
{
  int n = countLiveNeighbors(x, y);
  cells[x * height + y].update(n);
}
 

That is, update each cell after the other. Obviously, that won't work, because each cell needs the data about the last generation, and some of the neighbors have already updated when they are counted.

Variant a) One solution would be to have a game state: store a copy of the "board", compute next generation based on that copy, replace, rinse & repeat. This is the standard board game approach, but means a lot of copy operations. Which is bad, if the board is large. (it's supposed to be infinite after all)

Variant b)Another option would be to do something similar, but on the cell level:

class Cell : public bool
{
public:
  void preUpdate(int numberOfLiveNeighbors)
  {
    inescapableFate = numberOfLiveNeighbours == 3 || (numberOfLiveNeighbours == 2 && *this);
  }

  void update(int numberOfLiveNeighbors)
  {
    *this = inescapableFate;
  }
private:
  bool inescapableFate;
};
 

Then, run the loop twice: Once to "precompute", once to actually update. That works, but is also terrible: you still are copying a lot of data (the same amount in this case), and increase the complexity of your code by counter-intuitively breaking a method in two. The advantage is, you don't have to copy stuff that doesn't change.

Of course, I am not really coding this "game", but the problem I am facing is basically the same. What would you do in this case?

[Groogy]

When I worked on Project Temporality we actually went with the second approach. We first collected all input that this object would receive, and after that we did a second loop where we actually executed the inputs. This had several practical benefits we gained from it. For one, it allowed us to record an entire game session(thus letting us do the whole time manipulation game mechanics the game is based on)

But it helps a lot with other problems, like this one. As it enforces that everyone is reading the same data, and do the same. So the order in when they are updated doesn't matter anymore. For instance you can get "out-of-synch" errors because you are reading modified data, so an object would behave incorrectly. Which happened to us when somebody messed up 

[cpolymeris]

Thanks for the feedback. I might follow that approach, but it really feels unnatural for an object to need to split the update process like that. So each object has to calculate/decide what will happen to it, then store that decision, then at another point actually apply it (i.e. update themself)? Sounds overly complicated.

Maybe it makes more sense if I look at it as a message system: In an evaluate method, all objects get full, but read-only access to the state of the game and an opportunity to send messages based on that state to whomever they wish, including their future selves. Then, in the update method, each objects gets a queue of all messages sent to them, but have otherwise no access to the state of the game. In the Life example, a cell would send a "kill" or "revive" message to themselves (or nothing at all, of course). That could potentially be good if I later wanted a client-server architecture for the game.

Are there any good articles or books on this topic? When I search for game programming, I only find material on how to use this or that library or how to render this or that thing, but nothing about the more fundamental structure of game logic.

[Groogy]

Well it might feel unnatural at first when you haven't done it before.

But logically it makes sense, it makes more things possible. Let's for instance take the example of that you could run the modifying update calls in parallel if you have previously read all the data you need to do the update. Since you know for sure that the data you are reading won't change

Also of course you want the input calculation to be as small as possible and still do as much as possible in the actual update.

About books on the subject, well I don't know any really. There is probably one small chapter in one Game Gem book somewhere. But I hardly think it got any huge article about it or anything like that. Most of the time it's a case-by-case situation when implementing it. You have to look at what you want to do and how you want to solve it.

I know what you are working on, and if this is for that project, I would say this is the way to go because of... reasons   

[cpolymeris]

Yes, it's for Pax, which btw, is not a secret project (it's open source). I have implemented something similar to your approach, the only difference being it uses messages to pass information to the future self to update, like I described in the previous message. I am also distinguishing about object that need info about others (they don't get to evaluate the state of the game before updating), and those that do (I've called them Actors, because in the evaluate method they can also send messages to others, but not sure if that's a good term).
One reason I was hesitant to use that, is, in Pax, the objects are coded in Python*, with the intent of facilitating modding. So I want the objects to know the least possible about the rest of the game. Now the modders have to worry about 2 functions and take care not to modify themselves in the first one.

*or, in principle at least, any Ironlanguage, like Ruby or Lua

[Groogy]

Well that sounds quite sane. The name "input" is just a general term for this, an input can be anything. Your messages would be considered inputs

In the book SFML Game Development we cover a message based system that might be interesting for you. Though we call it commands there but is in essence the same.