gol

Implementation of Conway's Game of Life writen in C
git clone git://git.dimitrijedobrota.com/gol.git
Log | Files | Refs | README

commit f10581d443ba92b50564adbe45ad54eb2cdaba8d
parent 875e9d53a57e3a6e89fa6e6239220986e25281d3
Author: Mateja Marsenic <matejamarsenic@gmail.com>
Date:   Mon, 30 May 2022 19:37:27 +0200

Rework of whole logic using Sparse Matrix Representation

Diffstat:
Minclude/logic.h | 20++++++++++----------
Ainclude/logic_old.h | 16++++++++++++++++
Msrc/logic.c | 524++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------------
Asrc/logic_old.c | 249+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 623 insertions(+), 186 deletions(-)

diff --git a/include/logic.h b/include/logic.h @@ -1,16 +1,16 @@ #ifndef LOGIC_H #define LOGIC_H -#define cell unsigned char +extern char *evolution_names[]; +extern int evolution_cells[]; +extern int evolution_size; -extern cell **mat; -extern char *evolution_names[]; -extern int evolution_cells[]; -extern int evolution_size; - -int logic_init(int w, int h); -int evolution_init(int index); -void do_evolution(int steps); -int logic_free(void); +int logic_init(int w, int h, int isWrapping); +int evolution_init(int index); +int do_evolution(int steps); +int logic_free(void); +void toggleAt(int i, int j) +void deleteAt(int i, int j); +int getNext(int *row, int *col, int *value, int reset); #endif diff --git a/include/logic_old.h b/include/logic_old.h @@ -0,0 +1,16 @@ +// #ifndef LOGIC_OLD_H +// #define LOGIC_OLD_H + +// #define cell unsigned char + +// extern cell **mat; +// extern char *evolution_names[]; +// extern int evolution_cells[]; +// extern int evolution_size; + +// int logic_init(int w, int h); +// int evolution_init(int index); +// void do_evolution(int steps); +// int logic_free(void); + +// #endif diff --git a/src/logic.c b/src/logic.c @@ -4,246 +4,417 @@ #include "logic.h" #include "utils.h" -cell **mat; -char *evolution_names[] = {"Normal", "CoExsistance", "Predator", "Virus", - "Unknown"}; -int evolution_cells[] = {2, 3, 3, 3, 3}; -int evolution_size = 5; +#define SIZE_TO_EXPAND 10 -static void (*evolve)(void); -static int height, width; -static int mod; +typedef struct Cell { + unsigned char val; + int row; + int col; +} Cell; -void addToECells(int a, int b) { - mod = (mat[a][b] & 3); - mod <<= mod << 1; - for (int i = MAX(a - 1, 0); i <= MIN(a + 1, height); i++) - for (int j = MAX(b - 1, 0); j <= MIN(b + 1, width + 1); j++) - if (i != a || j != b) - mat[i][j] += mod; -} +// GLOBALS +Cell *cells; +Cell *temp_cells; -void addToCells(int i, int j) { - mod = (mat[i][j] & 3); - mod <<= mod << 1; - for (int k = i - 1; k <= i + 1; k++) - for (int l = j - 1; l <= j + 1; l++) - if (k != i || l != j) - mat[k][l] += mod; -} +int WIDTH, HEIGHT; +int cells_size; +int temp_size; +int counter; -void doAdditions(void) { - for (int j = 1; j <= width; j++) { - mat[0][j] = mat[height][j]; - mat[height + 1][j] = mat[1][j]; - addToECells(0, j); - addToECells(height + 1, j); +char *evolution_names[] = {"Normal", "CoExsistance", "Predator", "Virus", + "Unknown"}; +int evolution_cells[] = {2, 3, 3, 3, 3}; +int evolution_size = 5; +static void (*evolve)(void); +static void (*addToCells)(int i, int j, int value); + +void addToCellsNormal(int i, int j, int value) { + int mod = 0; + switch (value) { + case 1: + mod = 4; + break; + case 2: + 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; + } - for (int i = 1; i <= height; i++) { - mat[i][0] = mat[i][width]; - mat[i][width + 1] = mat[i][1]; - addToECells(i, 0); - addToECells(i, width + 1); + if (k == i && l == j) { + temp_cells[temp_size].val = value; + temp_cells[temp_size].row = k; + temp_cells[temp_size].col = l; + temp_size++; + continue; + } + temp_cells[temp_size].val = mod; + temp_cells[temp_size].row = k; + temp_cells[temp_size].col = l; + temp_size++; + Kontinue: + continue; + } } +} - mat[0][0] = mat[height][width]; - mat[0][width + 1] = mat[height][1]; - mat[height + 1][0] = mat[1][width]; - mat[height + 1][width + 1] = mat[1][1]; +void addToCellsWrap(int i, int j, int value) { + int mod = 0; + switch (value) { + case 1: + mod = 4; + break; + case 2: + mod = 32; + break; + } + + for (int k = (i - 1 + HEIGHT) % HEIGHT; k <= (i + 1 + HEIGHT) % HEIGHT; k++) { + for (int l = (j - 1 + WIDTH) % WIDTH; l <= (j + 1 + WIDTH) % WIDTH; 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; + } - addToECells(0, 0); - addToECells(0, width + 1); - addToECells(height + 1, 0); - addToECells(height + 1, width + 1); + if (k == i && l == j) { + temp_cells[temp_size].val = value; + temp_cells[temp_size].row = k; + temp_cells[temp_size].col = l; + temp_size++; + continue; + } + temp_cells[temp_size].val = mod; + temp_cells[temp_size].row = k; + temp_cells[temp_size].col = l; + temp_size++; + Kontinue: + continue; + } + } +} - /* Normal AddToCells */ - for (int i = 1; i <= height; i++) - for (int j = 1; j <= width; j++) - addToCells(i, j); +void doAdditions(void) { + for (int cellIndex = 0; cellIndex < cells_size; cellIndex++) { + addToCells(cells[cellIndex].row, cells[cellIndex].col, + cells[cellIndex].val); + } } +/* Evolutions */ void evolveNormal(void) { doAdditions(); - /* Rules */ - for (int i = 1; i <= height; i++) - for (int j = 1; j <= width; j++) - switch (mat[i][j]) { - case 9: - case 12: - case 13: - mat[i][j] = 1; - break; - default: - mat[i][j] = 0; - } + counter = 0; + for (int i = 0; i < temp_size; i++) { + switch (temp_cells[i].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++; + break; + } + } + cells_size = counter; } void evolveCoExist(void) { - int s1, s2; doAdditions(); - for (int i = 1; i <= height; i++) { - for (int j = 1; j <= width; j++) { - s2 = mat[i][j] >> 5; - s1 = (mat[i][j] & 31) >> 2; - mod = mat[i][j] & 3; - if (mod == 0) { - if ((s1 + s2) == 3) { - if (mat[i][j] >= 64) - mat[i][j] = 2; - else - mat[i][j] = 1; - continue; - } - } - if ((s1 + s2) < 2 || (s1 + s2) > 3) { - mat[i][j] = 0; + 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; + if (mod == 0) { + if ((s1 + s2) == 3) { + if (temp_cells[i].val >= 64) + cells[counter].val = 2; + else + cells[counter].val = 1; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; continue; } - mat[i][j] = mod; } + if ((s1 + s2) < 2 || (s1 + s2) > 3) { + continue; + } + cells[counter].val = mod; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; } + cells_size = counter; } void evolvePredator(void) { - int s1, s2; doAdditions(); - for (int i = 1; i <= height; i++) { - for (int j = 1; j <= width; j++) { - s2 = mat[i][j] >> 5; - s1 = (mat[i][j] & 31) >> 2; - mod = mat[i][j] & 3; - if ((s1 + s2) < 2 || (s1 + s2) > 3) { - mat[i][j] = 0; + 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; + 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; + else + cells[counter].val = 1; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; continue; } - switch (mod) { - case 0: - if ((s1 + s2) == 3) { - if (mat[i][j] >= 64) - mat[i][j] = 2; - else - mat[i][j] = 1; - continue; - } - break; - case 1: - if (s2 > 0) { - mat[i][j] = 0; - continue; - } - break; + break; + case 1: + if (s2 > 0) { + continue; } - mat[i][j] = mod; + break; } + cells[counter].val = mod; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; } + cells_size = counter; } void evolveVirus(void) { - int s1, s2; doAdditions(); - for (int i = 1; i <= height; i++) { - for (int j = 1; j <= width; j++) { - s2 = mat[i][j] >> 5; - s1 = (mat[i][j] & 31) >> 2; - mod = mat[i][j] & 3; - if ((s1 + s2) < 2 || (s1 + s2) > 3) { - mat[i][j] = 0; + 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; + 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; + else + cells[counter].val = 1; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; continue; } - switch (mod) { - case 0: - if ((s1 + s2) == 3) { - if (mat[i][j] >= 64) - mat[i][j] = 2; - else - mat[i][j] = 1; - continue; - } - break; - case 1: - if (s2 > 0) { - mat[i][j] = 2; - continue; - } - break; + 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++; + continue; } - mat[i][j] = mod; + break; } + cells[counter].val = mod; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; } + cells_size = counter; } void evolveUnknown(void) { // Assumption 3 ones and 3 twos result in 50/50 // chanse of 0 becoming one of them: - int s1, s2; doAdditions(); - for (int i = 1; i <= height; i++) { - for (int j = 1; j <= width; j++) { - s2 = mat[i][j] >> 5; - s1 = (mat[i][j] & 31) >> 2; - mod = mat[i][j] & 3; - switch (mod) { - case 0: - if (s1 == 3 && s2 == 3) { - mat[i][j] = rand() % 2 + 1; - continue; - } - if (s1 == 3) { - mat[i][j] = 1; - continue; - } - if (s2 == 3) { - mat[i][j] = 2; - continue; - } - break; - case 1: - if (s1 < 2 || s1 > 3) { - mat[i][j] = 0; - continue; - } - break; - case 2: - if (s2 < 2 || s2 > 3) { - mat[i][j] = 0; - continue; - } - break; + 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; + 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++; + continue; } - - mat[i][j] = mod; + if (s1 == 3) { + cells[counter].val = 1; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; + continue; + } + if (s2 == 3) { + cells[counter].val = 2; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; + continue; + } + break; + case 1: + if (s1 < 2 || s1 > 3) { + continue; + } + break; + case 2: + if (s2 < 2 || s2 > 3) { + continue; + } + break; } + cells[counter].val = mod; + cells[counter].row = temp_cells[i].row; + cells[counter].col = temp_cells[i].col; + counter++; } + cells_size = counter; } -void do_evolution(int steps) { +/* Initializing functions */ +static void (*evolution_modes[])() = { + evolveNormal, evolveCoExist, evolvePredator, evolveVirus, evolveUnknown}; +static void (*addition_modes[])(int i, int j, int value) = {addToCellsNormal, + addToCellsWrap}; + +int do_evolution(int steps) { + int times_resized = 0; + counter = 0; while (steps--) { + int temp_alloc = 9 * cells_size; + temp_size = 0; + temp_cells = calloc(temp_alloc, sizeof(*temp_cells)); + if (!counter) { + if (shouldExpand()) { + expand_matrix(SIZE_TO_EXPAND); + times_resized++; + counter = SIZE_TO_EXPAND; + } else { + counter = 1; + } + } evolve(); + free(temp_cells); + counter--; } + counter = 0; + return times_resized * SIZE_TO_EXPAND; } -int logic_init(int w, int h) { - width = w; - height = h; - - mat = malloc((h + 2) * sizeof(cell *)); - for (int i = 0; i <= h + 1; i++) - mat[i] = calloc((w + 2), sizeof(cell)); +int logic_init(int w, int h, int isWrapping) { + WIDTH = w; + HEIGHT = h; + addToCells = addition_modes[0]; + if (isWrapping) { + addToCells = addition_modes[1]; + } + cells = malloc(WIDTH * HEIGHT * sizeof(*cells)); return 1; } -static void (*evolution_modes[])() = { - evolveNormal, evolveCoExist, evolvePredator, evolveVirus, evolveUnknown}; - int evolution_init(int index) { evolve = evolution_modes[index]; return 1; } +int shouldExpand(void) { + for (int i = 0; i < cells_size; i++) { + if (cells[i].row == 0 || cells[i].row == HEIGHT - 1 || cells[i].col == 0 || + cells[i].col == WIDTH - 1) { + return 1; + } + } + return 0; +} + +void expand_matrix(int size) { + WIDTH += 2 * size; + HEIGHT += 2 * size; + cells = realloc(cells, WIDTH * HEIGHT * sizeof(*cells)); + for (int cellIndex = 0; cellIndex < cells_size; cellIndex++) { + cells[cellIndex].row += size; + cells[cellIndex].col += size; + } +} + int logic_free(void) { - for (int i = 0; i <= height + 1; i++) - free(mat[i]); - free(mat); + free(cells); return 1; } + +void 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) % 3; + 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; + } + } + cells[cells_size].val = 1; + cells[cells_size].row = i; + cells[cells_size].col = j; + cells_size++; +} + +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; + } + } +} + +int getNext(int *row, int *col, int *value, int reset) { + static int index = 0; + if (reset) { + index = 0; + return 1; + } + + if (index == cells_size) + return 0; + + *row = cells[index].row; + *col = cells[index].col; + *value = cells[index].val; + index++; +} +\ No newline at end of file diff --git a/src/logic_old.c b/src/logic_old.c @@ -0,0 +1,249 @@ +// #include <stdio.h> +// #include <stdlib.h> + +// #include "logic_old.h" +// #include "utils.h" + +// cell **mat; +// char *evolution_names[] = {"Normal", "CoExsistance", "Predator", "Virus", +// "Unknown"}; +// int evolution_cells[] = {2, 3, 3, 3, 3}; +// int evolution_size = 5; + +// static void (*evolve)(void); +// static int height, width; +// static int mod; + +// void addToECells(int a, int b) { +// mod = (mat[a][b] & 3); +// mod <<= mod << 1; +// for (int i = MAX(a - 1, 0); i <= MIN(a + 1, height); i++) +// for (int j = MAX(b - 1, 0); j <= MIN(b + 1, width + 1); j++) +// if (i != a || j != b) +// mat[i][j] += mod; +// } + +// void addToCells(int i, int j) { +// mod = (mat[i][j] & 3); +// mod <<= mod << 1; +// for (int k = i - 1; k <= i + 1; k++) +// for (int l = j - 1; l <= j + 1; l++) +// if (k != i || l != j) +// mat[k][l] += mod; +// } + +// void doAdditions(void) { +// for (int j = 1; j <= width; j++) { +// mat[0][j] = mat[height][j]; +// mat[height + 1][j] = mat[1][j]; +// addToECells(0, j); +// addToECells(height + 1, j); +// } + +// for (int i = 1; i <= height; i++) { +// mat[i][0] = mat[i][width]; +// mat[i][width + 1] = mat[i][1]; +// addToECells(i, 0); +// addToECells(i, width + 1); +// } + +// mat[0][0] = mat[height][width]; +// mat[0][width + 1] = mat[height][1]; +// mat[height + 1][0] = mat[1][width]; +// mat[height + 1][width + 1] = mat[1][1]; + +// addToECells(0, 0); +// addToECells(0, width + 1); +// addToECells(height + 1, 0); +// addToECells(height + 1, width + 1); + +// /* Normal AddToCells */ +// for (int i = 1; i <= height; i++) +// for (int j = 1; j <= width; j++) +// addToCells(i, j); +// } + +// void evolveNormal(void) { +// doAdditions(); +// /* Rules */ +// for (int i = 1; i <= height; i++) +// for (int j = 1; j <= width; j++) +// switch (mat[i][j]) { +// case 9: +// case 12: +// case 13: +// mat[i][j] = 1; +// break; +// default: +// mat[i][j] = 0; +// } +// } + +// void evolveCoExist(void) { +// int s1, s2; +// doAdditions(); +// for (int i = 1; i <= height; i++) { +// for (int j = 1; j <= width; j++) { +// s2 = mat[i][j] >> 5; +// s1 = (mat[i][j] & 31) >> 2; +// mod = mat[i][j] & 3; +// if (mod == 0) { +// if ((s1 + s2) == 3) { +// if (mat[i][j] >= 64) +// mat[i][j] = 2; +// else +// mat[i][j] = 1; +// continue; +// } +// } +// if ((s1 + s2) < 2 || (s1 + s2) > 3) { +// mat[i][j] = 0; +// continue; +// } +// mat[i][j] = mod; +// } +// } +// } + +// void evolvePredator(void) { +// int s1, s2; +// doAdditions(); +// for (int i = 1; i <= height; i++) { +// for (int j = 1; j <= width; j++) { +// s2 = mat[i][j] >> 5; +// s1 = (mat[i][j] & 31) >> 2; +// mod = mat[i][j] & 3; +// if ((s1 + s2) < 2 || (s1 + s2) > 3) { +// mat[i][j] = 0; +// continue; +// } +// switch (mod) { +// case 0: +// if ((s1 + s2) == 3) { +// if (mat[i][j] >= 64) +// mat[i][j] = 2; +// else +// mat[i][j] = 1; +// continue; +// } +// break; +// case 1: +// if (s2 > 0) { +// mat[i][j] = 0; +// continue; +// } +// break; +// } +// mat[i][j] = mod; +// } +// } +// } + +// void evolveVirus(void) { +// int s1, s2; +// doAdditions(); +// for (int i = 1; i <= height; i++) { +// for (int j = 1; j <= width; j++) { +// s2 = mat[i][j] >> 5; +// s1 = (mat[i][j] & 31) >> 2; +// mod = mat[i][j] & 3; +// if ((s1 + s2) < 2 || (s1 + s2) > 3) { +// mat[i][j] = 0; +// continue; +// } +// switch (mod) { +// case 0: +// if ((s1 + s2) == 3) { +// if (mat[i][j] >= 64) +// mat[i][j] = 2; +// else +// mat[i][j] = 1; +// continue; +// } +// break; +// case 1: +// if (s2 > 0) { +// mat[i][j] = 2; +// continue; +// } +// break; +// } +// mat[i][j] = mod; +// } +// } +// } + +// void evolveUnknown(void) { // Assumption 3 ones and 3 twos result in 50/50 +// // chanse of 0 becoming one of them: +// int s1, s2; +// doAdditions(); +// for (int i = 1; i <= height; i++) { +// for (int j = 1; j <= width; j++) { +// s2 = mat[i][j] >> 5; +// s1 = (mat[i][j] & 31) >> 2; +// mod = mat[i][j] & 3; +// switch (mod) { +// case 0: +// if (s1 == 3 && s2 == 3) { +// mat[i][j] = rand() % 2 + 1; +// continue; +// } +// if (s1 == 3) { +// mat[i][j] = 1; +// continue; +// } +// if (s2 == 3) { +// mat[i][j] = 2; +// continue; +// } +// break; +// case 1: +// if (s1 < 2 || s1 > 3) { +// mat[i][j] = 0; +// continue; +// } +// break; +// case 2: +// if (s2 < 2 || s2 > 3) { +// mat[i][j] = 0; +// continue; +// } +// break; +// } + +// mat[i][j] = mod; +// } +// } +// } + +// void do_evolution(int steps) { +// while (steps--) { +// evolve(); +// } +// } + +// int logic_init(int w, int h) { +// width = w; +// height = h; + +// mat = malloc((h + 2) * sizeof(cell *)); +// for (int i = 0; i <= h + 1; i++) +// mat[i] = calloc((w + 2), sizeof(cell)); + +// return 1; +// } + +// static void (*evolution_modes[])() = { +// evolveNormal, evolveCoExist, evolvePredator, evolveVirus, evolveUnknown}; + +// int evolution_init(int index) { +// evolve = evolution_modes[index]; +// return 1; +// } + +// int logic_free(void) { +// for (int i = 0; i <= height + 1; i++) +// free(mat[i]); +// free(mat); +// return 1; +// }