How to run a city builder on 16 MHz
13 points by Yogthos
13 points by Yogthos
As it says, smearing out expensive computation over multiple frames is common in games even now~ One example I stumbled across recently is Minecraft's random-tick system.
I'm curious to what extent this was done specifically to smear out expensive computation. It definitely has that effect, but I can also imagine it being functional in other ways: for example, slowing down wheat's growth rate while keeping its age counter compact (wheat only has 8 grow states).
But maybe tick updates are just expensive in general, and so randomizing them saves CPU? I don't actually know where most of the CPU is consumed.
Random world ticks aren't expensive, but there's a ton of blocks.
We could imagine a system where every single block in the world has a random tick function which runs every game tick (i.e 20 times per second). For most blocks, this would do nothing, for slow-growing things like wheat you could just have a low probability to increase the growth counter, and the occasional tile which actually wants to do things every game tick could do that. The gameplay could be identical to today's (though there would be more developer freedom), storage would be identical to today. But every chunk, that's 16x16x384 blocks, would be roughly 100 000 updates per game tick. An absolutely tiny 128x128 block world (so 8x8 chunks) would have ~6.3 million block updates per game tick. 126 million per second.
This would give you a time budget of roughly 8 nanoseconds per block update function, in total. At 4GHz, that's 4 clock cycles per block.
The difficult thing about block games is never that any single thing you want to do with a block is expensive, it's that there are so damn many blocks.
This would give you a time budget of roughly 8 nanoseconds per block update function, in total. At 4GHz, that's 4 clock cycles per block.
I imagine even the overhead of calling a handler function would be substantial at that scale. Thank you for the explanation, this makes a lot of sense!
This assumes you'd literally tick every block every frame, even though most blocks in the game don't do anything. Receiving ticks could be opt-in instead, which would massively cut down on the computation needed.
In fact, Minecraft does just that. I don't remember the details (it's been ages since I've last played the game, let alone looked at the code), but IIRC only Block entities receive ticks. There's also a scheduled tick system, so you don't have to receive them every frame.
Tile entities and scheduled ticks are a different system from this.
Tile entities are Minecraft's solution for things which want to tick more frequently. But we're talking about random world ticks (https://minecraft.wiki/w/Random_Tick). Every game tick, 3 random blocks are chosen in each 16x16x16 sub-chunk. Blocks which don't "do anything" are still selected for these random ticks, so the game still has to look up what block is at the given coordinates and check whether it's a block which should be ticked.
Saplings, wheat, cactus, ice, leaves, etc. don't all have associated tile entities to handle their growth/melting/decay/whatever, they handle that behavior in the random tick.
The question was about why these random ticks which apply to every block are smeared out over many game ticks.
I was responding to the second paragraph in your reply - my point is that your numbers are much higher than they would really be.
My numbers are exactly as high as they would really be if you took the existing random tick mechanism and didn't "smear it out" across ticks.
But we could imagine a different implementation where we maintain a list per chunk of all blocks which need to be ticked, and then you'd only have to tick all ice, snow, leaves, saplings, growable produce, grass, etc. An implementation like that would for sure be a lot faster. Maybe that would be the most reasonable interpretation of "random ticks but not smeared across game ticks".
Anything to do with old-fashioned game AI tends to be a good fit for this because there are several natural time scales. For each unit in an RTS you might have orders -> pathing -> steering/physics -> rendering. Rendering interpolates based on the latest physics poses. Steering uses the latest navmesh path. Pathing calculates the navmesh path (usually only the first few triangles are actually emitted) toward the latest order's goal point.
With a system like this you can keep a simulation deterministic while performing load-sensitive scheduling/smearing of work. The scheduling can't be directly reactive to wall-clock time (that breaks determinism), but you can schedule based on any deterministic game state. E.g. if more units are currently moving they might re-plan their paths less frequently because the deterministic simulation plans at most 64 paths every simulation tick.
Sim City was available for ZX Spectrum with 3.5MHz Z80 microprocessor: https://worldofspectrum.net/item/0004509/ - I had a chance to play this game around 30 years ago on real hardware (Timex 2048 + FDD3000 floppy).
Ran on the Commodore 64 (0.986/1.022MHz) also.
And the SNES, actually (and I verified that the SA-1 and similar enhancers weren't used, so that was done purely with the 65816)
Civilization I (1991) is arguably even more impressive to me. An entire world with competing AIs, economies, diplomacy, warfare and tech trees, running on a 4.77 MHz 8088 with just 640 KB of RAM.
As someone who played Civ 1 on a 25 MHz desktop, you could spend a noticeable amount of time waiting on unit move animations, let alone the next turn generating.
I recall seeing this trick in the Wargus (Stratagus?) source code, 20+ years ago. In fact it's still here today!
You can think of it as a crude form of task scheduling, I guess. The same work could be all bunched up in one frame (and sleep the other 15), but this would lead to visible stutter in the (single-threaded) SimCity game UI.