Working on BVH

1 files changed, 148 insertions, 9 deletions

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)