return to table of content

How video games use lookup tables

bemmu
12 replies
13h44m

The first look-up table effect that really impressed me was to use them for making a textured tunnel.

You have a look-up table such that for each pixel on the screen, you know its angle and distance from the center of the screen. With this you can pick which texel to put at each pixel location.

It looks as if you are moving in a tunnel with 3D geometry, but it's so cheap you can even do it on pico: https://www.lexaloffle.com/bbs/?pid=63818

At first I thought the game Stardust must have used this effect, but reading up on it just now they actually just play a repeating 6 frame animation for the background! https://codetapper.com/amiga/sprite-tricks/stardust/

taeric
8 replies
13h17m

If you view color palette as a lookup table, palette cycling was very common and feels very related.

chongli
1 replies
11h52m

He gave one of my favourite GDC talks of all time [1]! I recommend this talk to anyone who is interested in the details and history of working on limited colour palette games!

[1] https://youtu.be/aMcJ1Jvtef0

indy
0 replies
10h8m

Love that video, his passion for the art form really comes through.

dividuum
0 replies
12h17m

Color palette definitely counts. I remember the lookup table Quake used to map its 256 color VGA palette to itself to implement light levels: https://quakewiki.org/wiki/Quake_palette#Colormap

You now basically have a two step lookup: palette_rgb[colormap[color, light]]

boomlinde
0 replies
10h28m

Yes, you could for example achieve the tunnel effect described above with a 16x16 or 32x8 texture using a 256-entry palette.

Unreal by Future Crew has an effect that comes to mind that is probably implemented exactly like that (on VGA mode 0x13), just more of a wormhole than a tunnel: https://www.youtube.com/watch?v=InrGJ7C9B3s&t=4m40s

JKCalhoun
0 replies
2h34m

I remember games that used 8-bit color palette cycling to do tear-free renders in an interesting way.

They would draw the next frame of the game direct to the screen in either the high nybble (4 bits) or the low nybble (alternating each frame).

The color palette was either one of two: one where the same color would be displayed regardless of the high nybble and the other palette had colors chosen where they were the same regardless of the bits in the low nybble.

To be sure the game threw away 256 possible colors to have instead only 16. But when the next frame was being rendered, the user was never aware until, at the very last instant, the next palette was slammed in revealing the new frame (and of course the rendering began for the next).

sylware
0 replies
3h58m

Looking at the symmetries of specific cases, you may find convenient solutions.

nopakos
0 replies
9h16m

There is a little button "Code ▽" under the demo if you want to see how it's working!

FrostKiwi
11 replies
1d11h

Many thanks for submitting <3 Author here, in case of any questions.

vsuperpower2020
3 replies
13h14m

All these animated gifs are annoying and distracting, and I can do without the unfunny boomer memes from 2010. It's just annoying to try and read text with all these colorful gifs being spammed.

alpaca128
1 replies
10h37m

Usually I'd agree but I can only see embedded videos which respect the disabled autoplay setting.

Edit: nevermind, once started it's impossible to pause the videos, they always continue playing after scrolling.

FrostKiwi
0 replies
9h10m

I was not sure how to handle that.

Battery optimization disables the top video element of a muted video once you scroll past it, which stops the WebGL samples from playing. Landing in the middle of the article from another page also prevents the WebGL samples from working with video, which is supposed to illustrate the realtime processing aspect. But unmuted cannot be auto played.

I'll rethink how I approach this for my next article. Maybe a pause button under every WebGL sample?

johnnyanmac
0 replies
11h37m

May I suggest reader view as a solution if you use Firefox?

But this is a technical topic in a visual concept. I appreciate visualizations and absolutely praise shaders in contexts like these.

Agentlien
2 replies
10h34m

Hello and thank you for the great article!

These uses of LUTs are great and I'm happy to see such a neat article describing them. Also love the use of webgl and the ability to upload your own data!

I was a bit surprised however by the way colour grading using LUTs was presented. The article makes it sound like a cool niche solution used by L4D2, but it's been the industry standard for a long while and was used on every game I've worked on, from AAA games like NFS (2015) to larger indie games like Lost in Random.

FrostKiwi
1 replies
10h15m

Glad you liked it! That's quite the incredible career. Lost in Random seems just like my taste. Guess who just bought it and is enjoining it tonight...

but it's been the industry standard for a long while

Yeah, I mixed messages with my colorful writing style I guess, thought the passage "Using 3D LUTs to style your game’s colors via outside tools is a very well known workflow." was enough to state, that it's not niche use. Clarified now with an extra sentence.

Agentlien
0 replies
2h46m

I really hope you'll enjoy the game! It's honestly my favourite project I've been on so far.

If you want a little insight into my corner of the making of LiR, check out this post I wrote about the fog: https:// agentlien.github.io/fog

fbdab103
1 replies
13h48m

There was a typo that was melting my brain until I confirmed that this was not some alternate plotting library.

"Here is every single colormap that matlibplot supports,..."

FrostKiwi
0 replies
11h40m

Ohh, that's funny. I just realized, I always read it the wrong way around in my brain up until now! Corrected the typo.

ronama
0 replies
6h25m

Loved your article! I just wanted to expand a bit on your last section. The Game Boy Advance did offer somewhat support for integer division, but it's not hardware-accelerated [1]. I suspect the LUT model was for performance reasons (and rightfully so!).

[1] https://www.copetti.org/writings/consoles/game-boy-advance/#...

nonoesp
0 replies
6h11m

Amazing write-up. Thanks for sharing.

pvg
7 replies
14h17m

That's about a different, less specific meaning of 'look up table' (vs. 'LUT')

pclmulqdq
6 replies
12h17m

I was the author of that piece. This blog is about graphics LUTs, which fall into point (4) of the "when to use lookup tables" section. GPUs have dedicated constant memories that were specifically made for holding lookup tables so that they can be accessed quickly and deterministically. Graphics LUTs are a really powerful tool because of that, and have none of the performance shortcomings.

Anotheroneagain
4 replies
10h4m

Why can't CPUs be told what to cache? Is it because the instruction sets are obsolete, or is there a technical reason why they can't be added?

pjc50
2 replies
5h15m

You absolutely can tell the CPU what to cache, and also what not to cache (such as PCIe memory-mapped registers), it's just that that's privileged instructions which no sensible multitasking operating system will let you have access to. Because it would have to be reset on every task switch.

bombcar
1 replies
4h28m

I’m still disappointed that you can’t boot a modern processor with its 8MB of L2 cache and run Windows 95 entirely in cache. Stupid requirements to have a backing store.

pclmulqdq
0 replies
3h49m

I think if you flip the right MSRs, you can actually run in this mode on Intel. BIOSes used to do DDR3 calibration in this mode, and needed to run a core DRAM-less to do it.

AMD Zen platforms have always put that functionality (ironically) in the secret platform security coprocessor.

djmips
0 replies
8h19m

It could be added and it was a feature on the Gamecube CPU for example - you were able to lock the cache and then, IIRC, half the cache was used as normal and half was at your disposal for very fast access to look up tables or data you were using over and over again. Some code to deform 3D meshes when animating them using a skeleton used the locked cache to speed up that operation greatly by having the bone matrices at hand.

A problem I imagine on modern processors is the cache might be shared amongst several cores and interrupts etc.

Back in the nineties, 3DFX made a speed of light rendering demo for the Voodoo1 where they took over the entire machine and through intimate knowledge of cache behaviour effectively set aside an area in the L1 cache that would contain some data they could stream in and speed up their triangle setup.

michaelnik
0 replies
4h1m

Can confirm CPU part. I once tried to replace a 2d stepwise linear function interpolations (basically, a loop finding the right step, then linear interpolation, on a double; the function's objective is to rescale inputs before they become regression's arguments) by LUTs.

All of this looping was happening in another tight loop, and there were multiple LUTs.

It was a failure with overall decreased performance and increased cache misses. Plus, I could never get the same precision.

pubby
8 replies
11h12m

Retro games used a ton of tables. Back then memory speeds were blazing fast, but processors were sluggish, so it made sense to pack as much computation as possible into tables. The more clever you were about it, the fancier games you could make.

ggambetta
3 replies
9h9m

I remember the days of resticting rotation accuracy to 360/256ths of a degree so it would fit on a byte, which then would be an index into trig lookup tables :)

Jevon23
1 replies
4h42m

I miss the days when professional software development was more akin to this sort of thing, rather than gluing together 20 Javascript frameworks on top of someone else's cloud infrastructure.

ggambetta
0 replies
3h21m

I'm with you. The current thing really isn't fun anymore :(

djmips
0 replies
8h37m

haha yes, we used 2π / 256 and we called them brads (binary radians).

alpaca128
3 replies
10h42m

Not always, though it might depend on what platform you mean with retro. Kaze Emanuar on YT does a lot of development for the N64 and it feels like half the time he talks about how the memory bus affects all kinds of optimizations. In Mario 64 he replaced the original lookup table for the sine function because an approximation was faster and accurate enough (or rather two approximations for two different purposes).

I love that channel, he reworked the entire Mario 64 code [0] to make it run at stable 60FPS...because he wanted his mods to run faster.

[0] https://www.youtube.com/watch?v=t_rzYnXEQlE

sumtechguy
0 replies
5h3m

Back when I started I thought I would make games. I used a lookup table for cos/sin kept as an integer. I only needed enough precision for rotation on 320x240. It was something like 20-30 cycles faster per pixel. Even more if you didn't have a FP co-processor.

djmips
0 replies
8h47m

The speedup from the approximation wasn't that much if anything. He made his real improvements elswhere. But your point stands that memory speed really has moved the goalposts on what is feasible to speed up through using precalculation tables and if you can do it with math then that is often much faster.

TacticalCoder
0 replies
2h5m

By retro platform GP meant Atari ST and Commodore Amiga and the like: LUT were the name of the game for everything back then. Games, intros/cracktros/demos.

Heck even sprites movements often weren't done using math but using precomputed tables: storing movements in "pixels per frame".

It worked particularly well on some platforms because they had relatively big RAM amounts compared to the slow CPU and RAM access weren't as taxing as today (these CPUs didn't have L1/L2/L3 caches).

The N64 is already a more modern machine.

joegibbs
8 replies
1d11h

This is brilliant - I've used plenty of LUTs for post-processing but it never occurred to me to use them for recolouring assets as well.

0cf8612b2e1e
2 replies
12h35m

Does this mean the engine is fully deterministic?

unleaded
0 replies
11h20m

Yes, if you make the exact same inputs you will get the exact same outcome. Demos and multiplayer rely on this, they just record player inputs, nothing about enemy movement or anything like that. This is also why you can leave a multiplayer game in the middle of a match, but you can't join one in the middle

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

bombcar
0 replies
4h32m

Yes, and that speed runs can be “seed runs” where you do things to make the right LUT number come up at the right time.

The DooM Engine Black Book goes into details.

https://fabiensanglard.net/doom_fire_psx/ also

Other games use seeded random number generators to be entirely deterministic even though random; Factorio does this to allow multiplayer without having to sync the entire game state all the time.

FrostKiwi
2 replies
1d11h

Yeah, developer commentaries are a goldmine in general for small gold nuggets of knowledge like that. Never would have come up with such an use-case either.

svec
1 replies
14h52m

Are there any other dev commentaries you recommend (other than the mentions in your post)?

FrostKiwi
0 replies
11h37m

Basically, all of the Valve ones. (Half-life 2, Half-life 2 Episode 1, Half-life 2 Episode 2, Team Fortress 2, Left 4 Dead, Left 4 Dead 2, Half-Life Alyx)

Each one of them is a time capsule of the techniques and game design philosophies at the time of development. Pretty sure there is a walk through on youtube for every single one of them, if you don't want to get the games yourself.

stevenwoo
0 replies
12h26m

This reminds me, we used a command line tool (originally made for Warcraft 2?) to take full color art assets and find a palette of 200 or so colors (the rest reserved for UI elements and the player characters) for the different areas in Diablo 2, and then remapped all the art assets to these small palettes, and then reuse the monster art with other colors within these palettes for varieties of monsters. I don't remember spending more than a day on putting this in our art pipeline, the guy who wrote the tool did all the hard work.

reactordev
7 replies
15h1m

Off the top of my head, my uses of LUTs have been:

   - Atmospheric scattering.
   - Tinting Sprites.
   - Nightvision Scopes.
   - FLIR scopes.
   - B&W “video feed” effect.
   - Glitch effects.
   - Heightmap Shading.
   - Alpha dot factor for spaceship exhaust plumes.
   - Heatmap of website visitors mouse dwellings.
   - Crystalline Effects.
   - And finally, post processing colorization in raw color space.
LUTs are a visualization of an array of values known to you, and it’s amazingly useful.

corysama
6 replies
13h55m

Tinting Sprites

Kids these days have forgotten all about palettized sprites! Where do ya think the term “palette swap” comes from? ;)

http://www.effectgames.com/demos/canvascycle/

It fell out of favor because OG Xbox was bad at it and Photoshop doesn’t support it. But, modern hardware can totally handle palette swaps make in AESprite.

bregma
4 replies
6h39m

It fell out of favour when the move to 16-bit systems meant no more hardware sprites.

reactordev
2 replies
6h14m

It fell out of favor when we could just store 1000x more sprites. It was memory, not instruction-set. Tinting then happened as a pre-build step until finally shaders replaced the practice entirely.

corysama
1 replies
3h37m

Instead of “fell out of favor” I shoulda said “artists stopped being informed of its existence and occasionally invented poor approximations to it from first principles”. Such as tinting sprites to approximate palette swaps of the retro style they are referencing.

You can do so much more than tint with palettes. The animations in the link I posted each a composed of a single 8-bit image and a function to rotate specific sections of the palette.

reactordev
0 replies
2h37m

I’m intimately familiar with palette animations. You’re right though, it’s a technique that was lost due to hardware no longer limiting the artists. I still find it to be far superior to sprite tile replacement animations.

corysama
0 replies
3h42m

The SNES and Genesis definitely had hardware sprites. The PS1 and PS2 worked with palettized textures 99% of the time and had hardware quads. The N64 could do palettized textures and quads. The same for the OG Xbox, but it was a big speed hit vs DXTC. With the Xbox360 and PS3 you could implement palettized textures as a shader. But, only the most special cases bothered.

charcircuit
0 replies
11h30m

It fell out of favor because OG Xbox was bad at it

It fell out of favor because hardware no longer needed to use palettes as they had enough memory to store the actual color.

zeta0134
5 replies
6h38m

Lookup tables are the only reason I was able to get this effect working at all:

https://twitter.com/zeta0134/status/1756988843851383181

The clever bit is that it's two lookup tables here: the big one stores the lighting details for a circle with a configurable radius around the player (that's one full lookup table per radius), but the second one is a pseudo-random ordering for the background rows. I only have time to actually update 1/20th of the screen each time the torchlight routine is called, but by randomizing the order a little bit, I can give it a sortof "soft edge" and hide the raster scan that you'd otherwise see. I use a table because the random order is a grab bag (to ensure rows aren't starved of updates) and that bit is too slow to calculate in realtime.

ecshafer
1 replies
3h40m

That looks pretty awesome, and the graphics are way better than any NES game I can remember, it looks more like an SNES level graphics. Since you are running on an emulator there, does the emulator lock you to NES level performance?

zeta0134
0 replies
2h47m

Yes, though full disclaimer, the cartridge is a tiny bit more powerful than your average NES game, and that is definitely contributing. The capabilities of the cartridge I'm using are something like Nintendo's MMC5 (used for Castlevania 3) but with a slightly more useful ExRAM implementation. The main benefit for this effect is that I can write to the nametable outside of vblank, and that helps with the double-buffer setup. The NES CPU isn't fast enough to process all of the enemies at once, so I batch the changes over time, and then present the updated board when the musical beat advances.

This should run on real hardware, I'm just waiting on a dev board from my cart supplier before I'll be able to test that properly. Mesen is what I use in the meantime. It is pretty darn accurate, and I haven't overclocked it or cheated any of the console's constraints away.

sourthyme
0 replies
6h14m

The 1/20 update works well because it gives the illusion of tiles popping into view naturally as the lamp moves. This is a cool effect to get away with.

rightbyte
0 replies
32m

Heh, cool. I always find it fascinating how games for the same console could get so much prettier as people learned to code for them. E.g. Mario 1 and 3 or the two Zeldas for N64.

nicole_express
0 replies
1h5m

Very nice work! Definitely looks way better than the contemporary NES attempts at doing it (thinking of MMC1 Ultima Exodus here)

gxs
5 replies
14h38m

Even in boring old business process land, it’s surprising how useful this is.

Often you can simplify a code base full of conditional statements with a tidy lookup table.

I think the reason this isn’t always thought of is because a lookup table might end up with 50k rows even for something that might seem simple. This might some like a lot to end users, but thankfully the computer doesn’t mind.

Also, the look up tables are so repetitive that the tables are usually pretty easy to manage, and still worth it even when they aren’t.

On top of that, they can be configured by end users without code changes.

All in all, a really useful concept, especially for a lot of scenarios that always pop up when coding business logic.

chii
3 replies
14h23m

On top of that, they can be configured by end users without code changes.

and that is how you end up with a DSL.

gxs
2 replies
13h58m

Here we go, knew someone would jump in here with their opinions on why this is bad etc.

You’re reading way too much into this, this simply solves a particular set of problems well in this context and that’s that.

Anything you use can get turned into something ugly given enough time and lack of supervision.

chii
1 replies
11h3m

their opinions on why this is bad etc.

where did i say it's bad? DSLs aren't inherently bad (or good for that matter).

You’re reading way too much into this

i think you're projecting your own ideas onto me!

gxs
0 replies
10h44m

Ha, sorry, guess I was a bit defensive. Forget sometimes not everyone is a jerk by default online.

oakwhiz
0 replies
12h39m

Double buffered lookup tables!

KingOfCoders
2 replies
12h21m

Back in the days assemblers (patched Seka) had tools to generate sin wave lookup tables.

OnlyMortal
1 replies
9h47m

Handy for vector graphics if you include a table for TAN.

082349872349872
2 replies
1d9h

If you try to program just about anything non-trivial in sed(1), LUTs are the way to go.

kragen
0 replies
14h25m

indeed! though you've had more success with that than i have

i'd add: or fpgas, or eproms, or m6

dredmorbius
0 replies
7h59m

I'm both fascinated and horrified to ask what non-trivial sed programming you might be doing, and why ;-)

wilg
1 replies
12h32m

If you work with LUTs a lot, I work on a Mac app that handles all kinds of advanced color science and conversion tasks: https://videovillage.com/lattice

cpach
0 replies
9h36m

Those tools look awesome! Makes me wanna make a movie :)

nicetryguy
0 replies
5h50m

the SNES didn't have a graphics processor

It absolutely did! Even the NES had one. In addition to the (cloned) Motorola 65c816 SNES CPU, the PPU (picture processing unit) was a custom chip that offered several different layouts for spitting out tile based backgrounds and sprites as each scanline physically drew across the CRT TV. It was even capable of fancy things like background rotation and scaling (Mode 7, think Mario Kart) and hardware transparences which you can see in many games. Furthermore, in the case of Doom (and games like Starfox) the cart was baked in with the "Super FX" chip that handled the 3d calculations. So you were actually dealing with two graphics processors for that specific title, heh.

Here's a wonderfully (and painfully) detailed series about the SNES hardware by Retro Game Mechanics Explained:

https://www.youtube.com/watch?v=57ibhDU2SAI&list=PLHQ0utQyFw...

vjfms
0 replies
2h49m

Awesome demonstration!

lulznews
0 replies
3h14m

TLDR?

luismedel
0 replies
11h38m

They are extra useful to precalculate other visual effects. In the past, following a magazine tutorial, I coded a very cheap raytraced "lens effect" on a 286. I recently (5 years ago!) ported it to js [0].

That magazine got me into fractals and raytracing, BTW.

[0] https://github.com/luismedel/jslens