Sprite diffing

[fengb]

Current sprite rendering uses the same diffing / rendering algorithm of patterns and tiles:

1. Any writes to patterns or OAM sets dirty bit
2. If dirty, rerender the entire scene

While this is less than optimal, it matches the usecase of patterns and tiles pretty well, but this does not make sense for sprites:

• Most of the screen does not have a sprite
• Every frame probably has one sprite changing, making the cache kinda pointless
• Most of the time, only a handful of sprites actually change

We should use a better algorithm that matches this behavior:

1. Ignore writes to patterns — this is technically wrong but I'd doubt most games would swap the pattern only
2. Writes to OAM should push into a stack of changed values
3. Render only the changed pixels. Need to test whether doing 2 passes is useful:
   • straight render is simpler and probably faster in general
   • batch then render can be faster if there are sprites that overlap on the coordinate
4. Replace painter's algorithm

[fengb]

Preliminary change is working: https://github.com/fengb/fundude/tree/optimize-sprites

A hybrid approach seems to work the best and improves sprite rendering by ~60%:

1. Use the diff algorithm if possible
2. Default back to painters if too many sprites are colliding

Unfortunately there are quite a few problems:

1. A ton of additional complexity
2. Only render changed sprites instead of correctly layering
3. Major performance regression for safety builds
4. Possibly impossible to add sprite limits per line (is perfect accuracy important?)

2 and 3 might be solvable... but 4 is definitely out.

[fengb]

Overthought this problem. Replacing data.reset(White) in painter's algorithm with the prev_oam diff improved performance by 600%.

Closed by cc56552be6e93ddbb46183c14adb9c081e70a8f0