Gets rid of `orig_palette`, we now always have only 2 palettes:
1. `logical_palette`
This palette has color cycling / swapping applied but no global
effects such as brightness / fade-in.
2. `system_palette`
This palette is the actual palette used for rendering.
It is usually `logical_palette` with the global brightness setting
and fade-in/out applied.
Additionally, we now keep the k-d tree around and use it to
update single colors.
The colors that are color-cycled / swapped are never included
in the k-d tree, so the tree does not need updating on color
cycles/swaps.
The previous implementation didn't behave quite like A-* is supposed to.
After trying to figure out what's causing it and giving up,
I've reimplemented it in a straightforward manner.
Now it seems to work a lot better.
Also increases maximum player path length to 100 steps.
We still only store the first 25 steps in the save file for vanilla
compatibility.
This is enough to make it usable as a backing storage for a
`priority_queue`. Had it in one of my branches and figured it might come
in handy in the future.
The new algorithm is a lot less code, slightly faster, and results
in a smaller binary (-40 KiB on rg99).
The previous algorithm filled all the pixels around every solid pixel.
The new algorithm only fills pixels that will be visible.
We first collect the outline pixels into an array (which may contain a
small amount of duplicates). Then, we render the entire array in a
single loop. This turns out to be slightly faster than rendering inline,
at the cost of ~4 KiB of stack (basically free).
To collect the pixels, we go through the CLX sprite, keeping track
of the solid runs in the current row, and the filled pixels on the line
above and the line below.
To be able to quickly test the pixels above and below, we introduce a
new data structure, `StaticBitVector`. It is similar to a bitset,
except the size is determined at runtime (capacity is fixed),
and it supports quick updates of entire subspans.
For monsters with the same sprite, load the sprite from the file system only once.
Example:
```
VERBOSE: Loaded monster graphics: falspear\phall 452 KiB x1
VERBOSE: Loaded monster graphics: skelbow\sklbw 618 KiB x1
VERBOSE: Loaded monster graphics: skelsd\sklsr 610 KiB x1
VERBOSE: Loaded monster graphics: goatbow\goatb 832 KiB x1
VERBOSE: Loaded monster graphics: bat\bat 282 KiB x2 <-- here we only load the sprite once
VERBOSE: Loaded monster graphics: rhino\rhino 1306 KiB x1
VERBOSE: Loaded monster graphics: golem\golem 298 KiB x1
VERBOSE: Total monster graphics: 4401 KiB 4684 KiB
```
Here, the bat sprite will be loaded from the MPQ only once.
For the second sprite, we simply clone the first sprite before applying TRNs.
This also reduces the size of `MonsterData` from 88 bytes to 80.
When we migrate monster data to a TSV, the sprite IDs can be generated automatically at load time.
When using `UNPACKED_MPQS`, avoid all the SDL machinery for reading
files.
This is beneficial not only due to reduced indirection but also because
we can test for the file's existence and get the file size without
opening it, which is much faster.
* Non-int versions of `Point` and `Displacement`
This will allow us to make some structs, such as `ActorPosition`, much
smaller.
* ActorPosition: Use smaller types
`Monsters`: 56K -> 46K
* player.cpp: Reduce size of `DirectionSettings`
* CrawlTable: Displacement -> DisplacementOf<int8_t>
* CrawlTable: vector<vector> -> array<vector>
Also only allocate one vector during construction instead of two.
A bit less indirection.
* Monster#enemyPosition: Point -> WorldTilePosition
sizeof(Monster): 240 -> 232
* Monster: Further optimize field layout and sizes
sizeof(Monster): 232 -> 208
`Monsters` is down to 40,000 bytes
* DMonsterStr: _mx/_my -> position
Previously, the memory for each frame was allocated separately.
Changes it to allocate a single buffer for all the frames.
This has the following advantages:
1. Less bookkeeping overhead in the allocator.
2. Less alignment overhead (allocator results are max-aligned by default).
We can follow this up with a similar treatment for other multi-file
animations.
Gleb Mazovetskiy
Yggdrasill