Free games for graphing calculators: NumWorks, TI-Nspire CX, Casio fx-CG50 and soon TI-84 Plus CE. Balatro, Celeste, Hollow Knight, Minecraft and more.
C calculatorcalculator-gamescasiochesscrossy-roaddrive-madfx-cg50gamesgeometry-dashgraphing-calculatorndlessnumworksnumworks-appsnumworks-calculatornumworks-gamenumworks-gamestetristi-84-plus-ceti-nspire
/* Level data: built-in levels are streamed chunk by chunk into a window of
* resident objects; custom levels are copied into it whole. */
#include "level.h"
#include <string.h>
uint8_t level_scratch[SCRATCH_BYTES];
_Static_assert(SCRATCH_BYTES >= LEVEL_SCRATCH, "scratch too small");
typedef struct { uint16_t chunk, first, count, rmax; float x0, x1, y0, y1; uint32_t base; } WinChunk;
static struct {
const Level *owner;
const LObj *flat; /* the flat array the window was built from */
unsigned flat_count;
unsigned count;
WinChunk wc[WIN_CHUNKS];
uint8_t nwc;
} win;
static RObj win_objs[WIN_CAP];
/* The editor's level shares the window's memory: its end is free while a
* custom level (at most CUSTOM_MAX objects) is resident, and the editor
* reloads its level from storage after a built-in level was played. */
LObj *const level_objs = (LObj *)(void *)((uint8_t *)win_objs + sizeof(win_objs) - CUSTOM_MAX * sizeof(LObj));
_Static_assert(CUSTOM_MAX * sizeof(RObj) + CUSTOM_MAX * sizeof(LObj) <= sizeof(win_objs), "window too small for the editor");
RObj obj_make(float x, float y, unsigned type, unsigned xf) {
uint32_t xq = (uint32_t)((int32_t)(x * 32 + (x >= 0 ? .5f : -.5f)) + OBJ_XBIAS);
uint32_t yq = (uint32_t)((int32_t)(y * 32 + (y >= 0 ? .5f : -.5f)) + OBJ_YBIAS);
RObj o;
o.xs = xq & OBJ_XMASK;
o.ys = (yq & 0xfffff) | (uint32_t)(xf & 3) << 28 | (uint32_t)((xf >> 2) & 3) << 30;
o.type = (uint16_t)type;
o.paint = 0;
return o;
}
/* ------------------------------------------------------------ decoding */
static const uint8_t *rd_p;
static unsigned rd_varint(void) {
unsigned v = 0;
for (int s = 0; s < 28; s += 7) {
uint8_t b = *rd_p++;
v |= (unsigned)(b & 127) << s;
if (!(b & 128)) break;
}
return v;
}
static int rd_zz(void) { unsigned v = rd_varint(); return (v & 1) ? -(int)((v + 1) >> 1) : (int)(v >> 1); }
/* Sorts n objects by x (stable; chunks come almost sorted). */
static void sort_x(RObj *o, unsigned n) {
for (unsigned i = 1; i < n; i++) {
RObj t = o[i];
uint32_t x = t.xs & OBJ_XMASK;
unsigned j = i;
while (j && (o[j - 1].xs & OBJ_XMASK) > x) { o[j] = o[j - 1]; j--; }
o[j] = t;
}
}
/* Inflates chunk c into out (room for c->count objects). */
static bool decode_chunk(const LevelDef *d, const LChunk *c, RObj *out) {
int n = inflate_raw(level_scratch, LEVEL_SCRATCH, d->data + c->off, c->len);
if (n < 0) return false;
if (c->fmt == 1) {
if ((unsigned)n != c->count * 6u) return false;
int32_t x = c->xq0 / 32;
for (unsigned i = 0; i < c->count; i++) {
const uint8_t *r = level_scratch + i * 6;
x += r[0] | r[1] << 8;
out[i] = obj_make((float)x, (float)(int16_t)(r[2] | r[3] << 8), r[4], r[5]);
}
return true;
}
/* column-coded records, sorted by type; runs expand afterwards */
unsigned nrec, cnt = c->count;
rd_p = level_scratch;
nrec = rd_varint();
if (nrec != c->nrec || nrec > cnt) return false;
RObj *rec = out + (cnt - nrec); /* records sit at the end, expanded forward */
uint8_t *props = level_scratch + LEVEL_SCRATCH - nrec;
if ((unsigned)n + nrec > LEVEL_SCRATCH) return false;
unsigned t = 0;
for (unsigned i = 0; i < nrec; i++) { t += (unsigned)rd_zz(); rec[i].type = (uint16_t)t; rec[i].paint = 0; }
for (unsigned i = 0; i < nrec; i++) props[i] = *rd_p++;
int32_t px = c->xq0, py = 0;
unsigned pt = 0;
for (unsigned i = 0; i < nrec; i++) {
if (rec[i].type != pt) { px = c->xq0; py = 0; pt = rec[i].type; }
int u = (props[i] & 64) ? 240 : 1;
px += rd_zz() * u;
rec[i].xs = (uint32_t)(px + OBJ_XBIAS) & OBJ_XMASK;
rec[i].ys = 0;
}
pt = 0;
for (unsigned i = 0; i < nrec; i++) {
if (rec[i].type != pt) { py = 0; pt = rec[i].type; }
int u = (props[i] & 64) ? 240 : 1;
py += rd_zz() * u;
rec[i].ys = (uint32_t)(py + OBJ_YBIAS) & 0xfffff;
}
for (unsigned i = 0; i < nrec; i++) if (props[i] & 1) rec[i].ys |= (rd_varint() & 1023) << 20;
for (unsigned i = 0; i < nrec; i++) if (props[i] & 2) rec[i].ys |= (uint32_t)(*rd_p++ & 3) << 30;
for (unsigned i = 0; i < nrec; i++) if (props[i] & 4) rec[i].xs |= (rd_varint() & 2047) << 21;
for (unsigned i = 0; i < nrec; i++) if (props[i] & 8) rec[i].paint = (uint16_t)rd_varint();
/* expand runs: records move to the front, each followed by its copies */
unsigned w = 0;
for (unsigned i = 0; i < nrec; i++) {
RObj r = rec[i];
unsigned k = 1;
int32_t step = 0;
bool col = false;
if (props[i] & 48) {
k = 2u + *rd_p++;
step = (int32_t)*rd_p++ * 240;
col = (props[i] & 32) != 0;
}
if (w + k > cnt || (w > cnt - nrec + i)) return false;
for (unsigned j = 0; j < k; j++) {
RObj o = r;
if (col) o.ys = (r.ys & ~0xfffffu) | ((r.ys + (uint32_t)(step * (int32_t)j)) & 0xfffff);
else o.xs = (r.xs & ~OBJ_XMASK) | ((r.xs + (uint32_t)(step * (int32_t)j)) & OBJ_XMASK);
out[w++] = o;
}
}
if (w != cnt || rd_p != level_scratch + n) return false;
sort_x(out, cnt);
return true;
}
/* ------------------------------------------------------------ window */
static void win_reset(const Level *L) {
win.owner = L;
win.count = 0;
win.nwc = 0;
win.flat = NULL;
if (L && !L->def) {
unsigned n = L->flat_count < WIN_CAP ? L->flat_count : WIN_CAP;
for (unsigned i = 0; i < n; i++) {
const LObj *o = &L->flat[i];
win_objs[i] = obj_make(o->x, o->y, o->type, o->xf);
}
win.count = n;
win.flat = L->flat;
win.flat_count = L->flat_count;
if (n) {
win.wc[0] = (WinChunk){0, 0, (uint16_t)n, 45, -1e9f, 1e9f, -1e9f, 1e9f, 0};
win.nwc = 1;
}
}
}
static void win_unload(unsigned k) {
WinChunk c = win.wc[k];
memmove(win_objs + c.first, win_objs + c.first + c.count, (win.count - c.first - c.count) * sizeof(RObj));
win.count -= c.count;
for (unsigned j = 0; j < win.nwc; j++)
if (win.wc[j].first > c.first) win.wc[j].first = (uint16_t)(win.wc[j].first - c.count);
memmove(win.wc + k, win.wc + k + 1, (win.nwc - k - 1) * sizeof(WinChunk));
win.nwc--;
}
static void win_load(const LevelDef *d, unsigned ci, float x0, float x1, float y0, float y1) {
const LChunk *c = &d->chunks[ci];
/* make room: drop the chunks farthest from the wanted range */
while (win.count + c->count > WIN_CAP || win.nwc >= WIN_CHUNKS) {
int best = -1;
float far = -1;
for (unsigned j = 0; j < win.nwc; j++) {
const WinChunk *w = &win.wc[j];
float dist = w->x1 < x0 ? x0 - w->x1 : w->x0 > x1 ? w->x0 - x1 : -1;
float dy = w->y1 < y0 ? y0 - w->y1 : w->y0 > y1 ? w->y0 - y1 : -1;
if (dy > dist) dist = dy;
if (dist > far) { far = dist; best = (int)j; }
}
if (best < 0) return; /* everything is needed: the window is too small */
win_unload((unsigned)best);
}
if (!decode_chunk(d, c, win_objs + win.count)) return;
unsigned k = win.nwc;
while (k && win.wc[k - 1].chunk > ci) { win.wc[k] = win.wc[k - 1]; k--; }
win.wc[k] = (WinChunk){(uint16_t)ci, (uint16_t)win.count, c->count, c->rmax, c->x0, c->x1, c->y0, c->y1, c->base};
win.nwc++;
win.count += c->count;
}
void level_stream_y(const Level *L, float x0, float x1, float y0, float y1) {
if (win.owner != L || (L && !L->def && (win.flat != L->flat || win.flat_count != L->flat_count))) win_reset(L);
if (!L || !L->def) return;
const LevelDef *d = L->def;
for (unsigned ci = 0; ci < d->nchunks; ci++) {
const LChunk *c = &d->chunks[ci];
if (c->x0 > x1) break;
if (c->x1 < x0 || c->y1 < y0 || c->y0 > y1) continue;
bool have = false;
for (unsigned j = 0; j < win.nwc && !have; j++) have = win.wc[j].chunk == ci;
if (!have) win_load(d, ci, x0, x1, y0, y1);
}
}
void level_stream(const Level *L, float x0, float x1) { level_stream_y(L, x0, x1, -1e9f, 1e9f); }
void level_iter_y(const Level *L, float x0, float x1, float y0, float y1, LIter *it) {
level_stream_y(L, x0, x1, y0, y1);
it->L = L;
it->c = 0;
it->i = it->end = it->first = 0;
it->lo = x0;
it->hi = x1;
it->ylo = y0;
it->yhi = y1;
}
void level_iter(const Level *L, float x0, float x1, LIter *it) { level_iter_y(L, x0, x1, -1e9f, 1e9f, it); }
const RObj *level_next(LIter *it) {
for (;;) {
if (it->i < it->end) {
const RObj *o = &win_objs[it->i];
const WinChunk *w = &win.wc[it->c - 1];
if (obj_x(o) > it->hi + w->rmax) { it->i = it->end; continue; }
it->gi = w->base + (it->i - it->first);
it->i++;
return o;
}
if (it->c >= win.nwc) return NULL;
const WinChunk *w = &win.wc[it->c++];
if (w->x1 < it->lo || w->x0 > it->hi || w->y1 < it->ylo || w->y0 > it->yhi) { it->i = it->end = 0; continue; }
/* first object whose centre is not left of lo - rmax */
unsigned a = w->first, b = w->first + w->count;
float lo = it->lo - w->rmax;
while (a < b) {
unsigned m = (a + b) / 2;
if (obj_x(&win_objs[m]) < lo) a = m + 1; else b = m;
}
it->first = w->first;
it->i = a;
it->end = w->first + w->count;
}
}
LObj *level_big_scratch(unsigned *cap) {
win.owner = NULL;
win.count = 0;
win.nwc = 0;
*cap = (unsigned)(sizeof(win_objs) / (sizeof(LObj)));
return (LObj *)(void *)win_objs;
}
/* ------------------------------------------------------------ loading */
bool level_load_builtin(Level *L, unsigned index) {
if (index >= LEVEL_COUNT) return false;
const LevelDef *d = &level_defs[index];
if (d->count > MAX_LEVEL_OBJS) return false;
memset(L, 0, sizeof(*L));
L->name = d->name;
L->def = d;
L->count = d->count;
L->events = d->events;
L->event_count = d->event_count;
L->ext = d->ext;
L->end_x = d->end_x;
L->wall_x = d->wall_x;
memcpy(L->colors[CH_BG], d->bg, 3);
memcpy(L->colors[CH_G1], d->g1, 3);
memcpy(L->colors[CH_LINE], d->line, 3);
memcpy(L->colors[CH_OBJ], d->obj, 3);
L->bpm = d->bpm;
L->start_mode = d->start_mode;
L->difficulty = d->difficulty;
L->stars = d->stars;
L->coin_count = d->coin_count;
memcpy(L->coin_obj, d->coins, sizeof(L->coin_obj));
win_reset(L);
return level_valid(L);
}
void level_load_flat(Level *L, const LObj *objs, unsigned count) {
L->def = NULL;
L->flat = objs;
L->flat_count = (uint16_t)count;
L->count = count;
level_index_coins(L);
win_reset(L);
}
void level_index_coins(Level *L) {
L->coin_count = 0;
for (unsigned i = 0; i < L->flat_count && L->coin_count < 3; i++)
if (L->flat[i].type == OT_COIN) L->coin_obj[L->coin_count++] = i;
}
static bool valid_obj(const RObj *o) {
float y = obj_y(o);
return o->type && o->type < OT_COUNT && y >= -2400 && y <= 4800;
}
bool level_valid(const Level *L) {
if (!L || L->end_x < 300 || L->wall_x < L->end_x - 30) return false;
if (L->def) {
/* every chunk must decode to what its header says */
const LevelDef *d = L->def;
for (unsigned ci = 0; ci < d->nchunks; ci++) {
const LChunk *c = &d->chunks[ci];
if (c->count > WIN_CAP || (ci && c->base != d->chunks[ci - 1].base + d->chunks[ci - 1].count)) return false;
}
} else {
if (!L->flat || L->flat_count > CUSTOM_MAX) return false;
for (unsigned i = 0; i < L->flat_count; i++) {
const LObj *o = &L->flat[i];
if (!o->type || o->type >= OT_LOBJ || o->y < -600 || o->y > 3000 || (o->xf & 0xf0) || (i && o->x < L->flat[i - 1].x))
return false;
}
}
for (unsigned i = 0; i < L->event_count; i++)
if (!L->events[i].kind || L->events[i].kind > EV_TRAIL) return false;
return true;
}
/* Checks every object of a built-in level (tests). */
bool level_check_all(const Level *L, unsigned *coins) {
if (!L->def) return false;
const LevelDef *d = L->def;
unsigned n = 0;
*coins = 0;
for (unsigned ci = 0; ci < d->nchunks; ci++) {
const LChunk *c = &d->chunks[ci];
level_stream_y(L, c->x0, c->x1, c->y0, c->y1);
LIter it;
level_iter_y(L, -1e9f, 1e9f, c->y0, c->y1, &it);
for (const RObj *o; (o = level_next(&it));) {
if (it.gi < c->base || it.gi >= c->base + c->count) continue;
if (!valid_obj(o)) return false;
if (o->type == OT_COIN) (*coins)++;
n++;
}
}
return n == d->count;
}
void obj_hitbox(const RObj *o, float *hw, float *hh) {
const ObjDef *d = &objdefs[o->type];
float w = d->w10 * 0.05f, h = d->h10 * 0.05f;
if (obj_rot(o) & 256) { *hw = h; *hh = w; } else { *hw = w; *hh = h; }
}