Hacker News Reader

Comment by zak_mc_kracken | Hacker News Reader

> "At what point in the frame was this change made?" Some parts of the game may have looked at the original version, while others looked at it after the change. Now magnify the potential for crossed-wires by all of the destructive rewriting going on during a typical frame, and it's a difficult problem.

Not really, it's a pretty trivial problem and one of the least concerns of game programming these days.

View on HN

This is an unsolved problem in a very high profile AAA competitive game: Starcraft II.

In Starcraft II, when 2 Protoss players order one of their templars to move/cast a particular fatal spell to the other templar, then wait, you do not get the expected double kill. Instead, when they get in range of each other one templar casts the spell first, kill the other, and survives.

Which templar lives and which dies depends on the order the units are processed in the frame —arguably an implementation detail. To the players, this is just plain unfair. Not a deal breaker for a hosts of reasons, but still no good.

This also happens with (quite common) high templar vs ghost duel. Both have ability to instantly kill the other type, with the same range. When you move them further than that range, and order both to use that ability on each other - the unit that was produced earlier always wins.

It's not game breaking, but players noticed this.

To avoid such problem with marines shooting (this would be game-breaking, because marines make up bulk of terran armies for most of the game) - there is miniscule random factor added to delay between shots for each marine.

If it was important enough - they would fix the high templar/ghost problem the same way.

BTW in e-sport games (like Starcraft) - finding such bugs and abusing them creatively is part of game. For example mineral-walking is legitimate techinque to micromanage your workers, used even in low-level matches, and it's caused by workaround of bug in Starcraft 1.

This is a pretty standard multithreading problem that has nothing to do with mutability or immutability.

Mutability implies caring about order. I think that's why GP used this example.

Indeed. This problem arises even in a single thread setting. Let's say 2 units aim at each other, and in frame N, they are at range of each other. Here's what should happen:

  - Unit1 kills unit2
  - Unit2 kills unit1

If you double buffer your actions properly, both unit will be dead at frame N+1. If however you modify your data in place, this may happen:

  1. Unit1 kills unit2 => delete unit 2
  2. Unit2 no longer exists.  Unit1 lives.

Or, this may happen:

  1. Unit2 kills unit1 => delete unit1
  2. Unit1 no longer exists.  Oops.

Oops.

What definitely does not happen is the double kill. StarcraftII can live with that, but other games, like Frozen Synapse, would be broken.

What you call double buffer, other call transaction I believe, and it's a system design. You have clear steps where information is gathered and rules are applied.

In that case you take all the attacks, computes the damages, apply them and prune the dead.

Indeed, this is a relatively trivial problem. There are reasons you might want to do something like this (like if you are trying to parallelize your sim) but I'd slot that under "open research problem that nobody agrees on".

There are a lot of problems with global state in games, but entity values are not one of them, mostly. Problems do crop up but you just deal when they do.

Exactly, and in fact it's usually not as simple as "you just work on the previous frame's data". There's a bunch of data dependencies that needs to be respected during a frame update. For example, if you update the player position wrt user input, you will want to update its animation in the same update, and also check if its not coliding with anything. Otherwise you're just lagging behind.

That's a problem only if your engine runs so slow that the changes between frames are relatively large. They shouldn't be, otherwise you'll end up with inconsistencies no matter how many sources of data you use during the calculation of the new frame. It's entirely legal to run your 'world' locally at a higher rate to resolve such issues than the display rate.

That was my initial thought too, but I think it's still a useful realization. at least one place in which this would make sense is physics response.

If your actors has a single 'update' method, the first actor would check for collisions and move before any other actors had a chance to do anything. This gives certain actors preferential treatment in movement.

Of course, you could instead plan out the dependencies better; do all collision detection before all physics response. But this is just a different way to look at 'immutability'

In most real physics systems, you have to solve systems of simultaneous constraints in order to get the right answer, i.e. all the guys involved in an interaction are sort of going at the same time. (Though also these systems do tend to have ways to break constraints and subdivide the problem when it gets too big, which then does give preferential movement, but not in a way that any kind of functional programming would solve, because it is inherent in reducing the complexity of the math problem.)

There may be exceptions to this; it is not a subject I keep current with.

Everyone has to go at the same time or weird instabilities occur in your physics engine; one way to do that is to have everyone read past frame values to produce current frame values (very much like a world -> world function).

That's exactly how it's done. See also: 'Conway's game of life' for a very simple version of such a system (and for kicks, try doing an asynchronous version of it).

yeah, that is actually what I was saying. I just provided an alternative way of looking at it where you pipeline the dependent operations instead of running them at the same time.

eg: instead of:

    foreach actor(find collisions -> find response -> do movement)

do:

    foreach actor(find collisions) -> 
    foreach actor(find response) -> 
    foreach actor(do movement)

That way you may modify the primary data structure directly in the 'do movement' response without any conceptual 'data races'. It really just off loads the information lost from 'mutability' to the secondary data structures of collision lists and the like.

Reply on news.ycombinator.com