Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

larstofus.com

Post reply on HN
Print view View original

11–20 of 186 posts

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#11

Post by timschmidt »

applfanboysbgon wrote: post #7

> Imagine a programmer asking a game designer if they could change their formula to use an 8 instead of a 9.5 because it is a number that the CPU prefers to calculate with. There is a very good argument to be made that a game designer should never have to worry about the runtime performance characteristics of binary arithmetic in their life, that’s a fate reserved for programmers Numeric characteristics are absolutel…

Absolutely. I have written a small but growing CAD kernel which is seeing use in some games and realtime visualization tools ( https://github.com/timschmidt/csgrs ) and can say that computing with numbers isn't really even a solved problem yet.

All possible numerical representations come with inherent trade-offs around speed, accuracy, storage size, complexity, and even the kinds of questions one can ask (it's often not meaningful to ask if two floats equal each other without an epsilon to account for floating point error, for instance).

"Toward an API for the Real Numbers" ( https://dl.acm.org/doi/epdf/10.1145/3385412.3386037 ) is one of the better papers I've found detailing a sort of staged complexity technique for dealing with this, in which most calculations are fast and always return (arbitrary precision calculations can sometimes go on forever or until memory runs out), but one can still ask for more precise answers which require more compute if required. But there are also other options entirely like interval arithmetic, symbolic algebra engines, etc.

One must understand the trade-offs else be bitten by them.

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#12

Post by andai »

edflsafoiewq wrote: post #9
applfanboysbgon wrote: post #7

> Imagine a programmer asking a game designer if they could change their formula to use an 8 instead of a 9.5 because it is a number that the CPU prefers to calculate with. There is a very good argument to be made that a game designer should never have to worry about the runtime performance characteristics of binary arithmetic in their life, that’s a fate reserved for programmers Numeric characteristics are absolutel…

Examples?

https://en.wikipedia.org/wiki/Nuclear_Gandhi

From what I heard, there was a Civilization game which suffered from an unsigned integer underflow error where Gandhi, whose aggression was set to 0, would become "less aggressive" due to some event in the game, but due to integer underflow, this would cause his aggression to go to 255, causing him to nuke the entire map.

The article says this was just an urban legend though. Well, real or not, it's a perfect example of the principle!

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#13

Post by luaKmua »

andai wrote: post #12
edflsafoiewq wrote: post #9

Earlier quoted context omitted.

Examples?

https://en.wikipedia.org/wiki/Nuclear_Gandhi From what I heard, there was a Civilization game which suffered from an unsigned integer underflow error where Gandhi, whose aggression was set to 0, would become "less aggressive" due to some event in the game, but due to integer underflow, this would cause his aggression to go to 255, causing him to nuke the entire map. The article says this was just an urban legend thou…

Indeed an urban legend. Sid Meier himself debunked in his memoir, which is a pretty great read.

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#14

Post by Waterluvian »

edflsafoiewq wrote: post #9
applfanboysbgon wrote: post #7

> Imagine a programmer asking a game designer if they could change their formula to use an 8 instead of a 9.5 because it is a number that the CPU prefers to calculate with. There is a very good argument to be made that a game designer should never have to worry about the runtime performance characteristics of binary arithmetic in their life, that’s a fate reserved for programmers Numeric characteristics are absolutel…

Examples?

Not really an example that proves any point, but one that comes to mind from a 20-year-old game:

World of Warcraft (at least originally) encoded every item as an ID. To keep the database simple and small (given millions of players with many characters with lots of items): if you wanted to permanently enchant your item with an upgrade, that was represented essentially as a whole new item. The item was replaced with a different item (your item + enchant). Represented by a different ID. The ID was essentially a bitmask type thing.

This meant that it was baked into the underlying data structures and deep into the core game engine that you could never have more than one enchant at a time. It wasn't like there was a relational table linking what enchants an item in your character's inventory had.

The first expansion introduced "gems" which you could socket into items. This was basically 0-4 more enchants per item. The way they handled this was to just lengthen item Ids by a whole bunch to make all that bitmask room.

I might have gotten some of this wrong. It's been forever since I read all about these details. For a while I was obsessed with how they implemented WoW given the sheer scale of the game's player base 20 years ago.

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#15

Post by shakow »

fweimer wrote: post #4

What language is this article talking where compilers don't optimize multiplication and division by powers of two? Even for division of signed integers, current compilers emit inline code that handles positive and negative values separately, still avoiding the division instruction (unless when optimizing for size, of course).

That's what I would have thought as well, but looks like that on x86, both clang and gcc use variations of LEA. But if they're doing it this way, I'm pretty sure it must be faster, because even if you change the ×4 for a https://godbolt.org/z/EKj58dx9T

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#16

Post by hcs »

edflsafoiewq wrote: post #9
applfanboysbgon wrote: post #7

> Imagine a programmer asking a game designer if they could change their formula to use an 8 instead of a 9.5 because it is a number that the CPU prefers to calculate with. There is a very good argument to be made that a game designer should never have to worry about the runtime performance characteristics of binary arithmetic in their life, that’s a fate reserved for programmers Numeric characteristics are absolutel…

Examples?

Not the same thing but I was reminded of a joke about the puzzle game Stephen's Sausage Roll:

> I have calculated the value of Pi on Sausage Island and found it to be 2.

https://web.archive.org/web/20240405034314/https://twitter.c...

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#17

Post by timschmidt »

mikkupikku wrote: post #5
sroerick wrote: post #2

I had always heard about how RCT was built in Assembly, and thought it was very impressive. The more I actually started digging into assembly, the more this task seems monumental and impossible. I didn't know there was a fork and I'm excited to look into it

Macros. Lots of macros.

And presumably generous use of code comments

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#18

Post by timschmidt »

londons_explore wrote: post #6

> it turns an optimization done out of technical necessity into a gameplay feature And this folks is why an optimizing compiler can never beat sufficient quantities of human optimization. The human can decide when the abstraction layers should be deliberately broken for performance reasons. A compiler cannot do that.

Agreed. It really requires an understanding of not just the software and computer it's running on, but the goal the combined system was meant to accomplish. Maybe some of us are starting to feed that sort of information into LLMs as part of spec-driven development, and maybe an LLM of tomorrow will be capable of noticing and exploiting such optimizations.

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#19

Post by lukan »

applfanboysbgon wrote: post #7

> Imagine a programmer asking a game designer if they could change their formula to use an 8 instead of a 9.5 because it is a number that the CPU prefers to calculate with. There is a very good argument to be made that a game designer should never have to worry about the runtime performance characteristics of binary arithmetic in their life, that’s a fate reserved for programmers Numeric characteristics are absolutel…

"and in many cases it is one of many silent contributing factors to a noticeable decrease in the quality of their game"

Game designers are not so constrained anymore by the limits of the hardware, unless they want to push boundaries. Quality of a game is not just the most efficient runtime performance - it is mainly a question if the game is fun to play. Do the mechanics work. Are there severe bugs. Is the story consistent and the characters relatable. Is something breaking immersion. So ... frequent stuttering because of bad programming is definitely a sign of low quality - but if it runs smooth on the targets audience hardware, improvements should be rather done elsewhere.

Re: The gold standard of optimization: A look under the hood of RollerCoaster Tycoon

#20

Post by mort96 »

edflsafoiewq wrote: post #9
applfanboysbgon wrote: post #7

> Imagine a programmer asking a game designer if they could change their formula to use an 8 instead of a 9.5 because it is a number that the CPU prefers to calculate with. There is a very good argument to be made that a game designer should never have to worry about the runtime performance characteristics of binary arithmetic in their life, that’s a fate reserved for programmers Numeric characteristics are absolutel…

Examples?

I think Minecraft's lighting system is a good example: there are 16 different brightness levels, from 0 to 15. This allows the game to store light levels in 4 bytes per block.

Similarly, redstone has 16 power levels: 0 to 15. This allows it to store the power level using 4 bits. In fact, quite a lot of attributes in Minecraft blocks are squeezed into 4 bits. I think the system has grown to be more flexible these days, but I'm pretty sure the chunk data structure used to set aside 4 bits for every block for various metadata.

And of course, the world height used to be at 255 blocks. Every block's Y position could be expressed as an 8-bit integer.

A voxel game like that is a good example of where this kind of efficiency really matters since there's just so much data. A single 1616256 chunk is 65.5k blocks. If a game designer says they want to add a new light source with brightness level 20, or a new kind of redstone which can go 25 blocks, it might very well be the right choice to say no.

Post reply on HN