diff options
| -rw-r--r-- | configure.ac | 1 | ||||
| -rw-r--r-- | src/libs/Makefile.am | 2 | ||||
| -rw-r--r-- | src/libs/grid/Makefile.am | 3 | ||||
| -rw-r--r-- | src/libs/grid/grid.c | 366 | ||||
| -rw-r--r-- | src/libs/grid/grid.h | 55 | ||||
| -rw-r--r-- | src/libs/grid/macros.h | 44 |
6 files changed, 470 insertions, 1 deletions
diff --git a/configure.ac b/configure.ac index ced42a7..3b98877 100644 --- a/configure.ac +++ b/configure.ac @@ -35,6 +35,7 @@ AC_CONFIG_FILES([ Makefile src/Makefile src/libs/Makefile + src/libs/grid/Makefile src/libs/ray/Makefile src/modules/Makefile src/modules/julia/Makefile diff --git a/src/libs/Makefile.am b/src/libs/Makefile.am index 99b6857..266fcf0 100644 --- a/src/libs/Makefile.am +++ b/src/libs/Makefile.am @@ -1 +1 @@ -SUBDIRS = ray +SUBDIRS = grid ray diff --git a/src/libs/grid/Makefile.am b/src/libs/grid/Makefile.am new file mode 100644 index 0000000..e9c8f3a --- /dev/null +++ b/src/libs/grid/Makefile.am @@ -0,0 +1,3 @@ +noinst_LIBRARIES = libgrid.a +libgrid_a_SOURCES = grid.c grid.h macros.h +libgrid_a_CPPFLAGS = -I@top_srcdir@/src 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 - <vcaputo@pengaru.com> + * + * 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 <http://www.gnu.org/licenses/>. + */ + +/* 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 <assert.h> +#include <stdlib.h> + +#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); + } +} diff --git a/src/libs/grid/grid.h b/src/libs/grid/grid.h new file mode 100644 index 0000000..e17989f --- /dev/null +++ b/src/libs/grid/grid.h @@ -0,0 +1,55 @@ +/* + * Copyright (C) 2018 - Vito Caputo - <vcaputo@pengaru.com> + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _GRID_H +#define _GRID_H + +#include <stdint.h> + +typedef enum grid_ops_move_result_t { + GRID_OPS_MOVE_RESULT_FAIL, + GRID_OPS_MOVE_RESULT_SUCCESS, + GRID_OPS_MOVE_RESULT_NOOP, +} grid_ops_move_result_t; + +/* hooks to integrate from back-end to front-end */ +typedef struct grid_ops_t { + void (*setup)(void *ctx, uint32_t player); /* the specified player number has been assigned to this context */ + void (*shutdown)(void *ctx); /* the grid has shutdown */ + void (*joined)(void *ctx, uint32_t player); /* the specified player joined */ + void (*parted)(void *ctx, uint32_t player); /* the specified player parted */ + void (*said)(void *ctx, uint32_t player, const char *text); /* the specified player says text */ + void (*planned)(void *ctx, uint32_t move); /* the specified move has been planned */ + void (*executed)(void *ctx, uint32_t move, grid_ops_move_result_t result);/* the specified move has been executed, removed from plan */ + void (*canceled)(void *ctx, uint32_t move); /* the specified move has been canceled, removed from plan */ + void (*taken)(void *ctx, uint32_t x, uint32_t y, unsigned player); /* the specified cell has been taken by the specified player */ + void (*won)(void *ctx, uint32_t player); /* the game has been won by the specified player */ +} grid_ops_t; + +typedef struct grid_t grid_t; +typedef struct grid_player_t grid_player_t; + +grid_t * grid_new(uint32_t players, uint32_t width, uint32_t height); +void grid_free(grid_t *grid); +void grid_tick(grid_t *grid); + +grid_player_t * grid_player_new(grid_t *grid, const grid_ops_t *ops, void *ops_ctx); +void grid_player_free(grid_player_t *player); +void grid_player_plan(grid_player_t *player, uint32_t move, uint32_t x, uint32_t y); +void grid_player_cancel(grid_player_t *player, uint32_t move); +void grid_player_say(grid_player_t *player, const char *text); + +#endif diff --git a/src/libs/grid/macros.h b/src/libs/grid/macros.h new file mode 100644 index 0000000..79a3c18 --- /dev/null +++ b/src/libs/grid/macros.h @@ -0,0 +1,44 @@ +/* + * Copyright (C) 2018 - Vito Caputo - <vcaputo@pengaru.com> + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _MACROS_H +#define _MACROS_H + +#include <stdio.h> + +#define fatal_if(_cond, _fmt, ...) \ + if (_cond) { \ + fprintf(stderr, "Fatal error: " _fmt "\n", ##__VA_ARGS__); \ + exit(EXIT_FAILURE); \ + } + +#define NELEMS(_a) \ + (sizeof(_a) / sizeof(_a[0])) + +#define CSTRLEN(_str) \ + (sizeof(_str) - 1) + +#ifndef MIN +#define MIN(_a, _b) \ + ((_a) < (_b) ? (_a) : (_b)) +#endif + +#ifndef MAX +#define MAX(_a, _b) \ + ((_a) > (_b) ? (_a) : (_b)) +#endif + +#endif |