Mirai's Miscellaneous Misadventures

M34 / core / paths.c

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