Mirai's Miscellaneous Misadventures
M42 / core / paths.c
1
2
3
4#include <mimimi/sprites.h>
5#include <mimimi/geometry.h>
6#include <mimimi/ground.h>
7#include <mimimi/behaviors.h>
8#include <mimimi/allocators.h>
9#include <mimimi/compound-behaviors.h>
10
11static int mimimi_stabilise(struct mimimi_sprite *sprite)
12{
13 int x = sprite->position->x / 128 * 128 + 64;
14 if (sprite->position->x > x + sprite->walk->ground_speed * 2)
15 {
16 sprite->walk->direction = 1;
17 return 1;
18 }
19 if (sprite->position->x < x - sprite->walk->ground_speed * 2)
20 {
21 sprite->walk->direction = 2;
22 return 1;
23 }
24
25 if (sprite->physics->dx > sprite->walk->ground_speed)
26 {
27 sprite->walk->direction = 1;
28 return 1;
29 }
30
31 if (sprite->physics->dx < -sprite->walk->ground_speed)
32 {
33 sprite->walk->direction = 2;
34 return 1;
35 }
36
37 sprite->walk->direction = 0;
38 sprite->position->x = x;
39 return 0;
40}
41
42struct mimimi_edge
43{
44 int index;
45 int x, y;
46 int time;
47 int type;
48};
49
50struct mimimi_node
51{
52 int index;
53 int x, y;
54 int count;
55 struct mimimi_edge *edges;
56};
57
58struct mimimi_graph
59{
60 int count;
61 struct mimimi_node *nodes;
62 struct mimimi_node **by_position;
63};
64
65struct mimimi_path_finding_data
66{
67 int x1, y1;
68 int direction;
69 struct mimimi_path_finding *path_finding;
70 struct mimimi_behavior *jump;
71 struct mimimi_graph *graph;
72 unsigned char *queue;
73 unsigned int *distances;
74 struct mimimi_node **previous;
75 struct mimimi_allocator *allocator;
76 struct mimimi_behavior *behavior;
77};
78
79static struct mimimi_edge *mimimi_grow_node(struct mimimi_node *node, struct mimimi_allocator *allocator)
80{
81 node->count++;
82 node->edges = mimimi_reallocate(allocator, node->edges, node->count * sizeof *node->edges);
83 return node->edges + node->count - 1;
84}
85
86static void mimimi_shrink_node(struct mimimi_node *node, struct mimimi_allocator *allocator)
87{
88 node->count--;
89 if (node->count == 0) mimimi_deallocate(allocator, node->edges), node->edges = allocator->null;
90 else node->edges = mimimi_reallocate(allocator, node->edges, node->count * sizeof *node->edges);
91}
92
93
94static int mimimi_max_dx(struct mimimi_walk *walk)
95{
96 int pdx = 0;
97 int dx = 0;
98 for (;;)
99 {
100 dx += walk->ground_speed;
101 dx *= 5;
102 dx /= 6;
103 if (dx == pdx) return dx;
104 pdx = dx;
105 }
106}
107
108
109static int mimimi_max_dy(struct mimimi_physics *physics)
110{
111 int pdy = 0;
112 int dy = 0;
113 for (;;)
114 {
115 dy += physics->gravity;
116 dy *= 23;
117 dy /= 24;
118 if (dy == pdy) return dy;
119 pdy = dy;
120 }
121}
122
123static void mimimi_jump_target(struct mimimi_edge *edge, struct mimimi_path_finding_data *path_finding_data, int dx, int x, int y, int direction)
124{
125 struct mimimi_position position;
126 struct mimimi_physics physics;
127 struct mimimi_walk walk;
128
129 struct mimimi_path_finding *path_finding = path_finding_data->path_finding;
130
131 struct mimimi_behavior *compound = mimimi_compound_behavior(path_finding_data->allocator);
132 mimimi_compound(compound, mimimi_physics(&physics, &position, path_finding->ground, path_finding_data->allocator));
133 mimimi_compound(compound, mimimi_walk(&walk, &physics, path_finding_data->allocator));
134
135 struct mimimi_behavior *jump = mimimi_jump(path_finding->jump, &physics, path_finding_data->allocator);
136
137 physics = *path_finding->sprite->physics;
138 walk = *path_finding->sprite->walk;
139
140 position.x = x * 128 + 64;
141 position.y = y * 128 + 128;
142 physics.dx = dx;
143 physics.dy = 0;
144 physics.airborne = 0;
145 walk.direction = direction;
146
147 (*jump->behave)(jump->data);
148 (*jump->finish)(jump->data);
149
150 edge->time = 0;
151 while (physics.airborne != 0 || mimimi_ground_tile(path_finding->ground, position.x / 128, (position.y - 64) / 128 + 1) == 0)
152 (*compound->behave)(compound->data),
153 edge->time++;
154 (*compound->finish)(compound->data);
155
156 edge->x = position.x / 128;
157 edge->y = (position.y - 64) / 128;
158}
159
160static void mimimi_path_finding_behave(void *data)
161{
162 struct mimimi_path_finding_data *path_finding_data = data;
163 struct mimimi_path_finding *path_finding = path_finding_data->path_finding;
164 struct mimimi_sprite *sprite = path_finding->sprite;
165 struct mimimi_behavior *jump = path_finding->jump_behavior;
166
167 if (sprite->physics->airborne == 0)
168 path_finding_data->direction = -1;
169
170 if (path_finding_data->direction != -1)
171 {
172 sprite->walk->direction = path_finding_data->direction;
173 return;
174 }
175
176 struct mimimi_graph *graph = path_finding_data->graph;
177
178 unsigned char *queue = path_finding_data->queue;
179 unsigned int *distances = path_finding_data->distances;
180 struct mimimi_node **previous = path_finding_data->previous;
181
182 for (int i = 0 ; i < graph->count ; i++)
183 {
184 distances[i] = -1;
185 queue[i] = 1;
186 }
187
188 int x0 = path_finding->sprite->position->x / 128;
189 int y0 = (path_finding->sprite->position->y - 64) / 128;
190
191 int x1 = path_finding->target->x / 128;
192 int y1 = (path_finding->target->y - 64) / 128;
193
194 if (mimimi_ground_tile(path_finding->ground, x1, y1 + 1) != 0 || path_finding_data->x1 == -1)
195 {
196 path_finding_data->x1 = x1;
197 path_finding_data->y1 = y1;
198 }
199 else
200 {
201 x1 = path_finding_data->x1;
202 y1 = path_finding_data->y1;
203 }
204
205 int i0 = x0 + y0 * path_finding->ground->width;
206 int i1 = x1 + y1 * path_finding->ground->width;
207
208 if (graph->by_position[i0]->index == -1 || graph->by_position[i1]->index == -1)
209 {
210 sprite->walk->direction = 0;
211 return;
212 }
213
214 if ((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) < path_finding->radius * path_finding->radius)
215 {
216 sprite->walk->direction = 0;
217 return;
218 }
219
220 if (x0 == x1 && y0 == y1)
221 {
222 mimimi_stabilise(sprite);
223 return;
224 }
225
226 unsigned char found = 0;
227 struct mimimi_edge *target;
228
229 distances[graph->by_position[i0]->index] = 0;
230 for (int c = 0 ; c < graph->count ; c++)
231 {
232 unsigned int distance = -1;
233 struct mimimi_node *u;
234 int k;
235
236 for (int i = 0 ; i < graph->count ; i++)
237 {
238 if (queue[i] == 0) continue;
239 struct mimimi_node *node = graph->nodes + i;
240 unsigned int other_distance = distances[i];
241 if (other_distance < distance)
242 {
243 distance = other_distance;
244 u = node;
245 k = i;
246 }
247 }
248
249 if (k == graph->by_position[i1]->index)
250 {
251 for (;;)
252 {
253 struct mimimi_node *next = previous[u->index];
254 if (next == graph->by_position[i0]) break;
255 u = next;
256 }
257 for (int i = 0 ; i < graph->by_position[i0]->count ; i++)
258 {
259 struct mimimi_edge *edge = graph->by_position[i0]->edges + i;
260 if (edge->index == u->index)
261 {
262 target = edge;
263 break;
264 }
265 }
266 found = 1;
267 break;
268 }
269
270 queue[k] = 0;
271
272 for (int i = 0 ; i < u->count ; i++)
273 {
274 struct mimimi_node *v = graph->nodes + u->edges[i].index;
275 if (queue[v->index] == 0) continue;
276
277 unsigned int alt = distances[u->index] + u->edges[i].time;
278 if (alt < distances[v->index])
279 {
280 distances[v->index] = alt;
281 previous[v->index] = u;
282 }
283 }
284 }
285
286 if (found == 0)
287 {
288 sprite->walk->direction = 0;
289 return;
290 }
291
292 if (target->type == 0)
293 {
294 mimimi_stabilise(sprite);
295 return;
296 }
297 if (target->type == 1)
298 {
299 sprite->walk->direction = 1;
300 return;
301 }
302 if (target->type == 2)
303 {
304 sprite->walk->direction = 2;
305 return;
306 }
307
308
309
310 if (target->type == 6)
311 {
312 if (path_finding->sprite->physics->dx > 0)
313 {
314 sprite->walk->direction = 2;
315 return;
316 }
317 sprite->walk->direction = 1;
318 if (path_finding->sprite->position->x - x0 * 128 < 64)
319 {
320 path_finding->sprite->physics->dx = -mimimi_max_dx(path_finding->sprite->walk);
321 (*jump->behave)(jump->data);
322 path_finding_data->direction = 1;
323 }
324 return;
325 }
326 if (target->type == 7)
327 {
328 if (path_finding->sprite->physics->dx < 0)
329 {
330 sprite->walk->direction = 1;
331 return;
332 }
333 sprite->walk->direction = 2;
334 if (path_finding->sprite->position->x - x0 * 128 > 64)
335 {
336 path_finding->sprite->physics->dx = mimimi_max_dx(path_finding->sprite->walk);
337 (*jump->behave)(jump->data);
338 path_finding_data->direction = 2;
339 }
340 return;
341 }
342
343 if (mimimi_stabilise(sprite) != 0) return;
344
345 int direction = -1;
346
347 if (target->type == 3)
348 direction = 0;
349 if (target->type == 4)
350 direction = 1;
351 if (target->type == 5)
352 direction = 2;
353
354 (*jump->behave)(jump->data);
355 sprite->walk->direction = direction;
356 path_finding_data->direction = direction;
357}
358
359static void mimimi_path_finding_finish(void *data)
360{
361 struct mimimi_path_finding_data *path_finding_data = data;
362 struct mimimi_allocator *allocator = path_finding_data->allocator;
363
364 for (int i = 0 ; i < path_finding_data->graph->count ; i++)
365 {
366 struct mimimi_node *node = path_finding_data->graph->nodes + i;
367 mimimi_deallocate(allocator, node->edges);
368 }
369 mimimi_deallocate(allocator, path_finding_data->graph->nodes);
370
371 mimimi_deallocate(allocator, path_finding_data->graph->by_position);
372 mimimi_deallocate(allocator, path_finding_data->graph);
373 mimimi_deallocate(allocator, path_finding_data->queue);
374 mimimi_deallocate(allocator, path_finding_data->distances);
375 mimimi_deallocate(allocator, path_finding_data->previous);
376 mimimi_deallocate(allocator, path_finding_data->behavior);
377 mimimi_deallocate(allocator, path_finding_data);
378}
379
380struct mimimi_behavior *mimimi_find_path(struct mimimi_path_finding *path_finding, struct mimimi_ground *ground, struct mimimi_position *target, struct mimimi_sprite *sprite, struct mimimi_allocator *allocator)
381{
382 struct mimimi_graph *graph = mimimi_allocate(allocator, sizeof *graph);
383 graph->nodes = mimimi_allocate(allocator, ground->width * ground->height * sizeof *graph->nodes);
384 graph->by_position = mimimi_allocate(allocator, ground->width * ground->height * sizeof *graph->by_position);
385
386 struct mimimi_path_finding_data *path_finding_data = mimimi_allocate(allocator, sizeof *path_finding_data);
387 path_finding_data->x1 = -1;
388 path_finding_data->y1 = -1;
389 path_finding_data->direction = -1;
390 path_finding_data->path_finding = path_finding;
391 path_finding_data->graph = graph;
392 path_finding_data->queue = mimimi_allocate(allocator, ground->width * ground->height * sizeof *path_finding_data->queue);
393 path_finding_data->distances = mimimi_allocate(allocator, ground->width * ground->height * sizeof *path_finding_data->distances);
394 path_finding_data->previous = mimimi_allocate(allocator, ground->width * ground->height * sizeof *path_finding_data->previous);
395 path_finding_data->allocator = allocator;
396
397 struct mimimi_behavior *behavior = mimimi_allocate(allocator, sizeof *behavior);
398 behavior->behave = &mimimi_path_finding_behave;
399 behavior->finish = &mimimi_path_finding_finish;
400 behavior->data = path_finding_data;
401 path_finding_data->behavior = behavior;
402
403 static struct mimimi_jump default_jump = {0};
404
405 path_finding->ground = ground;
406 path_finding->target = target;
407 path_finding->sprite = sprite;
408 path_finding->jump = &default_jump;
409 path_finding->jump_behavior = mimimi_noop;
410 path_finding->radius = 4;
411
412 int dx = mimimi_max_dx(path_finding->sprite->walk);
413 int dy = mimimi_max_dy(path_finding->sprite->physics);
414
415 graph->count = 0;
416 for (int y = 0 ; y < ground->height ; y++)
417 for (int x = 0 ; x < ground->width ; x++)
418 {
419 struct mimimi_node *node = graph->nodes + graph->count;
420 node->index = graph->count;
421 node->x = x;
422 node->y = y;
423
424 node->count = 0;
425 node->edges = allocator->null;
426
427 static struct mimimi_node no_node = {-1, 0, 0, 0, 0};
428 graph->by_position[x + y * ground->width] = &no_node;
429
430 if (mimimi_ground_tile(ground, x, y) != 0) continue;
431
432 if (mimimi_ground_tile(ground, x, y + 1) == 0)
433 if (mimimi_ground_tile(ground, x - 1, y + 1) == 0)
434 if (mimimi_ground_tile(ground, x + 1, y + 1) == 0)
435 continue;
436
437 graph->by_position[x + y * ground->width] = node;
438 graph->count++;
439
440 if (mimimi_ground_tile(ground, x - 1, y) == 0)
441 if (mimimi_ground_tile(ground, x, y + 1) != 0 || mimimi_ground_tile(ground, x - 1, y + 1) != 0)
442 {
443 struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
444 edge->type = 1;
445 edge->time = 128 / dx;
446 edge->x = x - 1;
447 edge->y = y;
448 }
449 if (mimimi_ground_tile(ground, x + 1, y) == 0)
450 if (mimimi_ground_tile(ground, x, y + 1) != 0 || mimimi_ground_tile(ground, x + 1, y + 1) != 0)
451 {
452 struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
453 edge->type = 2;
454 edge->time = 128 / dx;
455 edge->x = x + 1;
456 edge->y = y;
457 }
458
459 if (mimimi_ground_tile(ground, x, y + 1) == 0)
460 {
461 struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
462 edge->type = 0;
463 edge->x = x;
464 edge->y = y;
465 while (mimimi_ground_tile(ground, x, edge->y + 1) == 0)
466 edge->y++;
467 edge->time = (edge->y - y) * 128 / dy;
468 continue;
469 }
470
471 if (mimimi_ground_tile(ground, x - 1, y) == 1)
472 if (mimimi_ground_tile(ground, x - 1, y - 1) == 0)
473 {
474 struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
475 edge->type = 1;
476 edge->time = 128 / dx;
477 edge->x = x;
478 edge->y = y - 1;
479 }
480 if (mimimi_ground_tile(ground, x + 1, y) == 1)
481 if (mimimi_ground_tile(ground, x + 1, y - 1) == 0)
482 {
483 struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
484 edge->type = 2;
485 edge->time = 128 / dx;
486 edge->x = x;
487 edge->y = y - 1;
488 }
489
490 struct mimimi_edge *edge3 = mimimi_grow_node(node, allocator);
491 edge3->type = 3;
492 mimimi_jump_target(edge3, path_finding_data, 0, x, y, 0);
493 if (edge3->x == x && edge3->y == y) mimimi_shrink_node(node, allocator);
494
495 struct mimimi_edge *edge4 = mimimi_grow_node(node, allocator);
496 edge4->type = 4;
497 mimimi_jump_target(edge4, path_finding_data, 0, x, y, 1);
498 if (edge4->x == x && edge4->y == y) mimimi_shrink_node(node, allocator);
499
500 struct mimimi_edge *edge5 = mimimi_grow_node(node, allocator);
501 edge5->type = 5;
502 mimimi_jump_target(edge5, path_finding_data, 0, x, y, 2);
503 if (edge5->x == x && edge5->y == y) mimimi_shrink_node(node, allocator);
504
505 struct mimimi_edge *edge6 = mimimi_grow_node(node, allocator);
506 edge6->type = 6;
507 mimimi_jump_target(edge6, path_finding_data, -dx, x, y, 1);
508 if (edge6->x == x && edge6->y == y) mimimi_shrink_node(node, allocator);
509
510 struct mimimi_edge *edge7 = mimimi_grow_node(node, allocator);
511 edge7->type = 7;
512 mimimi_jump_target(edge7, path_finding_data, dx, x, y, 2);
513 if (edge7->x == x && edge7->y == y) mimimi_shrink_node(node, allocator);
514 }
515
516 for (int i = 0 ; i < graph->count ; i++)
517 {
518 struct mimimi_node *node = graph->nodes + i;
519 for (int j = 0 ; j < node->count ; j++)
520 {
521 struct mimimi_edge *edge = node->edges + j;
522 edge->index = graph->by_position[edge->x + edge->y * ground->width]->index;
523 }
524 }
525
526 return behavior;
527}