summaryrefslogtreecommitdiff
path: root/src/libs/grid/grid.c
diff options
context:
space:
mode:
authorVito Caputo <vcaputo@pengaru.com>2018-12-30 16:31:35 -0800
committerVito Caputo <vcaputo@pengaru.com>2018-12-30 16:31:35 -0800
commit2436fde1cfe091db740f15665822e18295a7f8de (patch)
tree88a982ed101fa30015a752f6a51f2907706ece46 /src/libs/grid/grid.c
parent7146b9c2a253c5c51d7935bae8725232ef276cdf (diff)
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.
Diffstat (limited to 'src/libs/grid/grid.c')
-rw-r--r--src/libs/grid/grid.c366
1 files changed, 366 insertions, 0 deletions
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);
+ }
+}
© All Rights Reserved