Hacker News Reader

Comment by yathern | Hacker News Reader

I'm working on a toy game engine for fun. What about the pattern of having a globally accessible list of game entities? EG when a bullet hits an object do (psuedocode)

  Game.getEntityById('player').applyDamage(20);

The bullet class then has access to all entities in the game and can mutate them. Global Mutable State, no? Barring the performance issues of doing this lookup dynamically, is that so bad?

View on HN

You can have that kind of flat, global structure without mutability. One way to do that would be to collect all actions done in each frame (instead of mutating) and then apply them all to create a new frame in a single step (a "reduce"). Then you call the game loop function with that frame to create another frame, etc. The issue isn't just global state, it's global and mutable state. Say that your game has a debuff that reduces the damage of an enemy, and your player debuffs an enemy in the same frame that it attacks him. If you're mutating everything, it can be very difficult to figure out or specify what order things like that happen in, since anything can mutate anything else at any time (concurrency makes this much worse). If you're using mutable state, there's no way to tell all the places that could be changing the enemy's damage, because it could be anywhere in the program. If you're passing everything through as arguments, it's very easy to see exactly where state changes occur and make code modifications in isolation without worrying about affecting unrelated behavior.

What you describe above is similar to what Carmack discussed at his QuakeCon keynote several years back when toying with a game engine on Haskell. Very interesting talk, https://www.youtube.com/watch?v=1PhArSujR_A

I've watched that, and it almost certainly contributed to my comment above. Thanks for linking it for others to enjoy - it's an A+ watch IMO.

That's an interesting concept - I'm not sure I'm fully understanding though.

In your example - in the 'reduce' step - the implication is that the attack and debuff are handled in a deterministic way, regardless of their order? I feel like then that would require the logic for reducing all game commands needs to reside in the engine loop, which doesn't seem right to me.

From what I understand, it is more that by collecting events that occur in a frame and then applying them on the next. It is easier to debug since you can print out the events on every frame. Which if there is a bug, makes it easier since you'll be able to see the events and the order they came in on.

Background. There are two ways gamers think about games "real-time" and turn-based. The question about a bullet is most likely referring to what gamers would call a "real-time" game. The thing is, we programmers are forced to make the game happen in discreet steps. There are multiple ways to accomplish this.

The naive way is to give every object in your game an Update() then on each discreet step you iterate through the list of objects in your game and call Update(). This way lies madness because every object can interact with every other object from any Update() and you can never know where the changes are coming from.

The concept above is that you move up a layer of abstraction and you create a GameState object that contains all objects. You instead give each object a GenerateUpdates() method that returns a list of GameStateChanges. Thus to update the game, you take the GameState, iterate through each of the objects in GameState and get a list of GameStateChanges. You then pass both to either GenerateNewGameState (if game states are cheap) or ApplyChangesToGameState (if they are expensive). This reduces all of your mutations to one method and is much easier to update/debug/fix/understand.

Does that help?

Determinism is indeed a major benefit of the structure I described. I'm curious about your objection, though - where else could the logic be other than in the game loop? In this architecture, your game loop is basically three steps - collect actions, reduce actions, render, repeat.

> One way to do that would be to collect all actions done in each frame (instead of mutating) and then apply them all to create a new frame in a single step (a "reduce")

This is actually a reliable way to construct most programs; it can aid significantly with reasoning, debugging, and performance. I try to build software this way whenever I can.

In FP world, there's a somewhat advanced solution to this, Free Monad DSL/Interpreter pattern. I first found out about it in this talk: [https://www.youtube.com/watch?v=fU8eKoakd6o](https://www.you.... There's an example of a pure functional game ai DSL in it.

The gist of the idea is you would write _pure_ functions like this with an imperative style (example in Haskell)

    bullet = do
      player <- getEntityByID playerID
      applyDamage 20 player

This will require some syntactic sugar (do notation in Haskell, for comprehension in Scala) to make it look procedure / imperative. However, the whole expression remains pure, and does not read or write to global state, it's just a data structure capable of expressing steps of mutations (and/or side effects).

A separate part of the system (interpreter) will actually collect all such data structures and apply actual updates to global states in one place and in a principled way.

Some additional benefits includes easily implementing different interpreters (eg. for unit testing), adding "middlewares" to support things like logging and type safety on mutations.

I have no idea whether game programmers uses this pattern or not. However, it's very common in games to add a scripting language (LUA is a popular one) to express things like unit AI, dialog trees on top the underlying engine; which seems rather similar architecturally: adding a layer of indirection, use a expressive (just enough) DSL to encode the logic for mutations with only limited exposure to underlying global states.

A better resource that explores this idea can be found here: http://gameprogrammingpatterns.com/bytecode.html

Well, it's kinda bad idea for the bullet to have access to everything. It can lead to a lot of mess later on. Global state is not your problem here.

An object shouldn't have access to independent objects, like a wall or another player.

I'd implement an observer pattern (or some other pattern) so you can safely decouple your bullet class say from the wall object.

    UserAction -> bulletFiredMessage -> bullet fires and travels
                                     -> wall receives message -> wall starts to poll if there was an impact
                                     -> boss entity does the same

It's probably not a really good example, but you see state remains in objects.

The fact that there logically exists a list of game entities, and that all threads are required to have a consistent view of these entities at any point in time and are allowed to mutate them, is a global mutable state.

So for games - like for most non-trivial applications - some global mutable state is unavoidable. The task IMHO is not to eliminate it but to reduce it or at least restrict its "degree of globality". For example - even when you can't avoid global mutable state shared by threads within one client process, probably you can reduce the global mutable state shared by different client machines in a multiplayer match.

I don't see this being a big deal with games. When you want to e.g. introduce power-ups that have complex interactions between players, bullets, enemies and the physic system you can't really avoid giving all your entities access to each other for flexibility. Maybe you could use immutable data while avoiding memory management issues but what are you gaining? For all rules of thumb, you need to weigh up the benefit with the cost.

The particular example of game engines is where many laws of clean code break down. The tradeoff to performance is usually not worth it to get immutable data structures, AoS and all those niceties. Instead you make singletons, SoA, collections of mutable entities and so on. And that's fine, as long as you have good performance reason to make that tradeoff.

Reply on news.ycombinator.com