1#include "ap_plan.h"
2#include "ap_item.h"
3#include "ap_map.h"
4#include "ap_snes.h"
5#include <limits.h>
6
7#define GOAL_SCORE_UNSATISFIABLE    (INT_MAX-1)
8#define GOAL_SCORE_GT_LIMIT         (INT_MAX)
9#define GOAL_SCORE_COMPLETE         (-2)
10static int ap_goal_score(struct ap_goal * goal, int max_cost);
11
12const char * const ap_goal_type_names[] = {
13#define X(type) [CONCAT(GOAL_, type)] = #type,
14AP_GOAL_TYPE_LIST
15#undef X
16};
17
18const char * const ap_task_type_names[] = {
19#define X(type) [CONCAT(TASK_, type)] = #type,
20AP_TASK_TYPE_LIST
21#undef X
22};
23
24static struct ap_goal _ap_goal_list = {.next = &_ap_goal_list, .prev = &_ap_goal_list};
25struct ap_goal * ap_goal_list = &_ap_goal_list;
26static struct ap_goal * ap_active_goal = NULL;
27static struct ap_task _ap_task_list = {.next = &_ap_task_list, .prev = &_ap_task_list};
28struct ap_task * ap_task_list = &_ap_task_list;
29static bool ap_new_goals = true;
30
31static int ap_goal_count[_GOAL_TYPE_MAX];
32static int ap_goal_completed[_GOAL_TYPE_MAX];
33
34void
35ap_print_goals(bool no_limit)
36{
37    FILE * f = fopen("goals.txt", "w+");
38    assert(f != NULL);
39    fprintf(f, "Goal list: (current index=%#x)\n", XYMAPSCREEN(ap_link_xy()));
40    int max_score = GOAL_SCORE_GT_LIMIT;
41    for (struct ap_goal * goal = ap_goal_list->next; goal != ap_goal_list; goal = goal->next) {
42        int score = ap_goal_score(goal, max_score);
43        goal->last_score = score;
44        char score_str[16];
45        if (score == GOAL_SCORE_COMPLETE) {
46            snprintf(score_str, sizeof(score_str), TERM_GREEN("compl"));
47        } else if (score == GOAL_SCORE_UNSATISFIABLE) {
48            snprintf(score_str, sizeof(score_str), TERM_RED("unsat"));
49        } else if (score == GOAL_SCORE_GT_LIMIT) {
50            snprintf(score_str, sizeof(score_str), TERM_BLUE("limit"));
51        } else {
52            if (!no_limit) {
53                max_score = MIN(score, max_score);
54            }
55            snprintf(score_str, sizeof(score_str), TERM_BLUE("%5d"), score);
56        }
57        fprintf(f, "    " TERM_BOLD("*") " %s " PRIGOAL, score_str, PRIGOALF(goal));
58        if (goal->type == GOAL_EXPLORE) {
59            if (goal->node != NULL && goal->node->adjacent_node != NULL) {
60                fprintf(f, " to %s %p", goal->node->adjacent_node->name, goal->node);
61            } else {
62                fprintf(f, " to umapped %p", goal->node);
63            }
64        } else {
65            if (goal->node != NULL && goal->node->screen != NULL) {
66                fprintf(f, " on %s", goal->node->screen->name);
67            }
68        }
69        fprintf(f, " Needs: %s", ap_req_print(&goal->req));
70        fprintf(f, "\n");
71    }
72    fprintf(f, "\n");
73    fprintf(f, "Stats: ");
74    for (int i = 0; i < _GOAL_TYPE_MAX; i++) {
75        fprintf(f, "%s %d/%d", ap_goal_type_names[i], ap_goal_completed[i], ap_goal_count[i]);
76        if (i != _GOAL_TYPE_MAX - 1) {
77            fprintf(f, ", ");
78        }
79    }
80
81    fprintf(f, "\n");
82    fflush(f);
83    rewind(f);
84    static char buf[4096];
85    size_t rc;
86    while ((rc = fread(buf, 1, sizeof(buf), f)) > 0) {
87        fwrite(buf, 1, rc, stdout);
88    }
89    fclose(f);
90}
91
92static struct ap_goal *
93ap_goal_append()
94{
95    struct ap_goal * goal = calloc(1, sizeof *goal);
96    assert(goal != NULL);
97
98    LL_INIT(goal);
99    LL_PUSH(ap_goal_list, goal);
100    //ap_graph_init(&goal->graph, goal->name);
101    ap_req_init(&goal->req);
102    ap_new_goals = true;
103    return goal;
104}
105
106struct ap_goal *
107ap_goal_add(enum ap_goal_type type, struct ap_node * node)
108{
109    for (struct ap_goal * goal = ap_goal_list->next; goal != ap_goal_list; goal = goal->next) {
110        if (goal->type == type && goal->node == node)
111            return NULL;
112    }
113    struct ap_goal * goal = ap_goal_append();
114    goal->type = type;
115    goal->node = node;
116    snprintf(goal->name, sizeof goal->name, PRIGOAL, PRIGOALF(goal));
117    if (type == GOAL_EXPLORE) {
118        LOG("New explore, attr: %#x", node->tile_attr);
119    } else if (type == GOAL_SCRIPT) {
120        if (goal->node->script->start_item == INVENTORY_BOMBS) {
121            ap_req_require(&goal->req, 0, REQUIREMENT_BOMBS);
122        }
123        if (goal->node->script->type == SCRIPT_KILLALL) {
124            ap_req_require(&goal->req, 0, REQUIREMENT_SWORD);
125        }
126    }
127    /*
128        if (!(type == GOAL_NPC && node->sprite_type == 0x73 && node->sprite_subtype == 0x100)) {
129            // Don't do anything but explore until we get sword from uncle
130            ap_req_require(&goal->req, 0, REQUIREMENT_SWORD);
131        }
132        */
133    if (type == GOAL_NPC && node->sprite_type == 0x16 && node->sprite_subtype == 0x0000) {
134        // Sahashrala needs the green pendant before giving us an item
135        ap_req_require(&goal->req, 0, REQUIREMENT_GREEN_PENDANT);
136    }
137    if (type == GOAL_EXPLORE) {
138        uint16_t attrs = ap_tile_attrs[node->tile_attr];
139        if (attrs & TILE_ATTR_SWIM) {
140            ap_req_require(&goal->req, 0, REQUIREMENT_FLIPPERS);
141        }
142        if (attrs & TILE_ATTR_BONK) {
143            ap_req_require(&goal->req, 0, REQUIREMENT_BOOTS);
144        }
145        if (node->tile_attr == 0x55) {
146            ap_req_require(&goal->req, 0, REQUIREMENT_GLOVES_1);
147        }
148        if (strcmp(node->name, "door 0x24") == 0) {
149            // Castle door to Agahnim
150            ap_req_require(&goal->req, 0, REQUIREMENT_MASTER_SWORD);
151        }
152        if (strcmp(node->name, "door 0x09") == 0) {
153            // Desert Palace
154            ap_req_require(&goal->req, 0, REQUIREMENT_BOOK);
155        }
156        if (strcmp(node->name, "door 0x63") == 0) {
157            // Big-bomb Fairy
158            ap_req_require(&goal->req, 0, REQUIREMENT_FIVESIX_CRYSTALS);
159        }
160    }
161    ap_goal_count[goal->type]++;
162    return goal;
163}
164
165static struct ap_task *
166ap_task_append()
167{
168    struct ap_task * task = NONNULL(calloc(1, sizeof *task));
169    LL_INIT(task);
170    LL_PUSH(ap_task_list, task);
171    return task;
172}
173
174static struct ap_task *
175ap_task_prepend()
176{
177    struct ap_task * task = NONNULL(calloc(1, sizeof *task));
178    LL_INIT(task);
179    LL_PREPEND(ap_task_list, task);
180    return task;
181}
182
183const char *
184ap_print_task(const struct ap_task * task)
185{
186    static char sbuf[2048];
187    char * buf = sbuf;
188    buf += sprintf(buf, "%s %s", ap_task_type_names[task->type], task->name);
189    switch (task->type) {
190    case TASK_GOTO_POINT:
191    case TASK_OPEN_CHEST:
192    case TASK_LIFT_POT:
193    case TASK_TRANSITION:
194    case TASK_STEP_OFF_SWITCH:
195    case TASK_TALK_NPC:
196        buf += sprintf(buf, " [node=" PRINODE "]", PRINODEF(task->node));
197        break;
198    case TASK_SCRIPT_SEQUENCE:
199    case TASK_SCRIPT_KILLALL:
200    case TASK_SCRIPT_KILLDROPS:
201        if (task->node != NULL) {
202            buf += sprintf(buf, " [script=%s start_tl=" PRIXYV "]", task->node->script->name, PRIXYVF(task->node->script->start_tl));
203        }
204        break;
205    case TASK_SET_INVENTORY:
206        buf += sprintf(buf, " [item=%#x]", task->item);
207        break;
208    case TASK_BOMB:
209        buf += sprintf(buf, " [bomb=%s]", task->node->name);
210        break;
211    case TASK_NONE:
212        break;
213    }
214    return sbuf;
215}
216
217void
218ap_print_tasks()
219{
220    if (ap_active_goal == NULL) {
221        printf("Current Goal: " PRIGOAL "\n", PRIGOALF(ap_active_goal));
222    }
223    printf("Task List:\n");
224    for (struct ap_task * task = ap_task_list->next; task != ap_task_list; task = task->next) {
225        printf("    > " PRITASK "\n", PRITASKF(task));
226    }
227    printf("\n");
228}
229
230static int
231ap_task_follow_targets(struct ap_task * task, uint16_t * joypad)
232{
233    enum ap_inventory equip = *ap_ram.current_item;
234    int rc = ap_follow_targets(joypad, &equip);
235    if (rc != RC_INPR) return rc;
236    if (equip != *ap_ram.current_item) {
237        struct ap_task * new_task = ap_task_prepend(); 
238        new_task->type = TASK_SET_INVENTORY;
239        new_task->item = equip;
240        snprintf(new_task->name, sizeof new_task->name, "equip to follow_targets");
241
242        task->state = 0;
243        task->timeout = 1;
244    }
245    return rc;
246}
247
248// return -1 for failure, 0 for success, 1 for in-progress
249static int
250ap_task_evaluate(struct ap_task * task, uint16_t * joypad)
251{
252    int rc;
253    struct ap_screen * screen = ap_update_map_screen(false);
254    struct xy link = ap_link_xy();
255    bool unlockable = false;
256    const struct ap_room_tag * unlock_tag = NULL;
257    if (task->node != NULL && ap_node_islocked(task->node, &unlockable, &unlock_tag)) {
258        if (!unlockable) {
259            LOG("Cannot unlock door");
260            return RC_FAIL;
261        }
262
263        if (task->node->type == NODE_TRANSITION && (ap_door_attrs[task->node->door_type] & (DOOR_ATTR_SKEY | DOOR_ATTR_BKEY))) {
264            // pass
265        } else if (task->node->type == NODE_TRANSITION && (ap_door_attrs[task->node->door_type] & DOOR_ATTR_BOMB) && task->type != TASK_TRANSITION) {
266            // pass
267        } else {
268            if (task->node->type == NODE_TRANSITION &&
269                ((ap_door_attrs[task->node->door_type] & DOOR_ATTR_BOMB) ||
270                 (task->node->lock_node != NULL && task->node->lock_node->type == NODE_OVERLAY && task->node->lock_node->overlay_index != 0x5B))) {
271                // Try bombing it
272                struct ap_node * bomb_node = task->node->lock_node;
273                if (bomb_node == NULL) {
274                    bomb_node = task->node;
275                }
276
277                struct ap_task * new_task = ap_task_prepend(); 
278                new_task->type = TASK_GOTO_POINT;
279                new_task->node = task->node;
280                snprintf(new_task->name, sizeof new_task->name, "goto bombed %s", task->node->name);
281
282                new_task = ap_task_prepend(); 
283                new_task->type = TASK_BOMB;
284                new_task->node = bomb_node;
285                snprintf(new_task->name, sizeof new_task->name, "bomb open");
286
287                new_task = ap_task_prepend(); 
288                new_task->type = TASK_SET_INVENTORY;
289                new_task->item = INVENTORY_BOMBS;
290                snprintf(new_task->name, sizeof new_task->name, "set bombs");
291
292                if (!XYIN(link, bomb_node->tl, bomb_node->br)) {
293                    new_task = ap_task_prepend(); 
294                    new_task->type = TASK_GOTO_POINT;
295                    new_task->node = bomb_node;
296                    snprintf(new_task->name, sizeof new_task->name, "goto bomb %s", task->node->name);
297                }
298            } else if (unlock_tag != NULL && unlock_tag->action == ROOM_ACTION_SWITCH_TOGGLE) {
299                struct ap_task * new_task = ap_task_prepend(); 
300                if (task->type != TASK_GOTO_POINT) {
301                    new_task->type = TASK_GOTO_POINT;
302                    new_task->node = task->node;
303                    snprintf(new_task->name, sizeof new_task->name, "goto %s", task->node->name);
304                    new_task = ap_task_prepend(); 
305                }
306                // Prepend an unlock task
307                new_task->type = TASK_GOTO_POINT;
308                new_task->node = task->node->lock_node;
309                snprintf(new_task->name, sizeof new_task->name, "unlock %s", task->node->name);
310
311                // Maybe we need to step off first
312                new_task = ap_task_prepend(); 
313                new_task->type = TASK_STEP_OFF_SWITCH;
314                new_task->node = task->node->lock_node;
315                snprintf(new_task->name, sizeof new_task->name, "step off");
316            } else if (unlock_tag != NULL &&
317                    (unlock_tag->action == ROOM_ACTION_KILL_ENEMY || unlock_tag->action == ROOM_ACTION_CLEAR_LEVEL)) {
318                // XXX CLEAR_LEVEL is separate from KILL_ENEMY
319                struct ap_task * new_task = ap_task_prepend(); 
320                if (task->type != TASK_GOTO_POINT) {
321                    new_task->type = TASK_GOTO_POINT;
322                    new_task->node = task->node;
323                    snprintf(new_task->name, sizeof new_task->name, "goto %s", task->node->name);
324                    new_task = ap_task_prepend(); 
325                }
326
327                // Prepend an killall task
328                new_task->type = TASK_SCRIPT_KILLALL;
329                snprintf(new_task->name, sizeof new_task->name, "killall");
330
331                // Spawn the stalfos
332                if (task->node->screen->id == 0x1580) {
333                    for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
334                        if (node->type == NODE_ITEM && node->tile_attr == 0x74) {
335                            new_task = ap_task_prepend(); 
336                            new_task->type = TASK_LIFT_POT;
337                            new_task->node = node;
338                            snprintf(new_task->name, sizeof new_task->name, "spawn");
339                            break;
340                        }
341                    }
342                }
343            } else {
344                LOG("Don't know how to unlock door (%s)", ap_room_tag_print(unlock_tag));
345                return RC_FAIL;
346            }
347
348            LOGB("Locked/bombable door; prepending open steps");
349            *joypad = 0;
350            return RC_INPR; // XXX should there be RC_RTRY?
351        }
352    }
353
354    uint8_t module_index = *ap_ram.module_index;
355    uint8_t submodule_index = *ap_ram.submodule_index;
356    // Dialog, Textbox, Inventory Screen
357    if (module_index == 0x0E) {
358        if (submodule_index == 0x01) {
359            // Inventory
360            if (task->type != TASK_SET_INVENTORY) {
361                JOYPAD_MASH(START, 0x01);
362            }
363        } else {
364            // Dialog?
365            LOGB("Mashing dialog; submodule = %#x", submodule_index);
366            JOYPAD_MASH(A, 0x01);
367        }
368    }
369
370    switch (task->type) {
371    case TASK_STEP_OFF_SWITCH:
372        if (!*ap_ram.link_on_switch && task->state < 5) {
373            task->state = 5;
374            task->timeout = 16;
375        }
376        switch (task->state) {
377        case 0:
378            task->timeout = 32;
379            task->state++;
380            task->state += rand() % 4;
381            break;
382            // FIXME
383            // Going in a random direction means it usually works if we retry a few times
384        case 1: JOYPAD_SET(LEFT); return RC_INPR;
385        case 2: JOYPAD_SET(RIGHT); return RC_INPR;
386        case 3: JOYPAD_SET(UP); return RC_INPR;
387        case 4: JOYPAD_SET(DOWN); return RC_INPR;
388        case 5:
389            if (task->timeout == 1)
390                return RC_DONE;
391        }
392        break;
393    case TASK_GOTO_POINT:
394        switch (task->state) {
395        case 0:
396            rc = ap_pathfind_node(task->node, true, 0);
397            if (rc < 0) {
398                LOG("ap_pathfind_node failed");
399                return RC_FAIL;
400            }
401            task->timeout = rc + 32;
402            task->state++;
403        case 1:
404        case 2:
405            /*
406            if (task->state == 2) {
407                JOYPAD_CLEAR(A);
408                task->state = 1;
409            } else if (*ap_ram.push_timer != 0x20) {
410                // TODO: Need a way of peaking ahead here to see if we need to use hammer
411                // then we can insert a TASK_SET_INVENTORY
412                JOYPAD_SET(A);
413                task->state = 2;
414            } else if (*ap_ram.carrying_bit7) {
415                JOYPAD_SET(A);
416                task->state = 2;
417            }
418            */
419            rc = ap_task_follow_targets(task, joypad);
420            if (rc != RC_INPR) return rc;
421        }
422        break;
423    case TASK_OPEN_CHEST:
424        LOG("timeout: %d; state: %d; touching: %x; push: %x; item_recv_method: %x; recving_item: %#x", task->timeout, task->state, *ap_ram.touching_chest, *ap_ram.push_timer, *ap_ram.item_recv_method, *ap_ram.recving_item);
425        switch (task->state) {
426        case 0:
427            task->timeout = 64;
428            task->state++;
429        case 1:
430            JOYPAD_SET(UP);
431            if (!(*ap_ram.touching_chest & 0xF) && (*ap_ram.push_timer == 0x20)) {
432                break;
433            }
434            task->state++;
435        case 2:
436        case 3:
437            JOYPAD_CLEAR(UP);
438            if (task->state == 2) { JOYPAD_SET(A); task->state = 3; }
439            else { JOYPAD_CLEAR(A); task->state = 2; }
440            if (*ap_ram.item_recv_method == 1) {
441                ap_item_loc_set_raw(task->node->item_loc, *ap_ram.recving_item);
442                task->timeout = 64;
443                task->state = 4;
444            }
445            break;
446        case 4:
447            if (*ap_ram.item_recv_method != 1) return RC_DONE;
448        }
449        break;
450    case TASK_TALK_NPC:
451        LOG("timeout: %d; state: %d; recving: %x; push: %x; item_recv_method: %x; link_state: %x; recving_item: %#x", task->timeout, task->state, *ap_ram.recving_item, *ap_ram.push_timer, *ap_ram.item_recv_method, *ap_ram.link_state, *ap_ram.recving_item);
452        switch (task->state) {
453        case 0:
454            task->timeout = 64;
455            task->state++;
456        case 1:
457            JOYPAD_SET(UP);
458            JOYPAD_MASH(A, 1);
459            if (*ap_ram.link_state == LINK_STATE_RECVING_ITEM || *ap_ram.link_state == LINK_STATE_RECVING_ITEM2 || *ap_ram.recving_item) {
460                // Holding item (uncle)
461                LOGB("holding item");
462                ap_item_loc_set_raw(task->node->item_loc, *ap_ram.recving_item);
463                task->timeout = 128;
464                task->state++;
465            }
466            if (task->node->sprite_type == 0x73) {
467                // Return success early from the uncle
468                return RC_DONE;
469            }
470            break;
471        case 2:
472            JOYPAD_CLEAR(UP);
473            if (*ap_ram.link_state != LINK_STATE_RECVING_ITEM && *ap_ram.link_state != LINK_STATE_RECVING_ITEM2) {
474                return RC_DONE;
475            }
476            break;
477        }
478        break;
479    case TASK_LIFT_POT:
480        switch (task->state) {
481        case 0:
482            rc = ap_pathfind_node(task->node, true, 0);
483            if (rc < 0) {
484                LOG("ap_pathfind_node failed");
485                return RC_FAIL;
486            }
487            task->timeout = rc + 32;
488            task->state++;
489        case 1:
490        case 2:
491            if (task->state == 1) { JOYPAD_SET(A); task->state = 2; }
492            else { JOYPAD_CLEAR(A); task->state = 1; }
493            rc = ap_task_follow_targets(task, joypad);
494            if (rc != RC_INPR) return rc;
495        }
496        break;
497    case TASK_TRANSITION:
498        INFO("cross: st=%d timeout=%d dir=%s", task->state, task->timeout, dir_names[task->direction]);
499        switch (task->state) {
500        case 0:
501            task->timeout = 200;
502            task->state++;
503        case 1:
504        case 2:
505            if (screen != task->node->screen) {
506                task->timeout = 8;
507                task->state = 3;
508            } else {
509                if (task->node->tile_attr == 0x55 && *ap_ram.push_timer != 0x20) {
510                    JOYPAD_SET(A);
511                    if (task->state == 1) {
512                        task->timeout += 500;
513                        task->state = 2;
514                    }
515                }
516                ap_joypad_setdir(joypad, task->direction);
517                break;
518            }
519        case 3:
520        case 4:
521            if (submodule_index == 0x10) {
522                task->timeout++;
523                break;
524            }
525            if (task->node->tile_attr == 0x55 && *ap_ram.push_timer != 0x20) {
526                LOG("Push timer in transition!");
527                JOYPAD_SET(A);
528                if (task->state == 3) {
529                    task->timeout += 500;
530                    task->state = 4;
531                }
532            }
533            if (task->timeout == 1) {
534                if (screen != task->node->screen) {
535                    ap_map_record_transition_from(task->node);
536                    return RC_DONE;
537                    //LOG("transition: %p %p %p", screen, task->node->screen, task->node->adjacent_screen[0]);
538                    //LOG("transition: %s; %s; -", screen->name, task->node->screen->name);
539                    //if (screen == task->node->adjacent_screen[0]) return RC_DONE;
540                }
541                LOG("Failed to transition in time");
542                return RC_FAIL;
543            }
544        }
545        break;
546    case TASK_SET_INVENTORY:
547        INFO("inv to %u", task->item);
548        if (*ap_ram.module_index != 0x0E && *ap_ram.current_item == task->item) {
549            return RC_DONE;
550        }
551        switch (task->state) {
552        case 0:
553            task->timeout = 200;
554            task->state++;
555        case 1:
556            if (*ap_ram.module_index != 0x0E) {
557                if (task->timeout & 1) {
558                    JOYPAD_SET(START);
559                }
560                break;
561            }
562            task->state++;
563        case 2:
564            if (*ap_ram.current_item != task->item) {
565                if (task->timeout & 1) {
566                    // XXX: Actually navigate to the right item
567                    JOYPAD_SET(LEFT);
568                }
569                break;
570            }
571            task->state++;
572        case 3: 
573            if (task->timeout & 1) {
574                JOYPAD_SET(START);
575            }
576        }
577        break;
578    case TASK_BOMB:;
579        bool active_bomb = false;
580        for (size_t i = 0; i < N_ANCILLIA; i++) {
581            if (ap_ancillia[i].type == 0x07) {
582                active_bomb = true;
583                break;
584            }
585        }
586        switch (task->state) {
587        case 0:
588            if (*ap_ram.current_item != INVENTORY_BOMBS) {
589                LOG("Bombs not equipped");
590                return RC_FAIL;
591            }
592            if (*ap_ram.inventory_bombs == 0) {
593                LOG("No bombs in inventory");
594                return RC_FAIL;
595            }
596            task->timeout = 200;
597            task->state++;
598            if (task->node != NULL && task->node->adjacent_direction) {
599                ap_joypad_setdir(joypad, task->node->adjacent_direction);
600            }
601            break;
602        case 1:
603            JOYPAD_SET(Y);
604            task->state++;
605            break;
606        case 2:
607            JOYPAD_CLEAR(Y);
608            if (active_bomb) {
609                task->state++;
610            }
611            break;
612        case 3:
613            // TODO: Dodge the bomb
614            if (!active_bomb) {
615                return RC_DONE;
616            }
617            break;
618        }
619        break;
620    case TASK_SCRIPT_SEQUENCE:
621        switch (task->state) {
622        case 0:
623            rc = ap_set_script(task->node->script);
624            if (rc < 0) {
625                LOG("ap_set_script failed: %s", task->node->script->sequence);
626                return RC_FAIL;
627            }
628            task->timeout = rc + 32;
629            task->state++;
630        case 1:
631            rc = ap_task_follow_targets(task, joypad);
632            if (rc != RC_INPR) return rc;
633        }
634        break;
635    case TASK_SCRIPT_KILLALL:
636    case TASK_SCRIPT_KILLDROPS:
637        if (*ap_ram.inventory_sword == 0) {
638            ap_req_require(&ap_active_goal->req, 0, REQUIREMENT_SWORD);
639            return RC_FAIL;
640        }
641        if (task->state == -100) {
642            if (task->timeout == 1) {
643                ap_update_map_screen(true);
644                return RC_DONE;
645            }
646            break;
647        }
648        if (ap_ram.overlord_types[7] == 0x19) {
649            if (*ap_ram.room_chest_state & 0x80) {
650                return RC_DONE;
651            }
652            // Wait for armos knights to spawn
653            //task->timeout = 2;
654            //if (!ap_sprites[0].active) {
655            //    break;
656            //}
657        }
658        bool no_sword = false;
659        if (task->state == 0 || task->timeout == 1) {
660            size_t target = -1;
661            for (size_t i = 0; i < 16; i++) {
662                if (!ap_sprites[i].active)
663                    continue;
664                if (!XYIN(ap_sprites[i].tl, screen->tl, screen->br))
665                    continue;
666                if (task->type == TASK_SCRIPT_KILLDROPS && ap_sprites[i].drop == 0)
667                    continue;
668                target = i;
669                LOGB("Targeting sprite #%zu", target);
670                break;
671            }
672            if (target == (size_t)-1) {
673                // Almost done; wait ~120 frames for loot to drop
674                LOG("Done killing; waiting 128 frames for loot to drop");
675                task->state = -100;
676                task->timeout = 128;
677                break;
678            }
679            if (ap_sprites[target].attrs & SPRITE_ATTR_VBOW) {
680                if (*ap_ram.current_item != INVENTORY_BOW) {
681                    struct ap_task * new_task = ap_task_prepend(); 
682                    new_task->type = TASK_SET_INVENTORY;
683                    new_task->item = INVENTORY_BOW;
684                    snprintf(new_task->name, sizeof new_task->name, "set bow to kill %zu", target);
685
686                    task->state = 0;
687                    task->timeout = 0;
688                    return RC_INPR;
689                }
690                if (ap_sprites[target].type == 0x84) {
691                    if (ap_sprites[target].interaction == 0x07) {
692                        JOYPAD_MASH(Y, 0x04);
693                    }
694                } else {
695                    JOYPAD_MASH(Y, 0x08);
696                }
697
698                no_sword = true;
699            }
700            rc = ap_pathfind_sprite(target);
701            if (rc == RC_FAIL) {
702                LOG("ap_pathfind_sprite failed");
703                return RC_FAIL;
704            }
705            task->timeout = MIN(20, MAX(8, rc));
706            task->state++;
707        } 
708        if (task->state == 8000) { // Actual timeout
709            LOG("timeout");
710            return RC_FAIL;
711        }
712        rc = ap_task_follow_targets(task, joypad);
713        if (rc == RC_FAIL) {
714            LOG("ap_follow_targets failed");
715            return RC_FAIL;
716        }
717        if (no_sword) {
718            JOYPAD_CLEAR(B);
719        }
720        break;
721    case TASK_NONE:
722    default:
723        LOG("unknown task type %d", task->type);
724        assert_bp(false);
725        return RC_FAIL;
726    }
727    if (task->timeout-- <= 0) {
728        LOG("task timeout: " PRITASK, PRITASKF(task));
729        return RC_FAIL;
730    }
731    return RC_INPR;
732}
733
734static int
735ap_goal_score(struct ap_goal * goal, int max_score)
736{
737    assert(goal != NULL);
738
739    struct ap_screen * screen = ap_update_map_screen(false);
740
741    /*
742    bool is_accessible = false;
743    for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
744        if (node->type == NODE_TRANSITION && node->adjacent_node != NULL) {
745            is_accessible = true;
746            break;
747        }
748    }
749    if (!is_accessible) {
750        return GOAL_SCORE_UNSATISFIABLE;
751    }
752    */
753    if (!ap_req_is_satisfied(&goal->req)) {
754        return GOAL_SCORE_UNSATISFIABLE;
755    }
756
757    int score = 0;
758
759    if (*ap_ram.inventory_sword == 0 && goal->type != GOAL_NPC) {
760        score += 10000;
761    }
762    /*
763    if (*ap_ram.inventory_sword == 0 && !(goal->node == NULL || goal->node->sprite_type == 0x73 || goal->node->sprite_subtype == 0x100)) {
764        //score += 1000000;
765        return GOAL_SCORE_UNSATISFIABLE;
766    }
767    */
768
769    //if (goal->type != GOAL_SCRIPT && goal->type != GOAL_NPC) {
770    //    score += 1000000;
771    //}
772    score += goal->attempts * 100; //1000000;
773    switch (goal->type) {
774    case GOAL_PICKUP:
775        score += 0;
776        if (goal->node->screen != screen) {
777            return GOAL_SCORE_UNSATISFIABLE;
778        }
779        if (ap_map_attr(goal->node->tl) == 0x27) {
780            return GOAL_SCORE_COMPLETE;
781        }
782        break;
783    case GOAL_CHEST:;
784        uint8_t attr = goal->node->tile_attr;
785        assert(attr >= 0x58 && attr <= 0x5D);
786        assert(goal->node->screen->dungeon_room != (uint16_t) -1);
787        uint16_t room_state = ap_ram.sram_room_state[goal->node->screen->dungeon_room];
788        if (room_state & (1 << (attr - 0x58 + 4))) {
789            return GOAL_SCORE_COMPLETE;
790        }
791        break;
792    case GOAL_NPC:
793        //score += 1000;
794        break;
795    case GOAL_SCRIPT:
796        break;
797    case GOAL_EXPLORE:
798        //if (goal->node->screen->name[0] != 'H') {
799        //    score += 100000;
800        //}
801        //if (goal->node->type != NODE_SWITCH)
802            //score += 1000;
803        if (goal->node->adjacent_node != NULL) {
804            return GOAL_SCORE_COMPLETE;
805        }
806        break;
807    case GOAL_ITEM:
808        if (ap_ram.inventory_base[goal->item]) {
809            return GOAL_SCORE_COMPLETE;
810        } else {
811            return GOAL_SCORE_UNSATISFIABLE;
812        }
813        break;
814    default:
815        return GOAL_SCORE_UNSATISFIABLE;
816        break;
817    }
818
819    /*
820    if (ap_graph_is_blocked(&goal->graph)) {
821        return GOAL_SCORE_UNSATISFIABLE;
822    }
823    */
824
825    if (goal->node != NULL) {
826        //struct xy link = ap_link_xy();
827        //int heuristic = ap_path_heuristic(link, goal->node->tl, goal->node->br);
828        int max_distance = max_score - score;
829        if (max_distance <= 0) {
830            return GOAL_SCORE_GT_LIMIT;
831        }
832        int distance = ap_pathfind_node(goal->node, false, max_distance);
833        if (distance < 0) {
834            return GOAL_SCORE_UNSATISFIABLE;
835        } else if (distance > max_distance) {
836            return GOAL_SCORE_GT_LIMIT;
837        }
838        score += distance;
839    }
840
841    return score;
842}
843
844static void
845ap_goal_complete(struct ap_goal * goal)
846{
847    assert(goal != NULL);
848    LOG(TERM_BOLD("Completed goal: ") TERM_GREEN(PRIGOAL), PRIGOALF(goal));
849
850    switch (goal->type) {
851    case GOAL_PICKUP:
852    case GOAL_CHEST:
853    case GOAL_NPC:
854    case GOAL_SCRIPT:
855        //LL_EXTRACT(goal->node->node_parent, goal->node);
856        //free(goal->node);
857        break;
858    default:
859        break;
860    }
861    ap_goal_completed[goal->type]++;
862
863    LL_EXTRACT(goal);
864    //ap_graph_mark_done(&goal->graph);
865    //free(goal);
866    if (ap_active_goal == goal)
867        ap_active_goal = NULL;
868}
869
870static void
871ap_goal_fail(struct ap_goal * goal)
872{
873    assert(goal != NULL);
874    assert_bp(false);
875    LOG(TERM_BOLD("Failed goal: ") TERM_RED(PRIGOAL), PRIGOALF(goal));
876    goal->attempts++;
877    if (goal->attempts > 3) {
878        LOG(TERM_BOLD("Permafailing goal: ") TERM_RED(TERM_BOLD(PRIGOAL)), PRIGOALF(goal));
879        LL_EXTRACT(goal);
880        //ap_graph_extract(&goal->graph);
881    }
882    if (ap_active_goal == goal)
883        ap_active_goal = NULL;
884}
885
886static void
887ap_goal_evaluate()
888{
889    ap_update_map_screen(true);
890    if (ap_active_goal == NULL && !ap_new_goals)
891        return;
892    ap_print_goals(false);
893
894retry_new_goal:;
895    int min_score = INT_MAX;
896    struct ap_goal * min_goal = NULL;
897    for (struct ap_goal * goal = ap_goal_list->next; goal != ap_goal_list; goal = goal->next) {
898        int score = goal->last_score; // ap_goal_score(goal);
899        if (score == GOAL_SCORE_COMPLETE) {
900            struct ap_goal * g = goal;
901            goal = goal->prev;
902            ap_goal_complete(g);
903            continue;
904        }
905        if (score == GOAL_SCORE_UNSATISFIABLE || score == GOAL_SCORE_GT_LIMIT) {
906            continue;
907        }
908        assert(score >= 0);
909        if (score < min_score) {
910            min_score = score;
911            min_goal = goal;
912        }
913    }
914    ap_active_goal = min_goal;
915    if (min_goal == NULL) {
916        //ap_new_goals = false;
917        ap_manual_mode = true;
918        ap_print_map_full();
919        LOGB("No goals available; falling back to manual mode");
920        //assert_bp(false);
921        return;
922    }
923
924    LOG(TERM_BOLD("Active goal: ") TERM_BLUE(PRIGOAL), PRIGOALF(min_goal));
925
926    while (LL_PEEK(ap_task_list) != NULL) {
927        free(LL_POP(ap_task_list));
928    }
929    assert(ap_task_list->next == ap_task_list);
930    assert(ap_task_list->prev == ap_task_list);
931    struct ap_task * task = NULL;
932    
933    // Get to point
934    switch (min_goal->type) {
935    case GOAL_CHEST:
936    case GOAL_PICKUP:
937    case GOAL_NPC:
938    case GOAL_SCRIPT:
939    case GOAL_EXPLORE:;
940        // For debugging: set inventory
941        //task = ap_task_prepend(); 
942        //task->type = TASK_SET_INVENTORY;
943        //task->item = 0x4;
944
945        struct ap_node * node = min_goal->node;
946        int rc = ap_pathfind_node(node, true, 0);
947        if (rc < 0) {
948            ap_goal_fail(min_goal);
949            ap_active_goal = NULL;
950            goto retry_new_goal;
951        }
952
953        uint64_t iter = node->pgsearch.iter;
954        while (node->pgsearch.from != NULL) {
955            assert_bp(node->pgsearch.iter == iter);
956            if (node->screen == node->pgsearch.from->screen) {
957                task = ap_task_prepend(); 
958                task->type = TASK_GOTO_POINT;
959                task->node = node;
960                snprintf(task->name, sizeof task->name, "goto point onscreen");
961            } else {
962                task = ap_task_prepend(); 
963                task->type = TASK_TRANSITION;
964                task->node = node->pgsearch.from;
965                task->direction = node->pgsearch.from->adjacent_direction;
966                snprintf(task->name, sizeof task->name, "transition %s", dir_names[task->direction]);
967            }
968            node = node->pgsearch.from;
969        }
970    default:;
971    }
972
973    switch (min_goal->type) {
974    case GOAL_PICKUP:
975        task = ap_task_append();
976        task->type = TASK_LIFT_POT;
977        task->node = min_goal->node;
978        snprintf(task->name, sizeof task->name, "item");
979        break;
980    case GOAL_CHEST:
981        task = ap_task_append();
982        task->type = TASK_OPEN_CHEST;
983        task->node = min_goal->node;
984        snprintf(task->name, sizeof task->name, "chest");
985        break;
986    case GOAL_EXPLORE:
987        if (min_goal->node->adjacent_direction == 0)
988            break;
989        task = ap_task_append(); 
990        task->type = TASK_TRANSITION;
991        task->node = min_goal->node;
992        task->direction = min_goal->node->adjacent_direction;
993        snprintf(task->name, sizeof task->name, "final transition %s", dir_names[task->direction]);
994        break;
995    case GOAL_NPC:
996        task = ap_task_append();
997        task->type = TASK_TALK_NPC;
998        task->node = min_goal->node;
999        snprintf(task->name, sizeof task->name, "npc");
1000        break;
1001    case GOAL_SCRIPT:;
1002        int item = min_goal->node->script->start_item;
1003        if (item > 0) {
1004            assert(item <= 0xff && ap_inventory_names[item] != NULL);
1005            task = ap_task_append();
1006            task->type = TASK_SET_INVENTORY;
1007            task->item = item;
1008            snprintf(task->name, sizeof task->name, "start item: %s", ap_inventory_names[item]);
1009        }
1010        task = ap_task_append();
1011        task->node = min_goal->node;
1012        enum script_type script_type = task->node->script->type;
1013        switch (task->node->script->type) {
1014        case SCRIPT_SEQUENCE: task->type = TASK_SCRIPT_SEQUENCE; break;
1015        case SCRIPT_KILLALL: task->type = TASK_SCRIPT_KILLALL; break;
1016        case SCRIPT_KILLDROPS: task->type = TASK_SCRIPT_KILLDROPS; break;
1017        default: assert(0);
1018        }
1019        snprintf(task->name, sizeof task->name, "script");
1020        break;
1021    default:
1022        LOG("Invalid goal type: %d", min_goal->type);
1023        assert_bp(false);
1024        break;
1025    }
1026}
1027
1028void
1029ap_plan_evaluate(uint16_t * joypad)
1030{
1031    while (true) {
1032        if (ap_active_goal == NULL) {
1033            ap_goal_evaluate();
1034            if (ap_active_goal == NULL) goto done;
1035            ap_print_tasks();
1036        }
1037
1038        struct ap_task * task = LL_PEEK(ap_task_list);
1039        if (task == NULL) {
1040            ap_goal_complete(ap_active_goal);
1041            task = LL_PEEK(ap_task_list);
1042            if (task == NULL) goto done;
1043        }
1044
1045        enum rc rc = ap_task_evaluate(task, joypad);
1046        if (rc != RC_INPR) {
1047            ap_print_tasks();
1048        }
1049        switch (rc) {
1050        case RC_DONE:
1051            LOG("task complete: " TERM_GREEN(PRITASK), PRITASKF(task));
1052            free(LL_POP(ap_task_list));
1053            break;
1054        case RC_FAIL:
1055            LOG("task failed: " TERM_RED(PRITASK), PRITASKF(task));
1056            ap_goal_fail(ap_active_goal);
1057            break;
1058        case RC_INPR:;
1059            goto done;
1060        }
1061    }
1062
1063done:;
1064    // Debug
1065    const char *goal_name = "(no goal)";
1066    if (ap_active_goal != NULL) {
1067        goal_name = ap_goal_type_names[ap_active_goal->type];
1068    }
1069    const char *task_name = "(no task)";
1070    int task_timeout = 0;
1071    if (LL_PEEK(ap_task_list) != NULL) {
1072        task_name = ap_task_type_names[LL_PEEK(ap_task_list)->type];
1073        task_timeout = LL_PEEK(ap_task_list)->timeout;
1074    }
1075    struct ap_screen * screen = ap_update_map_screen(NULL);
1076    INFO("Plan: %s via %s (%d)", goal_name, task_name, task_timeout);
1077}
1078
1079void
1080ap_plan_init()
1081{
1082}