←back to thread

333 points freetonik | 5 comments | | HN request time: 0.841s | source
Show context
fleabitdev ◴[] No.42471288[source]
This engine uses a Redux-like architecture. You have a State type (containing data like "the position of the black kingside rook") and a stream of in-game actions (like "knight to F3"). Each action is handled by a pure function which converts the current State to a new State. You can either transmit State deltas from the server to the client, or just transmit the actions themselves (https://longwelwind.net/blog/networking-turn-based-game/).

This design makes it easy to implement optimistic updates, rollback, replays, automated testing, and recovery after a disconnection. It's a surprisingly good fit for UI, too; you can render simple games as a React component which takes the current State as one of its props.

However, a stream of context-free actions can be a really inconvenient representation for some games. The rules of a board game are often like the control flow of a computer program: you'll see branching, iteration, local variables, function calls, structured concurrency, and sometimes even race conditions and reentrancy. When you try to represent all of this logic as a State object, you're basically maintaining a snapshot of a "call stack" as plain data, and manually resuming that "program" whenever you handle an action. It doesn't seem ideal.

I've been sketching a board game engine which would represent the game logic as normal code instead. It seems promising, but it really needs a couple of language features which don't exist in the mainstream yet, like serialisation of suspended async functions.

replies(5): >>42471791 #>>42472084 #>>42472570 #>>42475998 #>>42477605 #
1. NathanaelRea ◴[] No.42471791[source]
Can you explain more what type of game would need a call stack snapshot? I've never developed a game, but it seems like as long as you store like the initial state and prng you could always get the current state by replaying the full history. All the other logic would be stored outside the state, and only added when "committed". As long as prng is stable and you start from the clean state every time, you'd get the same outcome.
replies(2): >>42472203 #>>42472211 #
2. yojo ◴[] No.42472203[source]
I think I have a good example from Magic: the Gathering.

There’s a card called “Fact or Fiction”. You reveal the top five cards of your deck. Then your opponent splits the cards into two piles. Then you pick one of the two piles to take into your hand.

You’ll need to store structures representing the choices that are intermediary steps (split cards, pick stack) in your state, which is basically function calls and their params (a call stack). This example could get hairier - Magic also features cards with branching logic “choose 1: do a or b”. I can imagine designing cards with large and convoluted possible execution paths.

You could have the card define a schema for state transitions/params and represent all these choices as JSON encoded POJOs, but as a developer it sounds a lot nicer to just be able to suspend an async function every time a choice is made.

replies(1): >>42472730 #
3. fleabitdev ◴[] No.42472211[source]
That's the exact approach I'm considering for the new engine I mentioned!

Although that strategy enables you to store and recover the state of a game, it doesn't give you the ability to inspect a snapshot of that state. How can you print the card which has just been played, if that data only exists as an argument in the call stack of a suspended async function? In the same way that you can't inspect the local variables captured by a closure, mainstream languages also provide no way to inspect a suspended stack frame.

This problem interferes with debugging, consistency checks (e.g. hashing the game state to check that two clients are in sync), and unit testing.

4. Longwelwind ◴[] No.42472730[source]
I had the same issue in AGoT:BG and I solved it by representing the state of the game as a tree. At any point of the game, the current game state is a leaf of the tree.

You'd represent this kind of choice as a child node. When the user has made their choice, the code can return to the parent node with the choice being made so it can continue with the next "step" of the game.

replies(1): >>42474385 #
5. scrollaway ◴[] No.42474385{3}[source]
This is the correct response. Hearthstone is structured like this internally.

If you are curious about it, I wrote a cc0 spec which stores hearthstone game state in xml. It’s based on how hearthstone stores game state on the server and client, and it was the first time a replay format was created for hearthstone: https://hearthsim.info/hsreplay/

Incidentally the UI we wrote for hearthstone replays is a react app. It’s funny because looking back it was the first time I used react and typescript, and both were not at all adopted by the js community yet at the time.

https://github.com/hearthsim/joust