From 779ed23839fcabf53b72267f29e2f86a5691270e Mon Sep 17 00:00:00 2001 From: nathan Date: Mon, 7 Jul 2025 12:13:15 -0600 Subject: Working on BVH --- src/Makefile | 2 +- src/game.c | 2 +- src/utils.h | 2 + src/world.c | 157 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---- src/world.h | 7 ++- 5 files changed, 158 insertions(+), 12 deletions(-) diff --git a/src/Makefile b/src/Makefile index 711cb4a..0a01fd7 100644 --- a/src/Makefile +++ b/src/Makefile @@ -5,7 +5,7 @@ TARGET = FindThings SOURCES = $(shell find -name "*.c") OBJECTS = $(SOURCES:.c=.o) -%.o: %.c +%.o: %.c %.h $(CC) -c $(CFLAGS) -o $@ $< $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $(TARGET) $(OBJECTS) $(LDFLAGS) diff --git a/src/game.c b/src/game.c index c97914b..f76a0ee 100644 --- a/src/game.c +++ b/src/game.c @@ -21,7 +21,7 @@ void initGame(Game* game) game->player.position = (Vector3){0.0, 30.0, 0.0}; // World. - game->world = createWorld(&game->assets); + game->world = createWorld(134235234); DisableCursor(); } diff --git a/src/utils.h b/src/utils.h index e4cefee..08a7420 100644 --- a/src/utils.h +++ b/src/utils.h @@ -1,8 +1,10 @@ #include #include #include +#include #include #include +#include #include #include diff --git a/src/world.c b/src/world.c index b444ff1..b46b7a4 100644 --- a/src/world.c +++ b/src/world.c @@ -1,13 +1,148 @@ #include "world.h" #include "game.h" -World createWorld(const Assets* assets) +float hashWorldPosition(Vector3 position, Vector3 size) +{ + return (position.z * size.y) + (position.y * size.x) + position.x; +} + +void sortEntitiesUID(WorldUID entities[WORLD_ENTITY_MAX], const World* world) +{ + // Lazy selection sort. + for (int outer = 0; outer < WORLD_ENTITY_MAX - 1; ++outer) + { + int minIndex = outer; + + for (int inner = outer + 1; inner < WORLD_ENTITY_MAX; ++inner) + { + float entityHash = hashWorldPosition( + world->entities[entities[inner]].position, world->size); + float minHash = hashWorldPosition( + world->entities[entities[minIndex]].position, world->size); + + if (entityHash < minHash) + { + minIndex = inner; + } + } + + WorldUID temp = entities[outer]; + entities[outer] = entities[minIndex]; + entities[minIndex] = temp; + } +} + +// Bottom up method because bottom up better. Just if politicians agreed ): +void buildWorldBVH(World* world) +{ + Entity* entities = world->entities; + bool grouped[WORLD_ENTITY_MAX]; + + // This is a mess thats not going to work. + for (int index = 0; index < WORLD_ENTITY_MAX; ++index) + { + grouped[index] = false; + } + + int nodeCount = 0; + + for (int nodeIndex = 0; nodeIndex < WORLD_ENTITY_MAX; ++nodeIndex) + { + if (grouped[nodeIndex]) + { + continue; + } + + BVHNode leaf; + leaf.branch1 = NULL; + leaf.branch2 = NULL; + leaf.entities[0] = nodeIndex; + grouped[nodeIndex] = true; + + int leafIndex = 0; + + for (int outer = 0; outer < WORLD_ENTITY_MAX; ++outer) + { + if (grouped[outer]) + { + continue; + } + + int closest = outer; + + float closestDistance = Vector3Distance( + entities[closest].position, + entities[nodeIndex].position); + + for (int inner = 0; inner < WORLD_ENTITY_MAX; ++inner) + { + if (grouped[inner]) + { + continue; + } + + float distance = Vector3Distance( + entities[inner].position, + entities[nodeIndex].position); + + if (distance < closestDistance) + { + closest = inner; + closestDistance = distance; + } + } + + leaf.entities[leafIndex] = closest; + grouped[closest] = true; + ++leafIndex; + + if (leafIndex >= BVH_MAX) + { + break; + } + } + + // Create bounding box. + leaf.box.min = entities[leaf.entities[0]].position; + leaf.box.max = entities[leaf.entities[0]].position; + + for (int index = 1; index < BVH_MAX; ++index) + { + leaf.box.min = Vector3Min(leaf.box.min, + entities[leaf.entities[index]].position); + leaf.box.max = Vector3Max(leaf.box.max, + entities[leaf.entities[index]].position); + } + + world->bvhTest[nodeCount] = leaf; + ++nodeCount; + + if (nodeCount >= 250) + { + break; + } + } + + // test + for (int index = 0; index < WORLD_ENTITY_MAX; ++index) + { + if (!grouped[index]) + { + printf("%d\n", index); + } + } +} + +World createWorld(int seed) { World world; - world.size = (Vector3){1000.0, 100.0, 1000.0}; + world.size = WORLD_SIZE; // Heightmap image. - Image image = GenImagePerlinNoise(100, 100, 0, 0, 5.0); + int offsetX = FT_RANDOM16(seed); + int offsetY = FT_RANDOM16(seed); + Image image = GenImagePerlinNoise(WORLD_IMAGE_WIDTH, WORLD_IMAGE_HEIGHT, + offsetX, offsetY, WORLD_IMAGE_SCALE); // Heightmap. Mesh mesh = GenMeshHeightmap(image, world.size); @@ -18,23 +153,21 @@ World createWorld(const Assets* assets) UnloadImage(image); - int seed = 57; - // Entities. for (int index = 0; index < WORLD_ENTITY_MAX; ++index) { FT_RANDOM16(seed); Entity entity = createEntity(seed % ENTITY_COUNT, Vector3Zero()); - FT_RANDOM16(seed); - entity.position.x = seed % (int)world.size.x; - FT_RANDOM16(seed); - entity.position.z = seed % (int)world.size.z; + entity.position.x = FT_RANDOM16(seed) % (int)world.size.x; + entity.position.z = FT_RANDOM16(seed) % (int)world.size.z; entity.position.y = getWorldHeightAtLocation(world, entity.position.x, entity.position.z) + 1.0; world.entities[index] = entity; } + buildWorldBVH(&world); + return world; } @@ -46,6 +179,12 @@ void updateWorld(World* world, Game* game) { updateEntity(&world->entities[index], game); } + + for (int index = 0; index < 250; ++index) + { + Color colors[] = {RED, GREEN, BLUE, ORANGE, YELLOW, PINK}; + DrawBoundingBox(world->bvhTest[index].box, colors[index % 6]); + } } void freeWorld(World world) diff --git a/src/world.h b/src/world.h index e06d628..d5c1a46 100644 --- a/src/world.h +++ b/src/world.h @@ -11,6 +11,10 @@ #define BVH_MAX 4 #define WORLD_ENTITY_MAX 1000 +#define WORLD_SIZE (Vector3){1000.0, 100.0, 1000.0} +#define WORLD_IMAGE_WIDTH 100 +#define WORLD_IMAGE_HEIGHT 100 +#define WORLD_IMAGE_SCALE 5.0 // UID for anything in the world.x typedef int16_t WorldUID; @@ -28,9 +32,10 @@ typedef struct { Model heightmap; Entity entities[WORLD_ENTITY_MAX]; BVHNode bvh; + BVHNode bvhTest[250]; } World; -World createWorld(const Assets* assets); +World createWorld(int seed); void updateWorld(World* world, Game* game); void freeWorld(World world); // Dam, I wanta live in a free world ): -- cgit v1.2.3