Working on BVH

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 <stdio.h>
 #include <stdlib.h>
 #include <stdint.h>
+#include <string.h>
 #include <math.h>
 #include <float.h>
+#include <stdbool.h>
 
 #include <raylib.h>
 #include <raymath.h>
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 ):