Skip to content

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.

35.1 KB
Raw Blame
/* Finds a run to the finish of each official track with the game's own physics, for tests/routes.h:
 *
 *   route [TRACK...]     prints the runs (letters, as in routes.h) of the tracks given, or of all
 *
 * How: a map of how far each place is from the next checkpoint along the track (2 m cubes over the track's
 * surfaces, walked back from the checkpoint's box, not through walls), a driver that steers along it, and
 * Go-Explore: an archive of cars, one for each stretch of the way (and how fast, and which way), the quickest kept;
 * again and again a car is taken from it, those further on and less tried first, and driven on a while by the
 * driver or with keys held; cars that get somewhere new go in.
 *
 * Options (in the environment): TRIES, SEED; VC and AU, what climbing and going up through the air cost on the map;
 * VIA="k x y z r", a place to go through after k checkpoints; HB, SPEEDW, ENERGY, more kinds of stretches;
 * PREFIX=file, going on from a run found before (LANE="k x0 x1 z y" to hold its run-up on a lane); PARTIAL, print
 * the furthest run when none finishes; TRACE, FIELD_DUMP and PILOT, to look at the map and the driver.
 * The runs in routes.h came from this finder over its versions, a few with options (Desert 3: a run-up held on its
 * lane with LANE, then VC=2 AU=10); a run found again is another, as good, with its own times and hashes. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../src/car.h"
#include "../src/data.h"
#include "../src/world.h"

#define VOX 2.0f
#define INF 0xFFFF

typedef struct {
  int nx, ny, nz;
  float x0, y0, z0;
  uint8_t *walk;                    /* 1: a car can be there */
  uint8_t *wall;                    /* 1: a barrier; 2: next to one or to a drop, 3: one further in */
  uint8_t *cut;                     /* bits 1, 2, 4: a surface between the cube and the next one in x, y, z */
  uint16_t *dist[17];               /* to each target: the checkpoint orders, then the finish (and a VIA) */
  int ntarget;
} field_t;

static field_t F;

static int vidx(int x, int y, int z) { return (z * F.ny + y) * F.nx + x; }
static bool vox_of(v3 p, int *x, int *y, int *z) {
  *x = (int)((p.x - F.x0) / VOX), *y = (int)((p.y - F.y0) / VOX), *z = (int)((p.z - F.z0) / VOX);
  return *x >= 0 && *y >= 0 && *z >= 0 && *x < F.nx && *y < F.ny && *z < F.nz;
}

/* the cubes a car's centre goes through on a triangle: up to 2.5 m off its face, on its front side only (so the
   map doesn't go through a thin wall) */
static void mark_tri(uint8_t *g, v3 a, v3 b, v3 c, v3 n, uint8_t kind) {
  float l = pt_maxf(vlen(vsub(b, a)), pt_maxf(vlen(vsub(c, a)), vlen(vsub(c, b))));
  int m = (int)(l / (VOX * 0.5f)) + 1;
  for (int i = 0; i <= m; i++)
    for (int j = 0; j <= m - i; j++) {
      float u = (float)i / (float)m, v = (float)j / (float)m;
      v3 p = vadd(a, vadd(vmul(vsub(b, a), u), vmul(vsub(c, a), v)));
      for (int k = 0; k < 3; k++) {
        int x, y, z;
        if (vox_of(vadd(p, vmul(n, 0.5f + (float)k)), &x, &y, &z) && g[vidx(x, y, z)] < kind) g[vidx(x, y, z)] = kind;
      }
    }
}

/* parts a car drives on whatever their slope: the wall tracks, loops, tilted roads, slopes to vertical */
static bool drive_part(int id) {
  static const uint8_t L[] = {30, 31, 32, 50, 51, 66, 67, 79, 80, 81, 87, 88, 90, 98, 134, 135, 136, 137, 138, 139, 142,
                              143, 144, 156, 157, 158, 159, 160, 161, 162, 163, 166, 167};
  for (unsigned i = 0; i < sizeof L; i++)
    if (L[i] == id) return true;
  return false;
}

static void floor_tri(float *g, v3 a, v3 b, v3 c) {
  float l = pt_maxf(vlen(vsub(b, a)), pt_maxf(vlen(vsub(c, a)), vlen(vsub(c, b))));
  int n = (int)(l / (VOX * 0.5f)) + 1;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n - i; j++) {
      float u = (float)i / (float)n, v = (float)j / (float)n;
      v3 p = vadd(a, vadd(vmul(vsub(b, a), u), vmul(vsub(c, a), v)));
      int x, y, z;
      if (vox_of(p, &x, &y, &z) && p.y < g[vidx(x, y, z)]) g[vidx(x, y, z)] = p.y;
    }
}

static void build_field(void) {
  const pt_track *t = W.t;
  v3 lo = V3(1e9f, 1e9f, 1e9f), hi = V3(-1e9f, -1e9f, -1e9f);
  for (int i = 0; i < t->ninst; i++) {
    v3 a, b;
    world_box(world_inst(i), &a, &b);
    lo = V3(pt_minf(lo.x, a.x), pt_minf(lo.y, a.y), pt_minf(lo.z, a.z));
    hi = V3(pt_maxf(hi.x, b.x), pt_maxf(hi.y, b.y), pt_maxf(hi.z, b.z));
  }
  F.x0 = lo.x - 40.0f, F.y0 = -2.0f, F.z0 = lo.z - 40.0f;
  F.nx = (int)((hi.x - lo.x + 80.0f) / VOX) + 1;
  F.ny = (int)((hi.y + 30.0f) / VOX) + 1;
  F.nz = (int)((hi.z - lo.z + 80.0f) / VOX) + 1;
  size_t n = (size_t)F.nx * F.ny * F.nz;
  uint8_t *surf = calloc(n, 1);
  F.walk = calloc(n, 1);
  float *floor = malloc(n * sizeof(float));
  for (size_t i = 0; i < n; i++) floor[i] = 1e9f;
  v3 *walls = NULL;
  int nwall = 0, cap = 0;
  /* every physics triangle */
  for (int i = 0; i < t->ninst; i++) {
    const pt_inst *in = world_inst(i);
    const pt_part *p = &pt_parts[in->part];
    uint32_t mask = p->simple ? pt_masks[t->mask + in->mask] : 0xFFFFFFFFu;
    for (int k = 0; k < p->ncol; k++) {
      if (k < 32 && !(mask & (1u << k))) continue;
      const uint16_t *tr = &pt_ctri[(p->col + k) * 3];
      v3 v[3];
      for (int j = 0; j < 3; j++) {
        const int16_t *q = &pt_pool[(p->vbase + tr[j]) * 3];
        v[j] = world_apply(in, V3((float)q[0] / PT_FIX, (float)q[1] / PT_FIX, (float)q[2] / PT_FIX));
      }
      v3 nn = vnorm(vcross(vsub(v[1], v[0]), vsub(v[2], v[0])));
      /* (a part's floor is driven on however the part is turned: a road up a wall) */
      const int8_t *o = world_orient(in);
      float local_up = (float)o[1] * nn.x + (float)o[4] * nn.y + (float)o[7] * nn.z;
      bool dp = drive_part(pt_part_id[in->part]) || (in->orient >> 2 && local_up > 0.5f);
      /* flat floors (1), and what can be climbed: slopes, walls, loops (2) */
      if (nn.y > 0.5f || dp) {
        mark_tri(surf, v[0], v[1], v[2], nn, nn.y >= 0.96f && !dp ? 1 : 2);
        floor_tri(floor, v[0], v[1], v[2]);
      } else if (nn.y > -0.5f) {
        if (nwall + 3 > cap) cap = cap ? cap * 2 : 65536, walls = realloc(walls, sizeof(v3) * (size_t)cap);
        walls[nwall++] = v[0], walls[nwall++] = v[1], walls[nwall++] = v[2];
      }
    }
  }
  /* near a surface (and the ground everywhere) */
  for (int z = 0; z < F.nz; z++)
    for (int y = 0; y < F.ny; y++)
      for (int x = 0; x < F.nx; x++) {
        F.walk[vidx(x, y, z)] = (uint8_t)(surf[vidx(x, y, z)] + 1);   /* 1 air, 2 over a floor, 3 by a slope or a wall */
      }
  /* not inside blocks */
  for (int i = 0; i < t->ninst; i++) {
    const pt_inst *in = world_inst(i);
    int id = pt_part_id[in->part];
    if (id != 29 && id != 53 && id != 54) continue;   /* Block, HalfBlock, QuarterBlock */
    v3 a, b;
    world_box(in, &a, &b);
    for (float zz = a.z + 1.0f; zz < b.z - 0.5f; zz += VOX)
      for (float yy = a.y + 1.0f; yy < b.y - 0.5f; yy += VOX)
        for (float xx = a.x + 1.0f; xx < b.x - 0.5f; xx += VOX) {
          int x, y, z;
          if (vox_of(V3(xx, yy, zz), &x, &y, &z)) F.walk[vidx(x, y, z)] = 0;
        }
  }
  /* barriers: walls standing on a floor, where a car can't go; next to them a cube costs more */
  F.wall = calloc(n, 1);
  for (int w = 0; w < nwall; w += 3) {
    v3 a = walls[w], b = walls[w + 1], c = walls[w + 2];
    float l = pt_maxf(vlen(vsub(b, a)), pt_maxf(vlen(vsub(c, a)), vlen(vsub(c, b))));
    int m = (int)(l / (VOX * 0.25f)) + 1;
    for (int i = 0; i <= m; i++)
      for (int j = 0; j <= m - i; j++) {
        float u = (float)i / (float)m, v = (float)j / (float)m;
        v3 p = vadd(a, vadd(vmul(vsub(b, a), u), vmul(vsub(c, a), v)));
        int x, y, z;
        if (!vox_of(p, &x, &y, &z)) continue;
        int k = vidx(x, y, z);
        bool on = floor[k] < p.y - 0.25f || (y > 0 && floor[vidx(x, y - 1, z)] < p.y - 0.25f);
        if (!on && p.y > 0.25f && p.y < VOX) on = true;     /* (the ground) */
        if (on) F.wall[k] = 1;
      }
  }
  for (size_t i = 0; i < n; i++)
    if (F.wall[i] == 1) F.walk[i] = 0;
  /* edges: next to a barrier or a drop (2), and one further in (3); the way keeps off them */
  for (size_t i = 0; i < n; i++) F.wall[i] = F.wall[i] == 1;
  for (int pass = 2; pass <= 3; pass++)
    for (int z = 1; z < F.nz - 1; z++)
      for (int y = 0; y < F.ny; y++)
        for (int x = 1; x < F.nx - 1; x++) {
          int i = vidx(x, y, z);
          if (F.walk[i] < 2 || F.wall[i]) continue;
          int nb[4] = {i - 1, i + 1, vidx(x, y, z - 1), vidx(x, y, z + 1)};
          for (int k = 0; k < 4; k++) {
            int j = nb[k];
            bool edge = pass == 2 ? F.walk[j] < 2 : F.wall[j] == 2;
            if (edge) F.wall[i] = (uint8_t)pass;
          }
        }
  /* surfaces between neighbours (so the way doesn't pass through a thin wall or floor) */
  F.cut = calloc(n, 1);
  static wtri near[PT_CACHE * 8];
  for (int z = 0; z < F.nz - 1; z++)
    for (int y = 0; y < F.ny - 1; y++)
      for (int x = 0; x < F.nx - 1; x++) {
        int i = vidx(x, y, z);
        int nb[3] = {i + 1, vidx(x, y + 1, z), vidx(x, y, z + 1)};
        bool any = false;
        for (int k = 0; k < 3; k++) any |= F.walk[i] >= 2 || F.walk[nb[k]] >= 2;
        if (!any || !F.walk[i]) continue;
        v3 a = V3(F.x0 + ((float)x + 0.5f) * VOX, F.y0 + ((float)y + 0.5f) * VOX, F.z0 + ((float)z + 0.5f) * VOX);
        int m = world_gather(vsub(a, V3(0.1f, 0.1f, 0.1f)), vadd(a, V3(VOX + 0.1f, VOX + 0.1f, VOX + 0.1f)), near,
                             PT_CACHE * 8);
        for (int k = 0; k < 3; k++) {
          if (!F.walk[nb[k]] || (F.walk[i] < 2 && F.walk[nb[k]] < 2)) continue;
          v3 b = vadd(a, V3(k == 0 ? VOX : 0.0f, k == 1 ? VOX : 0.0f, k == 2 ? VOX : 0.0f));
          for (int q = 0; q < m; q++) {
            const wtri *w = &near[q];
            float da = vdot(w->n, a) - w->d, db = vdot(w->n, b) - w->d;
            if ((da > 0.0f) == (db > 0.0f)) continue;
            float u = da / (da - db);
            v3 p = vadd(a, vmul(vsub(b, a), u));
            if (vdot(vcross(vsub(w->b, w->a), vsub(p, w->a)), w->n) < 0.0f) continue;
            if (vdot(vcross(vsub(w->c, w->b), vsub(p, w->b)), w->n) < 0.0f) continue;
            if (vdot(vcross(vsub(w->a, w->c), vsub(p, w->c)), w->n) < 0.0f) continue;
            F.cut[i] |= (uint8_t)(1 << k);
            break;
          }
        }
      }
  free(walls);
  free(floor);
  free(surf);
}

/* Dijkstra with a bucket queue: near a drivable surface a cube costs 2; in the air 6 across, 3 down and 24 up
   (a jump goes across or down, not up) */
#define NB 32
static int vcost = 1;      /* up or down a slope or a wall (VC=) */
static int air_up = 0;     /* up through the air (AU=; 0: never) */
static int height_buckets; /* HB= */
static double speed_w = 0.5; /* SPEEDW=: what a faster class is worth, in metres of the way */
static double energy_w;     /* ENERGY=: archive by energy instead, each 150 J/kg worth this many metres */
static int *bucket[NB], bcount[NB], bcap[NB];
static void push(int b, int i) {
  if (bcount[b] == bcap[b]) bcap[b] = bcap[b] ? bcap[b] * 2 : 4096, bucket[b] = realloc(bucket[b], sizeof(int) * (size_t)bcap[b]);
  bucket[b][bcount[b]++] = i;
}
static void bfs(uint16_t *d, v3 lo, v3 hi) {
  size_t n = (size_t)F.nx * F.ny * F.nz;
  for (size_t i = 0; i < n; i++) d[i] = INF;
  for (int b = 0; b < NB; b++) bcount[b] = 0;
  for (float zz = lo.z; zz <= hi.z + 0.01f; zz += 1.0f)
    for (float yy = lo.y; yy <= hi.y + 0.01f; yy += 1.0f)
      for (float xx = lo.x; xx <= hi.x + 0.01f; xx += 1.0f) {
        int x, y, z;
        if (!vox_of(V3(xx, yy, zz), &x, &y, &z)) continue;
        int i = vidx(x, y, z);
        if (d[i] == INF) d[i] = 0, push(0, i);
      }
  /* (walked backwards from the target: a step from j to i costs what going from i to j would) */
  for (uint32_t cur = 0, left = 1; left && cur < 60000; cur++) {
    int b = (int)(cur % NB);
    left = 0;
    for (int k = 0; k < NB; k++) left += (uint32_t)bcount[k];
    while (bcount[b]) {
      int i = bucket[b][--bcount[b]];
      if (d[i] != cur) continue;
      int x = i % F.nx, y = (i / F.nx) % F.ny, z = i / (F.nx * F.ny);
      static const int D[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
      for (int k = 0; k < 6; k++) {
        int a = x + D[k][0], bb = y + D[k][1], c = z + D[k][2];
        if (a < 0 || bb < 0 || c < 0 || a >= F.nx || bb >= F.ny || c >= F.nz) continue;
        int j = vidx(a, bb, c);
        int w = F.walk[j];
        if (!w) continue;
        /* (through a surface: no) */
        int lo = j < i ? j : i, axis = k / 2;
        if (F.cut[lo] & (1 << axis)) continue;
        /* the car would go from j to i: up when i is above j */
        int cost;
        int wi = F.walk[i];
        if (D[k][1] == -1) {
          /* i above j: up only along a slope or a wall */
          if (wi != 3 && w != 3) {
            /* (up through the air: off a ramp, say, dearly) */
            if (!air_up) continue;
            cost = air_up;
          } else cost = wi == 3 && w == 3 ? vcost : 2;
        } else if (D[k][1] == 1 && wi == 3 && w == 3) cost = vcost;
        else if (w >= 2 && wi >= 2) cost = 2;
        else if (D[k][1] == 1) cost = 3;        /* down */
        else cost = 6;
        if (F.wall[j] == 2) cost += 4;
        else if (F.wall[j] == 3) cost += 2;
        uint32_t nd = cur + (uint32_t)cost;
        if (nd < d[j]) d[j] = (uint16_t)nd, push((int)(nd % NB), j);
      }
    }
  }
}

/* a place the run must go through between two checkpoints, where the map's way can't be driven (a jump it takes
   too straight, say): VIA="k x y z r", after k checkpoints; then g_via says whether the car has been there */
static int via_k = -1, via_t;
static v3 via_p;
static float via_r;
static int g_via;
static int target_of(const car_t *c) {
  if (c->next_cp == via_k && !g_via) return via_t;
  return c->next_cp < F.ntarget ? c->next_cp : F.ntarget - 1;
}
static int stage_of(const car_t *c) { return c->next_cp * 2 + (via_k < 0 || c->next_cp != via_k || g_via); }
static void via_check(const car_t *c) {
  if (c->next_cp == via_k && !g_via && vlen2(vsub(c->pos, via_p)) < via_r * via_r) g_via = 1;
}

static void build_targets(void) {
  const pt_track *t = W.t;
  size_t n = (size_t)F.nx * F.ny * F.nz;
  int no = car_checkpoints();
  F.ntarget = no + 1;
  /* the checkpoint detectors, by order */
  detector_t d;
  int k = 0;
  uint16_t last = 0xFFFF;
  int target = -1;
  for (int i = 0; i < t->ncp; i++) {
    world_detector(i, &d);
    if (d.order != last) target++, last = d.order, F.dist[target] = malloc(n * 2), k = 0;
    /* (alternatives share a map: the nearest box) */
    if (k == 0) bfs(F.dist[target], d.lo, d.hi);
    else {
      uint16_t *tmp = malloc(n * 2);
      bfs(tmp, d.lo, d.hi);
      for (size_t j = 0; j < n; j++)
        if (tmp[j] < F.dist[target][j]) F.dist[target][j] = tmp[j];
      free(tmp);
    }
    k++;
  }
  if (getenv("VIA")) {
    sscanf(getenv("VIA"), "%d %f %f %f %f", &via_k, &via_p.x, &via_p.y, &via_p.z, &via_r);
    via_t = no + 1;
    F.dist[via_t] = malloc(n * 2);
    v3 h = V3(via_r * 0.7f, via_r * 0.7f, via_r * 0.7f);
    bfs(F.dist[via_t], vsub(via_p, h), vadd(via_p, h));
  }
  F.dist[no] = malloc(n * 2);
  for (int i = 0; i < t->nfin; i++) {
    world_detector(t->ncp + i, &d);
    if (i == 0) bfs(F.dist[no], d.lo, d.hi);
    else {
      uint16_t *tmp = malloc(n * 2);
      bfs(tmp, d.lo, d.hi);
      for (size_t j = 0; j < n; j++)
        if (tmp[j] < F.dist[no][j]) F.dist[no][j] = tmp[j];
      free(tmp);
    }
  }
}

static void free_field(void) {
  free(F.walk);
  free(F.cut);
  free(F.wall);
  for (int i = 0; i < F.ntarget; i++) free(F.dist[i]);
  if (via_k >= 0) free(F.dist[via_t]), via_k = -1;
}

/* the car's cube on the map: a metre up from it (its own up), else two, else just above it; -1 when off the map */
static int car_vox(const car_t *c, int k) {
  static const float UP[3] = {1.0f, 2.0f, 0.4f};
  v3 up = mcolumn(&c->basis, 1);
  for (int i = 0; i < 3; i++) {
    int x, y, z;
    if (!vox_of(vadd(c->pos, vmul(up, UP[i])), &x, &y, &z)) continue;
    int v = vidx(x, y, z);
    if (F.dist[k][v] != INF) return v;
  }
  return -1;
}

/* how far the car is from its next target (in map units, about metres; 1e5 when lost) */
static float dist_of(const car_t *c) {
  if (c->next_cp >= F.ntarget) return 0.0f;
  int k = target_of(c);
  int v = car_vox(c, k);
  return v < 0 ? 1e5f : (float)F.dist[k][v];
}

/* ------------------------------------------------------------------ a driver that follows the map */
/* the place L cubes further down the map from the car (towards target k) */
static v3 ahead(int k, const car_t *c, int L) {
  int v = car_vox(c, k);
  if (v < 0) return c->pos;
  int x = v % F.nx, y = (v / F.nx) % F.ny, z = v / (F.nx * F.ny);
  uint16_t best = F.dist[k][v];
  for (int s = 0; s < L && best > 0; s++) {
    int nx = x, ny = y, nz = z;
    for (int dz = -1; dz <= 1; dz++)
      for (int dy = -1; dy <= 1; dy++)
        for (int dx = -1; dx <= 1; dx++) {
          int a = x + dx, b = y + dy, cc = z + dz;
          if (a < 0 || b < 0 || cc < 0 || a >= F.nx || b >= F.ny || cc >= F.nz) continue;
          uint16_t d = F.dist[k][vidx(a, b, cc)];
          if (d < best) best = d, nx = a, ny = b, nz = cc;
        }
    if (nx == x && ny == y && nz == z) break;
    x = nx, y = ny, z = nz;
  }
  return V3(F.x0 + ((float)x + 0.5f) * VOX, F.y0 + ((float)y + 0.5f) * VOX, F.z0 + ((float)z + 0.5f) * VOX);
}

/* the keys for the next 10 ms: steer towards the place L cubes ahead, gas up to vmax km/h */
static unsigned pilot(const car_t *c, int L, float vmax) {
  int k = target_of(c);
  v3 d = mcol(&c->basis, vsub(ahead(k, c, L), c->pos));
  float ang = pt_atan2f(d.x, d.z);
  float want = pt_clampf(ang * 2.5f, -1.0f, 1.0f);
  unsigned keys = 0;
  if (want > c->steer_in + 0.05f) keys |= IN_LEFT;
  else if (want < c->steer_in - 0.05f) keys |= IN_RIGHT;
  else if (want > 0.3f) keys |= IN_LEFT;
  else if (want < -0.3f) keys |= IN_RIGHT;
  if (c->speed < vmax) keys |= IN_UP;
  else if (c->speed > vmax + 20.0f) keys |= IN_DOWN;
  return keys;
}

/* ------------------------------------------------------------------ the search */
#define SLOT 10                     /* ms a key is held, at least */
#define STEP 10                     /* slots a try lasts */
#define MAXN 16000000
typedef struct {
  int32_t parent;
  uint8_t keys[STEP];
} node_t;
static node_t *nodes;
static int nnodes;
typedef struct {
  car_t car;
  int32_t node;
} beam_t;
static beam_t beam[1];

/* the tries: the driver looking near, far or between, at full speed or slower; and keys held */
typedef struct { int L; float vmax; uint8_t keys; } action_t;
static const action_t ACTIONS[] = {
  {4, 999.0f, 0}, {7, 999.0f, 0}, {11, 999.0f, 0}, {16, 999.0f, 0}, {22, 999.0f, 0}, {8, 60.0f, 0}, {10, 110.0f, 0},
  {0, 0.0f, IN_UP}, {0, 0.0f, IN_UP | IN_LEFT}, {0, 0.0f, IN_UP | IN_RIGHT}, {0, 0.0f, 0}, {0, 0.0f, IN_DOWN},
  {0, 0.0f, IN_DOWN | IN_LEFT}, {0, 0.0f, IN_DOWN | IN_RIGHT},
};
#define NACT ((int)(sizeof ACTIONS / sizeof ACTIONS[0]))

/* a try: STEP slots; writes the keys used */
static void act(car_t *c, const action_t *a, uint8_t *keys) {
  for (int s = 0; s < STEP; s++) {
    unsigned k = a->L ? pilot(c, a->L, a->vmax) : a->keys;
    /* (the game's clock starts with the first driving key: a run starts with one) */
    if (!c->frames && !(k & (IN_UP | IN_DOWN | IN_LEFT | IN_RIGHT))) k |= IN_UP;
    if (keys) keys[s] = (uint8_t)k;
    for (int i = 0; i < SLOT && !c->finish; i++) car_step(c, k);
    via_check(c);
  }
}

/* the archive */
#define MAXC 60000
#define TEMP 25.0
static double wcum[MAXC];
#define HASH 131072
static int32_t slot[HASH];          /* cell + 1 by key */
static int wn;
static double pt_expd(double x) {
  /* e^x for x <= 0, near enough */
  double r = 1.0 + x / 1024.0;
  for (int i = 0; i < 10; i++) r *= r;
  return r;
}
static double sqrt_d(double x) {
  double r = x > 1.0 ? x : 1.0;
  for (int i = 0; i < 30; i++) r = 0.5 * (r + x / r);
  return r;
}
typedef struct {
  car_t car;
  int32_t node;
  int32_t tries;
  uint32_t key;
  uint32_t frames;
  uint8_t via;
} cell_t;
/* a stretch: the next checkpoint, the distance left in 4 m steps, whether the car goes the way the map says
   (back, across, on) and how fast (under 20, 80, 140, 200, 260, 320 km/h, or over) */
static uint32_t cell_key(const car_t *c) {
  int k = target_of(c);
  if (energy_w > 0.0) {
    /* (ENERGY=w: the stretch in 8 m steps and the car's energy, speed and height, in steps of 150 J/kg: for a
       jump that wants all the speed there is) */
    int d8 = (int)(dist_of(c) / 8.0f);
    float e = 0.5f * vlen2(c->vel) + 9.82f * c->pos.y;
    int eb = (int)pt_clampf(e / 150.0f, 0.0f, 1023.0f);
    return (uint32_t)stage_of(c) << 24 | (uint32_t)(d8 < 16383 ? d8 : 16383) << 10 | (uint32_t)eb;
  }
  int d = (int)(dist_of(c) / 4.0f);
  float v = pt_absf(c->speed);
  int sb = v < 20.0f ? 0 : v < 80.0f ? 1 : v < 140.0f ? 2 : v < 200.0f ? 3 : v < 260.0f ? 4 : v < 320.0f ? 5 : 6, ab = 1;
  if (v >= 20.0f) {
    v3 to = vsub(ahead(k, c, 6), c->pos);
    float l = vlen(to) * vlen(c->vel);
    float cs = l > 0.0f ? vdot(to, c->vel) / l : 0.0f;
    ab = cs < -0.3f ? 0 : cs < 0.5f ? 1 : 2;
  }
  /* (HB=1: and how high, in 20 m steps: a car up a wall has more to give than one at its foot) */
  uint32_t hb = height_buckets ? (uint32_t)pt_clampf(c->pos.y / 20.0f, 0.0f, 3.0f) : 0u;
  return (uint32_t)stage_of(c) << 24 | (uint32_t)(d < 65535 ? d : 65535) << 8 | hb << 6 | (uint32_t)ab << 4 | (uint32_t)sb;
}
static double progress(const cell_t *e) {
  if (energy_w > 0.0)
    return (double)(e->key >> 24) * 1e6 - (double)((e->key >> 10) & 0x3FFF) * 8.0 + (double)(e->key & 1023) * energy_w;
  return (double)(e->key >> 24) * 1e6 - (double)((e->key >> 8) & 0xFFFF) * 4.0 + (double)((e->key >> 4) & 3) +
         (double)(e->key & 7) * speed_w;
}
static uint32_t lcg(uint32_t *s) { return *s = *s * 1103515245u + 12345u, *s >> 8; }

static bool route(int t, FILE *out) {
  world_load(t);
  static car_t start;
  car_reset(&start);
  build_field();
  build_targets();
  if (getenv("TRACE")) {
    /* the way down the map from a point: TRACE="target x y z" */
    int k;
    float px, py, pz;
    sscanf(getenv("TRACE"), "%d %f %f %f", &k, &px, &py, &pz);
    int x, y, z;
    vox_of(V3(px, py, pz), &x, &y, &z);
    for (int step = 0; step < 400; step++) {
      int i = vidx(x, y, z);
      uint16_t best = F.dist[k][i];
      int bx = x, by = y, bz = z;
      for (int dz = -1; dz <= 1; dz++)
        for (int dy = -1; dy <= 1; dy++)
          for (int dx = -1; dx <= 1; dx++) {
            int a = x + dx, b = y + dy, c = z + dz;
            if (a < 0 || b < 0 || c < 0 || a >= F.nx || b >= F.ny || c >= F.nz) continue;
            uint16_t v = F.dist[k][vidx(a, b, c)];
            if (v < best) best = v, bx = a, by = b, bz = c;
          }
      if (step % 5 == 0 || best == 0)
        fprintf(stderr, "  %3d: %.0f %.0f %.0f dist %u walk %d\n", step, (double)(F.x0 + x * VOX), (double)(F.y0 + y * VOX),
                (double)(F.z0 + z * VOX), F.dist[k][i], F.walk[i]);
      if (best == 0 || (bx == x && by == y && bz == z)) break;
      x = bx, y = by, z = bz;
    }
    return false;
  }
  if (getenv("FIELD_DUMP")) {
    int k = atoi(getenv("FIELD_DUMP"));
    FILE *f = fopen("field.ppm", "wb");
    fprintf(f, "P6 %d %d 255\n", F.nx, F.nz);
    for (int z = 0; z < F.nz; z++)
      for (int x = 0; x < F.nx; x++) {
        uint16_t m = INF;
        int wy = 0;
        for (int y = 0; y < F.ny; y++) {
          uint16_t v = F.dist[k][vidx(x, y, z)];
          if (v < m) m = v, wy = y;
        }
        int walkable = 0;
        for (int y = 0; y < F.ny; y++) walkable |= F.walk[vidx(x, y, z)] == 2 && F.y0 + y * VOX > 4.0f;
        int c = m == INF ? 0 : 255 - (m / 8) % 200;
        fputc(m == INF ? 80 : c, f), fputc(m == INF ? 0 : (walkable ? 255 : c / 2), f), fputc(m == INF ? 0 : wy * 4 % 256, f);
      }
    fclose(f);
    fprintf(stderr, "field %d: origin %.0f %.0f size %d x %d\n", k, (double)F.x0, (double)F.z0, F.nx, F.nz);
    return false;
  }
  if (getenv("PILOT")) {
    /* the driver alone: PILOT="L vmax" */
    int L = 12;
    float vmax = 999.0f;
    sscanf(getenv("PILOT"), "%d %f", &L, &vmax);
    static car_t c;
    c = start;
    int until = getenv("UNTIL") ? atoi(getenv("UNTIL")) : 120000;
    for (int f = 0; f < until && !c.finish; f += SLOT) {
      unsigned k = pilot(&c, L, vmax);
      for (int i = 0; i < SLOT; i++) car_step(&c, k);
      if (getenv("PV2") && f >= atoi(getenv("PV2")) && f < atoi(getenv("PV2")) + 500)
        fprintf(stderr, "    f %d pos %.2f %.2f %.2f vel %.1f %.1f %.1f cache %d imp %.0f wheels %d%d%d%d up %.2f %.2f %.2f\n", f,
                (double)c.pos.x, (double)c.pos.y, (double)c.pos.z, (double)c.vel.x, (double)c.vel.y, (double)c.vel.z, c.ncache,
                (double)c.impulse, c.w[0].contact, c.w[1].contact, c.w[2].contact, c.w[3].contact, (double)c.basis.r[0].y,
                (double)c.basis.r[1].y, (double)c.basis.r[2].y);
      if (getenv("PV") && f < atoi(getenv("PV")) && f % 50 == 0) {
        v3 tg = ahead(c.next_cp, &c, L);
        v3 d = mcol(&c.basis, vsub(tg, c.pos));
        v3 fw = mcolumn(&c.basis, 2);
        fprintf(stderr, "    f %d pos %.1f %.1f fwd %.2f %.2f tgt %.1f %.1f local %.1f %.1f keys %u steer %.2f spd %.0f\n", f,
                (double)c.pos.x, (double)c.pos.z, (double)fw.x, (double)fw.z, (double)tg.x, (double)tg.z, (double)d.x,
                (double)d.z, k, (double)c.steer_in, (double)c.speed);
      }
      if (f % 1000 == 0)
        fprintf(stderr, "  %3d s: %7.1f %5.1f %7.1f cp %d dist %.0f speed %.0f\n", f / 1000, (double)c.pos.x, (double)c.pos.y,
                (double)c.pos.z, c.next_cp, (double)dist_of(&c), (double)c.speed);
    }
    fprintf(stderr, "  finish %u; up %.2f %.2f %.2f fwd %.2f %.2f %.2f wheels %d%d%d%d\n", c.finish, (double)c.basis.r[0].y,
            (double)c.basis.r[1].y, (double)c.basis.r[2].y, (double)c.basis.r[0].z, (double)c.basis.r[1].z,
            (double)c.basis.r[2].z, c.w[0].contact, c.w[1].contact, c.w[2].contact, c.w[3].contact);
    free_field();
    return c.finish != 0;
  }
  /* Go-Explore: an archive of cars, one per stretch of the way (the next checkpoint, the distance left in 4 m
     steps), the quickest there kept; again and again a car is taken from near the front, the less tried first, and
     driven on a while with the driver or keys held; new stretches go in the archive */
  nodes = malloc(sizeof(node_t) * MAXN);
  nnodes = 1;
  nodes[0].parent = -1;
  int ncell = 0;
  static cell_t cells[MAXC];
  memset(slot, 0, sizeof slot);
  g_via = 0;
  cells[ncell++] = (cell_t){start, 0, 0, cell_key(&start), 0, 0};
  {
    uint32_t h = (cells[0].key * 2654435761u) & (HASH - 1);
    slot[h] = 1;
  }
  int found = -1, best = 0;
  if (getenv("PREFIX")) {
    /* (going on from a run found before: its cars, every 100 ms, in the archive) */
    static char buf[400000];
    static uint8_t pk[60000];
    FILE *f = fopen(getenv("PREFIX"), "r");
    int n = 0, ch, in = 0;
    while (f && (ch = fgetc(f)) != EOF && n < (int)sizeof buf - 1) {
      if (ch == '"') in = !in;
      else if (in) buf[n++] = (char)ch;
    }
    buf[n] = 0;
    if (f) fclose(f);
    int ns = 0;
    for (const char *q = buf; *q && ns < (int)sizeof pk;) {
      char c0 = *q++;
      if (c0 < 'a' || c0 > 'p') continue;
      int r = 0;
      while (*q >= '0' && *q <= '9') r = r * 10 + (*q++ - '0');
      for (r = r ? r : 1; r-- && ns < (int)sizeof pk;) pk[ns++] = (uint8_t)(c0 - 'a');
    }
    static car_t c;
    if (getenv("LANE")) {
      /* (LANE="k x0 x1 z y": a run-up held on a lane northwards, flat out, from the best of the prefix's moments
         after k checkpoints: the one that reaches z the highest above y; for Desert 3's jump) */
      int lk;
      float x0, x1, zs, ys;
      sscanf(getenv("LANE"), "%d %f %f %f %f", &lk, &x0, &x1, &zs, &ys);
      static car_t s;
      static uint8_t lkeys[2000], bkeys[2000];
      int bi = -1, bn = 0;
      float bh = -1e9f;
      c = start;
      for (int i = 0; i < ns && !c.finish; i++) {
        for (int f2 = 0; f2 < SLOT; f2++) car_step(&c, pk[i]);
        if (c.next_cp < lk || i % 5) continue;
        for (float X = x0; X <= x1; X += 2.0f) {
          s = c;
          car_cache_rebuild(&s);
          int m = 0;
          float h = -1e9f;
          while (m < 2000 && !s.finish && s.pos.y > -3.0f) {
            /* heading north (-z), drifting onto x = X */
            v3 fw = mcolumn(&s.basis, 2);
            float want = pt_clampf(0.04f * (X - s.pos.x), -0.3f, 0.3f), err = fw.x - want;
            unsigned k = IN_UP | (err > 0.02f ? IN_LEFT : err < -0.02f ? IN_RIGHT : 0u);
            lkeys[m++] = (uint8_t)k;
            for (int f2 = 0; f2 < SLOT; f2++) car_step(&s, k);
            if (s.pos.z < zs) {
              h = s.pos.y;
              break;
            }
          }
          if (h > bh) bh = h, bi = i, bn = m, memcpy(bkeys, lkeys, (size_t)m);
        }
      }
      fprintf(stderr, "  lane: from %d ms, %.1f m up at the end\n", (bi + 1) * SLOT, (double)bh);
      if (bi >= 0 && bh > ys) {
        memcpy(&pk[bi + 1], bkeys, (size_t)bn);
        ns = bi + 1 + bn;
      }
    }
    c = start;
    int node = 0;
    g_via = 0;
    for (int i = 0; i + STEP <= ns && !c.finish; i += STEP) {
      nodes[nnodes].parent = node;
      memcpy(nodes[nnodes].keys, &pk[i], STEP);
      for (int s2 = 0; s2 < STEP; s2++) {
        for (int f2 = 0; f2 < SLOT && !c.finish; f2++) car_step(&c, pk[i + s2]);
        via_check(&c);
      }
      node = nnodes++;
      if (dist_of(&c) >= 1e5f) continue;
      uint32_t key = cell_key(&c);
      uint32_t h = (key * 2654435761u) & (HASH - 1);
      while (slot[h] && cells[slot[h] - 1].key != key) h = (h + 1) & (HASH - 1);
      int k = slot[h] ? slot[h] - 1 : -1;
      if (k < 0 && ncell < MAXC) k = ncell++, cells[k].tries = 0, cells[k].key = key, cells[k].frames = 0xFFFFFFFFu, slot[h] = k + 1;
      if (k >= 0 && c.frames < cells[k].frames) {
        cells[k].car = c, cells[k].node = node, cells[k].frames = c.frames, cells[k].via = (uint8_t)g_via;
        if (progress(&cells[k]) > progress(&cells[best])) best = k;
      }
    }
    fprintf(stderr, "  prefix: %d ms, %d stretches, cp %d dist %.0f\n", ns * SLOT, ncell, c.next_cp, (double)dist_of(&c));
  }
  uint32_t seed = 12345u + (uint32_t)t * 7919u + (getenv("SEED") ? (uint32_t)atoi(getenv("SEED")) * 104729u : 0u);
  int tries = getenv("TRIES") ? atoi(getenv("TRIES")) : 200000;
  for (int it = 0; it < tries && found < 0 && nnodes + 64 < MAXN; it++) {
    /* the car to go on from: weighted by how far on it is (a factor e for each TEMP metres) over the root of how
       often it was tried, so that when the front gets nowhere the cars behind it get their turn */
    if (it % 64 == 0) {
      double top = -1e30;
      for (int i = 0; i < ncell; i++)
        if (progress(&cells[i]) > top) top = progress(&cells[i]);
      double acc = 0.0;
      for (int i = 0; i < ncell; i++) {
        double x = (progress(&cells[i]) - top) / TEMP;
        acc += x < -30.0 ? 0.0 : pt_expd(x) / sqrt_d(1.0 + cells[i].tries);
        wcum[i] = acc;
      }
      wn = ncell;
    }
    double r = (double)(lcg(&seed) % 1000000u) / 1000000.0 * wcum[wn - 1];
    int lo = 0, hi = wn - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (wcum[mid] < r) lo = mid + 1;
      else hi = mid;
    }
    int pick = lo;
    cells[pick].tries++;
    static car_t c;
    c = cells[pick].car;
    g_via = cells[pick].via;
    car_cache_rebuild(&c);
    int node = cells[pick].node;
    int steps = 5 + (int)(lcg(&seed) % 26u), a = (int)(lcg(&seed) % (uint32_t)NACT), lost = 0;
    for (int s = 0; s < steps && !c.finish; s++) {
      if (lcg(&seed) % 10 >= 6) {
        /* (the driver more often than held keys) */
        a = (int)(lcg(&seed) % (uint32_t)(NACT + 7));
        if (a >= NACT) a = a - NACT;
      }
      nodes[nnodes].parent = node;
      act(&c, &ACTIONS[a], nodes[nnodes].keys);
      node = nnodes++;
      if (c.finish) {
        found = node;
        cells[0].car = c, cells[0].node = node;
        best = 0;
        break;
      }
      float d = dist_of(&c);
      if (c.pos.y < -3.0f) break;
      if (d >= 1e5f) {
        /* (off the map, high in the air say: on, but not kept) */
        if (++lost > 30) break;
        continue;
      }
      lost = 0;
      uint32_t key = cell_key(&c);
      uint32_t h = (key * 2654435761u) & (HASH - 1);
      while (slot[h] && cells[slot[h] - 1].key != key) h = (h + 1) & (HASH - 1);
      int k = slot[h] ? slot[h] - 1 : -1;
      if (k < 0 && ncell < MAXC) {
        k = ncell++, cells[k].tries = 0, cells[k].key = key, cells[k].frames = 0xFFFFFFFFu;
        slot[h] = k + 1;
      }
      if (k >= 0 && c.frames < cells[k].frames) {
        cells[k].car = c, cells[k].node = node, cells[k].frames = c.frames, cells[k].via = (uint8_t)g_via;
        if (progress(&cells[k]) > progress(&cells[best])) best = k;
      }
    }
    if (it % 10000 == 0)
      fprintf(stderr, "  %s try %5d: %d stretches, furthest cp %d/%d dist %.0f at %.1f s\n", pt_tracks[t].name, it, ncell,
              cells[best].car.next_cp, F.ntarget - 1, (double)dist_of(&cells[best].car),
              (double)cells[best].car.frames / 1000.0);
  }
  beam[0].car = found >= 0 ? cells[0].car : cells[best].car;
  beam[0].node = found >= 0 ? found : cells[best].node;
  bool ok = found >= 0;
  if (ok || getenv("PARTIAL")) {
    /* the keys, from the start, a letter per slot */
    int n = 0;
    for (int i = beam[0].node; i > 0; i = nodes[i].parent) n++;
    int ns = n * STEP;
    uint8_t *k = malloc((size_t)ns);
    int j = n;
    for (int i = beam[0].node; i > 0; i = nodes[i].parent) memcpy(&k[--j * STEP], nodes[i].keys, STEP);
    /* (the same keys from the start must come to the same car) */
    static car_t chk;
    chk = start;
    chk.cache_ok = 0;
    for (int i = 0; i < ns && !chk.finish; i++)
      for (int f = 0; f < SLOT && !chk.finish; f++) car_step(&chk, k[i]);
    fprintf(stderr, "  replay: %08x %.3f %.3f %.3f, search: %08x %.3f %.3f %.3f\n", car_hash(&chk), (double)chk.pos.x,
            (double)chk.pos.y, (double)chk.pos.z, car_hash(&beam[0].car), (double)beam[0].car.pos.x,
            (double)beam[0].car.pos.y, (double)beam[0].car.pos.z);
    /* (to the finish only) */
    if (ok) ns = (int)((beam[0].car.finish + SLOT - 1) / SLOT);
    fprintf(out, "  /* %s: %u ms%s */\n  \"", pt_tracks[t].name, beam[0].car.finish, ok ? "" : " (not finished)");
    int col = 3;
    for (int i = 0; i < ns;) {
      int r = 1;
      while (i + r < ns && k[i + r] == k[i]) r++;
      char buf[16];
      int len = r > 1 ? snprintf(buf, sizeof buf, "%c%d", (k[i] & IN_RESET ? 'A' : 'a') + (k[i] & 15), r)
                      : snprintf(buf, sizeof buf, "%c", (k[i] & IN_RESET ? 'A' : 'a') + (k[i] & 15));
      if (col + len > 116) fprintf(out, "\"\n  \""), col = 3;
      fputs(buf, out), col += len;
      i += r;
    }
    fprintf(out, "\",\n");
    fflush(out);
    free(k);
  }
  free(nodes);
  free_field();
  return ok;
}

int main(int argc, char **argv) {
  if (getenv("VC")) vcost = atoi(getenv("VC"));
  if (getenv("AU")) air_up = atoi(getenv("AU"));
  if (getenv("HB")) height_buckets = atoi(getenv("HB"));
  if (getenv("SPEEDW")) speed_w = atof(getenv("SPEEDW"));
  if (getenv("ENERGY")) energy_w = atof(getenv("ENERGY"));
  int list[PT_NTRACKS], n = 0;
  for (int i = 1; i < argc; i++) list[n++] = atoi(argv[i]);
  if (!n)
    for (int i = 0; i < PT_NTRACKS; i++) list[n++] = i;
  for (int i = 0; i < n; i++) {
    bool ok = route(list[i], stdout);
    fprintf(stderr, "%s: %s\n", pt_tracks[list[i]].name, ok ? "finished" : "NOT FOUND");
  }
  return 0;
}