From 1aceb70c5659677929bfbbd3f6480bacd8d75e35 Mon Sep 17 00:00:00 2001 From: davidovski Date: Fri, 21 Jul 2023 00:21:17 +0200 Subject: add kdtree --- src/kdtree.c | 85 +++++++++++++++++++++++++++++++ src/kdtree.h | 21 ++++++++ src/tiled.h | 2 +- src/tiledfile.c | 155 -------------------------------------------------------- src/tiledfile.h | 23 --------- src/tiledmap.c | 155 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/tiledmap.h | 23 +++++++++ 7 files changed, 285 insertions(+), 179 deletions(-) create mode 100644 src/kdtree.c create mode 100644 src/kdtree.h delete mode 100644 src/tiledfile.c delete mode 100644 src/tiledfile.h create mode 100644 src/tiledmap.c create mode 100644 src/tiledmap.h diff --git a/src/kdtree.c b/src/kdtree.c new file mode 100644 index 0000000..6e9323b --- /dev/null +++ b/src/kdtree.c @@ -0,0 +1,85 @@ +#include + +#include "kdtree.h" + +kdtree_t * kdtree_create(int x, int y, char * value) { + kdtree_t * tree = malloc(sizeof(kdtree_t)); + tree->x = x; + tree->y = y; + tree->value = value; + tree->left = NULL; + tree->right = NULL; + return tree; +} + +kdtree_t * kdtree_insert_rec(kdtree_t **root, int x, int y, char * value, int depth) { + if ((*root) == NULL) + return *root = kdtree_create(x, y, value); + + int e = x < (*root)->x; + if (depth % 2 == 1) e = y < (*root)->y; + + if (e) + return kdtree_insert_rec(&(*root)->left, x, y, value, depth+1); + return kdtree_insert_rec(&(*root)->right, x, y, value, depth+1); +} + +kdtree_t * kdtree_insert(kdtree_t ** root, int x, int y, char * value) { + return kdtree_insert_rec(root, x, y, value, 0); +} + +char * kdtree_search_rec(kdtree_t *root, int x, int y, int depth) { + if (root == NULL) + return NULL; + + if (root->x == x && root->y == y) + return root->value; + + unsigned int r, p; + if (depth % 2 == 0) { + r = root->x; + p = x; + } else { + r = root->y; + p = y; + } + + if (p < r) { + if (root->left == NULL) + return NULL; + + return kdtree_search_rec(root->left, x, y, depth+1); + } + + if (root->right == NULL) + return NULL; + + return kdtree_search_rec(root->right, x, y, depth+1); +} + +char * kdtree_search(kdtree_t *root, int x, int y) { + return kdtree_search_rec(root, x, y, 0); +} + +void kdtree_free(kdtree_t **root) { + if ((*root)->left != NULL) + kdtree_free(&(*root)->left); + + if ((*root)->right != NULL) + kdtree_free(&(*root)->right); + + free(*root); +} + +void kdtree_walk(kdtree_t *root, void (* consume)(kdtree_t*)) { + if (root == NULL) + return; + + if (root->left != NULL) + kdtree_walk(root->left, consume); + + consume(root); + + if (root->right != NULL) + kdtree_walk(root->right, consume); +} diff --git a/src/kdtree.h b/src/kdtree.h new file mode 100644 index 0000000..8969533 --- /dev/null +++ b/src/kdtree.h @@ -0,0 +1,21 @@ +typedef struct KDTree { + unsigned int x; + unsigned int y; + char *value; + + struct KDTree *left; + struct KDTree *right; +} kdtree_t; + +//! insert an element into a kdtree +kdtree_t * kdtree_insert(kdtree_t ** root, int x, int y, char * value); + +//! return a value from a kdtree, NULL if not present +char * kdtree_search(kdtree_t *root, int x, int y); + +//! free memory for a kdtree +void kdtree_free(kdtree_t **root); + +//! in order walk of nodes in kdtree +void kdtree_walk(kdtree_t *root, void (* consume)(kdtree_t*)); + diff --git a/src/tiled.h b/src/tiled.h index 735c3a9..9890a72 100644 --- a/src/tiled.h +++ b/src/tiled.h @@ -1,6 +1,6 @@ #include -#include "tiledfile.h" +#include "tiledmap.h" #define SCREEN_W 1280 #define SCREEN_H 720 diff --git a/src/tiledfile.c b/src/tiledfile.c deleted file mode 100644 index eaeb814..0000000 --- a/src/tiledfile.c +++ /dev/null @@ -1,155 +0,0 @@ -#include -#include -#include -#include - -#include "tiledfile.h" - -const int i = 1; -#define is_bigendian() ( (*(char*)&i) == 0 ) - -void textureFromPixels(Texture2D *texOut, Color *pixels, int width, int height) { - Image checkedIm = { - .data = pixels, - .width = width, - .height = height, - .format = PIXELFORMAT_UNCOMPRESSED_R8G8B8A8, - .mipmaps = 1 - }; - - *texOut = LoadTextureFromImage(checkedIm); -} - -//! read rgba image from file -void readrgba(Texture2D *loc, int width, int height, FILE *file) { - Color *pixels = malloc(width*height*4); - fread(pixels, (size_t) width*height*4, (size_t) 1, file); - textureFromPixels(loc, pixels, width, height); -} - - - -//! write a big endian bytes from file -int writeb(char * in, size_t noBytes, FILE * file) { - if (!is_bigendian()) { - int tmp; - // reverse byte order - for(int i = 0; i < noBytes/2; i++) { - tmp = in[i]; - in[i] = in[noBytes-i-1]; - in[noBytes-i-1] = tmp; - } - - } - - return fwrite(in, (size_t)1, (size_t) noBytes, file); -} - -//! read a big endian bytes from file -int readb(char * out, size_t noBytes, FILE * file) { - if (!fread(out, (size_t)1, (size_t) noBytes, file)) - return 1; - - if (is_bigendian()) - return 0; - - int tmp; - // reverse byte order - for(int i = 0; i < noBytes/2; i++) { - tmp = out[i]; - out[i] = out[noBytes-i-1]; - out[noBytes-i-1] = tmp; - } - - return 0; -} - -char getTiledMapTile(TiledMap tiledMap, int pos[2]) { - return tiledMap.tilelayout[pos[1]*tiledMap.width + pos[0]]; -} - -void setTiledMapTile(TiledMap tiledMap, int pos[2], char tile) { - tiledMap.tilelayout[pos[1]*tiledMap.width + pos[0]] = tile; -} - -//! load tilemap data from file -TiledMap loadTiledMap(char * filename) { - TiledMap tiledMap; - FILE * file; - - if (!(file = fopen(filename, "rb"))) { - fprintf(stderr, "Failed to load %s\n", filename); - return tiledMap; - } - - // skip header - fseek(file, 10, SEEK_CUR); - // 4 bytes for int width - readb((char *)&tiledMap.width, 4, file); - // 4 bytes for int height - readb((char *)&tiledMap.height, 4, file); - - size_t layoutSize = tiledMap.width*tiledMap.height; - tiledMap.tilelayout = malloc(layoutSize); - fread(tiledMap.tilelayout, layoutSize, 1, file); - - // read the pixel size of each tile - readb((char *)&tiledMap.tileSize, 4, file); - - // read the atlas size - readb((char *)&tiledMap.atlasSize[0], 4, file); - readb((char *)&tiledMap.atlasSize[1], 4, file); - - // read the atlas itself - size_t atlasSizeBytes = tiledMap.atlasSize[0]*tiledMap.tileSize*tiledMap.atlasSize[1]*tiledMap.tileSize*4; - tiledMap.atlasData = malloc(atlasSizeBytes); - fread(tiledMap.atlasData, atlasSizeBytes, (size_t) 1, file); - - tiledMap.tileCount = tiledMap.atlasSize[0]*tiledMap.atlasSize[1] + 1; - - fclose(file); - return tiledMap; -} - -TiledMap newTiledMap(Image atlas, int tileSize, int width, int height) { - TiledMap tiledMap; - tiledMap.width = width; - tiledMap.height = height; - tiledMap.tilelayout = malloc(width * height); - - tiledMap.tileSize = tileSize; - - tiledMap.atlasSize[0] = atlas.width / tileSize; - tiledMap.atlasSize[1] = atlas.height / tileSize; - - tiledMap.atlasData = LoadImageColors(atlas); - - return tiledMap; -} - -void saveTiledMap(char * filename, TiledMap tiledMap) { - FILE * file; - - if (!(file = fopen(filename, "wb"))) { - fprintf(stderr, "Failed to load %s\n", filename); - return; - } - size_t layoutSize = tiledMap.width*tiledMap.height; - size_t atlasSizeBytes = tiledMap.atlasSize[0]*tiledMap.tileSize*tiledMap.atlasSize[1]*tiledMap.tileSize*4; - - fwrite("TILEFILEv2", 10, 1, file); - - writeb((char *) &tiledMap.width, 4, file); - writeb((char *) &tiledMap.height, 4, file); - - fwrite(tiledMap.tilelayout, 1, layoutSize, file); - - writeb((char *) &tiledMap.tileSize, 4, file); - writeb((char *) &tiledMap.atlasSize[0], 4, file); - writeb((char *) &tiledMap.atlasSize[1], 4, file); - - fwrite(tiledMap.atlasData, 1, atlasSizeBytes, file); - - fclose(file); - fprintf(stderr, "Written tiledfiled to %s\n", filename); -} diff --git a/src/tiledfile.h b/src/tiledfile.h deleted file mode 100644 index fb9c789..0000000 --- a/src/tiledfile.h +++ /dev/null @@ -1,23 +0,0 @@ -#include - -typedef struct TiledMap { - int width; - int height; - char * tilelayout; - int tileSize; - int atlasSize[2]; - int tileCount; - Color * atlasData; -} TiledMap; - -void textureFromPixels(Texture2D *texOut, Color *pixels, int width, int height); - -void setTiledMapTile(TiledMap tiledMap, int pos[2], char tile); - -char getTiledMapTile(TiledMap tiledMap, int pos[2]); - -TiledMap loadTiledMap(char * filename); - -void saveTiledMap(char * filename, TiledMap tiledMap); - -TiledMap newTiledMap(Image atlas, int tileSize, int width, int height); diff --git a/src/tiledmap.c b/src/tiledmap.c new file mode 100644 index 0000000..69dcdaa --- /dev/null +++ b/src/tiledmap.c @@ -0,0 +1,155 @@ +#include +#include +#include +#include + +#include "tiledmap.h" + +const int i = 1; +#define is_bigendian() ( (*(char*)&i) == 0 ) + +void textureFromPixels(Texture2D *texOut, Color *pixels, int width, int height) { + Image checkedIm = { + .data = pixels, + .width = width, + .height = height, + .format = PIXELFORMAT_UNCOMPRESSED_R8G8B8A8, + .mipmaps = 1 + }; + + *texOut = LoadTextureFromImage(checkedIm); +} + +//! read rgba image from file +void readrgba(Texture2D *loc, int width, int height, FILE *file) { + Color *pixels = malloc(width*height*4); + fread(pixels, (size_t) width*height*4, (size_t) 1, file); + textureFromPixels(loc, pixels, width, height); +} + + + +//! write a big endian bytes from file +int writeb(char * in, size_t noBytes, FILE * file) { + if (!is_bigendian()) { + int tmp; + // reverse byte order + for(int i = 0; i < noBytes/2; i++) { + tmp = in[i]; + in[i] = in[noBytes-i-1]; + in[noBytes-i-1] = tmp; + } + + } + + return fwrite(in, (size_t)1, (size_t) noBytes, file); +} + +//! read a big endian bytes from file +int readb(char * out, size_t noBytes, FILE * file) { + if (!fread(out, (size_t)1, (size_t) noBytes, file)) + return 1; + + if (is_bigendian()) + return 0; + + int tmp; + // reverse byte order + for(int i = 0; i < noBytes/2; i++) { + tmp = out[i]; + out[i] = out[noBytes-i-1]; + out[noBytes-i-1] = tmp; + } + + return 0; +} + +char getTiledMapTile(TiledMap tiledMap, int pos[2]) { + return tiledMap.tilelayout[pos[1]*tiledMap.width + pos[0]]; +} + +void setTiledMapTile(TiledMap tiledMap, int pos[2], char tile) { + tiledMap.tilelayout[pos[1]*tiledMap.width + pos[0]] = tile; +} + +//! load tilemap data from file +TiledMap loadTiledMap(char * filename) { + TiledMap tiledMap; + FILE * file; + + if (!(file = fopen(filename, "rb"))) { + fprintf(stderr, "Failed to load %s\n", filename); + return tiledMap; + } + + // skip header + fseek(file, 10, SEEK_CUR); + // 4 bytes for int width + readb((char *)&tiledMap.width, 4, file); + // 4 bytes for int height + readb((char *)&tiledMap.height, 4, file); + + size_t layoutSize = tiledMap.width*tiledMap.height; + tiledMap.tilelayout = malloc(layoutSize); + fread(tiledMap.tilelayout, layoutSize, 1, file); + + // read the pixel size of each tile + readb((char *)&tiledMap.tileSize, 4, file); + + // read the atlas size + readb((char *)&tiledMap.atlasSize[0], 4, file); + readb((char *)&tiledMap.atlasSize[1], 4, file); + + // read the atlas itself + size_t atlasSizeBytes = tiledMap.atlasSize[0]*tiledMap.tileSize*tiledMap.atlasSize[1]*tiledMap.tileSize*4; + tiledMap.atlasData = malloc(atlasSizeBytes); + fread(tiledMap.atlasData, atlasSizeBytes, (size_t) 1, file); + + tiledMap.tileCount = tiledMap.atlasSize[0]*tiledMap.atlasSize[1] + 1; + + fclose(file); + return tiledMap; +} + +TiledMap newTiledMap(Image atlas, int tileSize, int width, int height) { + TiledMap tiledMap; + tiledMap.width = width; + tiledMap.height = height; + tiledMap.tilelayout = malloc(width * height); + + tiledMap.tileSize = tileSize; + + tiledMap.atlasSize[0] = atlas.width / tileSize; + tiledMap.atlasSize[1] = atlas.height / tileSize; + + tiledMap.atlasData = LoadImageColors(atlas); + + return tiledMap; +} + +void saveTiledMap(char * filename, TiledMap tiledMap) { + FILE * file; + + if (!(file = fopen(filename, "wb"))) { + fprintf(stderr, "Failed to load %s\n", filename); + return; + } + size_t layoutSize = tiledMap.width*tiledMap.height; + size_t atlasSizeBytes = tiledMap.atlasSize[0]*tiledMap.tileSize*tiledMap.atlasSize[1]*tiledMap.tileSize*4; + + fwrite("TILEFILEv2", 10, 1, file); + + writeb((char *) &tiledMap.width, 4, file); + writeb((char *) &tiledMap.height, 4, file); + + fwrite(tiledMap.tilelayout, 1, layoutSize, file); + + writeb((char *) &tiledMap.tileSize, 4, file); + writeb((char *) &tiledMap.atlasSize[0], 4, file); + writeb((char *) &tiledMap.atlasSize[1], 4, file); + + fwrite(tiledMap.atlasData, 1, atlasSizeBytes, file); + + fclose(file); + fprintf(stderr, "Written tiledfiled to %s\n", filename); +} diff --git a/src/tiledmap.h b/src/tiledmap.h new file mode 100644 index 0000000..fb9c789 --- /dev/null +++ b/src/tiledmap.h @@ -0,0 +1,23 @@ +#include + +typedef struct TiledMap { + int width; + int height; + char * tilelayout; + int tileSize; + int atlasSize[2]; + int tileCount; + Color * atlasData; +} TiledMap; + +void textureFromPixels(Texture2D *texOut, Color *pixels, int width, int height); + +void setTiledMapTile(TiledMap tiledMap, int pos[2], char tile); + +char getTiledMapTile(TiledMap tiledMap, int pos[2]); + +TiledMap loadTiledMap(char * filename); + +void saveTiledMap(char * filename, TiledMap tiledMap); + +TiledMap newTiledMap(Image atlas, int tileSize, int width, int height); -- cgit v1.2.1