1 /* Simulate Wesnoth combat. */
2 #define _GNU_SOURCE
3 #include <stdbool.h>
4 #include <stdarg.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <assert.h>
9 #include <sys/time.h>
10 #include <time.h>
11 #include <errno.h>
12
13 /* from the Linux Kernel:
14 * min()/max() macros that also do
15 * strict type-checking.. See the
16 * "unnecessary" pointer comparison.
17 */
18
19 //NOTE: cppcheck reports memory leaks in this program
20 #define max(x,y) ({ \
21 typeof(x) _x = (x); \
22 typeof(y) _y = (y); \
23 (void) (&_x == &_y); \
24 _x > _y ? _x : _y; })
25
26 struct unit
27 {
28 unsigned damage, num_attacks, hp, max_hp;
29 unsigned hit_chance;
30 bool slowed, slows, drains, berserk, swarm, firststrike;
31 bool touched;
32 };
33
34 static void __attribute__((noreturn, format(printf,1,2)))
barf(const char * fmt,...)35 barf(const char *fmt, ...)
36 {
37 char *str;
38 va_list arglist;
39
40 fprintf(stderr, "FATAL: ");
41
42 va_start(arglist, fmt);
43 vasprintf(&str, fmt, arglist);
44 va_end(arglist);
45
46 fprintf(stderr, "%s\n", str);
47 free(str);
48 exit(1);
49 }
50
hits(unsigned int chance)51 static bool hits(unsigned int chance)
52 {
53 return (random() % 100) < chance;
54 }
55
strike(struct unit * attacker,struct unit * defender)56 static void strike(struct unit *attacker, struct unit *defender)
57 {
58 unsigned damage = attacker->damage;
59
60 if (!hits(attacker->hit_chance))
61 return;
62
63 if (damage > defender->hp)
64 damage = defender->hp;
65 if (attacker->slows && !defender->slowed) {
66 defender->slowed = true;
67 defender->damage = (defender->damage + 1) / 2;
68 }
69 if (attacker->drains) {
70 attacker->hp += damage/2;
71 if (attacker->hp > attacker->max_hp)
72 attacker->hp = attacker->max_hp;
73 }
74 defender->hp -= damage;
75 defender->touched = true;
76 }
77
78 // A attacks B.
simulate_attack(struct unit * a,struct unit * b)79 static void simulate_attack(struct unit *a, struct unit *b)
80 {
81 unsigned int i, j;
82
83 for (i = 0; i < ((a->berserk || b->berserk) ? 30: 1); i++) {
84 for (j = 0; j < max(a->num_attacks, b->num_attacks); j++) {
85 if (j < a->num_attacks) {
86 strike(a, b);
87 if (b->hp == 0)
88 return;
89 }
90 if (j < b->num_attacks) {
91 strike(b, a);
92 if (a->hp == 0)
93 return;
94 }
95 }
96 }
97 }
98
num_attacks(unsigned base,unsigned max,unsigned hp,bool swarm)99 static unsigned int num_attacks(unsigned base, unsigned max, unsigned hp,
100 bool swarm)
101 {
102 if (!swarm)
103 return base;
104 /* Swarm scales num attacks by hp. */
105 return base * hp / max;
106 }
107
108 /* This gives a max variation of around 1%. */
calculate_attack(const struct unit * defender,double defender_res[],double * defender_touched,double attacker_touched[],const struct unit * attackers[],double * attacker_res[],unsigned num_attackers,unsigned num_sims)109 static void calculate_attack(const struct unit *defender,
110 double defender_res[],
111 double *defender_touched,
112 double attacker_touched[],
113 const struct unit *attackers[],
114 double *attacker_res[],
115 unsigned num_attackers,
116 unsigned num_sims)
117 {
118 unsigned int i, j;
119
120 *defender_touched = 0;
121
122 for (j = 0; j < num_attackers; j++)
123 attacker_touched[j] = 0;
124
125 for (i = 0; i < num_sims; i++) {
126 struct unit def = *defender;
127
128 def.slowed = false;
129 def.touched = false;
130 for (j = 0; j < num_attackers && def.hp; j++) {
131 struct unit att = *attackers[j];
132
133 att.slowed = false;
134 att.touched = false;
135 att.num_attacks = num_attacks(att.num_attacks,
136 att.max_hp, att.hp,
137 att.swarm);
138 def.num_attacks = num_attacks(defender->num_attacks,
139 defender->max_hp, def.hp,
140 def.swarm);
141 if (def.firststrike && !att.firststrike)
142 simulate_attack(&def, &att);
143 else
144 simulate_attack(&att, &def);
145 attacker_res[j][att.hp]++;
146 if (att.touched)
147 attacker_touched[j]++;
148 }
149 defender_res[def.hp]++;
150 if (def.touched)
151 (*defender_touched)++;
152 }
153
154 /* Now normalize each one by number of battles it was in. */
155 for (i = 0; i <= defender->max_hp; i++)
156 defender_res[i] /= num_sims;
157 *defender_touched /= num_sims;
158
159 for (i = 0; i < num_attackers; i++) {
160 unsigned int battles = 0;
161 for (j = 0; j <= attackers[i]->max_hp; j++) {
162 battles += attacker_res[i][j];
163 attacker_res[i][j] /= num_sims;
164 }
165 /* Any battle we weren't in, we're unscathed. */
166 attacker_res[i][attackers[i]->hp]
167 += (1.0*num_sims-battles)/num_sims;
168
169 /* If this attacker wasn't in more than 1% of battles, don't
170 * pretend to know this probability. */
171 if (battles <= num_sims / 100)
172 attacker_touched[i] = -1.0;
173 else
174 /* FIXME: attack_prediction doesn't take into account
175 * that opponent might already be dead. */
176 attacker_touched[i] /= num_sims;
177 }
178 }
179
parse_unit(char *** argv)180 static struct unit *parse_unit(char ***argv)
181 {
182 struct unit *u = (unit *)malloc(sizeof(*u));
183
184 u->damage = atoi((*argv)[1]);
185 u->num_attacks = atoi((*argv)[2]);
186 u->hp = u->max_hp = atoi((*argv)[3]);
187 u->hit_chance = atoi((*argv)[4]);
188 u->slows = false;
189 u->slowed = false;
190 u->drains = false;
191 u->berserk = false;
192 u->swarm = false;
193 u->firststrike = false;
194 if ((*argv)[5] && atoi((*argv)[5]) == 0) {
195 char *max = strstr((*argv)[5], "maxhp=");
196 if (max) {
197 u->max_hp = atoi(max + strlen("maxhp="));
198 if (u->max_hp < u->hp)
199 barf("maxhp must be at least hitpoints");
200 }
201 if (strstr((*argv)[5], "drain")) {
202 if (!max)
203 fprintf(stderr, "WARNING: drain specified without maxhp; assuming uninjured.\n");
204 u->drains = true;
205 }
206 if (strstr((*argv)[5], "slow"))
207 u->slows = true;
208 if (strstr((*argv)[5], "berserk"))
209 u->berserk = true;
210 if (strstr((*argv)[5], "firststrike"))
211 u->firststrike = true;
212 if (strstr((*argv)[5], "swarm")) {
213 if (!max)
214 fprintf(stderr, "WARNING: swarm specified without maxhp; assuming uninjured.\n");
215 u->swarm = true;
216 }
217 *argv += 5;
218 } else
219 *argv += 4;
220
221 return u;
222 }
223
224 #if 0
225 static void graph_prob(unsigned int hp, double prob)
226 {
227 unsigned int i, percent;
228
229 percent = (prob + 1/200.0) * 100;
230
231 printf("%-3u %3u%% |", hp, percent);
232 for (i = 0; i < percent; i++)
233 printf("#");
234 printf("\n");
235 }
236 #endif
237
draw_results(const double res[],const struct unit * u,double touched,const char label[])238 static void draw_results(const double res[], const struct unit *u,
239 double touched,
240 const char label[])
241 {
242 unsigned int i;
243
244 printf("#0: %s: %u %u %u %u%% ",
245 label, u->damage, u->num_attacks, u->hp, u->hit_chance);
246 if (u->drains)
247 printf("drains,");
248 if (u->slows)
249 printf("slows,");
250 if (u->berserk)
251 printf("berserk,");
252 if (u->swarm)
253 printf("swarm,");
254 if (u->firststrike)
255 printf("firststrike,");
256 printf("maxhp=%u ", u->max_hp);
257 if (touched == -1)
258 printf("touched:unknown ");
259 else
260 printf("touched:%.2f%% ", touched*100);
261 for (i = 0; i < u->max_hp+1; i++)
262 printf(" %.2f", res[i]*100);
263 printf("\n");
264 }
265
compare_results(const double res[],const struct unit * u,const char label[],unsigned battle,double touched,FILE * f)266 static void compare_results(const double res[], const struct unit *u,
267 const char label[], unsigned battle,
268 double touched, FILE *f)
269 {
270 unsigned int i;
271 char line[128], cmp[128];
272 double val;
273
274 sprintf(cmp, "#%u: %s: %u %u %u %u%% ", battle,
275 label, u->damage, u->num_attacks, u->hp, u->hit_chance);
276 if (u->drains)
277 sprintf(cmp+strlen(cmp), "drains,");
278 if (u->slows)
279 sprintf(cmp+strlen(cmp), "slows,");
280 if (u->berserk)
281 sprintf(cmp+strlen(cmp), "berserk,");
282 if (u->swarm)
283 sprintf(cmp+strlen(cmp), "swarm,");
284 if (u->firststrike)
285 sprintf(cmp+strlen(cmp), "firststrike,");
286 sprintf(cmp+strlen(cmp), "maxhp=%u", u->max_hp);
287
288 if (fread(line, strlen(cmp), 1, f) != 1)
289 barf("Unexpected end of file on battle %u", battle);
290
291 if (strncmp(line, cmp, strlen(cmp)) != 0)
292 barf("Battle %u is different: '%.*s' should be '%s'",
293 battle, (int)strlen(cmp), line, cmp);
294
295 if (fscanf(f, " %lf", &val) != 1)
296 barf("Malformed untouched: %s battle %u",
297 label, battle);
298
299 /* We *must* have result for defender and attacker 1. */
300 if (touched == -1)
301 assert(strcmp(label, "Attacker #2") == 0);
302 else if ( abs(val - (1.0 - touched)) > 0.01 )
303 printf("Warning: expected %f untouched, but got %f (battle %u %s).\n",
304 1.0 - touched, val, battle, label);
305
306 for (i = 0; i < u->max_hp+1; i++) {
307 if (fscanf(f, " %lf", &val) != 1)
308 barf("Malformed hp line: %s hp %u battle %u",
309 label, i, battle);
310 #if 0
311 if (abs(val - res[i]*100) > 5.0)
312 barf("Battle %u %s hp %u %f should be %f",
313 battle, label, i, val, res[i]*100);
314 #endif
315 if (abs(val - res[i]*100) > 1.0)
316 printf("Warning: in battle %u, %s hp %u chance was %f; should be %f.\n",
317 battle, label, i, val, res[i]*100);
318 }
319 fscanf(f, "\n");
320 }
321
check_sum(double * arr,unsigned int num)322 static void check_sum(double *arr, unsigned int num)
323 {
324 unsigned int i;
325 double sum = 0;
326
327 for (i = 0; i <= num; i++)
328 sum += arr[i];
329
330 assert(sum > 0.999 && sum < 1.001);
331 }
332
333 #define NUM_UNITS 50
check(const char * filename)334 static void check(const char *filename)
335 {
336 /* N^2 battles. */
337 struct unit u[NUM_UNITS];
338 unsigned int i, j, k, battle = 0, percent;
339 FILE *f = fopen(filename, "r");
340 if (!f)
341 barf("Could not open %s for reading: %s",
342 filename, strerror(errno));
343
344 printf("Creating %i units...\n", NUM_UNITS);
345 for (i = 0; i < NUM_UNITS; i++) {
346 unsigned alt = i + 74; // To offset some cycles.
347 // Setting the specials.
348 // Try to have these on different cycles so we do not, for example,
349 // only have slows when there is also swarm.
350 u[i].slows = (i % 11) % 3 == 0;
351 u[i].drains = (i % 13) % 4 == 0;
352 u[i].swarm = i % 5 == 0;
353 u[i].berserk = i % 7 == 0;
354 u[i].firststrike = (i % 17) / 2 == 0;
355 // The number of attacks and hit points lost at the start of combat
356 // should also be on their own cycles, as these strongly interact with
357 // some specials.
358 u[i].num_attacks = (alt%19 + 3) / 4; // range: 0-5, with 0 and 5 less common
359 u[i].max_hp = (i*2)%23 + (i*3)%14 + 25; // range: 25-60, with a bit of a bell curve.
360
361 // Miscellaneous unit stats.
362 // Having these on their own cycles would be desirable, but
363 // is not critical.
364 u[i].hit_chance = (i % 6)*10 + 30; // range: 30%-80%
365 u[i].damage = alt % 8 + 2; // range: 2-9
366 u[i].hp = (alt*5)%u[i].max_hp + 1; // range: 1-max_hp
367 }
368
369 printf("Beginning battle...\n");
370
371 percent = NUM_UNITS*(NUM_UNITS-1)*(NUM_UNITS-2)/100;
372 srandom(time(NULL));
373 for (i = 0; i < NUM_UNITS; i++) {
374 for (j = 0; j < NUM_UNITS; j++) {
375 if (i == j)
376 continue;
377 for (k = 0; k < NUM_UNITS; k++) {
378 if (k == i || k == j)
379 continue;
380 double i_result[u[i].max_hp+1];
381 double j_result[u[j].max_hp+1];
382 double k_result[u[k].max_hp+1];
383 double i_touched;
384 double *attacker_res[2];
385 const struct unit *attackers[2];
386 double touched[2];
387
388 memset(i_result, 0, sizeof(i_result));
389 memset(j_result, 0, sizeof(j_result));
390 memset(k_result, 0, sizeof(k_result));
391
392 attacker_res[0] = j_result;
393 attacker_res[1] = k_result;
394 attackers[0] = &u[j];
395 attackers[1] = &u[k];
396 calculate_attack(&u[i], i_result, &i_touched, touched,
397 attackers, attacker_res, 2, 20000);
398 battle++;
399 check_sum(i_result, u[i].max_hp);
400 check_sum(j_result, u[j].max_hp);
401 check_sum(k_result, u[k].max_hp);
402 compare_results(i_result, &u[i], "Defender",
403 battle, i_touched, f);
404 compare_results(j_result, &u[j], "Attacker #1",
405 battle, touched[0], f);
406 compare_results(k_result, &u[k], "Attacker #2",
407 battle, touched[1], f);
408 if ((battle % percent) == 0) {
409 printf(".");
410 fflush(stdout);
411 }
412 }
413 }
414 }
415 printf("\nTotal combats: %i\n", NUM_UNITS*(NUM_UNITS-1)*(NUM_UNITS-2));
416 exit(0);
417 }
418
main(int argc,char * argv[])419 int main(int argc, char *argv[])
420 {
421 unsigned int i;
422 double *res_def, *res_att[argc / 4], def_touched, att_touched[argc/4];
423 const struct unit *def, *attacker[argc / 4 + 1];
424
425 if (argc == 3 && strcmp(argv[1], "--check") == 0)
426 check(argv[2]);
427
428 if (argc < 9)
429 barf("Usage: %s --check <results-file>\n"
430 "\t%s <damage> <attacks> <hp> <hitprob> [drain,slow,swarm,firststrike,berserk,maxhp=<num>] <damage> <attacks> <hp> <hitprob> [drain,slow,berserk,firststrike,swarm,maxhp=<num>] ...",
431 argv[0], argv[0]);
432
433 def = parse_unit(&argv);
434 res_def = (double *)calloc(sizeof(double), def->max_hp+1);
435 for (i = 0; argv[1]; i++) {
436 attacker[i] = parse_unit(&argv);
437 res_att[i] = (double *)calloc(sizeof(double), attacker[i]->max_hp+1);
438 }
439 attacker[i] = NULL;
440
441 srandom(time(NULL));
442 calculate_attack(def, res_def, &def_touched, att_touched,
443 attacker, res_att, i, 10000);
444 draw_results(res_def, def, def_touched, "Defender");
445 for (i = 0; attacker[i]; i++)
446 draw_results(res_att[i], attacker[i], att_touched[i],
447 "Attacker");
448 return 0;
449 }
450