Mirai's Miscellaneous Misadventures

M42 / core / paths.c

1// license: AGPLv3 or later
2// copyright 2023 zamfofex
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// todo: perhaps improve this (?)
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// todo: perhaps improve this (?)
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	// todo: for types 6 and 7, it would be neat to avoid setting 'dx'
309	// and instead find a way to build up speed normally.
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}