Hacker News Reader

Comment by marian42 | Hacker News Reader

Since the algorithm is not deterministic I imagine it would be a nightmare to make all clients see the same world. But I agree it would be fun!

View on HN

someone explained above that it’s just a bunch of “tiles” (assume they’re premade), so it’s a fairly simple matrix. it would be much less to transfer than custom maps for example, where clients download a large payload at the start of the game.

or, you don’t really care about tiles except that are directly around the players, as long as there’s a reasonable path between them. the city between them can regenerate and it wouldn’t matter; it’s not like they’d compare notes (and if they did, it’d be an odd coincidence rather than broken)

or, you can always use a map seed so the PRNG that makes it non deterministic (assuming that’s the only thing that does) generates the same numbers so that it is deterministic. the age of empires (old yes, but still relevant!) team wrote a great little piece about their multiplayer, and how they kept all their PRNGs in sync so that the games remained the same across hosts

> generates the same numbers so that it is deterministic.

The problem is, that the algorithm is path-dependent, deterministic PRNG is most likely already used, and doesn't help.

So if 2 players started at (x0, y0, z0) and went to (x1, y1, z1), but took different paths to get there - they would see a different tile :)

oh it's not? is it at least deterministic on the same architecture (ignore float precision) or is just inherent to the implementation?

someone mentioned that it’s random, but i feel like a PRNG seed would make it deterministic?

I get the feeling it's path-dependent. If I start uptown and you start downtown the algorithm could potentially show us two different cities. So we would have to agree on a city beforehand.

This is exacly it. Collapsing one area changes the possible blocks for nearby areas. If you use the same seed, you can still get different results by exploring places in a different order. Maybe there is a way to get around this though.

The server can establish an ordering for the collapse events, and send back to the client that ordering.

Edit: depending on how complex the world is, the server could probably just send out the world changes itself, rather than relying on each client to correctly (deterministically) apply the changes. It needs to do so anyhow for late joiners.

Just keep some buffer of generated tiles around the players, and either use a server to asynchronously decide on when which player moved to cause which tile to be generated. You can also use something distributed if you go for peer-to-peer communication. fix the seed and ensure everyone aggrees on the order in which they tell the generatoe that a certain chunk needs yo be fixed or should be freed from memory. Consider just aggreeing on added/deleted blocks inside fixed intervals, and then process the list in e.g. coordinate order. Consider Raft for peer-to-peer aggreement of the exact diff for the most recent period. Consider chunks of like 0.5 seconds per diff. Don't apply the diff tk the generator until a moment later. You can interleave the cknsensus process of successive blocks a bit.

Peer to peer greatly complicated multiplayer architecture- you _can_ build it like that, but it will be 10 times more difficult.

You kind of have to have the server doing the collapse anyway, or clients can cheat by biasing the collapse towards tiles that are beneficial to them in some way.

You can partially work around this by requiring the client to use a server-provided PRNG seed, although even then a kind of aim bot could help the player decide which path to explore to get favourable tiles.

So your best bet to avoid cheating is to do the collapse on the server using a hidden RNG.

either you have a server doing the collapse or you could send explored tiles as constraints to the other clients (this also reveals your position, but oh well).

of course tiles would need to be large enough to keep latency reasonable.

Reply on news.ycombinator.com