Mirai's Miscellaneous Misadventures
M36 / 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 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);
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 || 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;
}
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;
for (int i = 0 ; i < node->count ; i++)
mimimi_deallocate(allocator, node->edges);
}
mimimi_deallocate(allocator, path_finding_data->graph->nodes);
mimimi_deallocate(allocator, path_finding_data->path_finding);
mimimi_deallocate(allocator, path_finding_data->graph->by_position);
mimimi_deallocate(allocator, path_finding_data->graph->nodes);
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;
}