Mirai's Miscellaneous Misadventures
M34 / core / paths.c
#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);
}
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;
}
}
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;
}
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;
}
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;
}