The gold standard of optimization: A look under the hood of RollerCoaster Tycoon • Hacker News Board

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

#151

Post by msk-lywenn » Mon, Mar 23, 2026, 7:09 PM UTC

ConceptJunkie wrote: post #143

> The same trick can also be used for the other direction to save a division: > NewValue = OldValue >> 3; > This is basically the same as > NewValue = OldValue / 8; > RCT does this trick all the time, and even in its OpenRCT2 version, this syntax hasn’t been changed, since compilers won’t do this optimization for you. The author loses a lot of credibility by suggesting the compiler won't replace multiplying or dividi…

I wouldn't go that far, but yes, no compiler will leave that on the table today or even twenty years ago. They do even more impressive transformations than that on basic math.

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

#152

Post by WalterBright » Mon, Mar 23, 2026, 7:24 PM UTC

DougN7 wrote: post #79

WalterBright wrote: post #64

Earlier quoted context omitted.

I wrote the Intellivision Mattel Roulette cartridge game back in the 1970s. It was all in assembler on a 10 bit (!) CPU. In order to get the game to fit in the ROM, you had to do every feelthy dirty trick imaginable.

I would love to hear more about that.

I wish I'd kept a listing of that and other projects I worked on. But that never occurred to me.

A friend of mine wrote the Mattel Intellivision poker game. I was playtesting it (a very boring job), and got suspicious. I walked over to his desk and said the program was cheating. It was looking at my hole cards. He sighed and asked how I knew, and I replied it was obvious. He said he didn't have room to add code to improve its play otherwise. I don't know if he fixed it or not.

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

#153

Post by WalterBright » Mon, Mar 23, 2026, 7:31 PM UTC

tialaramex wrote: post #130

WalterBright wrote: post #63

Earlier quoted context omitted.

I originally got into writing compilers because I was convinced I could write a better code generator. I succeeded for about 10 years in doing very well with code generation. But then all the complexities of the evolving C++ (and D!) took up most of my time, and I haven't been able to work much on the optimizer since. Fortunately, D compilers gdc and ldc take advantage of the gcc and llvm optimizers to stay even with…

The thing which would really help IMNSHO is to nail down the IR to eliminate weird ambiguities where OK optimisation A is valid according to one understanding, optimisation B is valid under another but alas if we use both sometimes it breaks stuff.

Yes, one of the unexpected problems I ran into is one optimization undoing another one, and the optimizer would flip-flop between the two states.

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

#154

Post by Melatonic » Mon, Mar 23, 2026, 7:32 PM UTC

netcoyote wrote: post #73

Warcraft 1 (1994), Warcraft 2 (1995), and StarCraft (1998) all use power-of-2 aligned map sizes (64 blocks, 128 blocks, and 256 blocks) so the shift-factor could be pre-computed to avoid division/multiplication, which was dang slow on those old 386/486 computers. Each map block was 2x2 cells, and each cell, 8x8 pixels. Made rendering background cells and fog-of-war overlays very straightforward assembly language. All…

Any idea how Total Annihilation did it in comparison?

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

#155

Post by WalterBright » Mon, Mar 23, 2026, 7:33 PM UTC

jkestner wrote: post #126

WalterBright wrote: post #66

Earlier quoted context omitted.

> getting stuck in the walls I remember the early Simpsons video game. Sometimes, due to some bug in it (probably a sign error), you could go through the walls and see the rendered scenery from the other side. It was like you went backstage in a play. It would have made a great Twilight Zone episode!

That immediately made me think of the Treehouse of Horror episode where Homer got stuck in the third dimension.

Maybe that episode was inspired by the game bug!

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

#156

Post by nitwit005 » Mon, Mar 23, 2026, 7:36 PM UTC

tosti wrote: post #50

mort96 wrote: post #20

Earlier quoted context omitted.

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…

I don't think Minecraft would be considered a cornerstone of optimal programming.

You can find other people discussing implementing similar games on YouTube, and the need to cram the representation of blocks into as small a size as possible always comes up.

Information about blocks is the overwhelmingly dominant thing being stored in memory for those games, so naturally reducing the size of that data becomes important.

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

#157

Post by astrange » Mon, Mar 23, 2026, 7:49 PM UTC

danbolt wrote: post #86

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…

Yeah, I’m quite surprised at this comment. Commercial video games are mass-produced products, and as much as I dislike designers being bogged down in technical minutiae, having a sense of industrial design for the thing you’re making is an incredible boon. Fumito Ueda was notably quite concerned with the technical/production feasibility of his designs for Shadow of the Colossus . [1] Doom was an exercise in both crea…

> Fumito Ueda was notably quite concerned with the technical/production feasibility of his designs for Shadow of the Colossus. [1]

And he didn't really achieve it - the game runs very slowly and has a good deal of cut content.

(I once got him in trouble because I found a GPL violation in ICO. I assume the developer didn't pursue it because I don't see the source code up anywhere.)

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

#158

Post by nearbuy » Mon, Mar 23, 2026, 7:50 PM UTC

ConceptJunkie wrote: post #143

> The same trick can also be used for the other direction to save a division: > NewValue = OldValue >> 3; > This is basically the same as > NewValue = OldValue / 8; > RCT does this trick all the time, and even in its OpenRCT2 version, this syntax hasn’t been changed, since compilers won’t do this optimization for you. The author loses a lot of credibility by suggesting the compiler won't replace multiplying or dividi…

The author is partly right here. If those values are ints, you'll get something like this:

  sar eax, 0x1f
  and eax, 7
  add eax, edx
  sar eax, 3

You get 4 instructions instead of one because value >> 3 rounds towards negative infinity and value / 8 rounds towards zero.

And while this wouldn't apply to C++, in languages with checked arithmetic, the left shift won't necessarily set the overflow flag, so the compiler often can't use it.

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

#159

Post by dmitrygr » Mon, Mar 23, 2026, 8:27 PM UTC

ConceptJunkie wrote: post #144

mid-kid wrote: post #123

Earlier quoted context omitted.

Yeah. I'm surprised this along with the money thing are listed in the article at all. These are the sort of things you learn within the first month of writing assembly, and were widely used across the industry at the time (and times prior). The bit shifting optimization is performed by GCC even at -O0, and likely already was at the time, as it's one of the simpler optimizations to make. It's like calling "xor eax, ea…

"XOR AXAX" was my license plate in the 90s.

I had "PUSH EAX" and "BX LR" :)

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

#160

Post by ben7799 » Mon, Mar 23, 2026, 9:04 PM UTC

I guess I'm showing my age but having read stuff like Michel Abrash's books years ago this article was a bit underwhelming.

Like no one who wrote any code back in the 80s or 90s even for a homebrew game was skipping this stuff, it was in almost every book and tutorial. Stuff like bit shifting was extremely common and a lot of games would have had design choices that were informed by coding challenges. Lots and lots of code had data structures aligned on byte/word boundaries or had data massaged to fit into the limits of hardware in order to make reads happen in a certain # of cycles, etc.. certainly almost all console games had lots and lots of fascinating design choices like this.

This game may have been exceptionally well optimized but it feels like if the original code is not in the public domain these weren't the best examples.

When he started writing about their being a clean sheet re-implementation I thought there was going to be a benchmark comparison of the modern rewrite vs the original on old hardware or something, that would have been interesting.

Thankfully or not I'm just barely young enough that I never had to write anything professional in assembly, though if I had gone into games maybe I would have.