From 2436fde1cfe091db740f15665822e18295a7f8de Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Sun, 30 Dec 2018 16:31:35 -0800 Subject: libs/grid: add grid cellular automata component Prep for adding a new module displaying a cellular automata based on the grid component from a multiplayer game I'm working on. --- src/libs/grid/grid.c | 366 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 366 insertions(+) create mode 100644 src/libs/grid/grid.c (limited to 'src/libs/grid/grid.c') diff --git a/src/libs/grid/grid.c b/src/libs/grid/grid.c new file mode 100644 index 0000000..e9b140e --- /dev/null +++ b/src/libs/grid/grid.c @@ -0,0 +1,366 @@ +/* + * Copyright (C) 2018 - Vito Caputo - + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 3 as published + * by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +/* This implements a simple cellular automata engine with basic rules, taken + * from a multiplayer game project I'm working on hence the concept of players, + * variable move planning queues, and a rudimentary chat function. It's all + * pluggable for mixed use as a client-resident local component, or as a daemon + * for remote multiplayer games, and it appears, simple use as a gadget in + * programs like rototiller. + * + * The rules are currently fixed in execute_plan(), but could easily be made + * pluggable by having the execute_plan() supplied to grid_new(). TODO + * + * Note this is also rather allocation/free heavy, this hasn't seen any + * optimization at all. + */ + +#include +#include + +#include "grid.h" +#include "macros.h" + +typedef struct grid_plan_t grid_plan_t; +typedef struct grid_player_t grid_player_t; +typedef struct grid_t grid_t; + +struct grid_plan_t { + grid_plan_t *next, *prev; + uint32_t x, y; + uint32_t id; +}; + +struct grid_player_t { + grid_player_t *next, *prev; + grid_t *grid; + const grid_ops_t *ops; + void *ops_ctx; + + grid_plan_t *plan_tail, *plan_head; + uint32_t n_cells; + uint32_t id; +}; + +struct grid_t { + grid_player_t *players; + uint32_t req_players, num_players; + uint32_t next_player; + uint32_t width, height; + uint32_t cells[]; +}; + + +grid_t * grid_new(uint32_t players, uint32_t width, uint32_t height) +{ + grid_t *grid; + + assert(players && width && height); + + grid = calloc(1, sizeof(grid_t) + sizeof(uint32_t) * width * height); + fatal_if(!grid, "Unable to allocate grid_t"); + + grid->width = width; + grid->height = height; + grid->req_players = players; + grid->next_player = 1; /* XXX: zero is reserved for blank cells */ + + return grid; +} + + +void grid_free(grid_t *grid) +{ + grid_player_t *p, *p_next; + + assert(grid); + + for (p = grid->players; p != NULL; p = p_next) { + p_next = p->next; + + if (p->ops->shutdown) + p->ops->shutdown(p->ops_ctx); + + free(p); + } + + free(grid); +} + + +static grid_ops_move_result_t execute_plan(grid_player_t *player, grid_plan_t *plan) +{ + uint32_t *cells, width, height; + + assert(player); + assert(plan); + + cells = player->grid->cells; + width = player->grid->width; + height = player->grid->height; + + if (cells[plan->y * width + plan->x] == player->id) + return GRID_OPS_MOVE_RESULT_NOOP; + + /* is the cell uncontested and orthogonally adjacent? */ + if (!cells[plan->y * width + plan->x]) { + /* if the player has no cells, it may take any + * uncontested one. + */ + if (!player->n_cells) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->x > 0 && + cells[plan->y * width + plan->x - 1] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->x < width - 1 && + cells[plan->y * width + plan->x + 1] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->y > 0 && + cells[(plan->y - 1) * width + plan->x] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->y < height - 1 && + cells[(plan->y + 1) * width + plan->x] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + } + + /* does the player have two cells chained orthogonally adjacent? */ + if (plan->x > 1 && + cells[plan->y * width + plan->x - 1] == player->id && + cells[plan->y * width + plan->x - 2] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->x < width - 2 && + cells[plan->y * width + plan->x + 1] == player->id && + cells[plan->y * width + plan->x + 2] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->y > 1 && + cells[(plan->y - 1) * width + plan->x] == player->id && + cells[(plan->y - 2) * width + plan->x] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + if (plan->y < height - 2 && + cells[(plan->y + 1) * width + plan->x] == player->id && + cells[(plan->y + 2) * width + plan->x] == player->id) + return GRID_OPS_MOVE_RESULT_SUCCESS; + + /* does the player surround the target's group? */ + /* TODO TODO */ + + return GRID_OPS_MOVE_RESULT_FAIL; +} + + +/* call this at the frequency desired for the game. */ +void grid_tick(grid_t *grid) +{ + assert(grid); + + /* TODO: shuffle grid->players every tick */ + + /* execute every player's next planned move */ + for (grid_player_t *p = grid->players; p != NULL; p = p->next) { + grid_plan_t *plan; + grid_ops_move_result_t res; + + plan = p->plan_head; + if (!plan) + continue; + + /* TODO: add a simple doubly linked list header, use it */ + p->plan_head = plan->next; + if (p->plan_head) + p->plan_head->prev = NULL; + else + p->plan_tail = NULL; + + res = execute_plan(p, plan); + if (p->ops->executed) + p->ops->executed(p->ops_ctx, plan->id, res); + if (res == GRID_OPS_MOVE_RESULT_SUCCESS) { + /* find the current owner, dec their n_cells */ + if (grid->cells[plan->y * grid->width + plan->x]) { + for (grid_player_t *pp = grid->players; pp != NULL; pp = pp->next) { + if (grid->cells[plan->y * grid->width + plan->x] == pp->id) { + pp->n_cells--; + break; + } + } + } + + /* new ownership */ + grid->cells[plan->y * grid->width + plan->x] = p->id; + p->n_cells++; + + /* notify all players of a successfully executed plan */ + for (grid_player_t *pp = grid->players; pp != NULL; pp = pp->next) { + if (pp->ops->taken) + pp->ops->taken(pp->ops_ctx, plan->x, plan->y, p->id); + } + + /* winner! */ + if (p->n_cells == grid->width * grid->height) { + for (grid_player_t *pp = grid->players; pp != NULL; pp = pp->next) { + if (pp->ops->won) + pp->ops->won(pp->ops_ctx, p->id); + } + } + } + + free(plan); + } +} + + +/* establish a new player on the specified grid, using the supplied ops to + * communicate state changes from the grid back to the player. + */ +grid_player_t * grid_player_new(grid_t *grid, const grid_ops_t *ops, void *ops_ctx) +{ + static grid_ops_t null_ops; + grid_player_t *player; + + assert(grid); + + if (!ops) + ops = &null_ops; + + player = calloc(1, sizeof(grid_player_t)); + fatal_if(!player, "Unable to allocate grid_player_t"); + + /* TODO: refuse when exceeding grid->req_players? */ + + player->grid = grid; + player->ops = ops; + player->ops_ctx = ops_ctx; + player->id = grid->next_player++; + + if (ops->setup) + ops->setup(ops_ctx, player->id); + + /* TODO: add a simple doubly linked list header, use it */ + player->next = grid->players; + if (player->next) + player->next->prev = player; + grid->players = player; + + grid->num_players++; + + for (grid_player_t *p = grid->players; p != NULL; p = p->next) { + if (p->ops->joined) + p->ops->joined(p->ops_ctx, player->id); + } + + return player; +} + + +void grid_player_free(grid_player_t *player) +{ + assert(player); + + /* TODO: add a simple doubly linked list header, use it */ + if (player->next) + player->next->prev = player->prev; + + if (player->prev) + player->prev->next = player->next; + else + player->grid->players = player->next; + + player->grid->num_players--; + + for (grid_player_t *p = player->grid->players; p != NULL; p = p->next) { + if (p->ops->parted) + p->ops->parted(p->ops_ctx, player->id); + } + + free(player); +} + + +void grid_player_plan(grid_player_t *player, uint32_t move, uint32_t x, uint32_t y) +{ + grid_plan_t *plan; + + assert(player); + assert(x < player->grid->width && y < player->grid->height); + + plan = calloc(1, sizeof(grid_plan_t)); + fatal_if(!plan, "Unable to allocate plan"); + + plan->id = move; + plan->x = x; + plan->y = y; + + /* TODO: add a simple doubly linked list header, use it */ + plan->prev = player->plan_tail; + player->plan_tail = plan; + if (!plan->prev) + player->plan_head = plan; + else + plan->prev->next = plan; + + if (player->ops->planned) + player->ops->planned(player->ops_ctx, move); +} + + +void grid_player_cancel(grid_player_t *player, uint32_t move) +{ + grid_plan_t *p; + + assert(player); + + for (p = player->plan_head; p != NULL; p = p->next) + if (p->id == move) + break; + + if (!p) + return; + + /* TODO: add a simple doubly linked list header, use it */ + if (p->next) + p->next->prev = p->prev; + else + player->plan_tail = p->prev; + + if (p->prev) + p->prev->next = p->next; + else + player->plan_head = p->next; + + free(p); + + if (player->ops->canceled) + player->ops->canceled(player->ops_ctx, move); +} + + +void grid_player_say(grid_player_t *player, const char *text) +{ + assert(player); + assert(player->grid); + + for (grid_player_t *p = player->grid->players; p != NULL; p = p->next) { + if (player->ops->said) + p->ops->said(p->ops_ctx, player->id, text); + } +} -- cgit v1.2.3