Guest User

axe knight battle finder

a guest
Dec 6th, 2015
493
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // tabulates manipulated axe knight battles in dragon warrior
  2. // assumes hero attacks are weak, axe knight attacks are strong. doesn't try to
  3. // cast sleep or anything fancy, just attacks.
  4. #include <limits.h>
  5. #include <stdio.h>
  6. #include <stdbool.h>
  7.  
  8. // the maximum number of turns to which an axe knight battle may be routed,
  9. // including both enemy and hero turns.
  10. #define MAX_TURNS 10
  11.  
  12. // the maximum number of buffers in any turn.
  13. #define MAX_BUFFERS 100
  14.  
  15. // how many ticks buffering A or B in the menu advances the rng.
  16. #define MENU_TICKS 11
  17.  
  18. // cost model for search
  19. #define TURN_COST 2
  20. #define BUF_COST 1
  21.  
  22. // axe knight stats
  23. #define AXE_KNIGHT_MAX_HP 70
  24. #define AXE_KNIGHT_STRENGTH 94
  25. #define AXE_KNIGHT_AGILITY 82
  26. #define AXE_KNIGHT_DODGE 1
  27.  
  28. // shift and mask the most significant byte of a 16-bit value.
  29. #define MSB(x) ((x >> 8) & 0xff)
  30.  
  31. // mask the least significant byte of a 16-bit value.
  32. #define LSB(x) (x & 0xff)
  33.  
  34. // who has done some action.
  35. typedef enum { NOBODY, HERO, ENEMY } who;
  36.  
  37. // things that can happen.
  38. // values > 0 mean "buffer N times before attacking".
  39. typedef enum {
  40.   SKIP = -3,
  41.   SLEEP = -2,
  42.   ATTACK = -1,
  43.   NOTHING = 0
  44. } action;
  45.  
  46. // an rng state.
  47. typedef struct {
  48.   int s;
  49. } rng;
  50.  
  51. // a synposis of all the stuff that happened in a battle.
  52. typedef struct {
  53.   int seed;
  54.   int starting_hp;
  55.   who first_strike;
  56.   action turn_action[MAX_TURNS];
  57.   int turn_damage[MAX_TURNS];
  58.   int len;
  59.   int cost;
  60. } battle;
  61.  
  62. // hero stuff.
  63. typedef struct {
  64.   int hp;
  65.   int mp;
  66.   int strength;
  67.   int agility;
  68.   int attack;
  69.   int defense;
  70.   bool has_sleep;
  71. } hero_stats;
  72.  
  73. static hero_stats L6_no_dscale = {
  74.   .hp = 34,  // 38 - two swamp tiles
  75.   .mp = 24,
  76.   .strength = 16,
  77.   .agility = 12,
  78.   .attack = 36,
  79.   .defense = 16,
  80.   .has_sleep = false
  81. };
  82.  
  83. static hero_stats L6_with_dscale = {
  84.   .hp = 34,  // 38 - two swamp tiles
  85.   .mp = 24,
  86.   .strength = 16,
  87.   .agility = 12,
  88.   .attack = 36,
  89.   .defense = 18,
  90.   .has_sleep = false
  91. };
  92.  
  93. // a current state during the battle search.
  94. typedef struct {
  95.   who turn;
  96.   int enemy_hp;
  97.   bool enemy_awake;
  98.   int hero_hp;
  99.   bool hero_awake;
  100.   bool hero_just_slept;
  101.   rng r;
  102.   int cost;
  103. } state;
  104.  
  105. // this is called recursively to route the battle.
  106. static int do_turn(int index, int bufs, hero_stats* h, state s, battle* b);
  107.  
  108. // this labels what to do.
  109. static void describe_action(action what, int damage) {
  110.   if (what == ATTACK) {
  111.     printf("tank [%d damage]", damage);
  112.   } else if (what == SLEEP) {
  113.     printf("put to sleep");
  114.   } else if (what == SKIP) {
  115.     printf("asleep");
  116.   } else {
  117.     printf("buffer %d [%d damage]", what, damage);
  118.   }
  119. }
  120.  
  121. // prints a routed battle out.
  122. static void print_battle(battle* b) {
  123.   if (b->len == 0) {
  124.     printf("seed %04x: HP %d, bad\n", b->seed, b->starting_hp);
  125.   } else {
  126.     int total_buffers = 0;
  127.     for (int i = 0; i < b->len; i++) {
  128.       if (b->turn_action[i] > 0) {
  129.         total_buffers += (int)b->turn_action[i];
  130.       }
  131.     }
  132.     printf("seed %04x: HP %d, %d buffers, %d turns [",
  133.            b->seed, b->starting_hp, total_buffers, b->len);
  134.     for (int i = 0; i < b->len; i++) {
  135.       printf("%d. ", i);
  136.       describe_action(b->turn_action[i], b->turn_damage[i]);
  137.       printf("] [");
  138.     }
  139.     printf("win]\n");
  140.   }
  141. }
  142.  
  143. static void print_battle_csv(battle* b) {
  144.   if (b->len > 0) {
  145.     int total_buffers = 0;
  146.     for (int i = 0; i < b->len; i++) {
  147.       if (b->turn_action[i] > 0) {
  148.         total_buffers += (int)b->turn_action[i];
  149.       }
  150.     }
  151.     printf("\"0x%04x\",%d,%d", b->seed, b->starting_hp, total_buffers);
  152.     int i;
  153.     for (i = 0; i < b->len; i++) {
  154.       printf(",%d", b->turn_action[i]);
  155.     }
  156.     for (; i < 5; i++) {
  157.       printf(",-");
  158.     }
  159.     printf("\n");
  160.   }
  161. }
  162.  
  163. // advance rng a single iteration.
  164. static void tick(rng *r) {
  165.   r->s = (771 * r->s + 129) & 0xffff;
  166. }
  167.  
  168. // returns starting hp for an axe knight.
  169. static int roll_starting_hp(rng* r) {
  170.   tick(r);
  171.   return AXE_KNIGHT_MAX_HP - (MSB(MSB(r->s) * AXE_KNIGHT_MAX_HP) >> 2);
  172. }
  173.  
  174. // returns who goes first.
  175. static who roll_initiative(rng *r, int hero_agility) {
  176.   tick(r);
  177.   int enemy_roll = (MSB(r->s) & 0x3f) * AXE_KNIGHT_AGILITY;
  178.   tick(r);
  179.   int hero_roll = MSB(r->s) * hero_agility;
  180.   return hero_roll >= enemy_roll ? HERO : ENEMY;
  181. }
  182.  
  183. // returns true if enemy should wake up and false if not.
  184. static bool roll_for_enemy_awake(rng *r) {
  185.   tick(r);
  186.   while ((MSB(r->s) & 3) == 0) {
  187.     // roll again until the roll is not zero.
  188.     tick(r);
  189.   }
  190.   return (MSB(r->s) & 3) == 1 ? true : false;
  191. }
  192.  
  193. // executes one turn for the axe knight.
  194. static action do_enemy_turn(hero_stats* h, state* s, int* damage) {
  195.   *damage = 0;
  196.   if (!s->enemy_awake) {
  197.     s->enemy_awake = roll_for_enemy_awake(&s->r);
  198.   }
  199.   if (!s->enemy_awake) {
  200.     return SKIP;
  201.   }
  202.   // roll for whether to cast sleep.
  203.   tick(&s->r);
  204.   if ((MSB(s->r.s) & 0x30) < 0x10) {
  205.     if (s->hero_awake) {
  206.       s->hero_awake = false;
  207.       s->hero_just_slept = true;
  208.       return SLEEP;
  209.     }
  210.   }
  211.   // roll for whether to cast other spell.
  212.   // does nothing because axe knight has no other spells.
  213.   tick(&s->r);
  214.   // attack. assume the hero's defense is less than the axe knight's strength,
  215.   // so the strong damage formula always applies. technically you could set
  216.   // things up so this is not true, but it wouldn't make sense to do so.
  217.   int d = AXE_KNIGHT_STRENGTH - h->defense/2;
  218.   tick(&s->r);
  219.   *damage = (MSB(MSB(s->r.s) * (d + 1)) + d) / 4;
  220.   s->hero_hp -= *damage;
  221.   if (s->hero_hp < 0) {
  222.     s->hero_hp = 0;
  223.   }
  224.   return ATTACK;
  225. }
  226.  
  227. // returns true if crit else false.
  228. static bool roll_for_crit(rng* r) {
  229.   tick(r);
  230.   return (MSB(r->s) & 0x1f) == 0;
  231. }
  232.  
  233. // returns true if axe knight dodges and false if not.
  234. static bool roll_for_dodge(rng* r) {
  235.   tick(r);
  236.   // dodge check clobbers the rng state.
  237.   r->s = ((MSB(r->s) & 0x3f) << 8) | LSB(r->s);
  238.   return MSB(r->s) <= AXE_KNIGHT_DODGE - 1;
  239. }
  240.  
  241. static void update_sleep_status(hero_stats* h, state* s) {
  242.   if (!s->hero_just_slept && !s->hero_awake) {
  243.     tick(&s->r);
  244.     s->hero_awake = (MSB(s->r.s) & 1) ? true : false;
  245.   }
  246.   s->hero_just_slept = false;
  247. }
  248.  
  249. // assumes update_sleep_status has been called already.
  250. static action do_hero_turn(hero_stats* h, int bufs, state* s, int* damage) {
  251.   *damage = 0;
  252.   if (!s->hero_awake) {
  253.     return SKIP;
  254.   }
  255.   // always attack (TODO sleep route).
  256.   // buffer a certain number of times on the menu before attacking.
  257.   for (int i = 0; i < bufs * MENU_TICKS - 1; i++) {
  258.     tick(&s->r);
  259.   }
  260.   bool crit = roll_for_crit(&s->r);
  261.   if (crit) {
  262.     tick(&s->r);
  263.     *damage = h->attack - MSB(MSB(s->r.s) * (h->attack/2));
  264.   } else {
  265.     // assume that the hero will do minimal damage to the axe knight.
  266.     // this stops being true at L9 with broad sword and long-term strength
  267.     // growth, but it doesn't make sense to route that.
  268.     tick(&s->r);
  269.     *damage = MSB(s->r.s) & 1;
  270.   }
  271.   // crits and non-crit, non-zero damage rolls get a check for dodge unless the
  272.   // enemy is asleep.
  273.   if ((crit || *damage != 0) && s->enemy_awake) {
  274.     if (roll_for_dodge(&s->r)) {
  275.       *damage = 0;
  276.     }
  277.   }
  278.   s->enemy_hp -= *damage;
  279.   if (s->enemy_hp < 0) {
  280.     s->enemy_hp = 0;
  281.   }
  282.   return bufs;
  283. }
  284.  
  285. static action do_best_hero_turn(int index, hero_stats* h, state* s, int* damage) {
  286.   int best_bufs = 0;
  287.   int best_cost = INT_MAX;
  288.   update_sleep_status(h, s);
  289.   // if the hero is asleep and does not wake up, we do not need to search each
  290.   // possible number of buffers for this turn; they are all the same.
  291.   if (s->hero_awake) {
  292.     // any hero turn where the menu opens introduces an extra tick.
  293.     tick(&s->r);
  294.     for (int i = 1; i < MAX_BUFFERS; i++) {
  295.       int cost = do_turn(index, i, h, *s, NULL);
  296.       if (cost > 0 && cost < best_cost) {
  297.         best_bufs = i;
  298.         best_cost = cost;
  299.       }
  300.     }
  301.   }
  302.   return do_hero_turn(h, best_bufs, s, damage);
  303. }
  304.  
  305. static int do_turn(int index, int bufs, hero_stats* h, state s, battle* b) {
  306.   // figure out what happens and advance rng state.
  307.   int damage;
  308.   action what;
  309.   if (s.turn == ENEMY) {
  310.     what = do_enemy_turn(h, &s, &damage);
  311.   } else {
  312.     if (bufs == 0) {
  313.       what = do_best_hero_turn(index, h, &s, &damage);
  314.     } else {
  315.       what = do_hero_turn(h, bufs, &s, &damage);
  316.       s.cost += BUF_COST * bufs;
  317.     }
  318.     if (what == 0) {
  319.       return -1;
  320.     }
  321.   }
  322.   s.cost += TURN_COST;
  323.  
  324.   // if battle is over for any reason (hero dead, enemy dead, past max search
  325.   // depth) then return right away.
  326.   if (s.hero_hp == 0) {
  327.     return -1;
  328.   }
  329.   if (s.enemy_hp == 0) {
  330.     if (b != NULL && (b->cost == -1 || s.cost < b->cost)) {
  331.       b->turn_action[index] = what;
  332.       b->turn_damage[index] = damage;
  333.       b->len = index + 1;
  334.     }
  335.     return s.cost;
  336.   }
  337.   if (index + 1 >= MAX_TURNS) {
  338.     return -1;
  339.   }
  340.   // otherwise, recurse.
  341.   s.turn = s.turn == HERO ? ENEMY : HERO;
  342.   int total_cost = do_turn(index + 1, 0, h, s, b);
  343.   if (b != NULL && (b->cost == -1 || total_cost < b->cost)) {
  344.     b->turn_action[index] = what;
  345.     b->turn_damage[index] = damage;
  346.   }
  347.   return total_cost;
  348. }
  349.  
  350. // routes an axe knight battle.
  351. // returns -1 if the battle is lost or the cost if won.
  352. // h has the hero's max stats.
  353. // seed is the rng value in $94/$95 while the battle background draws.
  354. // b is filled with the detailed outcome of the battle.
  355. int do_battle(hero_stats* h, int seed, battle* b) {
  356.   state s = {.r = {.s = seed}};
  357.   b->seed = seed;
  358.   b->len = 0;
  359.   b->cost = -1;
  360.   b->starting_hp = roll_starting_hp(&s.r);
  361.   // if hero strength >= 2 * enemy strength, the enemy tries to run away.
  362.   // since the axe knight's strength is 94 and the max possible hero strength
  363.   // is 140, this never happens.
  364.   b->first_strike = roll_initiative(&s.r, h->agility);
  365.   // set up mutable battle state.
  366.   s.turn = b->first_strike;
  367.   s.enemy_hp = b->starting_hp;
  368.   s.enemy_awake = true;
  369.   s.hero_hp = h->hp;
  370.   s.hero_awake = true;
  371.   s.hero_just_slept = false;
  372.   s.cost = 0;
  373.   return do_turn(0, 0, h, s, b);
  374. }
  375.  
  376. int main() {
  377.   battle result;
  378.   printf("seed,hp,buffers,\"turn 1\",\"turn 2\",\"turn 3\",\"turn 4\",\"turn 5\"\n");
  379.   for (int seed = 0; seed < 65536; seed++) {
  380.     do_battle(&L6_no_dscale, seed, &result);
  381.     print_battle_csv(&result);
  382.   }
  383. }
RAW Paste Data