Mirai's Miscellaneous Misadventures

M42 / core / paths.c

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

#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 index;
	int x, y;
	int time;
	int type;
};

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

struct mimimi_graph
{
	int count;
	struct mimimi_node *nodes;
	struct mimimi_node **by_position;
};

struct mimimi_path_finding_data
{
	int x1, y1;
	int direction;
	struct mimimi_path_finding *path_finding;
	struct mimimi_behavior *jump;
	struct mimimi_graph *graph;
	unsigned char *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 * sizeof *node->edges);
	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 * sizeof *node->edges);
}

// 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 || mimimi_ground_tile(path_finding->ground, position.x / 128, (position.y - 64) / 128 + 1) == 0)
		(*compound->behave)(compound->data),
		edge->time++;
	(*compound->finish)(compound->data);
	
	edge->x = position.x / 128;
	edge->y = (position.y - 64) / 128;
}

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;
	
	unsigned char *queue = path_finding_data->queue;
	unsigned int *distances = path_finding_data->distances;
	struct mimimi_node **previous = path_finding_data->previous;
	
	for (int i = 0 ; i < graph->count ; i++)
	{
		distances[i] = -1;
		queue[i] = 1;
	}
	
	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 (mimimi_ground_tile(path_finding->ground, x1, y1 + 1) != 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 * path_finding->ground->width;
	int i1 = x1 + y1 * path_finding->ground->width;
	
	if (graph->by_position[i0]->index == -1 || graph->by_position[i1]->index == -1)
	{
		sprite->walk->direction = 0;
		return;
	}
	
	if ((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) < path_finding->radius * path_finding->radius)
	{
		sprite->walk->direction = 0;
		return;
	}
	
	if (x0 == x1 && y0 == y1)
	{
		mimimi_stabilise(sprite);
		return;
	}
	
	unsigned char found = 0;
	struct mimimi_edge *target;
	
	distances[graph->by_position[i0]->index] = 0;
	for (int c = 0 ; c < graph->count ; c++)
	{
		unsigned int distance = -1;
		struct mimimi_node *u;
		int k;
		
		for (int i = 0 ; i < graph->count ; i++)
		{
			if (queue[i] == 0) continue;
			struct mimimi_node *node = graph->nodes + i;
			unsigned int other_distance = distances[i];
			if (other_distance < distance)
			{
				distance = other_distance;
				u = node;
				k = i;
			}
		}
		
		if (k == graph->by_position[i1]->index)
		{
			for (;;)
			{
				struct mimimi_node *next = previous[u->index];
				if (next == graph->by_position[i0]) break;
				u = next;
			}
			for (int i = 0 ; i < graph->by_position[i0]->count ; i++)
			{
				struct mimimi_edge *edge = graph->by_position[i0]->edges + i;
				if (edge->index == u->index)
				{
					target = edge;
					break;
				}
			}
			found = 1;
			break;
		}
		
		queue[k] = 0;
		
		for (int i = 0 ; i < u->count ; i++)
		{
			struct mimimi_node *v = graph->nodes + u->edges[i].index;
			if (queue[v->index] == 0) continue;
			
			unsigned int alt = distances[u->index] + u->edges[i].time;
			if (alt < distances[v->index])
			{
				distances[v->index] = alt;
				previous[v->index] = 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;
	
	for (int i = 0 ; i < path_finding_data->graph->count ; i++)
	{
		struct mimimi_node *node = path_finding_data->graph->nodes + i;
		mimimi_deallocate(allocator, node->edges);
	}
	mimimi_deallocate(allocator, path_finding_data->graph->nodes);
	
	mimimi_deallocate(allocator, path_finding_data->graph->by_position);
	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->nodes = mimimi_allocate(allocator, ground->width * ground->height * sizeof *graph->nodes);
	graph->by_position = mimimi_allocate(allocator, ground->width * ground->height * sizeof *graph->by_position);
	
	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, ground->width * ground->height * sizeof *path_finding_data->queue);
	path_finding_data->distances = mimimi_allocate(allocator, ground->width * ground->height * sizeof *path_finding_data->distances);
	path_finding_data->previous = mimimi_allocate(allocator, ground->width * ground->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);
	
	graph->count = 0;
	for (int y = 0 ; y < ground->height ; y++)
	for (int x = 0 ; x < ground->width ; x++)
	{
		struct mimimi_node *node = graph->nodes + graph->count;
		node->index = graph->count;
		node->x = x;
		node->y = y;
		
		node->count = 0;
		node->edges = allocator->null;
		
		static struct mimimi_node no_node = {-1, 0, 0, 0, 0};
		graph->by_position[x + y * ground->width] = &no_node;
		
		if (mimimi_ground_tile(ground, x, y) != 0) continue;
		
		if (mimimi_ground_tile(ground, x, y + 1) == 0)
		if (mimimi_ground_tile(ground, x - 1, y + 1) == 0)
		if (mimimi_ground_tile(ground, x + 1, y + 1) == 0)
			continue;
		
		graph->by_position[x + y * ground->width] = node;
		graph->count++;
		
		if (mimimi_ground_tile(ground, x - 1, y) == 0)
		if (mimimi_ground_tile(ground, x, y + 1) != 0 || mimimi_ground_tile(ground, x - 1, y + 1) != 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 (mimimi_ground_tile(ground, x + 1, y) == 0)
		if (mimimi_ground_tile(ground, x, y + 1) != 0 || mimimi_ground_tile(ground, x + 1, y + 1) != 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 (mimimi_ground_tile(ground, x, y + 1) == 0)
		{
			struct mimimi_edge *edge = mimimi_grow_node(node, allocator);
			edge->type = 0;
			edge->x = x;
			edge->y = y;
			while (mimimi_ground_tile(ground, x, edge->y + 1) == 0)
				edge->y++;
			edge->time = (edge->y - y) * 128 / dy;
			continue;
		}
		
		if (mimimi_ground_tile(ground, x - 1, y) == 1)
		if (mimimi_ground_tile(ground, x - 1, y - 1) == 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 (mimimi_ground_tile(ground, x + 1, y) == 1)
		if (mimimi_ground_tile(ground, x + 1, y - 1) == 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);
	}
	
	for (int i = 0 ; i < graph->count ; i++)
	{
		struct mimimi_node *node = graph->nodes + i;
		for (int j = 0 ; j < node->count ; j++)
		{
			struct mimimi_edge *edge = node->edges + j;
			edge->index = graph->by_position[edge->x + edge->y * ground->width]->index;
		}
	}
	
	return behavior;
}