Decentish now

1 files changed, 117 insertions, 82 deletions

diff --git a/src/world.c b/src/world.c
index b46b7a4..13a1c7e 100644
--- a/src/world.c
+++ b/src/world.c
@@ -1,42 +1,91 @@
 #include "world.h"
 #include "game.h"
 
-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;
-  }
-}
+/* int64_t hashWorldPosition(Vector3 position, Vector3 size) */
+/* { */
+/*   return (((int64_t)position.x) << 32) | (((int64_t)position.z) << 16) */
+/*     | ((int64_t)position.y); */
+/* } */
+
+/* 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) */
+/*     { */
+/*       int64_t entityHash = hashWorldPosition( */
+/*         world->entities[entities[inner]].position, world->size); */
+/*       int64_t 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; */
+/*   } */
+
+/*   for (int index = 0; index < WORLD_ENTITY_MAX; ++index) */
+/*   { */
+/*     PRINT_VECTOR3(world->entities[entities[index]].position); */
+/*   } */
+/* } */
+
+/* void buildWorldBVH(World* world) */
+/* { */
+/*   WorldUID sorted[WORLD_ENTITY_MAX]; */
+
+/*   for (int index = 0; index < WORLD_ENTITY_MAX; ++index) */
+/*   { */
+/*     sorted[index] = index; */
+/*   } */
+
+/*   sortEntitiesUID(sorted, world); */
+
+/*   for (int index = 0; index < WORLD_ENTITY_MAX; index += BVH_MAX) */
+/*   { */
+/*     BVHNode leaf; */
+/*     leaf.branch1 = NULL; */
+/*     leaf.branch2 = NULL; */
+
+/*     for (int leafIndex = 0; leafIndex < BVH_MAX; ++leafIndex) */
+/*     { */
+/*       leaf.entities[leafIndex] = sorted[index + leafIndex]; */
+/*     } */
+
+/*     // Create bounding box. */
+/*     leaf.box.min = world->entities[leaf.entities[0]].position; */
+/*     leaf.box.max = world->entities[leaf.entities[0]].position; */
+
+/*     for (int index = 1; index < BVH_MAX; ++index) */
+/*     { */
+/*       leaf.box.min = Vector3Min( */
+/*         leaf.box.min, */
+/*         world->entities[leaf.entities[index]].position); */
+/*       leaf.box.max = Vector3Max( */
+/*         leaf.box.max, */
+/*         world->entities[leaf.entities[index]].position); */
+/*     } */
+
+/*     world->bvhTest[index / 4] = leaf; */
+/*   } */
+/* } */
 
 // Bottom up method because bottom up better. Just if politicians agreed ):
+// z curve broky, last metho was decent but was first come first serve and
+// would leave leafs toward the end with shitty options and end up being big.
 void buildWorldBVH(World* world)
 {
   Entity* entities = world->entities;
   bool grouped[WORLD_ENTITY_MAX];
+  BVHNode leafs[250];
 
   // This is a mess thats not going to work.
   for (int index = 0; index < WORLD_ENTITY_MAX; ++index)
@@ -44,82 +93,68 @@ void buildWorldBVH(World* world)
     grouped[index] = false;
   }
 
-  int nodeCount = 0;
-  
-  for (int nodeIndex = 0; nodeIndex < WORLD_ENTITY_MAX; ++nodeIndex)
+  for (int leafIndex = 0; leafIndex < BVH_MAX; ++leafIndex)
   {
-    if (grouped[nodeIndex])
+    for (int nodeIndex = 0; nodeIndex < 250; ++nodeIndex)
     {
-      continue;
-    }
-    
-    BVHNode leaf;
-    leaf.branch1 = NULL;
-    leaf.branch2 = NULL;
-    leaf.entities[0] = nodeIndex;
-    grouped[nodeIndex] = true;
-
-    int leafIndex = 0;
+      BVHNode* leaf = &leafs[nodeIndex];
 
-    for (int outer = 0; outer < WORLD_ENTITY_MAX; ++outer)
-    {
-      if (grouped[outer])
+      // First entity.
+      if (leafIndex == 0)
       {
+        leaf->entities[0] = nodeIndex * 4;
+        grouped[nodeIndex * 4] = true;
         continue;
       }
-      
-      int closest = outer;
-      
-      float closestDistance = Vector3Distance(
-        entities[closest].position,
-        entities[nodeIndex].position);
-      
-      for (int inner = 0; inner < WORLD_ENTITY_MAX; ++inner)
+
+      // Find closest to entity one.
+      // TODO: Average out the entities.
+      int closest = -1;
+      float closestDistance = world->size.x * world->size.z * 2.0;
+
+      for (int index = 0; index < WORLD_ENTITY_MAX; ++index)
       {
-        if (grouped[inner])
+        if (grouped[index])
         {
           continue;
         }
         
         float distance = Vector3Distance(
-          entities[inner].position,
-          entities[nodeIndex].position);
+          entities[leaf->entities[0]].position,
+          entities[index].position);
 
         if (distance < closestDistance)
         {
-          closest = inner;
           closestDistance = distance;
+          closest = index;
         }
       }
 
-      leaf.entities[leafIndex] = closest;
-      grouped[closest] = true;
-      ++leafIndex;
-
-      if (leafIndex >= BVH_MAX)
+      if (closest != -1)
       {
-        break;
+        leaf->entities[leafIndex] = closest;
+        grouped[closest] = true;
       }
-    }
-
-    // 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);
-    }
+      // Last entity
+      if (leafIndex == BVH_MAX - 1)
+      {
+        // Create bounding box. */
+        leaf->box.min = world->entities[leaf->entities[0]].position;
+        leaf->box.max = world->entities[leaf->entities[0]].position;
 
-    world->bvhTest[nodeCount] = leaf;
-    ++nodeCount;
+        for (int index = 1; index < BVH_MAX; ++index)
+        {
+          leaf->box.min = Vector3Min(
+            leaf->box.min,
+            world->entities[leaf->entities[index]].position);
+          leaf->box.max = Vector3Max(
+            leaf->box.max,
+            world->entities[leaf->entities[index]].position);
+        }
 
-    if (nodeCount >= 250)
-    {
-      break;
+        world->bvhTest[nodeIndex] = leafs[nodeIndex];
+      }
     }
   }