commit 8e6a27421fd714f1ef85cd441400e0172c603347
parent 47b3c8aa11bf7f078cc0b695ad0d71cb36769e3e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 6 Jun 2022 16:19:05 +0200
Update game logic to use hashmap
Diffstat:
| M | include/logic.h | | | 34 | +++++++++++++++++++++++++++++++--- |
| M | src/logic.c | | | 371 | +++++++++++++++++++++++++++++++++++-------------------------------------------- |
2 files changed, 194 insertions(+), 211 deletions(-)
diff --git a/include/logic.h b/include/logic.h
@@ -1,17 +1,45 @@
#ifndef LOGIC_H
#define LOGIC_H
+#include "uthash.h"
+
+#define MAX_SIZE 101
+
+typedef struct Cell_cord {
+ int row;
+ int col;
+} Cell_cord;
+
+typedef struct Cell {
+ Cell_cord cord;
+ unsigned char val;
+ UT_hash_handle hh;
+} Cell;
+
+extern Cell *hash;
+
extern char *evolution_names[];
extern int evolution_cells[];
extern int evolution_size;
+extern int evolve_index;
+
+extern Cell **save_cells;
+extern int save_cells_s;
+
+extern int pos_y;
+extern int pos_x;
+
+extern int WIDTH, HEIGHT;
int logic_init(int w, int h, int isWrapping);
int evolution_init(int index);
-void do_evolution(int steps);
+void do_evolution(int steps);
int logic_free(void);
-int toggleAt(int i, int j);
+int toggleAt(int i, int j);
int getAt(int i, int j);
void deleteAt(int i, int j);
-int getNext(int *row, int *col, int *value, int reset);
+void saveCell(int i, int j);
+void setPosition(int i, int j);
+void setAt(int i, int j, int val);
#endif
diff --git a/src/logic.c b/src/logic.c
@@ -4,43 +4,61 @@
#include "logic.h"
#include "utils.h"
-#define SIZE_TO_EXPAND 10
+Cell *hash = NULL;
-typedef struct Cell {
- unsigned char val;
- int row;
- int col;
-} Cell;
+void deleter(Cell *c) {
+ HASH_DEL(hash, c);
+ free(c);
+}
+
+Cell *get(int row, int col) {
+ Cell *c, t;
-// GLOBALS
-Cell *cells;
-Cell *temp_cells;
+ memset(&t, 0, sizeof(Cell));
+ t.cord.row = row;
+ t.cord.col = col;
+ HASH_FIND(hh, hash, &t.cord, sizeof(Cell_cord), c);
+
+ return c;
+}
+
+void insert(int row, int col, int val, int mod) {
+ Cell *c;
+
+ c = get(row, col);
+ if (c == NULL) {
+ c = malloc(sizeof(Cell));
+ c->cord.row = row;
+ c->cord.col = col;
+ c->val = val;
+ HASH_ADD(hh, hash, cord, sizeof(Cell_cord), c);
+ }
+ c->val += mod;
+}
int WIDTH, HEIGHT;
-int cells_size;
-int temp_size;
-int counter;
int isExpanding;
+Cell **save_cells;
+int save_cells_s;
+int save_cells_sm;
+
+int pos_y;
+int pos_x;
+
char *evolution_names[] = {"Normal", "CoExsistance", "Predator", "Virus",
"Unknown"};
int evolution_cells[] = {2, 3, 3, 3, 3};
int evolution_size = 5;
+int evolve_index;
int toggle_mod = 2;
static void (*evolve)(void);
static void (*addToCells)(int i, int j, int value);
-void insert(int row, int col, int value) {
- temp_cells[temp_size].val = value;
- temp_cells[temp_size].row = row;
- temp_cells[temp_size].col = col;
- temp_size++;
-}
-
void addToCellsNormal(int i, int j, int value) {
int mod = 0;
- switch (value) {
+ switch (value & 3) {
case 1:
mod = 4;
break;
@@ -48,32 +66,15 @@ void addToCellsNormal(int i, int j, int value) {
mod = 32;
break;
}
- for (int k = i - 1; k <= i + 1; k++) {
- for (int l = j - 1; l <= j + 1; l++) {
- for (int m = 0; m < temp_size; m++)
- if (temp_cells[m].row == k && temp_cells[m].col == l) {
- temp_cells[m].val += mod;
- if (k == i && l == j) {
- temp_cells[m].val -= mod;
- temp_cells[m].val += value;
- }
- goto Kontinue;
- }
-
- if (k == i && l == j) {
- insert(k, l, value);
- continue;
- }
- insert(k, l, mod);
- Kontinue:
- continue;
- }
- }
+ for (int k = i - 1; k <= i + 1; k++)
+ for (int l = j - 1; l <= j + 1; l++)
+ if (k != i || l != j)
+ insert(k, l, 0, mod);
}
void addToCellsWrap(int i, int j, int value) {
int mod = 0;
- switch (value) {
+ switch (value & 3) {
case 1:
mod = 4;
break;
@@ -82,218 +83,181 @@ void addToCellsWrap(int i, int j, int value) {
break;
}
- for (int k = i - 1; k <= i + 1; k++) {
+ for (int k = i - 1; k <= i + 1; k++)
for (int l = j - 1; l <= j + 1; l++) {
int a = (k + HEIGHT) % HEIGHT;
int b = (l + WIDTH) % WIDTH;
- for (int m = 0; m < temp_size; m++)
- if (temp_cells[m].row == a && temp_cells[m].col == b) {
- temp_cells[m].val += mod;
- if (a == i && b == j) {
- temp_cells[m].val -= mod;
- temp_cells[m].val += value;
- }
- goto Kontinue;
- }
-
- if (a == i && b == j) {
- insert(a, b, value);
- continue;
- }
- insert(a, b, mod);
- Kontinue:
- continue;
+ if (a != i || b != j)
+ insert(a, b, 0, mod);
}
- }
}
void doAdditions(void) {
- for (int cellIndex = 0; cellIndex < cells_size; cellIndex++) {
- addToCells(cells[cellIndex].row, cells[cellIndex].col,
- cells[cellIndex].val);
- }
+ Cell *c;
+
+ Cell *buff[10000];
+ int size = 0;
+ for (c = hash; c != NULL; c = c->hh.next)
+ buff[size++] = c;
+
+ for (int i = 0; i < size; i++)
+ addToCells(buff[i]->cord.row, buff[i]->cord.col, buff[i]->val);
}
/* Evolutions */
void evolveNormal(void) {
+ Cell *c, *c_next;
+
doAdditions();
- counter = 0;
- for (int i = 0; i < temp_size; i++) {
- switch (temp_cells[i].val) {
+ for (c = hash; c != NULL; c = c_next) {
+ c_next = c->hh.next;
+ switch (c->val) {
case 9:
case 12:
case 13:
- cells[counter].val = 1;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 1;
break;
+ default:
+ deleter(c);
}
}
- cells_size = counter;
}
void evolveCoExist(void) {
+ Cell *c, *c_next;
+
doAdditions();
- counter = 0;
int s1, s2, mod;
- for (int i = 0; i < temp_size; i++) {
- s2 = temp_cells[i].val >> 5;
- s1 = (temp_cells[i].val & 31) >> 2;
- mod = temp_cells[i].val & 3;
+ for (c = hash; c != NULL; c = c_next) {
+ c_next = c->hh.next;
+ s2 = c->val >> 5;
+ s1 = (c->val & 31) >> 2;
+ mod = c->val & 3;
if (mod == 0) {
if ((s1 + s2) == 3) {
- if (temp_cells[i].val >= 64)
- cells[counter].val = 2;
+ if (c->val >= 64)
+ c->val = 2;
else
- cells[counter].val = 1;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 1;
continue;
}
}
if ((s1 + s2) < 2 || (s1 + s2) > 3) {
- continue;
+ deleter(c);
}
- cells[counter].val = mod;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = mod;
}
- cells_size = counter;
}
void evolvePredator(void) {
+ Cell *c, *c_next;
doAdditions();
- counter = 0;
int s1, s2, mod;
- for (int i = 0; i < temp_size; i++) {
- s2 = temp_cells[i].val >> 5;
- s1 = (temp_cells[i].val & 31) >> 2;
- mod = temp_cells[i].val & 3;
+ for (c = hash; c != NULL; c = c_next) {
+ c_next = c->hh.next;
+ s2 = c->val >> 5;
+ s1 = (c->val & 31) >> 2;
+ mod = c->val & 3;
if ((s1 + s2) < 2 || (s1 + s2) > 3) {
continue;
}
switch (mod) {
case 0:
if ((s1 + s2) == 3) {
- if (temp_cells[i].val >= 64)
- cells[counter].val = 2;
+ if (c->val >= 64)
+ c->val = 2;
else
- cells[counter].val = 1;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 1;
continue;
}
+ deleter(c);
break;
case 1:
if (s2 > 0) {
+ deleter(c);
continue;
}
break;
}
- cells[counter].val = mod;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = mod;
}
- cells_size = counter;
}
void evolveVirus(void) {
+ Cell *c, *c_next;
doAdditions();
- counter = 0;
int s1, s2, mod;
- for (int i = 0; i < temp_size; i++) {
- s2 = temp_cells[i].val >> 5;
- s1 = (temp_cells[i].val & 31) >> 2;
- mod = temp_cells[i].val & 3;
+ for (c = hash; c != NULL; c = c_next) {
+ c_next = c->hh.next;
+ s2 = c->val >> 5;
+ s1 = (c->val & 31) >> 2;
+ mod = c->val & 3;
if ((s1 + s2) < 2 || (s1 + s2) > 3) {
- continue;
+ deleter(c);
}
switch (mod) {
case 0:
if ((s1 + s2) == 3) {
- if (temp_cells[i].val >= 64)
- cells[counter].val = 2;
+ if (c->val >= 64)
+ c->val = 2;
else
- cells[counter].val = 1;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 1;
continue;
}
+ deleter(c);
break;
case 1:
if (s2 > 0) {
- cells[counter].val = 2;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 2;
continue;
}
break;
}
- cells[counter].val = mod;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = mod;
}
- cells_size = counter;
}
void evolveUnknown(void) { // Assumption 3 ones and 3 twos result in 50/50
// chanse of 0 becoming one of them:
+ Cell *c, *c_next;
doAdditions();
- counter = 0;
int s1, s2, mod;
- for (int i = 0; i < temp_size; i++) {
- s2 = temp_cells[i].val >> 5;
- s1 = (temp_cells[i].val & 31) >> 2;
- mod = temp_cells[i].val & 3;
+ for (c = hash; c != NULL; c = c_next) {
+ c_next = c->hh.next;
+ s2 = c->val >> 5;
+ s1 = (c->val & 31) >> 2;
+ mod = c->val & 3;
switch (mod) {
case 0:
if (s1 == 3 && s2 == 3) {
- cells[counter].val = rand() % 2 + 1;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = rand() % 2 + 1;
continue;
}
if (s1 == 3) {
- cells[counter].val = 1;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 1;
continue;
}
if (s2 == 3) {
- cells[counter].val = 2;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = 2;
continue;
}
+ deleter(c);
break;
case 1:
if (s1 < 2 || s1 > 3) {
+ deleter(c);
continue;
}
break;
case 2:
if (s2 < 2 || s2 > 3) {
+ deleter(c);
continue;
}
break;
}
- cells[counter].val = mod;
- cells[counter].row = temp_cells[i].row;
- cells[counter].col = temp_cells[i].col;
- counter++;
+ c->val = mod;
}
- cells_size = counter;
}
/* Initializing functions */
@@ -304,100 +268,91 @@ static void (*addition_modes[])(int i, int j, int value) = {addToCellsNormal,
void do_evolution(int steps) {
while (steps--) {
- int temp_alloc = 9 * cells_size;
- temp_size = 0;
- temp_cells = calloc(temp_alloc, sizeof(*temp_cells));
evolve();
- free(temp_cells);
}
}
int logic_init(int w, int h, int isWrapping) {
WIDTH = w;
HEIGHT = h;
-
addToCells = addition_modes[isWrapping];
+ save_cells_sm = 100;
+ save_cells = malloc(save_cells_sm * sizeof(struct Cell *));
+ save_cells_s = 0;
- cells = malloc(WIDTH * HEIGHT * sizeof(*cells));
- cells_size = 0;
return 1;
}
int evolution_init(int index) {
+ evolve_index = index;
evolve = evolution_modes[index];
toggle_mod = evolution_cells[index];
return 1;
}
int logic_free(void) {
- free(cells);
- cells = NULL;
-
- HEIGHT = -1;
- WIDTH = -1;
+ HASH_CLEAR(hh, hash);
addToCells = NULL;
evolve = NULL;
toggle_mod = -1;
+ free(save_cells);
+ save_cells_s = 0;
return 1;
}
int toggleAt(int i, int j) {
- for (int k = 0; k < cells_size; k++) {
- if (cells[k].row == i && cells[k].col == j) {
- cells[k].val = (cells[k].val + 1) % toggle_mod;
- if (cells[k].val == 0) {
- for (int t = k + 1; t < cells_size; t++) {
- cells[t - 1].val = cells[t].val;
- cells[t - 1].row = cells[t].row;
- cells[t - 1].col = cells[t].col;
- }
- cells_size--;
- return 0; // since the cell was deleted it's value is 0
- }
- return cells[k].val; // only return value if it hasn't been deleted
- }
+ Cell *c;
+
+ if (!(c = get(i, j))) {
+ insert(i, j, 1, 0);
+ return 1;
}
- cells[cells_size].val = 1;
- cells[cells_size].row = i;
- cells[cells_size].col = j;
- cells_size++;
- return 1;
+
+ int val = c->val = (c->val + 1) % toggle_mod;
+ if (!c->val)
+ deleter(c);
+ return val;
}
void deleteAt(int i, int j) {
- for (int k = 0; k < cells_size; k++) {
- if (cells[k].row == i && cells[k].col == j) {
- for (int t = k + 1; t < cells_size; t++) {
- cells[t - 1].val = cells[t].val;
- cells[t - 1].row = cells[t].row;
- cells[t - 1].col = cells[t].col;
- }
- cells_size--;
- return;
- }
- }
+ Cell *c;
+
+ if ((c = get(i, j)))
+ deleter(c);
+}
+
+void setAt(int i, int j, int val) {
+ Cell *c;
+
+ if ((c = get(i, j)) != NULL)
+ c->val = val;
+ else
+ insert(i, j, val, 0);
}
int getAt(int i, int j) {
- for (int k = 0; k < cells_size; k++)
- if (cells[k].row == i && cells[k].col == j)
- return cells[k].val;
- return 0;
+ Cell *c = get(i, j);
+ return ((c) ? c->val : 0);
}
-int getNext(int *row, int *col, int *value, int reset) {
- static int index = 0;
- if (reset) {
- index = 0;
- return 1;
- }
+void setPosition(int i, int j) {
+ pos_y = i;
+ pos_x = j;
+}
- if (index == cells_size)
- return 0;
+void saveCell(int i, int j) {
+ Cell *c;
+
+ if ((c = get(i, j))) {
+ if (save_cells_s == save_cells_sm) {
+ Cell **t;
+ save_cells_sm *= 2;
+ t = realloc(save_cells, save_cells_sm);
+ if (!t)
+ exit(1);
+ save_cells = t;
+ }
- *row = cells[index].row;
- *col = cells[index].col;
- *value = cells[index].val;
- index++;
- return 1;
+ save_cells[save_cells_s++] = c;
+ }
}
