1#include <string.h>
2#include "ap_map.h"
3#include "ap_item.h"
4#include "ap_math.h"
5#include "ap_macro.h"
6#include "ap_snes.h"
7#include "ap_plan.h"
8#include "pq.h"
9#include "pm.h"
10
11static struct ap_screen * map_screens[0x100 * 0x100];
12static bool map_screen_mask_x[0x100];
13static bool map_screen_mask_y[0x100];
14static volatile const struct ap_screen * last_screen = NULL;
15
16static struct ap_target {
17 struct xy tl;
18 uint16_t joypad;
19 uint16_t joypad_mask;
20} ap_targets[2048];
21static size_t ap_target_count = 0;
22static int ap_target_timeout = 0;
23static int ap_target_subtimeout = 0;
24static bool ap_target_scripted = false;
25static struct xy ap_target_dst_tl;
26static struct xy ap_target_dst_br;
27static uint8_t ap_target_sprite_index = 0;
28static struct ap_screen * ap_target_screen;
29
30const char * const ap_node_type_names[] = {
31#define X(type) [CONCAT(NODE_, type)] = #type,
32NODE_TYPE_LIST
33#undef X
34};
35
36static const struct ap_script ap_scripts[] = {
37 {
38 .start_tl = XY(0x9af8, 0x21c0),
39 .start_item = -1,
40 .sequence = "^^<^v>>^<^",
41 .type = SCRIPT_SEQUENCE,
42 .name = "Dam Chest Block Puzzle",
43 },
44 {
45 .start_tl = XY(0xaaf0, 0x2340),
46 .start_item = INVENTORY_BOMBS,
47 .sequence = "Yvvv>v<vv^^>>>vv<UA>^^<<<^<<vvv>vv>>>>>",
48 .type = SCRIPT_SEQUENCE,
49 .name = "Blind's House Block Puzzle",
50 },
51 {
52 .start_tl = XY(0x52f8, 0x0e60),
53 .start_item = -1,
54 .sequence = NULL,
55 .type = SCRIPT_KILLDROPS,
56 .name = "HC kill guard for key",
57 },
58 /*
59 {
60 .start_tl = XY(0x4878, 0x0fb0),
61 .start_item = -1,
62 .sequence = NULL,
63 .type = SCRIPT_KILLALL,
64 .name = "HC kill green guard for doors",
65 },
66 {
67 .start_tl = XY(0x4950, 0x0f80),
68 .start_item = -1,
69 .sequence = NULL,
70 .type = SCRIPT_KILLALL,
71 .name = "HC kill blue guard for door",
72 },
73 */
74 {
75 .start_tl = XY(0x4250, 0x1060),
76 .start_item = -1,
77 .sequence = NULL,
78 .type = SCRIPT_KILLDROPS,
79 .name = "HC kill miniboss free Zelda",
80 },
81 {
82 .start_tl = XY(0x4330, 0x1880),
83 .start_item = -1,
84 .sequence = NULL,
85 .type = SCRIPT_KILLDROPS,
86 .name = "AgTower small key",
87 },
88 {
89 .start_tl = XY(0x4278, 0x173C),
90 .start_item = -1,
91 .sequence = NULL,
92 .type = SCRIPT_KILLDROPS,
93 .name = "AgTower small key 2",
94 },
95 {
96 .start_tl = XY(0x4190, 0x0958),
97 .start_item = -1,
98 .sequence = "<<>",
99 .type = SCRIPT_SEQUENCE,
100 .name = "AgTower push statues",
101 },
102 {
103 .start_tl = XY(0x4278, 0x063D),
104 .start_item = -1,
105 .sequence = "UB><",
106 .type = SCRIPT_SEQUENCE,
107 .name = "AgTower open curtain",
108 },
109 {
110 .start_tl = XY(0x4278, 0x05C8),
111 .start_item = -1,
112 .sequence = NULL,
113 .type = SCRIPT_KILLALL,
114 .name = "AgTower boss",
115 },
116 {
117 .start_tl = XY(0x0058, 0x0681),
118 .start_item = -1,
119 .sequence = "DDDDDD",
120 .type = SCRIPT_SEQUENCE,
121 .name = "Jump into Kak well",
122 },
123 /*
124 {
125 .start_tl = XY(0x5a78, 0x25c0),
126 .start_item = -1,
127 .sequence = NULL,
128 .type = SCRIPT_KILLALL,
129 .name = "Mini Moldorm Cave",
130 },
131 */
132 /*
133 {
134 .start_tl = XY(0x8278, 0x1580),
135 .start_item = -1,
136 .sequence = NULL,
137 .type = SCRIPT_KILLALL,
138 .name = "EP Stalfos Room",
139 },
140 */
141 {
142 .start_tl = XY(0x8af8, 0x1390),
143 .start_item = -1,
144 .sequence = NULL,
145 .type = SCRIPT_KILLDROPS,
146 .name = "EP Igor Key",
147 },
148 {
149 .start_tl = XY(0x8378, 0x19B8),
150 .start_item = INVENTORY_BOW,
151 .sequence = NULL,
152 .type = SCRIPT_KILLALL,
153 .name = "EP Armos Knights Boss",
154 },
155 {
156 .start_tl = XY(0x83c0, 0x1b80),
157 .start_item = INVENTORY_BOW,
158 .sequence = NULL,
159 .type = SCRIPT_KILLALL,
160 .name = "EP Red Igor Room",
161 },
162 /* Need to bring old man to "door 0x30"
163 {
164 .start_tl = XY(0x4278, 0x1fc6),
165 .start_item = -1,
166 .sequence = "^^^^^^",
167 .type = SCRIPT_SEQUENCE,
168 .name = "Dark cave ledge jump",
169 },
170 */
171};
172
173static bool add_explore_goals_global = true;
174static const struct ap_screen_info {
175 uint16_t id;
176 char name[40];
177 bool add_explore_goals;
178 bool include_borders;
179} ap_screen_infos[] = {
180 // Light Overworld
181 { .id = 0x0402, .name = "North of Kak", },
182 { .id = 0x0406, .name = "Sanctuary Yard", },
183 { .id = 0x0408, .name = "Graveyard", },
184 { .id = 0x040c, .name = "Witches' Yard", },
185 { .id = 0x0606, .name = "Castle Yard", },
186 { .id = 0x060c, .name = "Ruins", },
187 { .id = 0x0600, .name = "Kak Village", .add_explore_goals = true, },
188 { .id = 0x0804, .name = "Smith's Yard", .add_explore_goals = true, },
189 { .id = 0x0a00, .name = "Maze Race" },
190 { .id = 0x0a02, .name = "Library Yard", .add_explore_goals = true, },
191 { .id = 0x0a04, .name = "Flute Grove", },
192 { .id = 0x0a08, .name = "Link's Yard", },
193 { .id = 0x0a68, .name = "Well Uncle", },
194 { .id = 0x0b68, .name = "Well Chest", },
195 { .id = 0x0c0a, .name = "Fortune Shore", },
196 // Overworld Interiors
197 { .id = 0x2161, .name = "Link's House", },
198 { .id = 0x2178, .name = "Library", },
199 { .id = 0x2188, .name = "Witches' Hut", },
200 { .id = 0x2198, .name = "Dam Chest", },
201 { .id = 0x2550, .name = "Fortune Teller", },
202 { .id = 0x1d58, .name = "Bat Cave Exit", },
203 { .id = 0x2548, .name = "Smiths' House", },
204 { .id = 0x1f68, .name = "Maze Race Entrance", },
205 { .id = 0x2388, .name = "Blind's House", .add_explore_goals = true, },
206 { .id = 0x23a8, .name = "Blind's Basement", .add_explore_goals = true, },
207 { .id = 0x22a8, .name = "Blind's Storage",},
208 { .id = 0x1e40, .name = "DM Dark Cave 1",},
209 { .id = 0x2369, .name = "Fairy Fountain; Stateful!!!",},
210 { .id = 0x2140, .name = "Master Sword Pedestal", },
211 // Hyrule Castle
212 { .id = 0x0c48, .name = "HC Entrance", },
213 { .id = 0x0e50, .name = "HC First Key", .add_explore_goals = true},
214 { .id = 0x0f50, .name = "HC Walkway", .include_borders = true, },
215 { .id = 0x0f48, .name = "HC Green Guard"},
216 { .id = 0x1040, .name = "HC Zelda Jail"},
217 { .id = 0x0650, .name = "Sewer Key Door" },
218 // Eastern Palace
219 { .id = 0x1988, .name = "EP Entrance", },
220 { .id = 0x1888, .name = "EP Hall 1", },
221 { .id = 0x1688, .name = "EP Dodgeball", },
222 { .id = 0x1488, .name = "EP Bigchest", },
223 { .id = 0x1490, .name = "EP Catwalk", },
224 { .id = 0x1491, .name = "EP 5 pots", },
225 { .id = 0x1591, .name = "EP Chest&Ledge", },
226 { .id = 0x1481, .name = "EP Crossover", },
227 { .id = 0x1580, .name = "EP Stalfos", },
228 { .id = -1 },
229};
230
231
232struct point_state {
233 // Parts that need to be cleared each time this ap_pathfind_local is called
234 struct point_state * from;
235 uint32_t gscore;
236 uint32_t fscore;
237
238 // Parts that can be cached for the same (screen, frame #)
239 struct xy xy;
240 uint16_t tile_attrs;
241 uint8_t raw_tile;
242 uint8_t ledge;
243 uint8_t corner;
244 uint32_t cost;
245};
246
247static int
248ap_pathfind_local(struct ap_screen * screen, struct xy start_xy, struct xy destination_tl, struct xy destination_br, bool commit);
249static void
250ap_print_pathfind_local_state(struct point_state *buf, struct xy grid);
251
252static void
253ap_map_add_sprite_nodes_to_screen(struct ap_screen * screen);
254
255static struct xy
256ap_box_edge(struct xy tl, struct xy br, int dir) {
257 // Return a point that is on the `dir` edge of the bounding box `tl, br`
258 struct xy dxy = dir_dxy[dir];
259 return XY(
260 ((dir_dx[dir] <= 0) ? tl.x : br.x),
261 ((dir_dy[dir] <= 0) ? tl.y : br.y));
262}
263
264struct xy
265ap_link_xy()
266{
267 // Returns the effective tl coordinate that link interacts with
268 // Which is 8 pixels below his head
269 struct xy link = XY(*ap_ram.link_x, *ap_ram.link_y + 8);
270 if (*ap_ram.in_building) {
271 link.x = ((link.x & ~0x1FF) << 2) | (link.x & 0x1FF);
272 link.x += 0x4000;
273 if (!*ap_ram.link_lower_level) {
274 link.x += 0x200;
275 }
276 } else if (*ap_ram.overworld_dark) {
277 link.y += 0x1000;
278 }
279 return link;
280}
281
282static void
283ap_map_room_bounds(struct xy base, struct xy * tl, struct xy * br) {
284 // Only works in current "room"
285 uint8_t layout = *ap_ram.room_layout;
286 struct xy size = XY(0x200, 0x200);
287 bool in_right = (base.x & 0x100) != 0;
288 bool in_bottom = (base.y & 0x100) != 0;
289 switch (layout >> 2) {
290 case ROOM_LAYOUT_A_B_C_D: size = XY(0x100, 0x100); break;
291 case ROOM_LAYOUT_AC_BD: size = XY(0x100, 0x200); break;
292 case ROOM_LAYOUT_AB_CD: size = XY(0x200, 0x100); break;
293 case ROOM_LAYOUT_ABCD: size = XY(0x200, 0x200); break;
294 case ROOM_LAYOUT_A_BD_C: size = XY(0x100, (in_right) ? 0x200 : 0x100); break;
295 case ROOM_LAYOUT_AC_B_D: size = XY(0x100, (in_right) ? 0x100 : 0x200); break;
296 case ROOM_LAYOUT_A_B_CD: size = XY((in_bottom) ? 0x200 : 0x100, 0x100); break;
297 case ROOM_LAYOUT_AB_C_D: size = XY((in_bottom) ? 0x100 : 0x200, 0x100); break;
298 default: assert_bp(false);
299 }
300 size = XYOP1(size, - 1);
301 struct xy mask = XY(~size.x, ~size.y);
302 *tl = XYOP2(base, &, mask);
303 *br = XYOP2(*tl, +, size);
304}
305
306void
307ap_map_bounds(struct xy * topleft, struct xy * bottomright)
308{
309 if (*ap_ram.in_building) {
310 struct xy link = ap_link_xy();
311 link.y = CAST16(link.y - 8);
312 ap_map_room_bounds(link, topleft, bottomright);
313 } else {
314 topleft->x = (uint16_t) (*ap_ram.map_x_offset * 8);
315 topleft->y = (uint16_t) (*ap_ram.map_y_offset);
316 bottomright->x = (uint16_t) (topleft->x + ((*ap_ram.map_x_mask * 8) | 0xF));
317 bottomright->y = (uint16_t) (topleft->y + (*ap_ram.map_y_mask | 0xF));
318 if (*ap_ram.overworld_dark) {
319 topleft->y += 0x1000;
320 bottomright->y += 0x1000;
321 }
322 }
323}
324
325uint16_t
326ap_map_attr(struct xy xy)
327{
328 struct ap_screen * screen = map_screens[XYMAPSCREEN(xy)];
329 if (screen == NULL) {
330 //LOG("null screen on xy:" PRIXYV, PRIXYVF(xy));
331 return 0;
332 }
333
334 // Read from cache
335 assert(XYIN(xy, screen->tl, screen->br));
336 uint16_t y = (xy.y - screen->tl.y) / 8;
337 uint16_t x = (xy.x - screen->tl.x) / 8;
338 return screen->attr_cache[y][x];
339}
340
341static uint16_t
342ap_link_tile_attr(struct xy link)
343{
344 uint16_t tile = 0;
345 tile |= ap_tile_attrs[ap_map_attr(XYOP2(link, +, XY(0, 0)))];
346 tile |= ap_tile_attrs[ap_map_attr(XYOP2(link, +, XY(0, 8)))];
347 tile |= ap_tile_attrs[ap_map_attr(XYOP2(link, +, XY(8, 0)))];
348 tile |= ap_tile_attrs[ap_map_attr(XYOP2(link, +, XY(8, 8)))];
349 return tile;
350}
351
352static uint16_t
353ap_map_attr_from_ram(struct xy point)
354{
355 if (*ap_ram.in_building) {
356 assert(XYINDOORS(point));
357 if (point.x & 0x200) {
358 return ap_ram.dngn_bg2_tattr[XYMAP8(point)];
359 } else {
360 // lower level
361 return ap_ram.dngn_bg1_tattr[XYMAP8(point)];
362 }
363 } else {
364#define LOAD(x) (*(uint16_t *)ap_emu->base((x) | 0x7E0000))
365#define LOAD2(x) (*(uint16_t *)ap_emu->base((x) ))
366 //uint16_t six = ((point.y - LOAD(0x708)) & LOAD(0x70A)) << 3;
367 //uint16_t x = (((point.x/8) - LOAD(0x70C)) & LOAD(0x70E)) | six;
368 uint16_t a, x, m06, tile;
369
370//CODE_008830: A5 00 LDA $00 ;
371 a = point.y;
372//CODE_008832: 38 SEC ;
373//CODE_008833: ED 08 07 SBC $0708 ;
374 a -= LOAD(0x708);
375//CODE_008836: 2D 0A 07 AND $070A ;
376 a &= LOAD(0x70A);
377//CODE_008839: 0A ASL A ;
378//CODE_00883A: 0A ASL A ;
379//CODE_00883B: 0A ASL A ;
380 a <<= 3;
381//CODE_00883C: 85 06 STA $06 ;
382 m06 = a;
383//CODE_00883E: A5 02 LDA $02 ;
384 a = point.x / 8;
385//CODE_008840: 38 SEC ;
386//CODE_008841: ED 0C 07 SBC $070C ;
387 a -= LOAD(0x70C);
388//CODE_008844: 2D 0E 07 AND $070E ;
389 a &= LOAD(0x70E);
390//CODE_008847: 05 06 ORA $06 ;
391 a |= m06;
392//CODE_008849: AA TAX ;
393 x = a;
394//CODE_00884A: BF 00 20 7E LDA $7E2000,x ;
395 a = tile = LOAD2(0x7E2000 + x);
396//CODE_00884E: 0A ASL A ;
397//CODE_00884F: 0A ASL A ;
398 a <<= 2;
399//CODE_008850: 85 06 STA $06 ;
400 m06 = a;
401//CODE_008852: A5 00 LDA $00 ;
402 a = point.y;
403//CODE_008854: 29 08 00 AND #$0008 ;
404 a &= 0x8;
405//CODE_008857: 4A LSR A ;
406//CODE_008858: 4A LSR A ;
407 a >>= 2;
408//CODE_008859: 04 06 TSB $06 ;
409 m06 |= a;
410//CODE_00885B: A5 02 LDA $02 ;
411 a = point.x / 8;
412//CODE_00885D: 29 01 00 AND #$0001 ;
413 a &= 0x1;
414//CODE_008860: 05 06 ORA $06 ;
415 a |= m06;
416//CODE_008862: 0A ASL A ;
417 a <<= 1;
418//CODE_008863: AA TAX ;
419 x = a;
420//CODE_008864: BF 00 80 0F LDA.l DATA_0F8000,x ;
421 a = LOAD2(0xF8000 + x);
422//CODE_008868: 85 06 STA $06 ;
423 m06 = a;
424//CODE_00886A: 29 FF 01 AND #$01FF ;
425 a &= 0x1ff;
426//CODE_00886D: AA TAX ;
427 x = a;
428//CODE_00886E: BF 59 94 0E LDA.l DATA_0E9459,x ;
429 a = LOAD2(0xFFD94 + x);
430//CODE_008872: E2 30 SEP #$30 ;
431 a &= 0xFF;
432//CODE_008874: C9 10 CMP #$10 ;
433//CODE_008876: 90 0F BCC CODE_008887 ;
434//CODE_008878: C9 1C CMP #$1C ;
435//CODE_00887A: B0 0B BCS CODE_008887 ;
436 //if (a < 0x10 || a >= 0x1C) return a;
437 if (a >= 0x10 && a < 0x1C) {
438//CODE_00887C: 85 06 STA $06 ;
439 m06 = (m06 & 0xFF00) | (a & 0xFF);
440//CODE_00887E: A5 07 LDA $07 ;
441 a = (m06 & 0xFF) >> 8;
442//CODE_008880: 29 40 AND #$40 ;
443 a &= 0x40;
444//CODE_008882: 0A ASL A ;
445//CODE_008883: 2A ROL A ;
446//CODE_008884: 2A ROL A ;
447 a <<= 3;
448 a = (a & 0xF8) | ((a >> 8) & 0x7); // XXX is this right w/ carry?
449//CODE_008885: 05 06 ORA $06 ;
450 a |= m06 & 0xFF;
451//CODE_008887: 6B RTL ;
452 }
453 //return a;
454
455 // Patch: make 0x27 always mean a hammerable peg; fences etc turned to 0x01
456 if (a == 0x27 && tile != 0x021B) {
457 return 0x01;
458 }
459
460 return a;
461
462/*
463 uint16_t cy = (uint16_t) (point.y - *ap_ram.map_y_offset) & *ap_ram.map_y_mask;
464 uint16_t cx = (uint16_t) ((point.x / 8) - *ap_ram.map_x_offset) & *ap_ram.map_x_mask;
465 uint16_t offset = (uint16_t) (cy << 3) | cx;
466 uint16_t map16 = (uint16_t) (ap_ram.over_map16[offset/2] << 2);
467 uint16_t q = (uint16_t) (((point.y & 0x8) >> 2) | ((point.x & 0x8) >> 3));
468 uint16_t x = (uint16_t) (map16 | q);
469 uint16_t af = ((uint16_t *) ap_emu->base(0x0F8000))[x];
470 uint8_t a = ap_ram.over_tattr[af & 0x1ff];
471 if (a < 0x10 || a > 0x1C) return a;
472 return 0xff;
473 */
474 }
475}
476
477static bool
478ap_screen_refresh_cache(struct ap_screen * screen)
479{
480 bool change = false;
481 for (uint16_t y = 0; y < 0x80; y++) {
482 struct xy xy;
483 xy.y = screen->tl.y + 8 * y;
484 if (xy.y > screen->br.y) break;
485 for (uint16_t x = 0; x < 0x80; x++) {
486 xy.x = screen->tl.x + 8 * x;
487 if (xy.x > screen->br.x) break;
488 uint16_t attr = ap_map_attr_from_ram(xy);
489 if (attr != screen->attr_cache[y][x]) {
490 screen->attr_cache[y][x] = attr;
491 change = true;
492 }
493 }
494 }
495 return change;
496}
497
498struct xy
499ap_map16_to_xy(struct xy tl, uint16_t map16)
500{
501 struct xy xy;
502 //xy.x = tl.x + ((map16 & 0x03F) << 4);
503 //xy.y = tl.y + ((map16 & 0xFC0) >> 2);
504 xy.x = tl.x + ((map16 & 0x07E) << 3) + 8;
505 xy.y = tl.y + ((map16 & 0x1F80) >> 3) + 16;
506 if (XYEQ(tl, XY(0x0c00, 0x0600))) {
507 // XXX: Not sure why this correction is nessassary?
508 //xy = XYOP2(xy, -, XY(8, 16));
509 xy.x = tl.x + ((map16 & 0x07F) << 3);
510 xy.y = tl.y + ((map16 & 0xFC0) >> 3);
511 }
512 return xy;
513}
514
515struct xy
516ap_tilemap_to_xy(struct xy tl, uint16_t tilemap)
517{
518 assert_bp(XYINDOORS(tl));
519 assert_bp(tilemap < 0x4000);
520 // TODO: What do bits 0x0040 and 0x0001 do?
521 //assert_bp((tilemap & 0x0041) == 0);
522
523 struct xy xy = XYOP1(tl, &~0x1FF);
524 if (tilemap & 0x2000) {
525 xy = XYTOLOWER(xy);
526 } else {
527 xy = XYTOUPPER(xy);
528 }
529 xy.x += ((tilemap & 0x007E) << 2) + 8;
530 xy.y += ((tilemap & 0x1F80) >> 4) + 16;
531 return xy;
532}
533
534void
535ap_print_map_screen_pair() {
536 struct xy link = ap_link_xy();
537 ap_print_map_screen(map_screens[XYMAPSCREEN(link)]);
538 if (XYINDOORS(link)) {
539 ap_print_map_screen(map_screens[XYMAPSCREEN(XYFLIPBG(link))]);
540 }
541}
542
543void
544ap_print_map_screen(struct ap_screen * screen)
545{
546 FILE * mapf = NONNULL(fopen("map", "w"));
547 FILE * mapimg = NONNULL(fopen("map.pbm.tmp", "w"));
548
549 struct xy link = ap_link_xy();
550 struct xy link_tl = link;
551 struct xy link_br = XYOP1(link, + 15);
552 if (screen == NULL) {
553 screen = map_screens[XYMAPSCREEN(link_tl)];
554 }
555
556 struct xy screen_size = XYOP1(XYOP2(screen->br, -, screen->tl), / 8 + 1);
557 fprintf(mapimg, "P6 %u %u %u\n", screen_size.x, screen_size.y, 255);
558
559 uint16_t lift_mask = TILE_ATTR_LFT0;
560 if (*ap_ram.inventory_gloves >= 1) lift_mask |= TILE_ATTR_LFT1;
561 if (*ap_ram.inventory_gloves >= 2) lift_mask |= TILE_ATTR_LFT2;
562 if (*ap_ram.inventory_hammer >= 1) lift_mask |= TILE_ATTR_HMMR;
563
564 uint16_t semi_tile_attrs = lift_mask | TILE_ATTR_DOOR;
565 bool inside = XYINDOORS(screen->tl);
566
567 for (struct xy xy = screen->tl; xy.y < screen->br.y; xy.y += 8) {
568 for (xy.x = screen->tl.x; xy.x < screen->br.x; xy.x += 8) {
569 uint8_t tile_attr = ap_map_attr(xy);
570 bool tile_walk = ap_tile_attrs[tile_attr] & TILE_ATTR_WALK;
571 bool tile_semi = ap_tile_attrs[tile_attr] & semi_tile_attrs;
572 uint8_t px_shade = tile_walk ? 255 : (tile_semi ? 127 : 0);
573 if (XYIN(xy, link_tl, link_br)) {
574 fprintf(mapf, TERM_GREEN(TERM_BOLD("%02x ")), tile_attr);
575 fprintf(mapimg, "%c%c%c", 0, 128, 0);
576 goto next_point;
577 }
578 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
579 if (XYIN(xy, node->tl, node->br)) {
580 if (node->type == NODE_OVERLAY) {
581 fprintf(mapf, TERM_CYAN(TERM_BOLD("%02x ")), tile_attr);
582 goto next_point;
583 }
584 }
585 }
586 for (uint8_t i = 0; i < 16; i++) {
587 if (ap_sprites[i].type == 0) {
588 continue;
589 }
590 if (XYIN(xy, ap_sprites[i].tl, ap_sprites[i].br) ||
591 (inside && XYIN(XY(xy.x ^ 0x200, xy.y), ap_sprites[i].tl, ap_sprites[i].br))) {
592 if ((xy.x ^ xy.y) & 0x8) {
593 fprintf(mapf, TERM_MAGENTA("%02x "), tile_attr);
594 } else {
595 fprintf(mapf, TERM_MAGENTA(TERM_BOLD("%02x ")), ap_sprites[i].type);
596 }
597 fprintf(mapimg, "%c%c%c", 255, px_shade / 4, 255);
598 goto next_point;
599 }
600 }
601 for (struct ap_goal * goal = ap_goal_list->next; goal != ap_goal_list; goal = goal->next) {
602 if (goal->node == NULL) {
603 continue;
604 }
605 if (XYIN(xy, goal->node->locked_xy, XYOP1(goal->node->locked_xy, +7))) {
606 fprintf(mapf, TERM_CYAN(TERM_BOLD("%02x ")), tile_attr);
607 fprintf(mapimg, "%c%c%c", 64, 64, 0);
608 goto next_point;
609 }
610 if (XYIN(xy, goal->node->tl, goal->node->br)) {
611 fprintf(mapf, TERM_YELLOW("%02x "), tile_attr);
612 fprintf(mapimg, "%c%c%c", 255, 255 - goal->attempts * 64, 0);
613 goto next_point;
614 }
615 }
616 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
617 if (XYIN(xy, node->locked_xy, XYOP1(node->locked_xy, +7))) {
618 fprintf(mapf, TERM_CYAN(TERM_BOLD("%02x ")), tile_attr);
619 fprintf(mapimg, "%c%c%c", 64, 64, 0);
620 goto next_point;
621 }
622 if (XYIN(xy, node->tl, node->br)) {
623 fprintf(mapf, TERM_RED(TERM_BOLD("%02x ")), tile_attr);
624 if (node->adjacent_node == NULL) {
625 fprintf(mapimg, "%c%c%c", 255, 0, px_shade / 4);
626 } else {
627 fprintf(mapimg, "%c%c%c", 128, 255, 0);
628 }
629 goto next_point;
630 }
631 }
632 for (size_t i = 0; i < ap_target_count; i++) {
633 if (XYIN(xy, ap_targets[i].tl, XYOP1(ap_targets[i].tl, +8))) {
634 fprintf(mapf, TERM_BLUE(TERM_BOLD("%02x ")), tile_attr);
635 fprintf(mapimg, "%c%c%c", 0, px_shade / 4, 255);
636 goto next_point;
637 }
638 }
639 fprintf(mapimg, "%c%c%c", px_shade, px_shade, px_shade);
640 if (!(ap_tile_attrs[tile_attr] & TILE_ATTR_WALK)) {
641 fprintf(mapf, TERM_BOLD("%02x "), ap_map_attr(xy));
642 goto next_point;
643 }
644 fprintf(mapf, "%02x ", ap_map_attr(xy));
645next_point:;
646 }
647 fprintf(mapf, "\n");
648 }
649 fprintf(mapf, "--\n");
650 fprintf(mapf, "Screen '%s': " PRIBBV "\n", screen->name, PRIBBVF(*screen));
651 fclose(mapf);
652 fclose(mapimg);
653 rename("map.pbm.tmp", "map.pbm");
654}
655
656static int
657ap_set_targets(size_t count)
658{
659 assert(count < sizeof(ap_targets) / sizeof(*ap_targets));
660 ap_target_count = count;
661 ap_target_timeout = 0;
662 if (count == 0)
663 return 0;
664
665 ap_targets[count] = (struct ap_target) { .tl = ap_link_xy()};
666 //fprintf(stderr, "(dest) ");
667 for (size_t i = 0; i < count; i++) {
668 if (XYEQ(ap_targets[i].tl, XY(0,0))) {
669 LOG("target 0");
670 assert_bp(false);
671 }
672 ap_target_timeout += XYL1DIST(ap_targets[i].tl, ap_targets[i+1].tl) * 2;
673 if (ap_targets[i].joypad != ap_targets[i+1].joypad) {
674 ap_target_timeout += 1;
675 }
676 //fprintf(stderr, PRIXYV ", ", PRIXYVF(ap_targets[i]));
677 }
678 //fprintf(stderr, PRIXYV " (link)\n", PRIXYVF(ap_targets[count]));
679
680 for (size_t i = count; i < sizeof(ap_targets) / sizeof(*ap_targets); i++) {
681 ap_targets[count] = (struct ap_target) {.tl = XY(0, 0), .joypad = 0, .joypad_mask = 0};
682 }
683
684 ap_target_subtimeout = 32;
685 ap_target_timeout += 64;
686 fflush(NULL);
687 LOG("Following %zu targets with timeout: %d", ap_target_count, ap_target_timeout);
688 ap_print_map_screen(NULL);
689 return ap_target_timeout;
690}
691
692int
693ap_follow_targets(uint16_t * joypad, enum ap_inventory * equip_out)
694{
695 static struct xy last_link = XY(0, 0);
696 static int stationary_link_count = 0;
697 struct xy link = ap_link_xy();
698
699 if (XYEQ(last_link, link)) {
700 stationary_link_count++;
701 } else {
702 stationary_link_count = 0;
703 }
704 last_link = link;
705
706 if (stationary_link_count >= 128) {
707 LOGB("Stuck Link Detected! " PRIXY " en route to " PRIXY,
708 PRIXYF(link), PRIXYF(ap_targets[0].tl));
709 ap_target_timeout = 0;
710 stationary_link_count = 0;
711 }
712
713 if (ap_target_timeout <= 0) {
714 //INFO("L:" PRIXY "; " PRIXY " timeout", PRIXYF(link), PRIXYF(ap_targets[0].tl));
715 LOG("L:" PRIXY "; " PRIXY " timeout", PRIXYF(link), PRIXYF(ap_targets[0].tl));
716 ap_target_count = 0;
717 return RC_FAIL;
718 }
719
720 bool on_stairs = *ap_ram.submodule_index == 0x10 || *ap_ram.submodule_index == 0x08;
721 if (!ap_target_scripted && !on_stairs && (ap_target_subtimeout-- <= 0 || ap_sprites_changed)) {
722 int prev_timeout = ap_target_timeout;
723 int rc = ap_pathfind_local(NULL, link, ap_target_dst_tl, ap_target_dst_br, true);
724 if (rc < 0) {
725 LOGB("Path is now blocked");
726 ap_target_count = 0;
727 ap_target_timeout = -1;
728 return RC_FAIL;
729 }
730 ap_target_timeout = MIN(prev_timeout, ap_target_timeout);
731 }
732
733 struct ap_target target;
734 uint16_t joypad_mask = 0;
735 while (true) {
736 if (ap_target_count < 1) {
737 //INFO("L:" PRIXY "; done", PRIXYF(link));
738 //LOG("L:" PRIXY "; done", PRIXYF(link));
739 return RC_DONE;
740 }
741
742 target = ap_targets[ap_target_count-1];
743 if (target.joypad_mask & joypad_mask) {
744 break;
745 }
746
747 *joypad &= (uint16_t) ~target.joypad_mask;
748 *joypad |= target.joypad;
749 joypad_mask |= target.joypad_mask;
750
751 if (XYL1DIST(link, target.tl) <= 1) {
752 ap_target_count--;
753 ap_target_subtimeout = 32;
754 continue;
755 }
756 if (!ap_target_scripted && ap_target_count > 1) {
757 struct ap_target next_target = ap_targets[ap_target_count-2];
758 if (XYIN(link, XYFN2(MIN, target.tl, next_target.tl), XYFN2(MAX, target.tl, next_target.tl))) {
759 ap_target_count--;
760 ap_target_subtimeout = 32;
761 continue;
762 }
763 }
764
765 break;
766 }
767
768
769 if (!ap_target_scripted && XYLINKIN(link, ap_target_dst_tl, ap_target_dst_br)) {
770 ap_target_count = 0;
771 return RC_DONE;
772 }
773
774 if (!XYIN(link, ap_target_screen->tl, ap_target_screen->br)) {
775 if (ap_target_scripted) {
776 LOG("Marking script done because link left screen");
777 ap_target_count = 0;
778 return RC_DONE;
779 }
780
781 LOGB("Link left the screen!");
782 static int leave_count = 0;
783 leave_count++;
784 assert_bp(leave_count % 32 != 0);
785 return RC_FAIL;
786 }
787
788 //INFO("L:" PRIXY "; %zu:" PRIXY "; %d %#x", PRIXYF(link), ap_target_count, PRIXYF(ap_targets[ap_target_count-1]), ap_target_timeout, *ap_ram.push_dir_bitmask);
789 //LOG("L:" PRIXY "; %zu:" PRIXY "; %d", PRIXYF(link), ap_target_count, PRIXYF(ap_targets[ap_target_count-1]), ap_target_timeout);
790
791 const uint16_t dir_mask = SNES_MASK(UP) | SNES_MASK(DOWN) | SNES_MASK(LEFT) | SNES_MASK(RIGHT);
792 struct xy next_xy = target.tl;
793 if ((joypad_mask & dir_mask) == 0) {
794 if (link.x > target.tl.x) {
795 JOYPAD_SET(LEFT);
796 } else if (link.x < target.tl.x) {
797 JOYPAD_SET(RIGHT);
798 next_xy.x += 8;
799 }
800 if (link.y > target.tl.y) {
801 JOYPAD_SET(UP);
802 } else if (link.y < target.tl.y) {
803 JOYPAD_SET(DOWN);
804 next_xy.y += 8;
805 }
806 }
807
808 uint16_t lift_mask = TILE_ATTR_LFT0;
809 if (*ap_ram.inventory_gloves >= 1) lift_mask |= TILE_ATTR_LFT1;
810 if (*ap_ram.inventory_gloves >= 2) lift_mask |= TILE_ATTR_LFT2;
811
812 uint8_t tile = ap_map_attr(next_xy);
813 if (tile == 0x50 && *ap_ram.inventory_sword > 0) {
814 JOYPAD_MASH(B, 0x04); // Sword
815 } else if ((ap_tile_attrs[tile] & lift_mask) && *ap_ram.push_timer != 0x20) {
816 JOYPAD_MASH(A, 0x01); // Lift
817 } else if (*ap_ram.carrying_bit7) {
818 JOYPAD_MASH(A, 0x01);
819 } else if ((ap_tile_attrs[tile] & TILE_ATTR_HMMR) && *ap_ram.inventory_hammer != 0) {
820 if (*equip_out == INVENTORY_HAMMER) {
821 JOYPAD_MASH(Y, 0x1);
822 }
823 *equip_out = INVENTORY_HAMMER;
824 } else {
825 JOYPAD_CLEAR(A);
826 JOYPAD_CLEAR(B);
827 JOYPAD_CLEAR(Y);
828 }
829
830
831 /*
832 uint8_t dir = 0;
833 if (link.x > target.x) {
834 if (link.y > target.y)
835 dir = DIR_LU;
836 else if (link.y < target.y)
837 dir = DIR_LD;
838 else
839 dir = DIR_L;
840 } else if (link.x < target.x) {
841 if (link.y > target.y)
842 dir = DIR_RU;
843 else if (link.y < target.y)
844 dir = DIR_RD;
845 else
846 dir = DIR_R;
847 } else {
848 if (link.y > target.y)
849 dir = DIR_U;
850 else if (link.y < target.y)
851 dir = DIR_D;
852 else
853 dir = 0;
854 }
855 if (dir != 0) {
856 *joypad |= dir_joypad[dir];
857 }
858 */
859
860 /*
861 uint16_t tile_mask = TILE_ATTR_WALK | TILE_ATTR_DOOR | TILE_ATTR_LDGE | TILE_ATTR_LFT0;
862 if (link.x > target.x && (ap_link_tile_attr(XYOP2(link, -, XY(8, 0))) & tile_mask))
863 JOYPAD_SET(LEFT);
864 else if (link.x < target.x && (ap_link_tile_attr(XYOP2(link, +, XY(8, 0))) & tile_mask))
865 JOYPAD_SET(RIGHT);
866 if (link.y > target.y && (ap_link_tile_attr(XYOP2(link, -, XY(0, 8))) & tile_mask))
867 JOYPAD_SET(UP);
868 else if (link.y < target.y && (ap_link_tile_attr(XYOP2(link, +, XY(0, 8))) & tile_mask))
869 JOYPAD_SET(DOWN);
870 */
871
872 uint8_t d = (*ap_ram.link_direction / 2) + 1;
873 struct xy sword_up = XYOP1(dir_dxy[d], * 16 + 8);
874 //struct xy sword_rt = XYOP1(dir_dxy[dir_cw[d]], * 16 + 8);
875 struct xy link_sword_up = XYOP2(link, +, sword_up);
876 //struct xy link_sword_rt = XYOP2(link, +, sword_rt);
877 //
878 if (ap_sprites[ap_target_sprite_index].attrs & SPRITE_ATTR_VBOW) {
879 uint8_t i = ap_target_sprite_index;
880 if (ap_sprites[i].type == 0x84 && ap_sprites[i].interaction == 0x07 &&
881 XYL1BOXDIST(link_sword_up, ap_sprites[i].tl, ap_sprites[i].br) <= 8) {
882 JOYPAD_MASH(Y, 0x08);
883 JOYPAD_CLEAR(B);
884 }
885 } else {
886 if ((joypad_mask & SNES_MASK(B)) == 0) {
887 for (uint8_t i = 0; i < 16; i++) {
888 if (!*ap_ram.inventory_sword) {
889 break;
890 }
891 if (!ap_sprites[i].active) {
892 continue;
893 }
894 if ((ap_sprites[i].attrs & SPRITE_ATTR_ENMY) && !(ap_sprites[i].attrs & SPRITE_ATTR_NVUL)) {
895 if (XYL1BOXDIST(link_sword_up, ap_sprites[i].tl, ap_sprites[i].br) <= 8) {
896 JOYPAD_MASH(B, 0x08); // Sword
897 break;
898 }
899 }
900 }
901 }
902 }
903
904 ap_target_timeout--;
905
906 return RC_INPR;
907}
908
909void
910ap_joypad_setdir(uint16_t * joypad, uint8_t dir)
911{
912 // 0 U D L R LU LD RU RD 0
913 JOYPAD_CLEAR(UP);
914 JOYPAD_CLEAR(DOWN);
915 JOYPAD_CLEAR(LEFT);
916 JOYPAD_CLEAR(RIGHT);
917 switch (dir) {
918 case 1: JOYPAD_SET(UP); break;
919 case 2: JOYPAD_SET(DOWN); break;
920 case 3: JOYPAD_SET(LEFT); break;
921 case 4: JOYPAD_SET(RIGHT); break;
922 case 5: JOYPAD_SET(UP); JOYPAD_SET(LEFT); break;
923 case 6: JOYPAD_SET(UP); JOYPAD_SET(LEFT); break;
924 case 7: JOYPAD_SET(DOWN); JOYPAD_SET(RIGHT); break;
925 case 8: JOYPAD_SET(DOWN); JOYPAD_SET(RIGHT); break;
926 }
927}
928
929uint32_t
930ap_path_heuristic(struct xy src, struct xy dst_tl, struct xy dst_br)
931{
932 uint32_t distance = 0;
933 if (XYINDOORS(src) && XYINDOORS(dst_tl) && XYINDOORS(dst_br)) {
934 // collapse BG1 & BG2
935 if ((src.x & ~0x200) != (dst_tl.x & ~0x200)) {
936 distance += 1;
937 }
938 distance += 1;
939 src.x &= ~0x200;
940 dst_tl.x &= ~0x200;
941 dst_br.x &= ~0x200;
942 }
943 if (src.x < dst_tl.x)
944 distance += dst_tl.x - src.x;
945 else if (src.x > dst_br.x)
946 distance += src.x - dst_br.x;
947 if (src.y < dst_tl.y)
948 distance += dst_tl.y - src.y;
949 else if (src.y > dst_br.y)
950 distance += src.y - dst_br.y;
951 return distance;
952}
953
954static volatile bool save_local_state = false;
955
956static int
957ap_pathfind_local(struct ap_screen * screen, struct xy start_xy, struct xy destination_tl, struct xy destination_br, bool commit)
958{
959 if (commit) {
960 ap_set_targets(0);
961 ap_update_map_screen(true);
962 }
963
964 if (screen == NULL) {
965 screen = map_screens[XYMAPSCREEN(start_xy)];
966 } else {
967 assert_bp(screen == map_screens[XYMAPSCREEN(start_xy)]);
968 }
969
970 if (!XYIN(start_xy, screen->tl, screen->br)) {
971 LOG("error: Start " PRIXYV " out of screen", PRIXYVF(start_xy));
972 return -1;
973 }
974 if (!XYIN(destination_tl, screen->tl, screen->br)) {
975 LOG("error: TL destination " PRIXYV " out of screen", PRIXYVF(destination_tl));
976 assert_bp(false);
977 return -1;
978 }
979 if (!XYIN(destination_br, screen->tl, screen->br)) {
980 LOG("error: BR destination " PRIXYV " out of screen", PRIXYVF(destination_br));
981 return -1;
982 }
983
984 if (commit) {
985 //LOG("Starting pathfind in screen " PRIBBV ", start " PRIXYV, PRIBBVF(*screen), PRIXYVF(start_xy));
986 }
987
988 start_xy = XYFN2(MAX, start_xy, XYOP1(screen->tl, + 16));
989 start_xy = XYFN2(MIN, start_xy, XYOP1(screen->br, - 16));
990
991 struct xy size = XYOP2(screen->br, -, screen->tl);
992 struct xy grid = XYOP1(size, / 8 + 1);
993 struct xy tl_offset = XYOP1(screen->tl, / 8);
994
995 struct xy src = XYOP2(XYOP1(start_xy, / 8), -, tl_offset);
996 struct xy dst_tl = XYOP2(XYOP1(destination_tl, / 8), -, tl_offset);
997 struct xy dst_br = XYOP2(XYOP1(destination_br, / 8), -, tl_offset);
998
999 uint32_t distance = ap_path_heuristic(src, dst_tl, dst_br);
1000 if (distance > (size.x + size.y)) {
1001 printf("error: invalid target " PRIXYV " x " PRIXYV, PRIXYVF(destination_tl), PRIXYVF(destination_br));
1002 return -1;
1003 }
1004 /*
1005 if (distance < 8) {
1006 ap_targets[0] = destination;
1007 return ap_target_count = 1;
1008 }
1009 */
1010
1011 uint16_t lift_mask = TILE_ATTR_LFT0;
1012 if (*ap_ram.inventory_gloves >= 1) lift_mask |= TILE_ATTR_LFT1;
1013 if (*ap_ram.inventory_gloves >= 2) lift_mask |= TILE_ATTR_LFT2;
1014 if (*ap_ram.inventory_hammer >= 1) lift_mask |= TILE_ATTR_HMMR;
1015
1016 static struct point_state buf[0x82 * 0x82];
1017
1018 // CORNER is used to identify boundaries of 2x2 tiles (like bushes)
1019 enum corner {
1020 CORNER_NONE = 0,
1021 CORNER_TL,
1022 CORNER_TR,
1023 CORNER_BL,
1024 CORNER_BR,
1025 CORNER_TA, // Left adjacent squares
1026 CORNER_BA,
1027 CORNER_AL, // Top adjacent squares
1028 CORNER_AR,
1029 CORNER_AA, // Up-Left diagonally adjacent
1030 };
1031 if (grid.x * grid.y > 0x80 * 0x80) {
1032 printf("error: grid too large: " PRIXY "\n", PRIXYF(grid));
1033 return -1;
1034 }
1035
1036 // Make a state[y][x]
1037 struct point_state (*state)[grid.x + 2] = (void *) &buf[0x83];
1038
1039 // Check if cache is valid
1040 static struct ap_screen *last_pf_screen = NULL;
1041 static uint32_t last_frame = 0;
1042 if (false && last_pf_screen == screen && last_frame == ap_frame) {
1043 for (uint16_t y = 0; y < grid.y; y++) {
1044 for (uint16_t x = 0; x < grid.x; x++) {
1045 assert_bp(&state[y][x] == &buf[0x83 + (grid.x + 2) * y + x]);
1046 state[y][x].from = NULL;
1047 state[y][x].gscore = (uint32_t) -1;
1048 state[y][x].fscore = (uint32_t) -1;
1049 }
1050 }
1051 } else {
1052 last_pf_screen = screen;
1053 last_frame = ap_frame;
1054
1055 for (size_t i = 0; i < 0x82 * 0x82; i++) {
1056 buf[i].ledge = 0xFF;
1057 }
1058
1059 for (uint16_t y = 0; y < grid.y; y++) {
1060 for (uint16_t x = 0; x < grid.x; x++) {
1061 assert_bp(&state[y][x] == &buf[0x83 + (grid.x + 2) * y + x]);
1062 state[y][x].from = NULL;
1063 state[y][x].xy = XYOP1(XYOP2(XY(x, y), +, tl_offset), * 8);
1064 state[y][x].gscore = (uint32_t) -1;
1065 state[y][x].fscore = (uint32_t) -1;
1066 state[y][x].cost = 0;
1067 state[y][x].corner = CORNER_NONE;
1068 state[y][x].ledge = 0;
1069 state[y][x].tile_attrs = 0;
1070 }
1071 }
1072 for (uint16_t y = 0; y < grid.y; y++) {
1073 for (uint16_t x = 0; x < grid.x; x++) {
1074 uint32_t cost = 0;
1075 struct xy mapxy = XYOP2(XYOP1(XY(x, y), * 8), +, screen->tl);
1076 uint8_t raw_tile = ap_map_attr(mapxy);
1077 uint16_t tile = ap_tile_attrs[raw_tile];
1078 state[y][x].tile_attrs = tile;
1079 state[y][x].raw_tile = raw_tile;
1080 uint8_t ledge_mask = 0;
1081 uint8_t ledge_dir = DIR_NONE;
1082 //if (tile & (TILE_ATTR_WALK | TILE_ATTR_DOOR)) {
1083 if (tile & (TILE_ATTR_WALK)) {
1084 cost = 0;
1085 } else if ((tile & TILE_ATTR_DOOR) && XYL1DIST(XY(x, y), src) <= 3) {
1086 cost = 0;
1087 } else if (tile & TILE_ATTR_LDGE) {
1088 cost = (1 << 20); // calculated at search time
1089 //cost = 0;
1090 assert_bp((raw_tile &~0x7) == 0x28);
1091 ledge_mask = 1ul << (raw_tile & 0x7);
1092 ledge_dir = (raw_tile & 0x7) + 1;
1093 } else if (tile & lift_mask) {
1094 cost = 20;
1095 if (state[y][x].corner == CORNER_NONE && raw_tile != 0x55) {
1096 state[y][x].corner = CORNER_TL;
1097 state[y][x+1].corner = CORNER_TR;
1098 state[y+1][x].corner = CORNER_BL;
1099 state[y+1][x+1].corner = CORNER_BR;
1100 if (state[y][x-1].corner == CORNER_NONE) {
1101 state[y][x-1].corner = CORNER_TA;
1102 state[y+1][x-1].corner = CORNER_BA;
1103 }
1104 if (state[y-1][x-1].corner == CORNER_NONE) {
1105 state[y-1][x-1].corner = CORNER_AA;
1106 }
1107 if (state[y-1][x-0].corner == CORNER_NONE) {
1108 state[y-1][x-0].corner = CORNER_AL;
1109 }
1110 if (state[y-1][x+1].corner == CORNER_NONE) {
1111 state[y-1][x+1].corner = CORNER_AR;
1112 }
1113 }
1114 // XXX This was correct; but it breaks caching
1115 } else if (XYIN(mapxy, destination_tl, destination_br)) {
1116 cost = 0;
1117 } else if (raw_tile == 0x1C) {
1118 cost = 1000;
1119 } else {
1120 cost = (1 << 20);
1121 }
1122
1123 // Pit collision is weird
1124 state[y-1][x-1].cost += cost;
1125 if (!(tile & TILE_ATTR_EDGE)) {
1126 state[y-0][x-0].cost += cost;
1127 state[y-0][x-1].cost += cost;
1128 state[y-1][x-0].cost += cost;
1129 }
1130
1131 //state[y+1][x+1].ledge |= ledge_mask;
1132 //state[y+1][x-0].ledge |= ledge_mask;
1133 //state[y+1][x-1].ledge |= ledge_mask;
1134 //state[y+1][x-2].ledge |= ledge_mask;
1135 //state[y-0][x+1].ledge |= ledge_mask;
1136 state[y-0][x-0].ledge |= ledge_mask;
1137 state[y-0][x-1].ledge |= ledge_mask;
1138 //state[y-0][x-2].ledge |= ledge_mask;
1139 //state[y-1][x+1].ledge |= ledge_mask;
1140 state[y-1][x-0].ledge |= ledge_mask;
1141 state[y-1][x-1].ledge |= ledge_mask;
1142 //state[y-1][x-2].ledge |= ledge_mask;
1143 //state[y-2][x+1].ledge |= ledge_mask;
1144 //state[y-2][x-0].ledge |= ledge_mask;
1145 //state[y-2][x-1].ledge |= ledge_mask;
1146 //state[y-2][x-2].ledge |= ledge_mask;
1147 // There's something particuarly thorny about 0x2D ledges (LD)
1148 if (raw_tile == 0x2D) {
1149 state[y][x+1].cost += cost;
1150 state[y][x+1].ledge |= ledge_mask;
1151 state[y][x+2].cost += cost;
1152 state[y][x+2].ledge |= ledge_mask;
1153 }
1154
1155 /*
1156 if (ledge_dir != DIR_NONE) {
1157 if (ledge_dir == DIR_U || ledge_dir == DIR_LU || ledge_dir == DIR_RU) {
1158 state[y-2][x+0].cost += cost;
1159 state[y-2][x+0].ledge |= ledge_mask;
1160 }
1161 if (ledge_dir == DIR_D || ledge_dir == DIR_LD || ledge_dir == DIR_RD) {
1162 state[y+1][x+0].cost += cost;
1163 state[y+1][x+0].ledge |= ledge_mask;
1164 }
1165 if (ledge_dir == DIR_L || ledge_dir == DIR_LU || ledge_dir == DIR_LD) {
1166 state[y+0][x-2].cost += cost;
1167 state[y+0][x-2].ledge |= ledge_mask;
1168 }
1169 if (ledge_dir == DIR_R || ledge_dir == DIR_RU || ledge_dir == DIR_RD) {
1170 state[y+0][x+1].cost += cost;
1171 state[y+0][x+1].ledge |= ledge_mask;
1172 }
1173 }
1174 */
1175
1176 if (x < 1 || x >= grid.x - 1 ||
1177 y < 1 || y >= grid.y - 1) {
1178 state[y][x].cost = (1 << 20);
1179 } else if (x < 3 || x >= grid.x - 3 ||
1180 y < 3 || y >= grid.y - 3) {
1181 state[y][x].cost += 10000;
1182 }
1183 }
1184 }
1185 for (uint8_t i = 0; i < 16; i++) {
1186 if (ap_sprites[i].type == 0) {
1187 continue;
1188 }
1189 if (!XYIN(ap_sprites[i].hitbox_tl, screen->tl, screen->br)) {
1190 continue;
1191 }
1192 if (ap_sprites[i].attrs & SPRITE_ATTR_ENMY && ap_sprites[i].active) {
1193 struct xy center = XYOP1(XYOP2(ap_sprites[i].hitbox_tl, -, screen->tl), / 8);
1194 for (int dx = -4; dx <= 4; dx++) {
1195 for (int dy = -4; dy <= 4; dy++) {
1196 struct xy ds = XYOP2(center, +, XY(dx, dy));
1197 if (!XYUNDER(ds, grid)) {
1198 continue;
1199 }
1200 state[ds.y][ds.x].cost += MAX(0, 7 - (ABS(dx) + ABS(dy))) * 100;
1201 }
1202 }
1203 }
1204 if ((ap_sprites[i].attrs & (SPRITE_ATTR_BLKF | SPRITE_ATTR_BLKS)) &&
1205 ap_sprites[i].state != 0x0A && // carried
1206 ap_sprites[i].state != 0x06) { // thrown
1207 assert_bp(ap_sprites[i].state == 0x08 ||
1208 ap_sprites[i].state == 0x09 ||
1209 ap_sprites[i].state == 0x00);
1210 //volatile struct xy center = XYOP1(XYOP2(ap_sprites[i].hitbox_tl, -, screen->tl), / 8);
1211 //assert_bp(i != 11);
1212 struct xy hb_tl = XYOP2(ap_sprites[i].hitbox_tl, -, screen->tl);
1213 struct xy hb_br= XYOP2(ap_sprites[i].hitbox_br, -, screen->tl);
1214 hb_tl = XYOP1(hb_tl, / 8);
1215 hb_br = XYOP1(hb_br, / 8);
1216 hb_tl = XYOP1(hb_tl, -1);
1217 hb_br = XYOP1(hb_br, +1);
1218 /*
1219 if (i == 11) {
1220 LOG(TERM_BOLD("11:") " " PRIXYV, PRIXYVF(center));
1221 }
1222 */
1223 struct xy ds;
1224 for (ds.x = hb_tl.x; ds.x <= hb_br.x; ds.x++) {
1225 for (ds.y = hb_tl.y; ds.y <= hb_br.y; ds.y++) {
1226 if (!XYUNDER(ds, grid)) {
1227 continue;
1228 }
1229 state[ds.y][ds.x].cost += (1 << 20);
1230 }
1231 }
1232 }
1233 }
1234 }
1235
1236 // Hack to round when there is an obstacle nearby
1237 // Doesn't handle diagonals perfectly, but should be fine?
1238 if ((start_xy.x & 0x7) != 0 &&
1239 state[src.y][src.x].cost > state[src.y][src.x+1].cost) {
1240 src.x += 1;
1241 if (commit) LOG("Nudged X start");
1242 }
1243 if ((start_xy.y & 0x7) != 0 &&
1244 state[src.y][src.x].cost > state[src.y+1][src.x].cost) {
1245 src.y += 1;
1246 if (commit) LOG("Nudged Y start");
1247 }
1248 if (save_local_state || commit) {
1249 ap_print_pathfind_local_state(buf, grid);
1250 }
1251
1252 // Hack to nudge starting poing if we are "trapped" (probably inside a sprite)
1253 if (state[src.y][src.x].cost >= (1 << 20)) {
1254 const uint32_t min_cost = state[src.y][src.x].cost;
1255 if (state[src.y-2][src.x-2].cost < min_cost) {
1256 src.x += -2;
1257 src.y += -2;
1258 } else if (state[src.y+2][src.x-2].cost < min_cost) {
1259 src.x += -2;
1260 src.y += +2;
1261 } else if (state[src.y-2][src.x+2].cost < min_cost) {
1262 src.x += +2;
1263 src.y += -2;
1264 } else if (state[src.y+2][src.x+2].cost < min_cost) {
1265 src.x += +2;
1266 src.y += +2;
1267 }
1268 }
1269
1270 static struct pq * pq = NULL;
1271 if (pq == NULL) {
1272 pq = pq_create(sizeof(struct xy));
1273 if (pq == NULL) exit(1);
1274 }
1275 pq_clear(pq);
1276 pq_push(pq, 0, &src);
1277
1278 struct point_state start_ps = { .xy = start_xy };
1279 state[src.y][src.x].from = &start_ps;
1280 state[src.y][src.x].fscore = 0;
1281 state[src.y][src.x].gscore = 0;
1282
1283 size_t r;
1284 struct xy final_xy;
1285 uint64_t min_heuristic = -1;
1286 for (r = 0; r < 0x80 * 0x80 + 100; r++) {
1287 struct xy node;
1288 uint64_t cost;
1289 int rc = pq_pop(pq, &cost, &node);
1290 if (rc != 0)
1291 goto search_failed;
1292 if (cost != state[node.y][node.x].fscore)
1293 continue;
1294 assert_bp(state[node.y][node.x].ledge != 0xFF);
1295 const struct point_state *const node_state = &state[node.y][node.x];
1296 for (uint8_t i = 1; i < 9; i++) {
1297 struct xy neighbor = XYOP2(node, +, dir_dxy[i]);
1298 const struct point_state *const neighbor_state = &state[neighbor.y][neighbor.x];
1299 if (neighbor.x >= grid.x || neighbor.y >= grid.y)
1300 continue;
1301 assert_bp(state[neighbor.y][neighbor.x].ledge != 0xFF);
1302 if (state[neighbor.y][neighbor.x].raw_tile == 0x1C)
1303 continue;
1304
1305 // Only pick up objects if you are square with them
1306 if (i == DIR_U || i == DIR_D || i >= 5) {
1307 if ((state[neighbor.y][node.x].tile_attrs & lift_mask) !=
1308 (state[neighbor.y][node.x+1].tile_attrs & lift_mask))
1309 continue;
1310 }
1311 if (i == DIR_L || i == DIR_R || i >= 5) {
1312 if ((state[node.y][neighbor.x].tile_attrs & lift_mask) !=
1313 (state[node.y+1][neighbor.x].tile_attrs & lift_mask))
1314 continue;
1315 }
1316 enum corner corner = state[neighbor.y][neighbor.x].corner;
1317 if (corner != CORNER_NONE) {
1318 if (i >= 5) continue;
1319 //if ((neighbor_state - node_state) != (node_state - node_state->from)) continue;
1320 if ((i == DIR_D || i == DIR_U) && !(corner == CORNER_AL || corner == CORNER_TL || corner == CORNER_BL))
1321 continue;
1322 if ((i == DIR_L || i == DIR_R) && !(corner == CORNER_TA || corner == CORNER_TL || corner == CORNER_TR))
1323 continue;
1324 }
1325 /*
1326 // Handle stairs
1327 if (state[node.y][node.x].raw_tile == 0x3E ||
1328 state[node.y][node.x].raw_tile == 0x1E) {
1329 // FIXME: This needs to change now that we've refactored
1330 // BG1/BG2 to be different screens
1331 neighbor.x ^= 0x200 / 8;
1332 //neighbor = XYOP2(neighbor, +, dir_dxy[i]);
1333 //neighbor = XYOP2(neighbor, +, dir_dxy[i]);
1334 assert_bp(XYUNDER(neighbor, grid));
1335 }
1336 */
1337 if ((state[neighbor.y][neighbor.x].ledge) && i >= 5) {
1338 // Stick to cardinal directions near ledges of any kind
1339 continue;
1340 }
1341 // Jump down ledges (disabled)
1342 uint8_t ledge_mask = 1ul << (i - 1);
1343 assert(ledge_mask != 0);
1344 if (false && (state[node.y][node.x].ledge & ledge_mask)) {
1345 bool fail_ledge = false;
1346 int iters = 0;
1347 while (true) {
1348 if (!XYUNDER(neighbor, grid)) {
1349 fail_ledge = true;
1350 break;
1351 }
1352 if (state[neighbor.y][neighbor.x].raw_tile == 0x1C) {
1353 // XXX this is broken now that screens are split by layer
1354 assert_bp(neighbor.x & (0x200 / 8));
1355 neighbor.x -= 0x200 / 8;
1356 neighbor = XYOP2(neighbor, +, dir_dxy[i]);
1357 assert_bp(XYUNDER(neighbor, grid));
1358 } else if (state[neighbor.y][neighbor.x].cost < (1 << 20) &&
1359 state[neighbor.y][neighbor.x].ledge == 0) {
1360 break;
1361 }
1362 if (state[neighbor.y][neighbor.x].tile_attrs & TILE_ATTR_SWIM) {
1363 fail_ledge = true;
1364 break;
1365 }
1366 //assert_bp(state[neighbor.y][neighbor.x].ledge != 0xFF);
1367 iters++;
1368 struct xy next_neighbor = XYOP2(neighbor, +, dir_dxy[i]);
1369 if (!XYUNDER(next_neighbor, grid))
1370 break;
1371 neighbor = next_neighbor;
1372 }
1373 if (fail_ledge)
1374 continue;
1375 if (commit) LOG("Ledge %u in %d iters from " PRIXYV " to " PRIXYV, i, iters, PRIXYVF(node), PRIXYVF(neighbor));
1376 assert_bp(XYUNDER(neighbor, grid));
1377 } else if (state[node.y][node.x].ledge != 0) {
1378 continue;
1379 } else if (state[neighbor.y][neighbor.x].ledge != 0) {
1380 continue;
1381 }
1382 assert_bp(XYUNDER(neighbor, grid));
1383
1384 uint32_t gscore = state[node.y][node.x].gscore;
1385 gscore += dir_cost[i];
1386 if (true || !(state[node.y][node.x].ledge & ledge_mask)) {
1387 uint32_t step_cost = state[neighbor.y][neighbor.x].cost;
1388 if (i >= 5) {
1389 step_cost = MAX(step_cost, state[neighbor.y][node.x].cost);
1390 step_cost = MAX(step_cost, state[node.y][neighbor.x].cost);
1391 }
1392 gscore += step_cost;
1393 //if (!XYIN(neighbor, dst_tl, XYOP1(dst_br, -1))
1394 // && XYL1DIST(neighbor, src) > 2) {
1395 // gscore += step_cost;
1396 //}
1397 }
1398 if (gscore >= (1 << 20))
1399 continue;
1400 if (gscore >= state[neighbor.y][neighbor.x].gscore)
1401 continue;
1402
1403 uint32_t heuristic = ap_path_heuristic(neighbor, dst_tl, dst_br);
1404 if (heuristic == 0) {
1405 assert_bp(XYIN(neighbor, dst_tl, dst_br));
1406 final_xy = neighbor;
1407 state[neighbor.y][neighbor.x].from = &state[node.y][node.x];
1408 state[neighbor.y][neighbor.x].gscore = gscore;
1409 goto search_done;
1410 }
1411
1412 min_heuristic = MIN(heuristic, min_heuristic);
1413 uint32_t fscore = gscore + heuristic;
1414 state[neighbor.y][neighbor.x].from = &state[node.y][node.x];
1415 state[neighbor.y][neighbor.x].gscore = gscore;
1416 state[neighbor.y][neighbor.x].fscore = fscore;
1417
1418 // Issue: neighbor.y == grid.y
1419 assert_bp(XYUNDER(neighbor, grid));
1420 assert_bp(state[neighbor.y][neighbor.x].ledge != 0xFF);
1421 pq_push(pq, fscore, &neighbor);
1422 }
1423 }
1424 if (commit) LOG("A* timed out, min heuristic: %lu", min_heuristic);
1425 return -1;
1426search_failed:
1427 if (commit) LOG("A* failed, min heuristic: %lu", min_heuristic);
1428 return -1;
1429search_done:;
1430 //if (commit) LOG("A* done in %zu steps, pq size = %zu", r, pq_size(pq));
1431
1432 struct point_state * next = &state[final_xy.y][final_xy.x];
1433 int final_gscore = next->gscore;
1434 if (!commit) {
1435 return final_gscore;
1436 }
1437
1438 size_t count = 0;
1439 ap_targets[count++] = (struct ap_target) { .tl = XY(
1440 MIN(next->xy.x, destination_br.x - 15),
1441 MIN(next->xy.y, destination_br.y - 15)),
1442 .joypad = 0, .joypad_mask = 0,
1443 };
1444
1445 struct xy last_dir = XY(1, 2);
1446 struct xy last_xy = next->xy;
1447 while (next != NULL && next->from != NULL) {
1448 struct xy dir = XYOP2(next->xy, -, last_xy);
1449 assert_bp(next->from == NULL || !XYEQ(next->from->xy, XY(0,0)));
1450 assert_bp(next->raw_tile != 0x10);
1451
1452 if (!next->ledge) {
1453 if (true || !XYEQ(dir, last_dir)) {
1454 //XXX This is normally bad, but for now assume recoil
1455 //assert_bp(!((next->xy.x <= screen->tl.x + 15) || (next->xy.y <= screen->tl.y + 15)));
1456 //assert_bp(!((next->xy.x >= screen->br.x - 15) || (next->xy.y >= screen->br.y - 15)));
1457 ap_targets[count++] = (struct ap_target) { .tl = next->xy };
1458 //printf("%zu: "PRIXY "\n", count, PRIXYF(ap_targets[count-1]));
1459 }
1460 }
1461 last_dir = dir;
1462 last_xy = next->xy;
1463 next = next->from;
1464 }
1465
1466 int timeout = ap_set_targets(count);
1467 ap_target_dst_tl = destination_tl;
1468 ap_target_dst_br = destination_br;
1469 ap_target_screen = screen;
1470 ap_target_scripted = false;
1471 ap_print_map_screen(screen);
1472 return final_gscore;
1473}
1474
1475static int
1476ap_pathfind_node_distance(const struct ap_node * src, const struct ap_node * dst)
1477{
1478 assert(src->screen == dst->screen);
1479 if (src->type == NODE_NONE) {
1480 // Fake node; have to use ap_pathfind_local
1481 return ap_pathfind_local(src->screen, src->tl, dst->tl, dst->br, false);
1482 }
1483 assert(dst->type != NODE_NONE);
1484 //assert_bp(src->screen->distances_length > 0);
1485 const struct ap_node_distance *dists = src->screen->distances;
1486 for (size_t i = 0; i < src->screen->distances_length; i++) {
1487 if (dists[i].src == src && dists[i].dst == dst) {
1488 return dists[i].distance;
1489 }
1490 }
1491 return -1;
1492}
1493
1494static int
1495ap_pathfind_global(struct xy start_xy, struct ap_node * destination, bool commit, int _max_distance)
1496{
1497 uint64_t max_distance = UINT64_MAX;
1498 if (_max_distance > 0) {
1499 max_distance = (uint64_t) _max_distance;
1500 }
1501
1502 struct ap_screen * start_screen = map_screens[XYMAPSCREEN(start_xy)];
1503 if (start_screen == NULL) {
1504 LOG("start screen == NULL");
1505 return -1;
1506 }
1507 if (destination->_debug_blocked) {
1508 return -1;
1509 }
1510
1511 static uint64_t iter = 0;
1512 iter += 2;
1513 static struct ap_node _start_node;
1514 struct ap_node * start_node = &_start_node;
1515 *start_node = (struct ap_node) {
1516 .screen = start_screen,
1517 .tl = start_xy,
1518 .type = NODE_NONE,
1519 .pgsearch = {
1520 .iter = iter,
1521 //.xy = start_xy,
1522 .from = NULL,
1523 .distance = 0,
1524 }
1525 };
1526
1527 if (start_screen == destination->screen) {
1528 int local_dist = ap_pathfind_local(start_screen, start_xy, destination->tl, destination->br, commit);
1529 if (local_dist >= 0) {
1530 destination->pgsearch.iter = iter;
1531 destination->pgsearch.from = start_node;
1532 return local_dist;
1533 }
1534 }
1535
1536 static struct pq * pq = NULL;
1537 if (pq == NULL) {
1538 pq = pq_create(sizeof(struct ap_node *));
1539 if (pq == NULL) exit(1);
1540 }
1541 pq_clear(pq);
1542 pq_push(pq, 0, &start_node);
1543
1544 size_t r = 0;
1545 while (true) {
1546 r++;
1547 struct ap_node * node;
1548 uint64_t distance;
1549 if (pq_pop(pq, &distance, &node) < 0)
1550 goto search_failed;
1551 if (distance > max_distance)
1552 goto search_too_far;
1553 if (node->pgsearch.iter == iter + 1)
1554 continue;
1555 bool unlockable = false;
1556 const struct ap_room_tag * unlock_tag = NULL;
1557 if (ap_node_islocked(node, &unlockable, &unlock_tag) && !unlockable)
1558 continue;
1559 assert(node->pgsearch.iter == iter);
1560 node->pgsearch.iter++;
1561 if (node == destination)
1562 goto search_done;
1563 assert(node->type == NODE_TRANSITION || node->type == NODE_KEYBLOCK || node == start_node);
1564
1565 // Try going to an adjacent screen
1566 if (node->adjacent_node != NULL && node->adjacent_direction != 0) {
1567 uint64_t d = node->pgsearch.distance + 1000;
1568 if ((node->adjacent_node->pgsearch.iter == iter &&
1569 node->adjacent_node->pgsearch.distance < d) ||
1570 node->adjacent_node->pgsearch.iter < iter) {
1571 node->adjacent_node->pgsearch = (struct ap_node_pgsearch) {
1572 .iter = iter,
1573 //.xy = XYMID(node->adjacent_node->tl, node->adjacent_node->br),
1574 .from = node,
1575 .distance = d,
1576 };
1577 pq_push(pq, d, &node->adjacent_node);
1578 }
1579 }
1580
1581 // Try going to nodes on the same screen
1582 for (struct ap_node * adj_node = node->screen->node_list->next; adj_node != node->screen->node_list; adj_node = adj_node->next) {
1583 if (adj_node == node)
1584 continue;
1585 if (adj_node->_debug_blocked)
1586 continue;
1587 if (!(adj_node == destination || adj_node->type == NODE_TRANSITION || adj_node->type == NODE_KEYBLOCK))
1588 continue;
1589 if (adj_node->pgsearch.iter == iter + 1)
1590 continue;
1591 // Don't 'hop through' transition nodes on the same screen
1592 if (adj_node->type == NODE_TRANSITION && node->type == NODE_TRANSITION &&
1593 node->pgsearch.from != NULL && node->pgsearch.from->screen == node->screen && node->pgsearch.from->type == NODE_TRANSITION)
1594 continue;
1595 //int delta_distance = ap_pathfind_local(node->screen, node->pgsearch.xy, adj_node->tl, adj_node->br, false);
1596 int delta_distance = ap_pathfind_node_distance(node, adj_node);
1597 if (delta_distance < 0)
1598 continue;
1599
1600 uint64_t d = node->pgsearch.distance + delta_distance;
1601 if ((adj_node->pgsearch.iter == iter &&
1602 adj_node->pgsearch.distance > d) ||
1603 adj_node->pgsearch.iter < iter) {
1604 adj_node->pgsearch = (struct ap_node_pgsearch) {
1605 .iter = iter,
1606 //.xy = XYMID(adj_node->tl, adj_node->br),
1607 .from = node,
1608 .distance = d,
1609 };
1610 pq_push(pq, d, &adj_node);
1611 }
1612 }
1613 }
1614search_too_far:
1615 if (commit) LOG("Search exceeded limit after %zu steps (max_distance=%d)", r, _max_distance);
1616 return _max_distance + 1;
1617search_failed:
1618 if (commit) LOG("Search failed after %zu steps (max_distance=%d)", r, _max_distance);
1619 return -1;
1620search_done:
1621 if (commit) LOG("Search done in %zu steps, pq size = %zu", r, pq_size(pq));
1622 else return destination->pgsearch.distance;
1623
1624 struct ap_node * next = destination;
1625 size_t count = 0;
1626 while (next != NULL) {
1627 assert(next->pgsearch.iter == iter + 1);
1628 LOG(" %zu: %s %ld", count, next->name, next->pgsearch.distance);
1629 next = next->pgsearch.from;
1630 count++;
1631 }
1632
1633 return destination->pgsearch.distance;
1634}
1635
1636void
1637ap_print_map_graph()
1638{
1639 FILE *graphf = NONNULL(fopen("full_map.dot", "w"));
1640 fprintf(graphf, "digraph map {\nconcatenate=true\n");
1641 struct xy link = ap_link_xy();
1642 int32_t link_min_dist = INT32_MAX;
1643 struct ap_node * link_nearest_node = NULL;
1644
1645 FILE *screenf = NONNULL(fopen("screen_map.dot", "w"));
1646 fprintf(screenf, "strict digraph map {\ngraph [concentrate=true];\n");
1647
1648 for (struct xy xy = XY(0, 0); xy.y < 0x8000; xy.y += 0x100) {
1649 if (!map_screen_mask_y[xy.y / 0x100]) continue;
1650 for (xy.x = 0; xy.x < 0xC000; xy.x += 0x100) {
1651 if (!map_screen_mask_x[xy.x / 0x100]) continue;
1652 struct ap_screen * screen = map_screens[XYMAPSCREEN(xy)];
1653 if (screen == NULL || !XYEQ(screen->tl, xy)) continue;
1654
1655 fprintf(graphf, "subgraph cluster_%p { color=black; label=\"%s\"\n", screen, screen->name);
1656 fprintf(screenf, "s%#x [label=\"%s\" shape=\"rect\"];\n", screen->id, screen->name);
1657 if (XYIN(link, screen->tl, screen->br)) {
1658 fprintf(screenf, "s%#x [color=\"green\"];\n", screen->id);
1659 }
1660
1661 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
1662 const char *shape = "oval";
1663 switch (node->type) {
1664 case NODE_TRANSITION: shape = "box"; break;
1665 case NODE_CHEST: shape = "house"; break;
1666 case NODE_ITEM: shape = "house"; break;
1667 case NODE_SWITCH: shape = "parallelogram"; break;
1668 default: break;
1669 }
1670 const char *special = "";
1671 if (node->_debug_blocked) {
1672 special = "fillcolor=grey";
1673 }
1674 fprintf(graphf, " n%p [label=\"%s\" shape=%s %s]\n", node, node->name, shape, special);
1675 }
1676 fprintf(graphf, "}\n");
1677
1678 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
1679 struct xy node_mid = XYMID(node->tl, node->br);
1680 if (XYL1DIST(link, node_mid) < link_min_dist) {
1681 link_min_dist = XYL1DIST(link, node_mid);
1682 link_nearest_node = node;
1683 }
1684
1685 if (node->adjacent_node != NULL) {
1686 fprintf(graphf, " n%p -> n%p [label=%s color=purple]\n", node, node->adjacent_node, dir_names[node->adjacent_direction]);
1687 fprintf(screenf, "s%#x -> s%#x;\n", screen->id, node->adjacent_node->screen->id);
1688 }
1689 if (node->type == NODE_CHEST) {
1690 if (ap_pathfind_node(node, false, -1) < 0) {
1691 fprintf(screenf, "s%#x [color=red];\n", screen->id);
1692 } else {
1693 fprintf(screenf, "s%#x [color=blue];\n", screen->id);
1694 }
1695 }
1696
1697 for (struct ap_node * node2 = node->next; node2 != screen->node_list; node2 = node2->next) {
1698 if (node->type != NODE_TRANSITION && node2->type != NODE_TRANSITION) continue;
1699 int dist1 = ap_pathfind_local(screen, XYMID(node->tl, node->br), node2->tl, node2->br, false);
1700 int dist2 = ap_pathfind_node_distance(node, node2);
1701 if (dist2 >= 0) {
1702 fprintf(graphf, " n%p -> n%p [color=blue dir=both]\n", node, node2);
1703 //assert(node->type != NODE_TRANSITION || dist1 >= 0);
1704 } else {
1705 //assert(node->type != NODE_TRANSITION || dist1 < 0);
1706 }
1707 }
1708 }
1709 }
1710 }
1711
1712 for (struct ap_goal * goal = ap_goal_list->next; goal != ap_goal_list; goal = goal->next) {
1713 if (goal->node == NULL) continue;
1714 fprintf(graphf, " n%p [color=red];\n", goal->node);
1715 }
1716
1717 fprintf(graphf, " n%p [color=green];\n", link_nearest_node);
1718 fprintf(graphf, "}\n");
1719 fclose(graphf);
1720
1721 fprintf(screenf, "}\n");
1722 fclose(screenf);
1723 LOG("Exported map graph to full_map.dot and screens to screen_map.dot");
1724}
1725
1726static void
1727ap_print_pathfind_local_state(struct point_state *buf, struct xy grid) {
1728 struct point_state (*state)[grid.x + 2] = (void *) &buf[0x83];
1729 struct xy link = ap_link_xy();
1730 link = XYOP1(link, & 0xFFF8);
1731
1732 FILE * mapf = fopen("local_cost.pgm.tmp", "w");
1733 fprintf(mapf, "P6 %u %u %u\n", grid.x, grid.y, 255);
1734 for (uint16_t y = 0; y < grid.y; y++) {
1735 for (uint16_t x = 0; x < grid.x; x++) {
1736 uint32_t cost = state[y][x].cost;
1737 uint8_t c = 0;
1738 if (cost >= (1 << 20)) {
1739 c = 0;
1740 } else if (cost >= 10000) {
1741 c = 25;
1742 } else if (cost >= 1000) {
1743 c = 40;
1744 } else if (cost > 200) {
1745 c = 50;
1746 } else {
1747 c = 255 - cost;
1748 }
1749 if (XYEQ(state[y][x].xy, link)) {
1750 fputc(0, mapf);
1751 fputc(255, mapf);
1752 fputc(c, mapf);
1753 } else {
1754 fputc(c, mapf);
1755 fputc(c, mapf);
1756 fputc(c, mapf);
1757 }
1758 }
1759 }
1760 fclose(mapf);
1761 rename("local_cost.pgm.tmp", "local_cost.pgm");
1762}
1763
1764void
1765ap_print_map_full()
1766{
1767 ap_print_state();
1768 ap_print_map_graph();
1769 FILE * mapf = fopen("full_map.pgm.tmp", "w");
1770 uint16_t size_x = 0, size_y = 0;
1771 for (size_t i = 0; i < 0xC0; i++) {
1772 if (map_screen_mask_x[i]) size_x += 0x100 / 8;
1773 if (map_screen_mask_y[i]) size_y += 0x100 / 8;
1774 }
1775 fprintf(mapf, "P6 %u %u %u\n", size_x, size_y, 255);
1776 //fprintf(mapf, "P6 %u %u %u\n", 0x800, 0x800, 255);
1777
1778 struct xy link = ap_link_xy();
1779 struct xy link_tl = link;
1780 struct xy link_br = XYOP1(link, + 15);
1781
1782 // Overworld: (0, 0)
1783 // Dark World: (0, 1)?
1784 // Underworld: (4, 0) x (7, 2)?
1785 // Zora's Domain: ?
1786 // Pedistal: ?
1787 //for (struct xy xy = XY(0, 0); xy.y < 0x8000; xy.y += 8) {
1788 for (struct xy xy = XY(0, 0); xy.y < 0x8000; xy.y += 8) {
1789 if (!map_screen_mask_y[xy.y / 0x100]) continue;
1790 //for (xy.x = 0; xy.x < 0x8000; xy.x += 8) {
1791 for (xy.x = 0; xy.x < 0xC000; xy.x += 8) {
1792 if (!map_screen_mask_x[xy.x / 0x100]) continue;
1793 //if (xy.x >= 0x1000 && xy.x < 0x4000) continue;
1794 //if ((xy.y & 0x2000) || (xy.x & 0x2000)) continue;
1795 if ((xy.y % 0x1000) == 0 || (xy.x % 0x1000) == 0) {
1796 fputc(200, mapf);
1797 fputc(0, mapf);
1798 fputc(200, mapf);
1799 goto next_point;
1800 }
1801 uint8_t tile_attr = 0x80; // default: grey
1802 struct ap_screen * screen = map_screens[XYMAPSCREEN(xy)];
1803 if (screen != NULL) {
1804 tile_attr = ap_map_attr(xy);
1805 }
1806 if (screen != NULL && (xy.y % 0x100) == 8 && (xy.x % 0x100) == 8) {
1807 if (screen->dungeon_room != (uint16_t) -1) {
1808 uint16_t state = ap_ram.sram_room_state[screen->dungeon_room];
1809 //LOG("Room: %#6x State: %#6x", screen->dungeon_room, state);
1810 if ((xy.y % 0x200) == 8 && (xy.x % 0x200) == 8) {
1811 fputc(100, mapf); fputc(50, mapf); fputc((state & 0x8) ? 255 : 20, mapf);
1812 } else if ((xy.y % 0x200) == 8) {
1813 fputc(100, mapf); fputc(50, mapf); fputc((state & 0x4) ? 255 : 20, mapf);
1814 } else if ((xy.x % 0x200) == 8) {
1815 fputc(100, mapf); fputc(50, mapf); fputc((state & 0x2) ? 255 : 20, mapf);
1816 } else {
1817 fputc(100, mapf); fputc(50, mapf); fputc((state & 0x1) ? 255 : 20, mapf);
1818 }
1819 goto next_point;
1820 }
1821 }
1822 if (screen != NULL && (xy.y % 0x200) == 16 && (xy.x % 0x200) < (8 * 13)) {
1823 uint16_t state = ap_ram.sram_room_state[screen->dungeon_room];
1824 uint8_t bit = (xy.x % 0x200) / 8;
1825 if (bit > 0 && screen->dungeon_room != (uint16_t) -1) {
1826 fputc(100, mapf);
1827 fputc((state & (1 << (15 - bit))) ? 255 : 20, mapf);
1828 fputc(20, mapf);
1829 goto next_point;
1830 }
1831 }
1832 if (XYIN(xy, link_tl, link_br)) {
1833 fputc(0, mapf);
1834 fputc(128, mapf);
1835 fputc(0, mapf);
1836 goto next_point;
1837 }
1838 for (size_t i = 0; i < ap_target_count; i++) {
1839 if (XYIN(xy, ap_targets[i].tl, XYOP1(ap_targets[i].tl, +8))) {
1840 fputc(0, mapf);
1841 fputc(255 - tile_attr, mapf);
1842 fputc(255, mapf);
1843 goto next_point;
1844 }
1845 }
1846 for (struct ap_goal * goal = ap_goal_list->next; goal != ap_goal_list; goal = goal->next) {
1847 if (goal->node == NULL) {
1848 continue;
1849 }
1850 if (XYIN(xy, goal->node->tl, goal->node->br)) {
1851 //if (ap_graph_is_blocked(&goal->graph)) {
1852 if (!ap_req_is_satisfied(&goal->req)) {
1853 fprintf(mapf, "%c%c%c", 200, 0, 100);
1854 } else {
1855 fprintf(mapf, "%c%c%c", 255, 255 - goal->attempts * 64, 0);
1856 }
1857 goto next_point;
1858 }
1859 }
1860 if (screen != NULL) {
1861 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
1862 if (node->adjacent_node == NULL)
1863 continue;
1864 if (!XYIN(xy, node->tl, node->br))
1865 continue;
1866 fprintf(mapf, "%c%c%c", 128, 255, 0);
1867 goto next_point;
1868 }
1869 }
1870 fputc(255 - tile_attr, mapf);
1871 fputc(255 - tile_attr, mapf);
1872 fputc(255 - tile_attr, mapf);
1873next_point:;
1874 }
1875 }
1876 fclose(mapf);
1877 rename("full_map.pgm.tmp", "full_map.pgm");
1878 LOG("Exported full map");
1879}
1880
1881void
1882ap_print_state()
1883{
1884 FILE * mapf = fopen("map_attrs.pgm", "w");
1885 fprintf(mapf, "P5 %u %u %u\n", 0x1000, 0x1000, 255);
1886 for (struct xy xy = XY(0, 0); xy.y < 0x8000; xy.y += 8) {
1887 for (xy.x = 0; xy.x < 0x8000; xy.x += 8) {
1888 uint8_t tile_attr = 0xFF; // default
1889 struct ap_screen * screen = map_screens[XYMAPSCREEN(xy)];
1890 if (screen != NULL) {
1891 tile_attr = ap_map_attr(xy);
1892 }
1893 fputc(tile_attr, mapf);
1894 }
1895 }
1896 fclose(mapf);
1897 LOG("Exported map_attrs.pgm");
1898
1899 FILE * screenf = fopen("screens.txt", "w");
1900 for (size_t i = 0; i < sizeof(map_screens) / sizeof(*map_screens); i++) {
1901 struct ap_screen * screen = map_screens[i];
1902 if (screen == NULL)
1903 continue;
1904 if (XYMAPSCREEN(screen->tl) != i)
1905 continue;
1906 fprintf(screenf, "[screen %s]\n", screen->name);
1907 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
1908 struct ap_node n;
1909 n.tl = XYOP2(node->tl, -, screen->tl);
1910 n.br = XYOP2(node->br, -, screen->tl);
1911 fprintf(screenf, " node: %s " PRIBBWH " ", node->name, PRIBBWHF(n));
1912 if (node->type == NODE_TRANSITION) {
1913 if (node->adjacent_node) {
1914 fprintf(screenf, "to screen %s node %s", node->adjacent_node->screen->name, node->adjacent_node->name);
1915 } else {
1916 fprintf(screenf, "unmapped");
1917 }
1918 }
1919 fprintf(screenf, "\n");
1920 }
1921 }
1922 fclose(screenf);
1923 LOG("Exported screens.txt");
1924}
1925
1926int
1927ap_pathfind_node(struct ap_node * node, bool commit, int max_distance)
1928{
1929 /*
1930 if (node->adjacent_direction) {
1931 struct xy offset = XYOP1(dir_dxy[node->adjacent_direction], * -7);
1932 tl = XYOP2(tl, +, offset);
1933 br = XYOP2(br, +, offset);
1934 }
1935 */
1936 bool unlockable = false;
1937 const struct ap_room_tag * unlock_tag = NULL;
1938 if (ap_node_islocked(node, &unlockable, &unlock_tag) && !unlockable) {
1939 return -1;
1940 }
1941 struct xy link = ap_link_xy();
1942 ap_target_sprite_index = 0;
1943 return ap_pathfind_global(link, node, commit, max_distance);
1944}
1945
1946int
1947ap_pathfind_sprite(size_t sprite_idx)
1948{
1949 struct xy link = ap_link_xy();
1950 struct ap_screen * screen = map_screens[XYMAPSCREEN(link)];
1951 assert(screen != NULL);
1952 assert_bp(XYIN(ap_sprites[sprite_idx].tl, screen->tl, screen->br));
1953 ap_target_sprite_index = sprite_idx;
1954 return ap_pathfind_local(screen, link, ap_sprites[sprite_idx].tl, ap_sprites[sprite_idx].br, true);
1955}
1956
1957static void
1958array_reverse(void *array_base, size_t item_size, size_t array_len) {
1959 uint8_t buf[item_size];
1960 uint8_t (*array)[item_size] = array_base;
1961 for (size_t i = 0; i < array_len / 2; i++) {
1962 size_t j = array_len - 1 - i;
1963 assert(j > i);
1964 memcpy(buf, array[i], item_size);
1965 memcpy(array[i], array[j], item_size);
1966 memcpy(array[j], buf, item_size);
1967 }
1968}
1969static void
1970array_reverse_test() {
1971 char buf[32] = "123 456 789 abc def ";
1972 array_reverse(buf, 4, 5);
1973 assert_bp(strcmp(buf, "def abc 789 456 123 ") == 0);
1974 array_reverse(buf, 4, 4);
1975 assert_bp(strcmp(buf, "456 789 abc def 123 ") == 0);
1976 array_reverse(buf, 1, 3);
1977 assert_bp(strcmp(buf, "654 789 abc def 123 ") == 0);
1978}
1979
1980int
1981ap_set_script(const struct ap_script * script) {
1982 LOG("Setting script: %s", script->name);
1983 assert(script->type == SCRIPT_SEQUENCE);
1984 assert(script->sequence != NULL);
1985 struct xy xy = script->start_tl;
1986 size_t i = 0;
1987 uint16_t dir_mask = SNES_MASK(UP) | SNES_MASK(DOWN) | SNES_MASK(LEFT) | SNES_MASK(RIGHT);
1988 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad = 0, .joypad_mask = 0 };
1989 for (const char *s = script->sequence; *s != '\0'; s++) {
1990 switch (*s) {
1991 case '<':
1992 xy.x -= 16;
1993 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad = 0, .joypad_mask = 0 };
1994 break;
1995 case '>':
1996 xy.x += 16;
1997 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad = 0, .joypad_mask = 0 };
1998 break;
1999 case '^':
2000 xy.y -= 16;
2001 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad = 0, .joypad_mask = 0 };
2002 break;
2003 case 'v':
2004 xy.y += 16;
2005 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad = 0, .joypad_mask = 0 };
2006 break;
2007 case 'A':
2008 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(A), .joypad = 0, };
2009 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(A), .joypad = SNES_MASK(A), };
2010 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(A), .joypad = 0, };
2011 break;
2012 case 'B':
2013 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(B), .joypad = 0, };
2014 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(B), .joypad = SNES_MASK(B), };
2015 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(B), .joypad = 0, };
2016 break;
2017 case 'Y':
2018 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(Y), .joypad = 0, };
2019 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(Y), .joypad = SNES_MASK(Y), };
2020 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = SNES_MASK(Y), .joypad = 0, };
2021 break;
2022 case 'U':
2023 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = dir_mask, .joypad = 0, };
2024 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = dir_mask, .joypad = SNES_MASK(UP), };
2025 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = dir_mask, .joypad = 0, };
2026 break;
2027 case 'D':
2028 ap_targets[i++] = (struct ap_target) { .tl = xy, .joypad_mask = dir_mask, .joypad = SNES_MASK(DOWN), };
2029 break;
2030 default:
2031 LOG("Unhandled character in sequence: '%c'", *s);
2032 assert_bp(false);
2033 break;
2034 }
2035 }
2036 if (ap_targets[i].joypad != 0) {
2037 ap_targets[i+1] = ap_targets[i];
2038 ap_targets[i+1].joypad = 0;
2039 ap_targets[i+1].joypad_mask = 0;
2040 i++;
2041 }
2042 array_reverse(ap_targets, sizeof(*ap_targets), i);
2043 int timeout = ap_set_targets(i);
2044 ap_target_dst_tl = xy;
2045 ap_target_dst_br = XYOP1(xy, + 15);
2046 ap_target_screen = map_screens[XYMAPSCREEN(xy)];
2047 ap_target_scripted = true;
2048
2049 LOG("Script timeout: %d", timeout);
2050 return timeout;
2051}
2052
2053static void
2054ap_screen_add_raw_node(struct ap_screen * screen, struct ap_node * new_node)
2055{
2056 // Pair overlays
2057 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2058 if (XYEQ(node->tl, new_node->tl) && XYEQ(node->br, new_node->br)) {
2059 if (node->type == NODE_TRANSITION && new_node->type == NODE_OVERLAY) {
2060 node->lock_node = new_node;
2061 } else if (node->type == NODE_OVERLAY && new_node->type == NODE_TRANSITION) {
2062 new_node->lock_node = node;
2063 }
2064 }
2065 }
2066
2067 // Attach to screen
2068 new_node->screen = screen;
2069 LL_INIT(new_node);
2070 LL_PUSH(screen->node_list, new_node);
2071 LOG("attached node %s", new_node->name);
2072
2073 // XXX This needs to be refactored to pair switches w/ doors
2074 // XXX Moved to ap_node_islocked
2075 /*
2076 if (new_node->type == NODE_SWITCH) {
2077 // Assign all doors to this switch
2078 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2079 if (node->lock_node == NULL && !XYEQ(node->locked_xy, XY(0, 0))) {
2080 LOGB("Assigning switch %s to unlock door %s", new_node->name, node->name);
2081 node->lock_node = new_node;
2082 break;
2083 }
2084 }
2085 }
2086 if (!XYEQ(new_node->locked_xy, XY(0, 0))) {
2087 // Assign the first switch we find to this door
2088 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2089 if (node->type == NODE_SWITCH) {
2090 LOGB("Assigning switch %s to unlock door %s", node->name, new_node->name);
2091 new_node->lock_node = node;
2092 break;
2093 }
2094 }
2095 LOGB("Unlock door %s = %p", new_node->name, new_node->lock_node);
2096 }
2097 */
2098
2099 // Add goals & locations
2100 switch (new_node->type) {
2101 case NODE_TRANSITION:
2102 if (add_explore_goals_global || (screen->info != NULL && screen->info->add_explore_goals)) {
2103 if (new_node->adjacent_node == NULL && new_node->adjacent_direction != 0)
2104 new_node->goal = ap_goal_add(GOAL_EXPLORE, new_node);
2105 }
2106 break;
2107 case NODE_ITEM:
2108 //ap_item_loc_add(new_node);
2109 new_node->goal = ap_goal_add(GOAL_PICKUP, new_node);
2110 break;
2111 case NODE_CHEST:
2112 new_node->locked_xy = XYOP2(new_node->tl, -, XY(0, 16));
2113 ap_item_loc_add(new_node);
2114 new_node->goal = ap_goal_add(GOAL_CHEST, new_node);
2115 break;
2116 case NODE_KEYBLOCK:
2117 //new_node->goal = ap_goal_add(GOAL_XXX new_node);
2118 break;
2119 case NODE_SWITCH:
2120 //ap_goal_add(GOAL_EXPLORE, new_node);
2121 break;
2122 case NODE_SPRITE:;
2123 uint16_t attrs = ap_sprite_attrs_for_type(new_node->sprite_type, new_node->sprite_subtype, screen->dungeon_room);
2124 ap_item_loc_add(new_node);
2125 if (attrs & SPRITE_ATTR_TALK) {
2126 new_node->goal = ap_goal_add(GOAL_NPC, new_node);
2127 } else if (attrs & SPRITE_ATTR_ITEM) {
2128 ap_goal_add(GOAL_PICKUP, new_node);
2129 }
2130 break;
2131 case NODE_SCRIPT:
2132 new_node->goal = ap_goal_add(GOAL_SCRIPT, new_node);
2133 break;
2134 case NODE_OVERLAY:
2135 break;
2136 case NODE_NONE:
2137 default:
2138 assert_bp(false);
2139 ;
2140 }
2141
2142 // Update Graph
2143 /*
2144 if (new_node->goal != NULL) {
2145 ap_graph_add_prereq(&new_node->goal->graph, &screen->graph);
2146
2147 for (struct ap_node * node2 = screen->node_list->next; node2 != screen->node_list; node2 = node2->next) {
2148 if (node2 == new_node) continue;
2149 if (new_node->goal == NULL || node2->goal == NULL) continue;
2150 if (new_node->type != NODE_TRANSITION && node2->type != NODE_TRANSITION) continue;
2151 int dist1 = ap_pathfind_local(screen, XYMID(new_node->tl, new_node->br), node2->tl, node2->br, false);
2152 int dist2 = ap_pathfind_local(screen, XYMID(node2->tl, node2->br), new_node->tl, new_node->br, false);
2153 if (dist1 >= 0 && dist2 >= 0) {
2154 if (new_node->type == NODE_TRANSITION && node2->type == NODE_TRANSITION) {
2155 // XXX only the first new equiv is actually added; transitivity is assumed
2156 ap_graph_add_equiv(&node2->goal->graph, &new_node->goal->graph);
2157 } else if (new_node->type == NODE_TRANSITION) {
2158 ap_graph_add_prereq(&node2->goal->graph, &new_node->goal->graph);
2159 } else {
2160 ap_graph_add_prereq(&new_node->goal->graph, &node2->goal->graph);
2161 }
2162 }
2163 }
2164 }
2165 */
2166 if (new_node->screen->id == 0x1481 && new_node->adjacent_direction == DIR_L) {
2167 // Door into EP stalfos room
2168 //new_node->_debug_blocked = true;
2169 }
2170 if (strcmp(new_node->name, "door 0x5e") == 0 || strcmp(new_node->name, "door 0x65") == 0) {
2171 // Stateful Fairy Fountain room
2172 new_node->_debug_blocked = true;
2173 }
2174 if (strcmp(new_node->name, "door 0x11") == 0 || strcmp(new_node->name, "door 0x38") == 0) {
2175 // One-way overworld doors
2176 new_node->_debug_blocked = true;
2177 }
2178
2179 /*
2180 if (strcmp(new_node->name, "0x198A D 4") == 0) {
2181 new_node->_debug_blocked = false;
2182 } else if (strcmp(new_node->name, "0x1483 L 3") == 0) {
2183 new_node->_debug_blocked = true;
2184 } else if (strcmp(new_node->name, "0x148A L 4 l") == 0) {
2185 new_node->_debug_blocked = true;
2186 //} else if (new_node->screen->id == 0x0e50 && strcmp(new_node->name, "stairs U 0x5e") == 0) {
2187 // new_node->_debug_blocked = true;
2188 } else if (new_node->screen->id == 0x0c0a && strncmp(new_node->name, "door", 4) == 0) {
2189 new_node->_debug_blocked = true;
2190 } else if (new_node->screen->id == 0x0402 && strncmp(new_node->name, "door", 4) == 0) {
2191 new_node->_debug_blocked = true;
2192 }
2193 */
2194
2195}
2196
2197static struct ap_node *
2198ap_screen_commit_node(struct ap_screen * screen, struct ap_node ** new_node_p)
2199{
2200 struct ap_node * new_node = *new_node_p;
2201 NONNULL(new_node);
2202
2203 if (new_node->tl.x == 0 && new_node->tl.y == 0)
2204 return NULL;
2205 assert(new_node->type != NODE_NONE);
2206 assert(XYUNDER(new_node->tl, new_node->br));
2207
2208 // Check if the node already exists
2209 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2210 if (node->type != new_node->type)
2211 continue;
2212 if (node->adjacent_direction != new_node->adjacent_direction)
2213 continue;
2214 if (node->type != NODE_SPRITE) {
2215 if (XYEQ(node->tl, new_node->tl) && XYEQ(node->br, new_node->br)) {
2216 //assert_bp(node->tile_attr == new_node->tile_attr);
2217 } else if (XYIN(new_node->tl, node->tl, node->br) && XYIN(new_node->br, node->tl, node->br)) {
2218 //assert(node->adjacent_screen == new_node->adjacent_screen);
2219 // XXX This has a lot of false positives
2220 //assert_bp(node->tile_attr == new_node->tile_attr);
2221
2222 //LOG("duplicate node %s == %s", node->name, new_node->name);
2223
2224 // Merge in new information???
2225 LOGB("node tl/br would shrink: before: " PRIBBV " after: " PRIBBV, PRIBBVF(*node), PRIBBVF(*new_node));
2226 new_node->tl = node->tl;
2227 new_node->br = node->br;
2228 } else if (node->type == NODE_TRANSITION && XYIN(node->tl, new_node->tl, new_node->br) && XYIN(node->br, new_node->tl, new_node->br)) {
2229 //assert_bp(node->tile_attr == new_node->tile_attr);
2230 LOGB("node tl/br grew: before: " PRIBBV " after: " PRIBBV, PRIBBVF(*node), PRIBBVF(*new_node));
2231 } else {
2232 continue;
2233 }
2234 }
2235
2236 node->tl = new_node->tl;
2237 node->br = new_node->br;
2238 node->overlay_index = new_node->overlay_index;
2239 if (!XYEQ(new_node->locked_xy, XY(0, 0))) {
2240 node->locked_xy = new_node->locked_xy;
2241 }
2242
2243 memset(new_node, 0, sizeof *new_node);
2244 return node;
2245 }
2246
2247 // Merge paired stairs from upper to lower levels
2248 if (new_node->type == NODE_TRANSITION && (ap_tile_attrs[new_node->tile_attr] & TILE_ATTR_STRS) && new_node->adjacent_node == NULL && XYINDOORS(new_node->tl)) {
2249 struct xy alt_xy = XYOP2(XYFLIPBG(new_node->tl), + 48 *, dir_dxy[new_node->adjacent_direction]);
2250 struct ap_screen * alt_screen = map_screens[XYMAPSCREEN(alt_xy)];
2251 if (alt_screen != NULL) {
2252 for (struct ap_node * node = alt_screen->node_list->next; node != alt_screen->node_list; node = node->next) {
2253 if (node->type != NODE_TRANSITION)
2254 continue;
2255 if (node->adjacent_node != NULL)
2256 continue;
2257 if (node->adjacent_direction != dir_opp[new_node->adjacent_direction])
2258 continue;
2259 if (node->tile_attr != new_node->tile_attr)
2260 continue;
2261 if (!XYIN(alt_xy, node->tl, node->br))
2262 continue;
2263 //LOG("Paring nodes: %s <-> %s", node->name, new_node->name);
2264 node->adjacent_node = new_node;
2265 new_node->adjacent_node = node;
2266 break;
2267 }
2268 }
2269 }
2270
2271 ap_screen_add_raw_node(screen, new_node);
2272
2273 *new_node_p = NONNULL(calloc(1, sizeof **new_node_p));
2274 return new_node;
2275}
2276
2277static void
2278ap_update_map_screen_nodes()
2279{
2280 // Update the nodes that already exist on the screen
2281 struct xy tl, br;
2282 ap_map_bounds(&tl, &br);
2283 size_t index = XYMAPSCREEN(tl);
2284 struct ap_screen * screen = NONNULL(map_screens[index]);
2285
2286 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2287 switch (node->type) {
2288 case NODE_SWITCH:;
2289 uint16_t mask = 0x0;
2290 switch(node->tile_attr) {
2291 case 0x23: mask = 0x8000; break;
2292 case 0x24: mask = 0x4000; break;
2293 case 0x25: mask = 0x2000; break; // XXX Wild guess
2294 case 0x26: mask = 0x1000; break; // XXX Wild guess
2295 default: assert(false);
2296 }
2297 if (*ap_ram.room_state & mask) {
2298 // what to update?
2299 }
2300 break;
2301 case NODE_SPRITE:
2302 break;
2303 case NODE_CHEST:
2304 case NODE_KEYBLOCK:
2305 case NODE_ITEM:
2306 case NODE_TRANSITION:
2307 case NODE_NONE:
2308 default:;
2309 }
2310 }
2311}
2312
2313static void ap_map_add_nodes_to_screen(struct ap_screen * screen);
2314static void ap_map_add_scripts_to_screen(struct ap_screen * screen);
2315static void ap_map_add_constants_to_screen(struct ap_screen * screen);
2316
2317static int ap_node_distance_cmp(const void *a, const void *b) {
2318 return memcmp(a, b, sizeof(struct ap_node_distance));
2319}
2320
2321static void ap_map_screen_update_distances(struct ap_screen * screen) {
2322 size_t n_transition_nodes = 0;
2323 size_t n_other_nodes = 0;
2324 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2325 if (node->type == NODE_TRANSITION || node->type == NODE_KEYBLOCK) {
2326 n_transition_nodes++;
2327 } else {
2328 n_other_nodes++;
2329 }
2330 }
2331
2332 size_t req_capcacity = n_transition_nodes * (n_transition_nodes + n_other_nodes);
2333 if (req_capcacity > screen->distances_capacity) {
2334 screen->distances = NONNULL(realloc(screen->distances, req_capcacity * sizeof(*screen->distances)));
2335 screen->distances_capacity = req_capcacity;
2336 }
2337 memset(screen->distances, 0, req_capcacity * sizeof(*screen->distances));
2338
2339 size_t d = 0;
2340 for (struct ap_node * src = screen->node_list->next; src != screen->node_list; src = src->next) {
2341 if (src->type != NODE_TRANSITION && src->type != NODE_KEYBLOCK) {
2342 continue;
2343 }
2344 for (struct ap_node * dst = screen->node_list->next; dst != screen->node_list; dst = dst->next) {
2345 int distance = ap_pathfind_local(screen, XYMID(src->tl, src->br), dst->tl, dst->br, false);
2346 if (distance < 0) {
2347 continue;
2348 }
2349 screen->distances[d++] = (struct ap_node_distance) {
2350 .src = src,
2351 .dst = dst,
2352 .distance = (uint64_t) distance,
2353 };
2354 }
2355 }
2356 assert(d <= req_capcacity);
2357 screen->distances_length = d;
2358 qsort(screen->distances, d, sizeof(*screen->distances), &ap_node_distance_cmp);
2359}
2360
2361struct ap_screen *
2362ap_update_map_screen(bool force)
2363{
2364 struct xy tl, br;
2365 ap_map_bounds(&tl, &br);
2366 size_t index = XYMAPSCREEN(tl);
2367 static size_t last_map_index = -1;
2368 //static uint8_t last_trap_doors = 0;
2369 //last_trap_doors = *ap_ram.room_trap_doors;
2370 last_screen = map_screens[index];
2371
2372 struct ap_screen * screen = map_screens[index];
2373 if (screen == NULL) {
2374 struct xy cells[8] = {
2375 XY(0x000, 0x000), XY(0x100, 0x000),
2376 XY(0x000, 0x100), XY(0x100, 0x100),
2377 XY(0x200, 0x000), XY(0x300, 0x000),
2378 XY(0x200, 0x100), XY(0x300, 0x100),
2379 };
2380 bool indoors = XYINDOORS(tl);
2381 for (size_t i = 0; i < (indoors ? 8 : 1); i++) {
2382 struct xy cell_tl, cell_br;
2383 if (indoors) {
2384 cell_tl = XYOP2(XYOP2(tl, &~, cells[7]), |, cells[i]);
2385 ap_map_room_bounds(cell_tl, &cell_tl, &cell_br);
2386 } else {
2387 cell_tl = tl;
2388 cell_br = br;
2389 }
2390 if (map_screens[XYMAPSCREEN(cell_tl)] != NULL) continue;
2391
2392 screen = calloc(1, sizeof *screen);
2393 screen->tl = cell_tl;
2394 screen->br = cell_br;
2395 screen->id = (screen->tl.x >> 8) | (screen->tl.y & 0xFF00);
2396 if (indoors) {
2397 screen->dungeon_id = *ap_ram.dungeon_id / 2;
2398 screen->dungeon_room = *ap_ram.dungeon_room;
2399 screen->dungeon_tags = *ap_ram.dungeon_tags;
2400 } else {
2401 screen->dungeon_id = -1;
2402 screen->dungeon_room = -1;
2403 screen->dungeon_tags = 0;
2404 }
2405 const char * suffix = "";
2406 if (XYINDOORS(screen->tl)) {
2407 if (XYONUPPER(screen->tl)) {
2408 screen->id &= ~0x2;
2409 suffix = " ^";
2410 } else {
2411 suffix = " v";
2412 }
2413 }
2414 for (const struct ap_screen_info * info = ap_screen_infos; info->id != (uint16_t) -1; info++) {
2415 if (info->id == screen->id) {
2416 screen->info = info;
2417 break;
2418 }
2419 }
2420 //ap_graph_init(&screen->graph, screen->name);
2421 LL_INIT(screen->node_list);
2422 if (screen->info) {
2423 snprintf(screen->name, sizeof screen->name, "%s%s %#x " PRIXY " x " PRIXY, screen->info->name, suffix, screen->dungeon_tags, PRIXYF(cell_tl), PRIXYF(cell_br));
2424 } else {
2425 snprintf(screen->name, sizeof screen->name, "%#06x%s %#x " PRIXYV " x " PRIXYV, screen->id, suffix, screen->dungeon_tags, PRIXYVF(cell_tl), PRIXYVF(cell_br));
2426
2427 }
2428
2429 struct xy xy;
2430 for (xy.y = cell_tl.y; xy.y < cell_br.y; xy.y += 0x100) {
2431 for (xy.x = cell_tl.x; xy.x < cell_br.x; xy.x += 0x100) {
2432 map_screens[XYMAPSCREEN(xy)] = screen;
2433 map_screen_mask_x[xy.x / 0x100] = true;
2434 map_screen_mask_y[xy.y / 0x100] = true;
2435 }
2436 }
2437
2438 ap_screen_refresh_cache(screen);
2439 ap_map_add_nodes_to_screen(screen);
2440 ap_map_add_scripts_to_screen(screen);
2441 ap_map_add_constants_to_screen(screen);
2442 ap_map_add_sprite_nodes_to_screen(screen);
2443 ap_map_screen_update_distances(screen);
2444 }
2445 screen = map_screens[index];
2446 } else {
2447 bool needs_refresh = !(index == last_map_index && !force);
2448 if (!needs_refresh && !XYINDOORS(screen->tl)) {
2449 ap_update_map_screen_nodes();
2450 return NONNULL(map_screens[index]);
2451 }
2452
2453 bool cache_changed = ap_screen_refresh_cache(screen);
2454 if (!cache_changed && index == last_map_index && !force) {
2455 ap_update_map_screen_nodes();
2456 return NONNULL(map_screens[index]);
2457 }
2458 ap_map_add_nodes_to_screen(screen);
2459 ap_map_add_sprite_nodes_to_screen(screen);
2460 }
2461 last_map_index = index;
2462
2463 ap_map_screen_update_distances(screen);
2464
2465 //ap_graph_mark_done(&screen->graph);
2466 ap_sprites_print();
2467 ap_ancillia_print();
2468 ap_print_map_screen(screen);
2469 // TODO: Skip this if link is not yet on the screen
2470 printf("Nodes: [(un)Reachable? (un)Adjacent?] (tl x br) type \"name\"\n");
2471
2472 int i = 0;
2473 for (struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2474 bool reachable = ap_pathfind_local(screen, ap_link_xy(), node->tl, node->br, false) >= 0;
2475 node->_reachable = reachable;
2476 printf(" %d. %p [%c%c] (" PRIXY " x " PRIXY ") %s \"%s\"\n",
2477 i++, node, "uR"[reachable], "uA"[node->adjacent_node != NULL], PRIXYF(node->tl), PRIXYF(node->br), ap_node_type_names[node->type], node->name);
2478
2479 }
2480
2481 return screen;
2482}
2483
2484static void ap_map_add_scripts_to_screen(struct ap_screen * screen) {
2485 for (size_t i = 0; i < ARRAYLEN(ap_scripts); i++) {
2486 const struct ap_script * script = &ap_scripts[i];
2487 if (!XYIN(script->start_tl, screen->tl, screen->br)) {
2488 continue;
2489 }
2490
2491 struct ap_node * new_node = NONNULL(calloc(1, sizeof *new_node));
2492 new_node->type = NODE_SCRIPT;
2493 new_node->tl = script->start_tl;
2494 new_node->br = XYOP1(script->start_tl, +15);
2495 new_node->script = script;
2496 snprintf(new_node->name, sizeof new_node->name, "Script: %s", script->name);
2497
2498 ap_screen_add_raw_node(screen, new_node);
2499 }
2500}
2501
2502static void ap_map_add_constants_to_screen(struct ap_screen * screen) {
2503 if (!XYINDOORS(screen->tl)) {
2504 screen->quadmask = QUAD_ALL;
2505 screen->room_tags[0] = NULL;
2506 screen->room_tags[1] = NULL;
2507 } else {
2508 // Quadrants are 0x100 x 0x100 big
2509 screen->quadmask = 0;
2510 struct xy tl = XYOP1(screen->tl, & 0x1FF);
2511 struct xy br = XYOP1(screen->br, & 0x1FF);
2512 struct {
2513 uint8_t q;
2514 struct xy xy;
2515 } points[4] = {
2516 { .q = QUAD_A, .xy = XY(0x080, 0x080), },
2517 { .q = QUAD_B, .xy = XY(0x180, 0x080), },
2518 { .q = QUAD_C, .xy = XY(0x080, 0x180), },
2519 { .q = QUAD_D, .xy = XY(0x180, 0x180), },
2520 };
2521 for (size_t i = 0; i < 4; i++) {
2522 if (XYIN(points[i].xy, tl, br)) {
2523 screen->quadmask |= points[i].q;
2524 }
2525 }
2526
2527 // Room Tags
2528 uint8_t index_1 = screen->dungeon_tags & 0xFF;
2529 uint8_t index_2 = (screen->dungeon_tags >> 8) & 0xFF;
2530 assert(index_1 < 0x40 && index_2 < 0x40);
2531 const struct ap_room_tag * tag_1 = &ap_room_tags[index_1];
2532 const struct ap_room_tag * tag_2 = &ap_room_tags[index_2];
2533
2534 size_t t = 0;
2535 screen->room_tags[0] = NULL;
2536 screen->room_tags[0] = NULL;
2537 if (tag_1->quadmask & screen->quadmask) {
2538 screen->room_tags[t++] = tag_1;
2539 assert_bp(!tag_1->unsure);
2540 }
2541 if (tag_2->quadmask & screen->quadmask) {
2542 screen->room_tags[t++] = tag_2;
2543 assert_bp(!tag_2->unsure);
2544 }
2545
2546 LOGB("Screen tags: %s %s; %s",
2547 ap_room_tag_print(screen->room_tags[0]),
2548 ap_room_tag_print(screen->room_tags[1]),
2549 screen->name);
2550 }
2551}
2552
2553static void
2554ap_map_add_sprite_nodes_to_screen(struct ap_screen * screen) {
2555 static struct ap_node * new_node = NULL;
2556 if (new_node == NULL)
2557 new_node = NONNULL(calloc(1, sizeof *new_node));
2558
2559 for (size_t i = 0; i < N_SPRITES; i++) {
2560 if (ap_sprites[i].type == 0)
2561 continue;
2562 if (ap_sprites[i].attrs & SPRITE_ATTR_NODE) {
2563 new_node->tl = ap_sprites[i].tl;
2564 if (!XYIN(new_node->tl, screen->tl, screen->br)) {
2565 LOG("Sprite %zu out of screen", i);
2566 } else {
2567 new_node->type = NODE_SPRITE;
2568 new_node->br = ap_sprites[i].br;
2569 new_node->sprite_type = ap_sprites[i].type;
2570 new_node->sprite_subtype = ap_sprites[i].subtype;
2571 /*
2572 if (ap_sprites[i].attrs & SPRITE_ATTR_TALK) {
2573 new_node->tl = XYOP2(ap_sprites[i].hitbox_tl, +, XY(0, 16));
2574 new_node->br = XYOP2(ap_sprites[i].hitbox_tl, +, XY(15, 31));
2575 }
2576 */
2577 snprintf(new_node->name, sizeof new_node->name, "sprite %#x.%#x %s", new_node->sprite_type, new_node->sprite_subtype, ap_sprite_attr_name(ap_sprites[i].attrs));
2578 ap_screen_commit_node(screen, &new_node);
2579 }
2580 }
2581 }
2582
2583 for (size_t i = 0; i < N_ANCILLIA; i++) {
2584 if (ap_ancillia[i].type == 0)
2585 continue;
2586 if (ap_ancillia[i].attrs & SPRITE_ATTR_NODE) {
2587 new_node->tl = ap_ancillia[i].tl;
2588 if (!XYIN(new_node->tl, screen->tl, screen->br)) {
2589 LOG("Ancillia %zu out of screen", i);
2590 } else {
2591 new_node->type = NODE_SPRITE;
2592 new_node->br = ap_ancillia[i].br;
2593 new_node->sprite_type = ap_ancillia[i].type;
2594 new_node->sprite_subtype = 0;
2595 /*
2596 if (ap_ancillia[i].attrs & SPRITE_ATTR_TALK) {
2597 new_node->tl = XYOP2(ap_ancillia[i].hitbox_tl, +, XY(0, 16));
2598 new_node->br = XYOP2(ap_ancillia[i].hitbox_tl, +, XY(15, 31));
2599 }
2600 */
2601 snprintf(new_node->name, sizeof new_node->name, "ancillia %#x %s", new_node->sprite_type, ap_sprite_attr_name(ap_ancillia[i].attrs));
2602 ap_screen_commit_node(screen, &new_node);
2603 }
2604 }
2605 }
2606}
2607
2608static void
2609ap_map_add_nodes_to_screen(struct ap_screen * screen) {
2610 struct xy tl = screen->tl;
2611 struct xy br = screen->br;
2612 size_t index = XYMAPSCREEN(tl);
2613 struct xy link = ap_link_xy();
2614
2615 int new_node_count = 0;
2616 static struct ap_node * new_node = NULL;
2617 if (new_node == NULL)
2618 new_node = NONNULL(calloc(1, sizeof *new_node));
2619
2620 uint16_t lift_mask = TILE_ATTR_LFT0;
2621 if (*ap_ram.inventory_gloves >= 1) lift_mask |= TILE_ATTR_LFT1;
2622 if (*ap_ram.inventory_gloves >= 2) lift_mask |= TILE_ATTR_LFT2;
2623
2624 //uint16_t walk_mask = TILE_ATTR_WALK | TILE_ATTR_SWIM;
2625 uint16_t walk_mask = TILE_ATTR_WALK;
2626 const uint8_t dirs[4] = {
2627 // Top, Botton, Left, Right edges
2628 DIR_U, DIR_D, DIR_L, DIR_R,
2629 };
2630 const struct xy xy_init[4] = {
2631 tl, XY(tl.x, br.y & ~7), tl, XY(br.x & ~7, tl.y),
2632 };
2633 const struct xy xy_step[4] = {
2634 dir_dxy[DIR_R], dir_dxy[DIR_R], dir_dxy[DIR_D], dir_dxy[DIR_D],
2635 };
2636 uint16_t masks[4] = {
2637 walk_mask, walk_mask, walk_mask, walk_mask,
2638 };
2639 uint8_t f = 2;
2640
2641 for (uint8_t k = 0; k < 4; k++) {
2642 uint8_t i = dirs[k];
2643 struct xy new_start = XY(0, 0);
2644 struct xy new_end = XY(0, 0);
2645 size_t size = 0;
2646
2647 for (struct xy xy = xy_init[k]; XYIN(xy, tl, br); xy = XYOP2(xy, +, XYOP1(xy_step[k], * 8))) {
2648 for (; XYIN(xy, tl, br); xy = XYOP2(xy, +, XYOP1(xy_step[k], * 8))) {
2649 bool can_walk = true;
2650 //if (XYINDOORS(xy) && (ap_map_attr(xy) == 0x00 || ap_map_attr(xy) == 0x1c)) {
2651 if (XYINDOORS(xy) && (ap_map_attr_from_ram(xy) == 0x1c)) {
2652 // NOTE: sometimes 0's are actually walkable
2653 // inside, border 0 or 1c is just empty
2654 // you could walk there, but you definitely can't get there
2655 can_walk = false;
2656 }
2657 for (int8_t j = 0; j < f + 2; j++) {
2658 struct xy lxy = XYOP2(xy, -, XYOP1(dir_dxy[i], * 8 * j));
2659 if (!(ap_tile_attrs[ap_map_attr_from_ram(lxy)] & masks[k])) {
2660 can_walk = false;
2661 break;
2662 }
2663 }
2664 if (can_walk) {
2665 new_end = XYOP2(xy, -, XYOP1(dir_dxy[i], * 8 * (f + 1)));
2666 for (int8_t j = f + 1; j < f + 8; j++) {
2667 struct xy lxy = XYOP2(new_end, -, XYOP1(dir_dxy[i], * 8));
2668 uint8_t attr = ap_map_attr_from_ram(lxy);
2669 // 0x80 through 0x9F are walkways between rooms
2670 // 0xF0 through 0xF8 are locked doors?
2671 if (attr < 0x80)
2672 break;
2673 else if (attr > 0x9F && attr < 0xF0)
2674 break;
2675 else if (attr > 0xF8)
2676 break;
2677 new_end = lxy;
2678 }
2679 if (size == 0) {
2680 //new_start = XYOP2(xy, -, XYOP1(dir_dxy[i], * 8 * f));
2681 new_start = xy;
2682 }
2683 size++;
2684 } else if (size < 2) {
2685 new_start = new_end = XY(0, 0);
2686 size = 0;
2687 } else {
2688 break;
2689 }
2690 }
2691 if (XYEQ(new_start, XY(0, 0)) && XYEQ(new_end, XY(0, 0))) {
2692 size = 0;
2693 continue;
2694 }
2695 new_node->tl = XYFN2(MIN, new_start, new_end);
2696 new_node->br = XYFN2(MAX, new_start, new_end);
2697 new_node->br = XYOP1(new_node->br, + 7);
2698 new_node->type = NODE_TRANSITION;
2699 new_node->adjacent_direction = i;
2700 new_node->tile_attr = ap_map_attr_from_ram(ap_box_edge(new_node->tl, new_node->br, i));
2701 new_node->locked_xy = XY(0, 0);
2702 if ((new_node->tile_attr & 0xF8) == 0x80) { // locked door
2703 new_node->locked_xy = ap_box_edge(new_node->tl, new_node->br, dir_opp[i]);
2704 new_node->locked_xy = XYOP1(new_node->locked_xy, &~7);
2705 uint8_t attr = ap_map_attr_from_ram(new_node->locked_xy);
2706 }
2707 // Skip unreachable border nodes
2708 if (new_node->tile_attr == 0x00 || (!XYINDOORS(link) && new_node->tile_attr == 0x48)) {
2709 bool is_reachable = false;
2710 if (screen->info != NULL && screen->info->include_borders) {
2711 is_reachable = true;
2712 } else if (XYIN(link, tl, br)) {
2713 is_reachable = ap_pathfind_local(screen, link, new_node->tl, new_node->br, false) > 0;
2714 } else {
2715 // XXX This is such a hack
2716 struct xy test_xy = XYMID(tl, br);
2717 is_reachable = ap_pathfind_local(screen, test_xy, new_node->tl, new_node->br, false) > 0;
2718 /*
2719 for (const struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
2720 if (ap_pathfind_local(screen, XYMID(node->tl, node->br), new_node->tl, new_node->br, false) > 0) {
2721 is_reachable = true;
2722 break;
2723 }
2724 }
2725 */
2726 }
2727 if (!is_reachable) {
2728 //if (!XYIN(link, tl, br) || ap_pathfind_local(screen, link, new_node->tl, new_node->br, false) < 0) {
2729 //if(!XYINDOORS(link)) assert_bp(false); // unreachable
2730 new_start = new_end = XY(0, 0);
2731 size = 0;
2732 continue;
2733 }
2734 }
2735
2736 //new_node->adjacent_screen = &map_screens[XYMAPSCREEN(XYOP2(new_node->tl, +, XYOP1(dir_dxy[i], * 0x100)))];
2737 snprintf(new_node->name, sizeof new_node->name, "0x%02zX %s %d%s", index, dir_names[i], ++new_node_count, XYEQ(new_node->locked_xy, XY(0, 0)) ? "" : " l");
2738 ap_screen_commit_node(screen, &new_node);
2739 new_start = new_end = XY(0, 0);
2740 size = 0;
2741 }
2742 }
2743 if (!*ap_ram.in_building) {
2744 //LOG("xo: %04x, xm: %04x, yo: %04x, ym: %04x", *ap_ram.map_x_offset, *ap_ram.map_x_mask, *ap_ram.map_y_offset, *ap_ram.map_y_mask);
2745 for (size_t i = 0; i < 0x81; i++) {
2746 if (ap_ram.over_ent_areas[i] != *ap_ram.map_area)
2747 continue;
2748
2749 uint16_t id = ap_ram.over_ent_ids[i];
2750 if (id > 0x85) {
2751 LOG("weird id: %u %zu", id, i);
2752 continue;
2753 }
2754 if (id == 0x5e || id == 0x65) {
2755 // Skip fairy fountain/Fortune teller; all doors lead to the same location and have state
2756 continue;
2757 }
2758
2759 struct xy original_xy = ap_map16_to_xy(tl, ap_ram.over_ent_map16s[i]);
2760 new_node->tl = ap_map16_to_xy(tl, ap_ram.over_ent_map16s[i]);
2761 if (id == 0x3c || id == 0x26 || id == 0x68) {
2762 // Door in a log is oddly placed
2763 new_node->tl.x -= 0x08;
2764 }
2765 new_node->tl.y += 16;
2766 new_node->br = XYOP1(new_node->tl, + 15);
2767 new_node->type = NODE_TRANSITION;
2768 //new_node->tile_attr = 0x80; // not quite true
2769 new_node->tile_attr = ap_map_attr_from_ram(original_xy);
2770 struct xy entrance = XY(ap_ram.entrance_xs[id], ap_ram.entrance_ys[id]);
2771 //new_node->adjacent_screen = &map_screens[XYMAPSCREEN(entrance)];
2772 new_node->adjacent_direction = DIR_U;
2773 snprintf(new_node->name, sizeof new_node->name, "door 0x%02x", ap_ram.over_ent_ids[i]);
2774 //LOG("tl: " PRIXYV ", out: " PRIXYV ", map16: %04x", PRIXYVF(tl), PRIXYVF(new_node->tl), ap_ram.over_ent_map16s[i]);
2775 ap_screen_commit_node(screen, &new_node);
2776 new_node_count++;
2777 }
2778
2779 // Overlays (Bombable Walls)
2780 uint16_t overlay_map16 = ap_ram.over_overlay_map16s[*ap_ram.overworld_index];
2781 if (overlay_map16 != 0) {
2782 new_node->overlay_index = *ap_ram.overworld_index;
2783 new_node->tl = ap_map16_to_xy(tl, overlay_map16);
2784 new_node->br = XYOP1(new_node->tl, + 15);
2785 new_node->type = NODE_OVERLAY;
2786 new_node->tile_attr = 0;
2787 snprintf(new_node->name, sizeof new_node->name, "overlay %#x", *ap_ram.overworld_index);
2788 ap_screen_commit_node(screen, &new_node);
2789 new_node_count++;
2790 }
2791
2792 /* TODO: work out map16 decoding
2793 for (size_t i = 1; i < 0x1C; i++) {
2794 if (ap_ram.over_hle_areas[i] != *ap_ram.map_area)
2795 continue;
2796 new_node = ap_node_append(map_node);
2797 node_count++;
2798 new_node->tl = ap_map16_to_xy(tl, ap_ram.over_hle_map16s[i]);
2799 new_node->br = XYOP1(new_node->tl, + 15);
2800 snprintf(new_node->name, sizeof new_node->name, "hole 0x%02x", ap_ram.over_hle_ids[i]);
2801 }
2802 */
2803 }
2804 if (XYONUPPER(tl)) {
2805 // Inside on upper level, look for non-diagonal ledges
2806 // and add them as nodes
2807 for (struct xy xy = tl; xy.y < br.y; xy.y += 0x8) {
2808 for (xy.x = tl.x; xy.x < br.x; xy.x += 0x8) {
2809 uint8_t attr = ap_map_attr_from_ram(xy);
2810 int d = attr - 0x27;
2811 if (d <= 0 || d >= 5)
2812 continue;
2813 // In dungeons 0x28 is used for both up & down; 0x2A for both left & right
2814 // Look for the 0x1C "hole" to fall into
2815 if (ap_map_attr_from_ram(XYOP2(xy, + 8*, dir_dxy[d])) != 0x1C)
2816 d++;
2817 if (ap_map_attr_from_ram(XYOP2(xy, + 8*, dir_dxy[d])) != 0x1C)
2818 continue;
2819 static const int perp_dirs[5] = {0, DIR_R, DIR_R, DIR_D, DIR_D};
2820 uint8_t adj_attr = ap_map_attr_from_ram(XYOP2(xy, - 8*, dir_dxy[perp_dirs[d]]));
2821 if (adj_attr == attr)
2822 continue; // already made a node for this
2823 struct xy l_tl = xy;
2824 struct xy l_br = xy;
2825 bool valid_ledge = true;
2826 int ledge_size = 0;
2827 bool found_start = false;
2828 for (struct xy t = xy; XYUNDER(t, br); t = XYOP2(t, + 8*, dir_dxy[perp_dirs[d]])) {
2829 uint8_t t_attr = ap_map_attr_from_ram(t);
2830 if (ap_tile_attrs[t_attr] & TILE_ATTR_STRS) {
2831 // If there are stairs, omit the ledge (because you can just take the stairs)
2832 valid_ledge = false;
2833 } else if (t_attr != attr) {
2834 break;
2835 } else if (ap_tile_attrs[ap_map_attr_from_ram(XYOP2(t, - 8*, dir_dxy[d]))] & TILE_ATTR_WALK) {
2836 if (!found_start) {
2837 found_start = true;
2838 l_tl = t;
2839 }
2840 ledge_size++;
2841 } else if (found_start) {
2842 break;
2843 }
2844 l_br = t;
2845 }
2846 if (found_start && valid_ledge && ledge_size >= 2) {
2847 struct xy ledge_tl = l_tl;
2848 struct xy ledge_br = XYOP1(l_br, + 7);
2849 struct xy offset = XYOP1(dir_dxy[d], * 8);
2850 if (d == DIR_D || d == DIR_R) {
2851 ledge_tl = XYOP2(ledge_tl, -, XYOP1(offset, * 2));
2852 } else {
2853 ledge_br = XYOP2(ledge_br, -, XYOP1(offset, * 2));
2854 }
2855 // landing target
2856 new_node->type = NODE_TRANSITION;
2857 new_node->adjacent_direction = 0;
2858 new_node->tl = XYOP2(ledge_tl, +, XYOP1(offset, * 3));
2859 new_node->br = XYOP2(ledge_br, +, XYOP1(offset, * 3));
2860 new_node->tl.x ^= 0x200;
2861 new_node->br.x ^= 0x200;
2862 new_node->tile_attr = 0x1C; // a lie
2863 snprintf(new_node->name, sizeof new_node->name, "ledge %s landing", dir_names[d]);
2864 struct ap_screen * bottom_screen = NONNULL(map_screens[XYMAPSCREEN(new_node->tl)]);
2865 struct ap_node * landing = ap_screen_commit_node(bottom_screen, &new_node);
2866 new_node_count++;
2867
2868 new_node->tile_attr = attr;
2869 new_node->type = NODE_TRANSITION;
2870 new_node->adjacent_direction = d;
2871 new_node->tl = XYOP2(ledge_tl, -, XYOP1(offset, * 1));
2872 new_node->br = XYOP2(ledge_br, -, XYOP1(offset, * 1));
2873 new_node->adjacent_node = landing;
2874 snprintf(new_node->name, sizeof new_node->name, "ledge %sx%d", dir_names[d], ledge_size);
2875 ap_screen_commit_node(screen, &new_node);
2876 new_node_count++;
2877 }
2878
2879 xy.x = l_br.x;
2880 }
2881 }
2882 }
2883 size_t n_doors = 0;
2884 for (struct xy xy = tl; xy.y < br.y; xy.y += 0x10) {
2885 for (xy.x = tl.x; xy.x < br.x; xy.x += 0x10) {
2886 uint8_t attr = ap_map_attr_from_ram(xy);
2887 if (!(ap_tile_attrs[attr] & (TILE_ATTR_NODE | TILE_ATTR_DOOR)))
2888 continue;
2889 struct xy ds[4] = {XY(8, 8), XY(-8, -8), XY(-8, 8), XY(8, -8)};
2890 new_node->tl = new_node->br = XY(0, 0);
2891 for (int i = 0; i < 4; i++) {
2892 struct xy xy2 = XYOP2(xy, +, ds[i]);
2893 uint8_t attr2 = ap_map_attr_from_ram(xy2);
2894 if ((ap_tile_attrs[attr] & TILE_ATTR_MERG) && (ap_tile_attrs[attr2] & TILE_ATTR_MERG)) {
2895 attr2 = attr;
2896 }
2897 if (XYIN(xy2, tl, br) && attr2 == attr) {
2898 // || ((ap_tile_attrs[attr2] & TILE_ATTR_MERG) && (ap_tile_attrs[attr] & TILE_ATTR_MERG))) {
2899 new_node->tl = XYFN2(MIN, xy, xy2);
2900 new_node->br = XYFN2(MAX, xy, xy2);
2901 new_node->br = XYOP1(new_node->br, + 7);
2902 break;
2903 }
2904 }
2905 if (XYEQ(new_node->tl, new_node->br)) {
2906 continue;
2907 }
2908 if (ap_tile_attrs[attr] & TILE_ATTR_DOOR) {
2909 uint8_t attr_mask = 0xFF;
2910 if (attr >= 0x80 && attr <= 0x87) {
2911 attr_mask = 0xEF;
2912 } else if (attr >= 0x90 && attr <= 0x97) {
2913 continue;
2914 }
2915 struct xy next_tl = new_node->tl;
2916 while (XYIN(next_tl, tl, br) && (ap_map_attr_from_ram(next_tl) & attr_mask) == attr) {
2917 new_node->tl = next_tl;
2918 next_tl.x -= 8;
2919 }
2920 next_tl = new_node->tl;
2921 while (XYIN(next_tl, tl, br) && (ap_map_attr_from_ram(next_tl) & attr_mask) == attr) {
2922 new_node->tl = next_tl;
2923 next_tl.y -= 8;
2924 }
2925 if (xy.x - new_node->tl.x >= 0x10) {
2926 continue;
2927 }
2928 if (xy.y - new_node->tl.y >= 0x10) {
2929 continue;
2930 }
2931 struct xy next_br = new_node->br;
2932 while (XYIN(next_br, tl, br) && (ap_map_attr_from_ram(next_br) & attr_mask) == attr) {
2933 new_node->br = next_br;
2934 next_br.x += 8;
2935 }
2936 next_br = new_node->br;
2937 while (XYIN(next_br, tl, br) && (ap_map_attr_from_ram(next_br) & attr_mask) == attr) {
2938 new_node->br = next_br;
2939 next_br.y += 8;
2940 }
2941 }
2942 new_node->tile_attr = attr;
2943 const char * attr_name = ap_tile_attr_name(attr);
2944 if (ap_tile_attrs[attr] & TILE_ATTR_STRS) {
2945 if (attr == 0x5e || attr == 0x5f) {
2946 //new_node->tl.y += 24;
2947 //new_node->br.y += 24;
2948 }
2949 new_node->type = NODE_TRANSITION;
2950 if ((attr & 0xF0) == 0x10 || attr == 0x5E) {
2951 new_node->adjacent_direction = DIR_U;
2952 } else {
2953 new_node->adjacent_direction = DIR_D;
2954 }
2955 if (attr == 0x3E || attr == 0x1E) { // TODO: Stairs 0x1F, 0x3F, 0x5F
2956 if (xy.x & 0x200) { // on upper level
2957 new_node->adjacent_direction = dir_opp[new_node->adjacent_direction];
2958 }
2959 struct xy offset = XYOP1(dir_dxy[new_node->adjacent_direction], * -24);
2960 new_node->tl = XYOP2(new_node->tl, +, offset);
2961 new_node->br = XYOP2(new_node->br, +, offset);
2962 } else if ((ap_map_attr_from_ram(XYOP2(new_node->tl, -, XY(0, 8))) & 0xF0) == 0x30) {
2963 // Check for 0x30 family which does a screen transition
2964 new_node->adjacent_direction = DIR_U;
2965 } else if ((ap_map_attr_from_ram(XYOP2(new_node->tl, +, XY(0, 16))) & 0xF0) == 0x30) {
2966 new_node->adjacent_direction = DIR_D;
2967 } else {
2968 if (xy.x & 0x200) { // on upper level
2969 new_node->adjacent_direction = dir_opp[new_node->adjacent_direction];
2970 }
2971 struct xy offset = XYOP1(dir_dxy[new_node->adjacent_direction], * -24);
2972 new_node->tl = XYOP2(new_node->tl, +, offset);
2973 new_node->br = XYOP2(new_node->br, +, offset);
2974 }
2975 snprintf(new_node->name, sizeof new_node->name, "stairs %c 0x%02x", new_node->adjacent_direction == DIR_U ? 'U' : 'D', attr);
2976 } else if (ap_tile_attrs[attr] & TILE_ATTR_DOOR) {
2977 new_node->type = NODE_TRANSITION;
2978 assert_bp(XYIN(new_node->tl, screen->tl, screen->br));
2979 assert_bp(XYIN(new_node->br, screen->tl, screen->br));
2980 if (attr == 0x5e || attr == 0x5f) {
2981 new_node->adjacent_direction = DIR_U;
2982 new_node->door_type = 0x80 | (attr & 0x1);
2983 } else {
2984 // Look for adjacent seals
2985 struct xy adjs[4] = {
2986 XYOP2(new_node->tl, -, XY(0, 8)), // U
2987 XYOP2(new_node->br, +, XY(0, 8)), // D
2988 XYOP2(new_node->tl, -, XY(8, 0)), // L
2989 XYOP2(new_node->br, +, XY(8, 0)), // R
2990 };
2991 uint8_t found_dir = 0;
2992 for (uint8_t i = 0; i < 4; i++) {
2993 if (!XYIN(adjs[i], tl, br)) {
2994 continue;
2995 }
2996 uint16_t a = ap_map_attr_from_ram(adjs[i]);
2997 if (attr >= 0xF0 && attr <= 0xFA) {
2998 // If we're an 0xF# node; discard ourselves if there is a neighboring 0x8#
2999 if (ap_tile_attrs[a] & TILE_ATTR_DOOR) {
3000 if (a == 0x30) {
3001 // Stairs; don't expand into it, but still count this node
3002 assert_bp(found_dir == 0);
3003 } else {
3004 assert_bp((a & 0xF8) == 0x80);
3005 found_dir = 0xFF;
3006 break;
3007 }
3008 }
3009 } else {
3010 // If we're an 0x8# node; expand into the 0xF# node
3011 if (a >= 0xF0 && a <= 0xFA) {
3012 assert_bp((attr & 0xF8) == 0x80);
3013 assert_bp(found_dir == 0);
3014 found_dir = i + 1;
3015 }
3016 }
3017 }
3018 if (found_dir == 0xFF) {
3019 continue;
3020 }
3021 if (found_dir != 0 || (attr >= 0xF0 && attr <= 0xFA)) {
3022 switch(found_dir) {
3023 case 0: break;
3024 case 1: new_node->tl.y -= 16; break;
3025 case 2: new_node->br.y += 16; break;
3026 case 3: new_node->tl.x -= 16; break;
3027 case 4: new_node->br.x += 16; break;
3028 }
3029 new_node->locked_xy = XYOP1(ap_box_edge(new_node->tl, new_node->br, found_dir), &~0x7);
3030 }
3031
3032 uint16_t d_t = new_node->tl.y - screen->tl.y;
3033 uint16_t d_l = new_node->tl.x - screen->tl.x;
3034 uint16_t d_b = screen->br.y - new_node->br.y;
3035 uint16_t d_r = screen->br.x - new_node->br.x;
3036 assert(d_t < 0x1000 && d_l < 0x1000 && d_b < 0x1000 && d_r < 0x1000);
3037 uint16_t dx = 0;
3038 if (d_l < d_r) {
3039 new_node->adjacent_direction = DIR_L;
3040 dx = d_l;
3041 } else {
3042 new_node->adjacent_direction = DIR_R;
3043 dx = d_r;
3044 }
3045 if (d_t < d_b) {
3046 if (d_t < dx) {
3047 new_node->adjacent_direction = DIR_U;
3048 }
3049 } else {
3050 if (d_b < dx) {
3051 new_node->adjacent_direction = DIR_D;
3052 }
3053 }
3054 assert_bp(found_dir == 0 || dir_opp[found_dir] == new_node->adjacent_direction);
3055
3056 size_t door_idx;
3057 for (door_idx = 0; door_idx < 16; door_idx++) {
3058 uint16_t door_tilemap = ap_ram.dungeon_door_tilemaps[door_idx];
3059 if (door_tilemap == 0) {
3060 continue;
3061 }
3062 struct xy door_xy = ap_tilemap_to_xy(tl, door_tilemap);
3063 if (XYIN(door_xy , new_node->tl, new_node->br)) {
3064 break;
3065 }
3066 }
3067 //assert_bp(door_idx < 16);
3068 if (door_idx < 16) {
3069 uint16_t raw_door_type = ap_ram.dungeon_door_types[door_idx];
3070 uint8_t door_type = (raw_door_type & 0xFE) >> 1;
3071 //uint8_t door_direction = ((raw_door_type & 0x0600) >> 9) + 1;
3072 uint8_t door_direction = (ap_ram.dungeon_door_dirs[door_idx] & 0x3) + 1;
3073 assert_bp(new_node->adjacent_direction == door_direction);
3074 new_node->door_type = door_type;
3075 n_doors++;
3076 } else {
3077 new_node->door_type = 0xFF;
3078 }
3079 }
3080
3081 struct xy dxy = XYOP1(dir_dxy[new_node->adjacent_direction], * -24);
3082 new_node->tl = XYOP2(new_node->tl, +, dxy);
3083 new_node->br = XYOP2(new_node->br, +, dxy);
3084
3085 snprintf(new_node->name, sizeof new_node->name, "door %s 0x%02x %s %s", dir_names[new_node->adjacent_direction], attr, attr_name, ap_door_attr_name(new_node->door_type));
3086 /*
3087 } else if (ap_tile_attrs[attr] & TILE_ATTR_CHST) {
3088 assert_bp(attr < (0x58 + (*ap_ram.room_keyblock_index / 2)));
3089 if (attr < (0x58 + (*ap_ram.room_chest_index / 2))) {
3090 new_node->type = NODE_CHEST;
3091 // Chests are opened from the bottom
3092 new_node->tl.y += 16;
3093 new_node->br.y += 16;
3094 snprintf(new_node->name, sizeof new_node->name, "chest 0x%02x %s", attr, attr_name);
3095 } else {
3096 new_node->type = NODE_KEYBLOCK;
3097 // Extend keyblocks node up 16px because key blocks always (?) face upwards
3098 // This makes it possible for pathfind to reach everything in the "locked" area
3099 // before the node is unlocked
3100 new_node->tl.y -= 16;
3101 snprintf(new_node->name, sizeof new_node->name, "keyblock 0x%02x %s", attr, attr_name);
3102 }
3103 n_chests++;
3104 */
3105 } else if (ap_tile_attrs[attr] & TILE_ATTR_SWCH) {
3106 new_node->type = NODE_SWITCH;
3107 new_node->adjacent_direction = 0;
3108 snprintf(new_node->name, sizeof new_node->name, "switch 0x%02x %s", attr, attr_name);
3109 } else if (ap_tile_attrs[attr] & lift_mask) {
3110 size_t i;
3111 for (i = 0; i < ARRAYLEN(ap_pushblocks); i++) {
3112 if (XYEQ(ap_pushblocks[i].tl, new_node->tl)) {
3113 break;
3114 }
3115 }
3116 if (i != ARRAYLEN(ap_pushblocks)) {
3117 continue;
3118 }
3119 new_node->type = NODE_ITEM;
3120 snprintf(new_node->name, sizeof new_node->name, "pot 0x%02x %s", attr, attr_name);
3121 } else {
3122 new_node->type = NODE_ITEM;
3123 snprintf(new_node->name, sizeof new_node->name, "unknown item!? 0x%02x %s", attr, attr_name);
3124 }
3125 ap_screen_commit_node(screen, &new_node);
3126 new_node_count++;
3127 }
3128 }
3129 if (XYINDOORS(tl)) {
3130 size_t n_doors2 = 0;
3131 size_t n_stairs = (
3132 *ap_ram.dngn_stairs_0 + \
3133 *ap_ram.dngn_stairs_1 + \
3134 *ap_ram.dngn_stairs_2 + \
3135 *ap_ram.dngn_stairs_3 + \
3136 *ap_ram.dngn_stairs_4 + \
3137 *ap_ram.dngn_stairs_5 + \
3138 *ap_ram.dngn_stairs_6 + \
3139 *ap_ram.dngn_stairs_7 + \
3140 *ap_ram.dngn_stairs_8 + \
3141 *ap_ram.dngn_stairs_9) / 2;
3142 //ap_ram_print();
3143 /*
3144 assert_bp(n_stairs <= 4);
3145 for (size_t i = 0; i < n_stairs; i++) {
3146 uint16_t stairs_tilemap = ap_ram.special_tilemaps[i];
3147 assert_bp(stairs_tilemap != 0);
3148 struct xy stairs_xy = ap_tilemap_to_xy(tl, stairs_tilemap);
3149 if (XYIN(stairs_xy, tl, br)) {
3150 n_doors2++;
3151 }
3152 }
3153 */
3154 for (size_t i = 0; i < 16; i++) {
3155 uint16_t raw_door_type = ap_ram.dungeon_door_types[i];
3156 uint16_t door_tilemap = ap_ram.dungeon_door_tilemaps[i];
3157 if (raw_door_type == 0 && door_tilemap == 0) {
3158 continue;
3159 }
3160
3161 uint8_t door_type = (raw_door_type & 0xFE) >> 1;
3162 uint8_t door_direction = (ap_ram.dungeon_door_dirs[i] & 3) + 1;//((raw_door_type & 0x0600) >> 9) + 1;
3163 struct xy door_xy = ap_tilemap_to_xy(tl, door_tilemap);
3164 if (XYIN(door_xy, tl, br)) {
3165 n_doors2++;
3166 }
3167 /*
3168 char layer = 'n';
3169 if (ap_tile_attrs[ap_map_attr_from_ram(XYTOLOWER(door_xy))] & TILE_ATTR_DOOR) {
3170 if (ap_tile_attrs[ap_map_attr_from_ram(XYTOUPPER(door_xy))] & TILE_ATTR_DOOR) {
3171 layer = 'B';
3172 } else {
3173 layer = 'v';
3174 }
3175 } else if (ap_tile_attrs[ap_map_attr_from_ram(XYTOUPPER(door_xy))] & TILE_ATTR_DOOR) {
3176 layer = '^';
3177 }
3178 assert_bp(layer != 'n');
3179 assert_bp(layer != 'B');
3180 */
3181 char layer = XYONLOWER(door_xy) ? 'v' : '^';
3182 LOG("Door %2zu: %#06x %#x %s " PRIXY " (%#06x) %c %s",
3183 i, raw_door_type, door_type, dir_names[door_direction],
3184 PRIXYF(door_xy), door_tilemap, layer, ap_door_attr_name(door_type));
3185 }
3186 if (n_doors != n_doors2) LOGB("%zu %zu", n_doors, n_doors2);
3187 assert_bp(n_doors <= n_doors2);
3188
3189 size_t n_chests_and_keyblocks = *ap_ram.room_keyblock_index / 2;
3190 size_t n_chests = *ap_ram.room_chest_index / 2;
3191 assert(n_chests <= n_chests_and_keyblocks);
3192
3193 size_t chest_index;
3194 for (chest_index = 0; chest_index < 168; chest_index++) {
3195 uint16_t chest_id = ap_ram.dungeon_chests[chest_index * 3 + 0];
3196 chest_id |= ap_ram.dungeon_chests[chest_index * 3 + 1] << 8;
3197 if ((chest_id & 0x7FFF) == *ap_ram.dungeon_room) {
3198 break;
3199 }
3200 }
3201 assert(n_chests == 0 || chest_index != 168);
3202
3203 for (size_t i = 0; i < n_chests_and_keyblocks; i++) {
3204 uint16_t chest_tilemap = ap_ram.room_chest_tilemaps[i];
3205 if (chest_tilemap == 0) {
3206 LOG("Skipping chest with tilemap 0 (%zu)", i);
3207 continue;
3208 }
3209 struct xy chest_xy = ap_tilemap_to_xy(screen->tl, chest_tilemap & 0x7FFF);
3210 // Undo the tilemap offset?
3211 chest_xy = XYOP2(chest_xy, -, XY(8, 16));
3212 if (!XYIN(chest_xy, screen->tl, screen->br)) {
3213 continue;
3214 }
3215
3216 new_node->tl = chest_xy;
3217 new_node->tile_attr = 0x58 + i;
3218
3219 if (i >= n_chests) {
3220 // Keyblock
3221 new_node->type = NODE_KEYBLOCK;
3222 // Extend keyblocks node up 16px because key blocks always (?) face upwards
3223 // This makes it possible for pathfind to reach everything in the "locked" area
3224 // before the node is unlocked
3225 new_node->tl.y -= 16;
3226 new_node->br = XYOP2(new_node->tl, +, XY(15, 31));
3227 snprintf(new_node->name, sizeof new_node->name, "keyblock %zu", i);
3228 } else {
3229 assert_bp(chest_index != 168);
3230 uint16_t chest_id = ap_ram.dungeon_chests[(chest_index + i) * 3 + 0];
3231 chest_id |= ap_ram.dungeon_chests[(chest_index + i) * 3 + 1] << 8;
3232 assert_bp((chest_id & 0x7FFF) == *ap_ram.dungeon_room);
3233 if (chest_id & 0x8000) {
3234 // Big Chest
3235 assert_bp(i <= n_chests);
3236 new_node->type = NODE_CHEST;
3237 new_node->chest_type = 1;
3238 new_node->tl.y += 24;
3239 new_node->br = XYOP2(new_node->tl, +, XY(31, 15));
3240 snprintf(new_node->name, sizeof new_node->name, "big chest %zu", i);
3241 } else {
3242 // Small Chest
3243 new_node->type = NODE_CHEST;
3244 new_node->chest_type = 0;
3245 new_node->tl.y += 16;
3246 new_node->br = XYOP2(new_node->tl, +, XY(15, 15));
3247 snprintf(new_node->name, sizeof new_node->name, "chest %zu", i);
3248 }
3249 }
3250 LOG("Chest %zu: " PRIXYV " (%#06x) %s",
3251 i, PRIXYVF(chest_xy), chest_tilemap, new_node->name);
3252
3253 ap_screen_commit_node(screen, &new_node);
3254 new_node_count++;
3255 }
3256 }
3257
3258}
3259
3260int
3261ap_map_record_transition_from(struct ap_node * src_node)
3262{
3263 if (src_node->adjacent_node != NULL)
3264 return 0;
3265
3266 struct ap_screen * src_screen = src_node->screen;
3267
3268 struct xy dst_xy = ap_link_xy();
3269 struct xy dst_xy2 = XYOP1(dst_xy, +15);
3270 struct ap_screen * dst_screen = map_screens[XYMAPSCREEN(dst_xy)];
3271 assert(dst_screen != src_screen);
3272
3273 // Find dst_node
3274 struct ap_node * dst_node = NULL;
3275 for (struct ap_node * node = dst_screen->node_list->next; node != dst_screen->node_list; node = node->next) {
3276 if (node->type != NODE_TRANSITION)
3277 continue;
3278 // TODO: Maybe use the type of the node (stairs) to see if it's valid to
3279 // link together nodes where the direction doesn't switch
3280 if (node->adjacent_direction != src_node->adjacent_direction &&
3281 dir_opp[node->adjacent_direction] != src_node->adjacent_direction)
3282 continue;
3283 // Check if any corner is in the ndoe
3284 if (XYL1BOXDIST(dst_xy, node->tl, node->br) && XYL1BOXDIST(dst_xy2, node->tl, node->br)
3285 && XYL1BOXDIST(XY(dst_xy.x, dst_xy2.y), node->tl, node->br) && XYL1BOXDIST(XY(dst_xy2.x, dst_xy.y), node->tl, node->br))
3286 continue;
3287 dst_node = node;
3288 break;
3289 }
3290 if (dst_node == NULL) {
3291 LOGB("Warning! dst_node is NULL so making own node");
3292 static struct ap_node * new_node = NULL;
3293 if (new_node == NULL)
3294 new_node = NONNULL(calloc(1, sizeof *new_node));
3295
3296 // TODO: Should be based on the size of src_node?
3297 new_node->tl = XYOP1(dst_xy, & ~7);
3298 new_node->br = XYOP1(new_node->tl, + 15);
3299 new_node->type = NODE_TRANSITION;
3300 if (ap_tile_attrs[src_node->tile_attr] & TILE_ATTR_LDGE) {
3301 new_node->adjacent_direction = 0;
3302 } else if (src_node->tile_attr == 0x5e || src_node->tile_attr == 0x5f) {
3303 new_node->adjacent_direction = DIR_U;
3304 new_node->tile_attr = src_node->tile_attr ^ 0x1; // XXX
3305 } else {
3306 new_node->adjacent_direction = dir_opp[src_node->adjacent_direction];
3307 }
3308 snprintf(new_node->name, sizeof new_node->name, "0x%02X %s cross", XYMAPSCREEN(dst_xy), dir_names[new_node->adjacent_direction]);
3309 assert_bp(false);
3310
3311 dst_node = ap_screen_commit_node(dst_screen, &new_node);
3312 }
3313 assert(dst_node != NULL);
3314
3315 LOGB("Attaching nodes from transition: %s <-> %s", dst_node->name, src_node->name);
3316 src_node->adjacent_node = dst_node;
3317 dst_node->adjacent_node = src_node;
3318
3319 return 0;
3320}
3321
3322void
3323ap_node_islocked_print(struct ap_node * node) {
3324 bool unlockable;
3325 const struct ap_room_tag * unlock_tag;
3326 bool islocked = ap_node_islocked(node, &unlockable, &unlock_tag);
3327 LOG("Node: %s; locked: %u; unlockable: %u; room tag: %s",
3328 node->name, islocked, unlockable, ap_room_tag_print(unlock_tag));
3329}
3330
3331bool
3332ap_node_islocked(struct ap_node * node, bool *unlockable_out, const struct ap_room_tag ** unlock_tag_out) {
3333 assert(unlockable_out != NULL);
3334 assert(unlock_tag_out != NULL);
3335 *unlockable_out = false;
3336 *unlock_tag_out = false;
3337
3338 if (node->type == NODE_KEYBLOCK) {
3339 // Requires Big Key for dungeon
3340 assert_bp(node->screen->dungeon_id < 16);
3341 uint16_t bit = 1 << (15 - node->screen->dungeon_id);
3342 return !(*ap_ram.sram_dungeon_bigkeys & bit);
3343 }
3344
3345 // Is locked or unlockable
3346 if (node->type != NODE_CHEST && node->type != NODE_TRANSITION) {
3347 return false;
3348 }
3349
3350 const struct ap_room_tag * unlock_tag = node->screen->room_tags[0];
3351 if (unlock_tag == NULL ||
3352 (node->type == NODE_TRANSITION && unlock_tag->result != ROOM_RESULT_OPEN_DOORS) ||
3353 (node->type == NODE_CHEST && unlock_tag->result != ROOM_RESULT_CHEST)) {
3354 unlock_tag = node->screen->room_tags[1];
3355 }
3356 if (unlock_tag == NULL ||
3357 (node->type == NODE_TRANSITION && unlock_tag->result != ROOM_RESULT_OPEN_DOORS) ||
3358 (node->type == NODE_CHEST && unlock_tag->result != ROOM_RESULT_CHEST)) {
3359 unlock_tag = NULL;
3360 }
3361 *unlock_tag_out = unlock_tag;
3362
3363 if (!XYEQ(node->locked_xy, XY(0, 0))) {
3364 uint8_t lock_attr = ap_map_attr(node->locked_xy);
3365 if (node->type == NODE_TRANSITION) {
3366 if (lock_attr < 0xF0) {
3367 return false;
3368 }
3369
3370 if (ap_door_attrs[node->door_type] & (DOOR_ATTR_SKEY | DOOR_ATTR_BKEY | DOOR_ATTR_BOMB)) {
3371 *unlock_tag_out = NULL;
3372 if (ap_door_attrs[node->door_type] & DOOR_ATTR_SKEY) {
3373 assert_bp(node->screen->dungeon_id < 16);
3374 bool available_keys = ap_ram.sram_dungeon_keys[node->screen->dungeon_id] > 0;
3375 if (*ap_ram.dungeon_id / 2 == node->screen->dungeon_id) {
3376 available_keys = available_keys || (*ap_ram.dungeon_current_keys > 0);
3377 }
3378 *unlockable_out = available_keys;
3379 } else if (ap_door_attrs[node->door_type] & DOOR_ATTR_BKEY) {
3380 assert_bp(node->screen->dungeon_id < 16);
3381 uint16_t bit = 1 << (15 - node->screen->dungeon_id);
3382 *unlockable_out = *ap_ram.sram_dungeon_bigkeys & bit;
3383 } else if (ap_door_attrs[node->door_type] & DOOR_ATTR_BOMB) {
3384 *unlockable_out = true;
3385 }
3386
3387 uint16_t bit = 0;
3388 switch (node->tile_attr) {
3389 case 0xF0: bit = 0x8000; break; // checked
3390 case 0xF1: bit = 0x2000; break; // guess
3391 case 0xF2: bit = 0x4000; break; // guess
3392 case 0xF3: bit = 0x8000; break; // guess
3393 case 0xF5: bit = 0x8000; break; // guess
3394 case 0xF6: bit = 0x4000; break; // guess
3395 case 0xF7: bit = 0x2000; break; // guess
3396 case 0xF8: bit = 0x8000; break; // contradictory; maybe 0x1000?
3397 case 0xF9: bit = 0x8000; break; // total guess
3398 case 0xFA: bit = 0x8000; break; // total guess
3399 }
3400 assert_bp(bit != 0);
3401 if (bit != 0) {
3402 uint16_t state = ap_ram.sram_room_state[node->screen->dungeon_room];
3403 if (node->screen->dungeon_room == *ap_ram.dungeon_room) {
3404 // Read from RAM instead of SRAM
3405 state = *ap_ram.room_state;
3406 }
3407 return !(state & bit);
3408 }
3409 }
3410 }
3411
3412 if (node->lock_node == NULL) {
3413 // Just-in-time assign switch unlock nodes
3414 for (struct ap_node * sw_node = node->screen->node_list->next; sw_node != node->screen->node_list; sw_node = sw_node->next) {
3415 if (sw_node->type == NODE_SWITCH) {
3416 LOGB("Assigning switch %s to unlock door %s", sw_node->name, node->name);
3417 node->lock_node = sw_node;
3418 break;
3419 }
3420 }
3421 }
3422 if (unlock_tag != NULL) {
3423 switch (unlock_tag->action) {
3424 case ROOM_ACTION_KILL_ENEMY:
3425 *unlockable_out = true;
3426 break;
3427 case ROOM_ACTION_SWITCH_TOGGLE:
3428 case ROOM_ACTION_SWITCH_HOLD:
3429 *unlockable_out = (node->lock_node != NULL);
3430 break;
3431 case ROOM_ACTION_OPEN_CHEST:
3432 case ROOM_ACTION_LIGHT_TORCHES:
3433 case ROOM_ACTION_MOVE_BLOCK:
3434 case ROOM_ACTION_PULL_LEVER:
3435 case ROOM_ACTION_CLEAR_QUADRANT:
3436 case ROOM_ACTION_CLEAR_ROOM:
3437 case ROOM_ACTION_CLEAR_LEVEL:
3438 case ROOM_ACTION_TURN_OFF_WATER:
3439 case ROOM_ACTION_TURN_ON_WATER:
3440 case ROOM_ACTION_NONE:
3441 *unlockable_out = false;
3442 break;
3443 }
3444 } else {
3445 *unlockable_out = false;
3446 }
3447 if (node->type == NODE_TRANSITION && *ap_ram.room_trap_doors && node->screen->dungeon_room == *ap_ram.dungeon_room) {
3448 return true;
3449 }
3450 if (node->type == NODE_CHEST) {
3451 return !(ap_tile_attrs[lock_attr] & TILE_ATTR_CHST || lock_attr == 0x27); // 0x27: opened chest
3452 }
3453 return false;
3454 }
3455 assert(node->type == NODE_TRANSITION);
3456
3457 // Overworld overlays (bombable walls)
3458 if (node->lock_node != NULL && node->lock_node->type == NODE_OVERLAY) {
3459 *unlockable_out = true;
3460 return !(ap_ram.sram_overworld_state[node->lock_node->overlay_index] & 0x02);
3461 }
3462
3463
3464 if (ap_update_map_screen(false) != node->screen) {
3465 return false;
3466 }
3467
3468 return false;
3469}
3470
3471void
3472ap_map_export(const char * filename) {
3473 FILE * f = fopen(filename, "w");
3474 if (f == NULL) return;
3475 for (size_t s = 0; s < 0x100 * 0x100; s++) {
3476 struct ap_screen *screen = map_screens[s];
3477 if (screen == NULL) continue;
3478 if (XYMAPSCREEN(screen->tl) != s) continue;
3479 fprintf(f, ">0x%04x 0x%04x,0x%04x 0x%04x,0x%04x %u %u %u # %s\n",
3480 screen->id, screen->tl.x, screen->tl.y, screen->br.x, screen->br.y,
3481 screen->dungeon_room, screen->dungeon_id, screen->dungeon_tags, screen->name);
3482 for (const struct ap_node * node = screen->node_list->next; node != screen->node_list; node = node->next) {
3483 fprintf(f, "@%p 0x%04x,0x%04x 0x%04x,0x%04x",
3484 node, node->tl.x, node->tl.y, node->br.x, node->br.y);
3485 fprintf(f, " %u %u %p %d %u %u %u %s\n",
3486 node->type, node->adjacent_direction, node->adjacent_node, node->tile_attr, node->sprite_type, node->sprite_subtype, node->door_type, node->name);
3487 }
3488 for (size_t y = 0; y < 0x80; y++) {
3489 fprintf(f, "|");
3490 for (size_t x = 0; x < 0x80; x++) {
3491 fprintf(f, "%02x ", screen->attr_cache[y][x]);
3492 }
3493 fprintf(f, "\n");
3494 }
3495 }
3496 fclose(f);
3497}
3498
3499void
3500ap_map_import(const char * filename) {
3501 array_reverse_test();
3502 FILE * f = fopen(filename, "r");
3503 if (f == NULL) return;
3504 struct pm * pm = pm_create();
3505 struct ap_screen *screen = NULL;
3506 size_t attr_row = 0;
3507 char *line = NULL;
3508 size_t line_len = 0;
3509 size_t line_number = 0;
3510 while (getline(&line, &line_len, f) != -1) {
3511 line_number++;
3512 if (line[0] == '#') {
3513 continue;
3514 } else if (line[0] == '>') {
3515 screen = NONNULL(calloc(1, sizeof *screen));
3516 int rc = sscanf(line, ">0x%hx 0x%hx,0x%hx 0x%hx,0x%hx %hu %hhu %hu",
3517 &screen->id, &screen->tl.x, &screen->tl.y, &screen->br.x, &screen->br.y,
3518 &screen->dungeon_room, &screen->dungeon_id, &screen->dungeon_tags);
3519 assert_bp(rc == 8);
3520 /*
3521 if (XYINDOORS(screen->tl)) {
3522 screen->dungeon_room = (screen->tl.x - 0x4000) / 0x800;
3523 screen->dungeon_room += ((screen->tl.y) / 0x200) * 16;
3524 } else {
3525 screen->dungeon_room = -1;
3526 }
3527 */
3528 for (const struct ap_screen_info * info = ap_screen_infos; info->id != (uint16_t) -1; info++) {
3529 if (info->id == screen->id) {
3530 screen->info = info;
3531 break;
3532 }
3533 }
3534 //ap_graph_init(&screen->graph, screen->name);
3535 LL_INIT(screen->node_list);
3536 const char * suffix = "";
3537 if (XYINDOORS(screen->tl)) {
3538 if (XYONUPPER(screen->tl)) {
3539 screen->id &= ~0x2;
3540 suffix = " ^";
3541 } else {
3542 suffix = " v";
3543 }
3544 }
3545 if (screen->info) {
3546 snprintf(screen->name, sizeof screen->name, "%s%s " PRIXY " x " PRIXY, screen->info->name, suffix, PRIXYF(screen->tl), PRIXYF(screen->br));
3547 } else {
3548 snprintf(screen->name, sizeof screen->name, "%#06x%s " PRIXYV " x " PRIXYV, screen->id, suffix, PRIXYVF(screen->tl), PRIXYVF(screen->br));
3549
3550 }
3551
3552 struct xy xy;
3553 for (xy.y = screen->tl.y; xy.y < screen->br.y; xy.y += 0x100) {
3554 for (xy.x = screen->tl.x; xy.x < screen->br.x; xy.x += 0x100) {
3555 map_screens[XYMAPSCREEN(xy)] = screen;
3556 map_screen_mask_x[xy.x / 0x100] = true;
3557 map_screen_mask_y[xy.y / 0x100] = true;
3558 }
3559 }
3560
3561 ap_map_add_scripts_to_screen(screen);
3562 ap_map_add_constants_to_screen(screen);
3563
3564 attr_row = 0;
3565 } else if (line[0] == '@') {
3566 assert(screen != NULL);
3567 struct ap_node * node = NONNULL(calloc(1, sizeof *node));
3568 void * node_ptr = 0;
3569 void * adj_node_ptr = 0;
3570 int node_type = NODE_NONE;
3571 int rc = sscanf(line, "@%p 0x%hx,0x%hx 0x%hx,0x%hx %d %hhu %p %hhd %hhu %hu %hhu %[^\n]",
3572 &node_ptr, &node->tl.x, &node->tl.y, &node->br.x, &node->br.y,
3573 &node_type, &node->adjacent_direction, &adj_node_ptr, &node->tile_attr, &node->sprite_type, &node->sprite_subtype, &node->door_type, node->name);
3574 assert_bp(rc == 13);
3575 node->type = node_type;
3576 if (node->type == NODE_SCRIPT) {
3577 free(node);
3578 continue;
3579 }
3580 assert(pm_set(pm, (uintptr_t) node_ptr, node) == 0);
3581 if (adj_node_ptr != 0) {
3582 assert(pm_get(pm, (uintptr_t) adj_node_ptr, (void **) &node->adjacent_node) == 0);
3583 }
3584
3585 ap_screen_add_raw_node(screen, node);
3586 } else if (line[0] == '|') {
3587 assert(screen != NULL);
3588 assert(attr_row < 0x80);
3589 char * buf = &line[1];
3590 for (size_t i = 0; i < 0x80; i++) {
3591 char * attr = strsep(&buf, " \n");
3592 screen->attr_cache[attr_row][i] = strtoul(attr, NULL, 16);
3593 }
3594 attr_row++;
3595 } else {
3596 LOG("unexpected line #%zu: %s", line_number, line);
3597 assert(0);
3598 }
3599 }
3600 free(line);
3601 size_t unmatched_pm = pm_destroy(pm);
3602 LOG("unmapped: %zu", unmatched_pm);
3603 assert_bp(unmatched_pm == 0);
3604
3605 for (struct xy xy = XY(0, 0); xy.y < 0x8000; xy.y += 0x100) {
3606 for (xy.x = 0; xy.x < 0xC000; xy.x += 0x100) {
3607 screen = map_screens[XYMAPSCREEN(xy)];
3608 if (screen == NULL || !XYEQ(screen->tl, xy)) continue;
3609 ap_map_screen_update_distances(screen);
3610 }
3611 }
3612}
3613
3614void
3615ap_map_tick() {
3616 struct ap_screen * screen = ap_update_map_screen(false);
3617 assert_bp(screen->dungeon_room == (uint16_t) -1 || screen->dungeon_room == *ap_ram.dungeon_room);
3618 if (ap_sprites_changed) {
3619 ap_map_add_sprite_nodes_to_screen(screen);
3620 //ap_map_screen_update_distances(screen);
3621 }
3622}
ap_map.c