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

121–130 of 186 posts

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

#121

Post by zekica »

makapuf wrote: post #111

Compilers won't do multiplication by power of two to bit shift for you ? I remember reading in ~2000: the only thing writing a<<2 instead of a/4 will do is make your compiler yawn

Even gcc's -O0 will do the bitshift, but even dividing with 5 on x86_64 will not do idiv:

        imul    rdx, rdx, 1717986919
        shr     rdx, 32
        sar     edx
        sar     eax, 31
        sub     edx, eax
        mov     eax, edx

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

#122

Post by 7bit »

eru wrote: post #95
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…

Constraints breed creativity.

Today, constraints are simply ignored. (Looking at you, we devs and Microsoft devs).

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

#123

Post by mid-kid »

youarentrightjr wrote: post #27

> 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 . (emphasis mine) Not at all true. Assuming the types are such that >> is equivalent to /, modern compilers w…

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, eax" a masterful optimization tactic for clearing a register.

Looking at the macro-level optimizations like the rest of the article does is significantly more interesting.

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

#124

Post by mmcconnell1618 »

evandale wrote: post #74

The pathfinding section reminded me that there's a YouTube steamer, Marcel Vos, who goes into a deep dive of how the pathfinding works. https://youtu.be/twU1SsFP-bE He has lots of videos that are deep dives into how RCT works and how things are implemented!

I've built a few transportation simulations where I started out with pathfinding methods like A* but the compute cost doesn't scale well with 10,000 or 100,000 agents running around. Pre-computing flow fields for common map destinations is one of those areas where you trade off storage for compute. The agents just look for the signpost telling them "this direction to destination x" instead of actually calculating a path.

https://en.wikipedia.org/wiki/A*_search_algorithm#

https://www.youtube.com/watch?v=zr6ObNVgytk

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

#125

Post by ionwake »

also I remember the excitement of a new game that looked different to others.

Somehow even as a child I just knew that it would be a whole new emergent game play experience.

Ofcourse I didnt know waht went into making Rolelrcoaster Tycoon but I could just by a couple of screenshots how this was clearly a ground up new game with new mechanics that would be extremely fun to play.

I dont get this feeling anymore, as I just assyne everything is just a clone of another game in the same engine generally.

Unless its been a decade in production like Breath of the Wild of GTA 5 i just dont expect much.

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

#126

Post by jkestner »

WalterBright wrote: post #66
sublinear wrote: post #24

Earlier quoted context omitted.

This way of thinking has caused at least a few prominent recurring bugs I can think of. Texture resolution mismatches causing blurriness/aliasing, floating point errors and bad level design causing collision detection problems (getting stuck in the walls), frame rate and other update rates not being synced causing stutter and lag (and more collision detection problems), bad illumination parameters ruining the look th…

> 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.

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

#127

Post by grumbelbart2 »

dmitrygr wrote: post #93
youarentrightjr wrote: post #27

> 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 . (emphasis mine) Not at all true. Assuming the types are such that >> is equivalent to /, modern compilers w…

they will do it for unsigned. for signed they will do a bit more to do the same rounding as C promises

Here is how that looks like:

https://godbolt.org/z/rooee4esd

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

#128

Post by almostdeadguy »

The pathfinder algorithm is a great example of why constraints are so important for creativity and creative development.

If AI has any benefit to creative endeavors at all it will be because of the challenges of coaxing a machine defined to produce an averaging of a large corpus of work (producing inherently mediocre slop) provides novel limitations, not because it makes art any more "accessible".

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

#130

Post by tialaramex »

WalterBright wrote: post #63
Pannoniae wrote: post #57

Earlier quoted context omitted.

This is all true but IMO forest for the trees.... For example the compiler basically doesn't do anything useful with your float math unless you enable fastmath. Period. Very few transformations are done automatically there. For integers the situation is better but even there, it hugely depends on your compiler and how much it cheats. You can't replace trig with intrinsics in the general case (sets errno for example),…

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.
Post reply on HN