Mirai's Miscellaneous Misadventures

M34 / core / paths.c

// copyright 2022 zamfofex
// license: AGPLv3 or later

#include <mimimi/sprites.h>
#include <mimimi/geometry.h>
#include <mimimi/ground.h>
#include <mimimi/behaviors.h>
#include <mimimi/allocators.h>
#include <mimimi/compound-behaviors.h>

static int mimimi_stabilise(struct mimimi_sprite *sprite)
{
	int x = sprite->position->x / 128 * 128 + 64;
	if (sprite->position->x > x + sprite->walk->ground_speed * 2)
	{
		sprite->walk->direction = 1;
		return 1;
	}
	if (sprite->position->x < x - sprite->walk->ground_speed * 2)
	{
		sprite->walk->direction = 2;
		return 1;
	}
	
	if (sprite->physics->dx > sprite->walk->ground_speed)
	{
		sprite->walk->direction = 1;
		return 1;
	}
	
	if (sprite->physics->dx < -sprite->walk->ground_speed)
	{
		sprite->walk->direction = 2;
		return 1;
	}
	
	sprite->walk->direction = 0;
	sprite->position->x = x;
	return 0;
}

struct mimimi_edge
{
	int x, y;
	int time;
	int type;
};

struct mimimi_node
{
	int x, y;
	int count;
	struct mimimi_edge *edges;
};

struct mimimi_graph
{
	int width, height;
	struct mimimi_node *nodes;
};

struct mimimi_path_finding_data
{
	int x1, y1;
	int direction;
	struct mimimi_path_finding *path_finding;
	struct mimimi_behavior *jump;
	struct mimimi_graph *graph;
	struct mimimi_node **queue;
	unsigned int *distances;
	struct mimimi_node **previous;
	struct mimimi_allocator *allocator;
	struct mimimi_behavior *behavior;
};

static struct mimimi_edge *mimimi_grow_node(struct mimimi_node *node, struct mimimi_allocator *allocator)
{
	node->count++;
	node->edges = mimimi_reallocate(allocator, node->edges, node->count);
	return node->edges + node->count - 1;
}

static void mimimi_shrink_node(struct mimimi_node *node, struct mimimi_allocator *allocator)
{
	node->count--;
	if (node->count == 0) mimimi_deallocate(allocator, node->edges), node->edges = allocator->null;
	else node->edges = mimimi_reallocate(allocator, node->edges, node->count);
}

// todo: perhaps improve this (?)
static int mimimi_max_dx(struct mimimi_walk *walk)
{
	int pdx = 0;
	int dx = 0;
	for (;;)
	{
		dx += walk->ground_speed;
		dx *= 5;
		dx /= 6;
		if (dx == pdx) return dx;
		pdx = dx;
	}
}

// todo: perhaps improve this (?)
static int mimimi_max_dy(struct mimimi_physics *physics)
{
	int pdy = 0;
	int dy = 0;
	for (;;)
	{
		dy += physics->gravity;
		dy *= 23;
		dy /= 24;
		if (dy == pdy) return dy;
		pdy = dy;
	}
}

static void mimimi_jump_target(struct mimimi_edge *edge, struct mimimi_path_finding_data *path_finding_data, int dx, int x, int y, int direction)
{
	struct mimimi_position position;
	struct mimimi_physics physics;
	struct mimimi_walk walk;
	
	struct mimimi_path_finding *path_finding = path_finding_data->path_finding;
	
	struct mimimi_behavior *compound = mimimi_compound_behavior(path_finding_data->allocator);
	mimimi_compound(compound, mimimi_physics(&physics, &position, path_finding->ground, path_finding_data->allocator));
	mimimi_compound(compound, mimimi_walk(&walk, &physics, path_finding_data->allocator));
	
	struct mimimi_behavior *jump = mimimi_jump(path_finding->jump, &physics, path_finding_data->allocator);
	
	physics = *path_finding->sprite->physics;
	walk = *path_finding->sprite->walk;
	
	position.x = x * 128 + 64;
	position.y = y * 128 + 128;
	physics.dx = dx;
	physics.dy = 0;
	physics.airborne = 0;
	walk.direction = direction;
	
	(*jump->behave)(jump->data);
	(*jump->finish)(jump->data);
	
	edge->time = 0;
	while (physics.airborne != 0 || path_finding->ground->tiles[position.x / 128 + ((position.y - 64) / 128 + 1) * path_finding->ground->width] == 0)
		(*compound->behave)(compound->data),
		edge->time++;
	(*compound->finish)(compound->data);
	
	edge->x = position.x / 128;
	edge->y = (position.y - 64) / 128;
}

// todo: queue lookup can be performed more efficiently by using binary search
static void mimimi_path_finding_behave(void *data)
{
	struct mimimi_path_finding_data *path_finding_data = data;
	struct mimimi_path_finding *path_finding = path_finding_data->path_finding;
	struct mimimi_sprite *sprite = path_finding->sprite;
	struct mimimi_behavior *jump = path_finding->jump_behavior;
	
	if (sprite->physics->airborne == 0)
		path_finding_data->direction = -1;
	
	if (path_finding_data->direction != -1)
	{
		sprite->walk->direction = path_finding_data->direction;
		return;
	}
	
	struct mimimi_graph *graph = path_finding_data->graph;
	
	int queue_count = 0;
	
	struct mimimi_node **queue = path_finding_data->queue;
	unsigned int *distances = path_finding_data->distances;
	struct mimimi_node **previous = path_finding_data->previous;
	
	for (int y = 0 ; y < graph->height ; y++)
	for (int x = 0 ; x < graph->width ; x++)
	{
		int i = x + y * graph->width;
		distances[i] = -1;
		if (y == graph->height) continue;
		queue[queue_count] = graph->nodes + i;
		queue_count++;
	}
	
	int x0 = path_finding->sprite->position->x / 128;
	int y0 = (path_finding->sprite->position->y - 64) / 128;
	
	int x1 = path_finding->target->x / 128;
	int y1 = (path_finding->target->y - 64) / 128;
	
	if (path_finding->ground->tiles[x1 + (y1 + 1) * graph->width] != 0 || path_finding_data->x1 == -1)
	{
		path_finding_data->x1 = x1;
		path_finding_data->y1 = y1;
	}
	else
	{
		x1 = path_finding_data->x1;
		y1 = path_finding_data->y1;
	}
	
	int i0 = x0 + y0 * graph->width;
	int i1 = x1 + y1 * graph->width;
	
	if ((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) < path_finding->radius * path_finding->radius)
	{
		sprite->walk->direction = 0;
		return;
	}
	
	if (i0 == i1)
	{
		mimimi_stabilise(sprite);
		return;
	}
	
	unsigned char found = 0;
	struct mimimi_edge *target;
	
	distances[i0] = 0;
	while (queue_count != 0)
	{
		unsigned int distance = -1;
		struct mimimi_node *u;
		int k = 0;
		
		for (int i = 0 ; i < queue_count ; i++)
		{
			struct mimimi_node *node = queue[i];
			unsigned int other_distance = distances[node->x + node->y * graph->width];
			if (other_distance < distance)
			{
				distance = other_distance;
				u = node;
				k = i;
			}
		}
		
		if (u == graph->nodes + i1)
		{
			for (;;)
			{
				struct mimimi_node *next = previous[u->x + u->y * graph->width];
				if (next == graph->nodes + i0) break;
				u = next;
			}
			for (int i = 0 ; i < graph->nodes[i0].count ; i++)
			{
				struct mimimi_edge *edge = graph->nodes[i0].edges + i;
				if (edge->x == u->x && edge->y == u->y)
				{
					target = edge;
					break;
				}
			}
			found = 1;
			break;
		}
		
		for (int j = k + 1 ; j < queue_count ; j++)
			queue[j - 1] = queue[j];
		queue_count--;
		
		for (int i = 0 ; i < u->count ; i++)
		{
			struct mimimi_node *v = graph->nodes + u->edges[i].x + u->edges[i].y * graph->width;
			
			unsigned char in_queue = 0;
			for (int i = 0 ; i < queue_count ; i++)
			{
				if (queue[i] == v)
				{
					in_queue = 1;
					break;
				}
			}
			
			if (in_queue == 0) continue;
			
			unsigned int alt = distances[u->x + u->y * graph->width] + u->edges[i].time;
			if (alt < distances[v->x + v->y * graph->width])
			{
				distances[v->x + v->y * graph->width] = alt;
				previous[v->x + v->y * graph->width] = u;
			}
		}
	}
	
	if (found == 0)
	{
		sprite->walk->direction = 0;
		return;
	}
	
	if (target->type == 0)
	{
		mimimi_stabilise(sprite);
		return;
	}
	if (target->type == 1)
	{
		sprite->walk->direction = 1;
		return;
	}
	if (target->type == 2)
	{
		sprite->walk->direction = 2;
		return;
	}
	
	// todo: for types 6 and 7, it would be neat to avoid setting 'dx'
	// and instead find a way to build up speed normally.
	if (target->type == 6)
	{
		if (path_finding->sprite->physics->dx > 0)
		{
			sprite->walk->direction = 2;
			return;
		}
		sprite->walk->direction = 1;
		if (path_finding->sprite->position->x - x0 * 128 < 64)
		{
			path_finding->sprite->physics->dx = -mimimi_max_dx(path_finding->sprite->walk);
			(*jump->behave)(jump->data);
			path_finding_data->direction = 1;
		}
		return;
	}
	if (target->type == 7)
	{
		if (path_finding->sprite->physics->dx < 0)
		{
			sprite->walk->direction = 1;
			return;
		}
		sprite->walk->direction = 2;
		if (path_finding->sprite->position->x - x0 * 128 > 64)
		{
			path_finding->sprite->physics->dx = mimimi_max_dx(path_finding->sprite->walk);
			(*jump->behave)(jump->data);
			path_finding_data->direction = 2;
		}
		return;
	}
	
	if (mimimi_stabilise(sprite) != 0) return;
	
	int direction = -1;
	
	if (target->type == 3)
		direction = 0;
	if (target->type == 4)
		direction = 1;
	if (target->type == 5)
		direction = 2;
	
	(*jump->behave)(jump->data);
	sprite->walk->direction = direction;
	path_finding_data->direction = direction;
}

static void mimimi_path_finding_finish(void *data)
{
	struct mimimi_path_finding_data *path_finding_data = data;
	struct mimimi_allocator *allocator = path_finding_data->allocator;
	mimimi_deallocate(allocator, path_finding_data->path_finding);
	mimimi_deallocate(allocator, path_finding_data->graph);
	mimimi_deallocate(allocator, path_finding_data->queue);
	mimimi_deallocate(allocator, path_finding_data->distances);
	mimimi_deallocate(allocator, path_finding_data->previous);
	mimimi_deallocate(allocator, path_finding_data->behavior);
	mimimi_deallocate(allocator, path_finding_data);
};

struct 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)
{
	struct mimimi_graph *graph = mimimi_allocate(allocator, sizeof *graph);
	graph->width = ground->width;
	graph->height = ground->height;
	graph->nodes = mimimi_allocate(allocator, graph->width * graph->height * sizeof *graph->nodes);
	
	struct mimimi_path_finding_data *path_finding_data = mimimi_allocate(allocator, sizeof *path_finding_data);
	path_finding_data->x1 = -1;
	path_finding_data->y1 = -1;
	path_finding_data->direction = -1;
	path_finding_data->path_finding = path_finding;
	path_finding_data->graph = graph;
	path_finding_data->queue = mimimi_allocate(allocator, graph->width * graph->height * sizeof *path_finding_data->queue);
	path_finding_data->distances = mimimi_allocate(allocator, graph->width * graph->height * sizeof *path_finding_data->distances);
	path_finding_data->previous = mimimi_allocate(allocator, graph->width * graph->height * sizeof *path_finding_data->previous);
	path_finding_data->allocator = allocator;
	
	struct mimimi_behavior *behavior = mimimi_allocate(allocator, sizeof *behavior);
	behavior->behave = &mimimi_path_finding_behave;
	behavior->finish = &mimimi_path_finding_finish;
	behavior->data = path_finding_data;
	path_finding_data->behavior = behavior;
	
	static struct mimimi_jump default_jump = {0};
	
	path_finding->ground = ground;
	path_finding->target = target;
	path_finding->sprite = sprite;
	path_finding->jump = &default_jump;
	path_finding->jump_behavior = mimimi_noop;
	path_finding->radius = 4;
	
	int dx = mimimi_max_dx(path_finding->sprite->walk);
	int dy = mimimi_max_dy(path_finding->sprite->physics);
	
	for (int y = 0 ; y < graph->height ; y++)
	for (int x = 0 ; x < graph->width ; x++)
	{
		int i = x + y * graph->width;
		struct mimimi_node *node = graph->nodes + i;
		node->x = x;
		node->y = y;
		
		node->count = 0;
		node->edges = allocator->null;
		if (ground->tiles[i] != 0) continue;
		
		if (x == 0) continue;
		if (y == 0) continue;
		if (x == graph->width - 1) continue;
		if (y == graph->height - 1) continue;
		
		if (ground->tiles[i - 1] == 0)
		if (ground->tiles[i - 1 + graph->width] != 0 || ground->tiles[i + graph->width] != 0)
		{
			struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
			edge->type = 1;
			edge->time = 128 / dx;
			edge->x = x - 1;
			edge->y = y;
		}
		if (ground->tiles[i + 1] == 0)
		if (ground->tiles[i + 1 + graph->width] != 0 || ground->tiles[i + graph->width] != 0)
		{
			struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
			edge->type = 2;
			edge->time = 128 / dx;
			edge->x = x + 1;
			edge->y = y;
		}
		
		if (ground->tiles[x + (y + 1) * graph->width] == 0)
		{
			struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
			edge->type = 0;
			edge->time = 128 / dy;
			edge->x = x;
			edge->y = y + 1;
			continue;
		}
		
		if (ground->tiles[i - 1] == 1)
		if (ground->tiles[i - 1 - graph->width] == 0)
		{
			struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
			edge->type = 1;
			edge->time = 128 / dx;
			edge->x = x;
			edge->y = y - 1;
		}
		if (ground->tiles[i + 1] == 1)
		if (ground->tiles[i + 1 - graph->width] == 0)
		{
			struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
			edge->type = 2;
			edge->time = 128 / dx;
			edge->x = x;
			edge->y = y - 1;
		}
		
		struct mimimi_edge *edge3 = mimimi_grow_node(node, allocator);
		edge3->type = 3;
		mimimi_jump_target(edge3, path_finding_data, 0, x, y, 0);
		if (edge3->x == x && edge3->y == y) mimimi_shrink_node(node, allocator);
		
		struct mimimi_edge *edge4 = mimimi_grow_node(node, allocator);
		edge4->type = 4;
		mimimi_jump_target(edge4, path_finding_data, 0, x, y, 1);
		if (edge4->x == x && edge4->y == y) mimimi_shrink_node(node, allocator);
		
		struct mimimi_edge *edge5 = mimimi_grow_node(node, allocator);
		edge5->type = 5;
		mimimi_jump_target(edge5, path_finding_data, 0, x, y, 2);
		if (edge5->x == x && edge5->y == y) mimimi_shrink_node(node, allocator);
		
		struct mimimi_edge *edge6 = mimimi_grow_node(node, allocator);
		edge6->type = 6;
		mimimi_jump_target(edge6, path_finding_data, -dx, x, y, 1);
		if (edge6->x == x && edge6->y == y) mimimi_shrink_node(node, allocator);
		
		struct mimimi_edge *edge7 = mimimi_grow_node(node, allocator);
		edge7->type = 7;
		mimimi_jump_target(edge7, path_finding_data, dx, x, y, 2);
		if (edge7->x == x && edge7->y == y) mimimi_shrink_node(node, allocator);
	}
	
	return behavior;
}