axe knight battle finder

// tabulates manipulated axe knight battles in dragon warrior
// assumes hero attacks are weak, axe knight attacks are strong. doesn't try to
// cast sleep or anything fancy, just attacks.
#include <limits.h>
#include <stdio.h>
#include <stdbool.h>

// the maximum number of turns to which an axe knight battle may be routed,
// including both enemy and hero turns.
#define MAX_TURNS 10

// the maximum number of buffers in any turn.
#define MAX_BUFFERS 100

// how many ticks buffering A or B in the menu advances the rng.
#define MENU_TICKS 11

// cost model for search
#define TURN_COST 2
#define BUF_COST 1

// axe knight stats
#define AXE_KNIGHT_MAX_HP 70
#define AXE_KNIGHT_STRENGTH 94
#define AXE_KNIGHT_AGILITY 82
#define AXE_KNIGHT_DODGE 1

// shift and mask the most significant byte of a 16-bit value.
#define MSB(x) ((x >> 8) & 0xff)

// mask the least significant byte of a 16-bit value.
#define LSB(x) (x & 0xff)

// who has done some action.
typedef enum { NOBODY, HERO, ENEMY } who;

// things that can happen.
// values > 0 mean "buffer N times before attacking".
typedef enum {
  SKIP = -3,
  SLEEP = -2,
  ATTACK = -1,
  NOTHING = 0
} action;

// an rng state.
typedef struct {
  int s;
} rng;

// a synposis of all the stuff that happened in a battle.
typedef struct {
  int seed;
  int starting_hp;
  who first_strike;
  action turn_action[MAX_TURNS];
  int turn_damage[MAX_TURNS];
  int len;
  int cost;
} battle;

// hero stuff.
typedef struct {
  int hp;
  int mp;
  int strength;
  int agility;
  int attack;
  int defense;
  bool has_sleep;
} hero_stats;

static hero_stats L6_no_dscale = {
  .hp = 34,  // 38 - two swamp tiles
  .mp = 24,
  .strength = 16,
  .agility = 12,
  .attack = 36,
  .defense = 16,
  .has_sleep = false
};

static hero_stats L6_with_dscale = {
  .hp = 34,  // 38 - two swamp tiles
  .mp = 24,
  .strength = 16,
  .agility = 12,
  .attack = 36,
  .defense = 18,
  .has_sleep = false
};

// a current state during the battle search.
typedef struct {
  who turn;
  int enemy_hp;
  bool enemy_awake;
  int hero_hp;
  bool hero_awake;
  bool hero_just_slept;
  rng r;
  int cost;
} state;

// this is called recursively to route the battle.
static int do_turn(int index, int bufs, hero_stats* h, state s, battle* b);

// this labels what to do.
static void describe_action(action what, int damage) {
  if (what == ATTACK) {
    printf("tank [%d damage]", damage);
  } else if (what == SLEEP) {
    printf("put to sleep");
  } else if (what == SKIP) {
    printf("asleep");
  } else {
    printf("buffer %d [%d damage]", what, damage);
  }
}

// prints a routed battle out.
static void print_battle(battle* b) {
  if (b->len == 0) {
    printf("seed %04x: HP %d, bad\n", b->seed, b->starting_hp);
  } else {
    int total_buffers = 0;
    for (int i = 0; i < b->len; i++) {
      if (b->turn_action[i] > 0) {
        total_buffers += (int)b->turn_action[i];
      }
    }
    printf("seed %04x: HP %d, %d buffers, %d turns [",
           b->seed, b->starting_hp, total_buffers, b->len);
    for (int i = 0; i < b->len; i++) {
      printf("%d. ", i);
      describe_action(b->turn_action[i], b->turn_damage[i]);
      printf("] [");
    }
    printf("win]\n");
  }
}

static void print_battle_csv(battle* b) {
  if (b->len > 0) {
    int total_buffers = 0;
    for (int i = 0; i < b->len; i++) {
      if (b->turn_action[i] > 0) {
        total_buffers += (int)b->turn_action[i];
      }
    }
    printf("\"0x%04x\",%d,%d", b->seed, b->starting_hp, total_buffers);
    int i;
    for (i = 0; i < b->len; i++) {
      printf(",%d", b->turn_action[i]);
    }
    for (; i < 5; i++) {
      printf(",-");
    }
    printf("\n");
  }
}

// advance rng a single iteration.
static void tick(rng *r) {
  r->s = (771 * r->s + 129) & 0xffff;
}

// returns starting hp for an axe knight.
static int roll_starting_hp(rng* r) {
  tick(r);
  return AXE_KNIGHT_MAX_HP - (MSB(MSB(r->s) * AXE_KNIGHT_MAX_HP) >> 2);
}

// returns who goes first.
static who roll_initiative(rng *r, int hero_agility) {
  tick(r);
  int enemy_roll = (MSB(r->s) & 0x3f) * AXE_KNIGHT_AGILITY;
  tick(r);
  int hero_roll = MSB(r->s) * hero_agility;
  return hero_roll >= enemy_roll ? HERO : ENEMY;
}

// returns true if enemy should wake up and false if not.
static bool roll_for_enemy_awake(rng *r) {
  tick(r);
  while ((MSB(r->s) & 3) == 0) {
    // roll again until the roll is not zero.
    tick(r);
  }
  return (MSB(r->s) & 3) == 1 ? true : false;
}

// executes one turn for the axe knight.
static action do_enemy_turn(hero_stats* h, state* s, int* damage) {
  *damage = 0;
  if (!s->enemy_awake) {
    s->enemy_awake = roll_for_enemy_awake(&s->r);
  }
  if (!s->enemy_awake) {
    return SKIP;
  }
  // roll for whether to cast sleep.
  tick(&s->r);
  if ((MSB(s->r.s) & 0x30) < 0x10) {
    if (s->hero_awake) {
      s->hero_awake = false;
      s->hero_just_slept = true;
      return SLEEP;
    }
  }
  // roll for whether to cast other spell.
  // does nothing because axe knight has no other spells.
  tick(&s->r);
  // attack. assume the hero's defense is less than the axe knight's strength,
  // so the strong damage formula always applies. technically you could set
  // things up so this is not true, but it wouldn't make sense to do so.
  int d = AXE_KNIGHT_STRENGTH - h->defense/2;
  tick(&s->r);
  *damage = (MSB(MSB(s->r.s) * (d + 1)) + d) / 4;
  s->hero_hp -= *damage;
  if (s->hero_hp < 0) {
    s->hero_hp = 0;
  }
  return ATTACK;
}

// returns true if crit else false.
static bool roll_for_crit(rng* r) {
  tick(r);
  return (MSB(r->s) & 0x1f) == 0;
}

// returns true if axe knight dodges and false if not.
static bool roll_for_dodge(rng* r) {
  tick(r);
  // dodge check clobbers the rng state.
  r->s = ((MSB(r->s) & 0x3f) << 8) | LSB(r->s);
  return MSB(r->s) <= AXE_KNIGHT_DODGE - 1;
}

static void update_sleep_status(hero_stats* h, state* s) {
  if (!s->hero_just_slept && !s->hero_awake) {
    tick(&s->r);
    s->hero_awake = (MSB(s->r.s) & 1) ? true : false;
  }
  s->hero_just_slept = false;
}

// assumes update_sleep_status has been called already.
static action do_hero_turn(hero_stats* h, int bufs, state* s, int* damage) {
  *damage = 0;
  if (!s->hero_awake) {
    return SKIP;
  }
  // always attack (TODO sleep route).
  // buffer a certain number of times on the menu before attacking.
  for (int i = 0; i < bufs * MENU_TICKS - 1; i++) {
    tick(&s->r);
  }
  bool crit = roll_for_crit(&s->r);
  if (crit) {
    tick(&s->r);
    *damage = h->attack - MSB(MSB(s->r.s) * (h->attack/2));
  } else {
    // assume that the hero will do minimal damage to the axe knight.
    // this stops being true at L9 with broad sword and long-term strength
    // growth, but it doesn't make sense to route that.
    tick(&s->r);
    *damage = MSB(s->r.s) & 1;
  }
  // crits and non-crit, non-zero damage rolls get a check for dodge unless the
  // enemy is asleep.
  if ((crit || *damage != 0) && s->enemy_awake) {
    if (roll_for_dodge(&s->r)) {
      *damage = 0;
    }
  }
  s->enemy_hp -= *damage;
  if (s->enemy_hp < 0) {
    s->enemy_hp = 0;
  }
  return bufs;
}

static action do_best_hero_turn(int index, hero_stats* h, state* s, int* damage) {
  int best_bufs = 0;
  int best_cost = INT_MAX;
  update_sleep_status(h, s);
  // if the hero is asleep and does not wake up, we do not need to search each
  // possible number of buffers for this turn; they are all the same.
  if (s->hero_awake) {
    // any hero turn where the menu opens introduces an extra tick.
    tick(&s->r);
    for (int i = 1; i < MAX_BUFFERS; i++) {
      int cost = do_turn(index, i, h, *s, NULL);
      if (cost > 0 && cost < best_cost) {
        best_bufs = i;
        best_cost = cost;
      }
    }
  }
  return do_hero_turn(h, best_bufs, s, damage);
}

static int do_turn(int index, int bufs, hero_stats* h, state s, battle* b) {
  // figure out what happens and advance rng state.
  int damage;
  action what;
  if (s.turn == ENEMY) {
    what = do_enemy_turn(h, &s, &damage);
  } else {
    if (bufs == 0) {
      what = do_best_hero_turn(index, h, &s, &damage);
    } else {
      what = do_hero_turn(h, bufs, &s, &damage);
      s.cost += BUF_COST * bufs;
    }
    if (what == 0) {
      return -1;
    }
  }
  s.cost += TURN_COST;

  // if battle is over for any reason (hero dead, enemy dead, past max search
  // depth) then return right away.
  if (s.hero_hp == 0) {
    return -1;
  }
  if (s.enemy_hp == 0) {
    if (b != NULL && (b->cost == -1 || s.cost < b->cost)) {
      b->turn_action[index] = what;
      b->turn_damage[index] = damage;
      b->len = index + 1;
    }
    return s.cost;
  }
  if (index + 1 >= MAX_TURNS) {
    return -1;
  }
  // otherwise, recurse.
  s.turn = s.turn == HERO ? ENEMY : HERO;
  int total_cost = do_turn(index + 1, 0, h, s, b);
  if (b != NULL && (b->cost == -1 || total_cost < b->cost)) {
    b->turn_action[index] = what;
    b->turn_damage[index] = damage;
  }
  return total_cost;
}

// routes an axe knight battle.
// returns -1 if the battle is lost or the cost if won.
// h has the hero's max stats.
// seed is the rng value in $94/$95 while the battle background draws.
// b is filled with the detailed outcome of the battle.
int do_battle(hero_stats* h, int seed, battle* b) {
  state s = {.r = {.s = seed}};
  b->seed = seed;
  b->len = 0;
  b->cost = -1;
  b->starting_hp = roll_starting_hp(&s.r);
  // if hero strength >= 2 * enemy strength, the enemy tries to run away.
  // since the axe knight's strength is 94 and the max possible hero strength
  // is 140, this never happens.
  b->first_strike = roll_initiative(&s.r, h->agility);
  // set up mutable battle state.
  s.turn = b->first_strike;
  s.enemy_hp = b->starting_hp;
  s.enemy_awake = true;
  s.hero_hp = h->hp;
  s.hero_awake = true;
  s.hero_just_slept = false;
  s.cost = 0;
  return do_turn(0, 0, h, s, b);
}

int main() {
  battle result;
  printf("seed,hp,buffers,\"turn 1\",\"turn 2\",\"turn 3\",\"turn 4\",\"turn 5\"\n");
  for (int seed = 0; seed < 65536; seed++) {
    do_battle(&L6_no_dscale, seed, &result);
    print_battle_csv(&result);
  }
}