Home /Modules/spatial/SLSpatialHash.sleela

SLSpatialHash.sleela

lib/spatial/SLSpatialHash.sleela · 210 line(s) · sleela

<< lib/spatial/SLSpatialHash.sleela
   SLeeLa Standard Library Definition.
   Definition: A sparse 3D spatial hash grid. Continuous points are quantized
   to integer cells of a fixed cellSize, and each occupied cell maps to a String
   payload (an id or label). Buckets are a fixed number of parallel native
   arrays keyed by a mixed hash of the cell coordinates, so insert and point
   lookup are near O(1) and a "what is near P" scan only visits the 27 cells of
   the 3x3x3 neighbourhood around P rather than the whole volume. Suited to
   sparse worlds, point clouds, and broad-phase collision. Negative coordinates
   are handled with floor division and a non-negative bucket index. >>
#sleela 2.5
material;
< Unified SLeeLa standard-library front-end object. >
< Family: spatial. Native VM/OS work crosses an explicit bridge. >
class SLSpatialHash {
  << ---- Descriptive metadata (version 1.11 nested-friendly accessors) ----
     Eleven catalogued attributes with getter/setter pairs, so a GUI, loader,
     or catalog can read and (where appropriate) override this record.
     Values are faithful to the subject real origin where publicly known. >>
  String metaVersion = "1.0.0";
  int metaId = 1602;
  String metaAuthor = "Max Rupplin vs. Dr. Mrs. Elisabeth Harkins";
  String metaDate = "2026-11-04";
  String metaCopyright = "SLeeLa project";
  String metaTrademark = "none";
  String metaCorporation = "none";
  < metaOrigin: National | <nation> | International | Galactic >
  String metaOrigin = "International";
  String metaBirthDate = "2026-11-04";
  < metaScienceRating: maturity/robustness on a 1..10 scale >
  int metaScienceRating = 8;
  < metaNationalSchedule: a real, citable instrument or "none" >
  String metaNationalSchedule = "none";

  String getMetaVersion() { return metaVersion; }
  void setMetaVersion(String v) { metaVersion = v; }
  int getMetaId() { return metaId; }
  void setMetaId(int v) { metaId = v; }
  String getAuthor() { return metaAuthor; }
  void setAuthor(String v) { metaAuthor = v; }
  String getDate() { return metaDate; }
  void setDate(String v) { metaDate = v; }
  String getCopyright() { return metaCopyright; }
  void setCopyright(String v) { metaCopyright = v; }
  String getTrademark() { return metaTrademark; }
  void setTrademark(String v) { metaTrademark = v; }
  String getCorporation() { return metaCorporation; }
  void setCorporation(String v) { metaCorporation = v; }
  String getOrigin() { return metaOrigin; }
  void setOrigin(String v) { metaOrigin = v; }
  String getBirthDate() { return metaBirthDate; }
  void setBirthDate(String v) { metaBirthDate = v; }
  int getScienceRating() { return metaScienceRating; }
  void setScienceRating(int v) { metaScienceRating = v; }
  String getNationalSchedule() { return metaNationalSchedule; }
  void setNationalSchedule(String v) { metaNationalSchedule = v; }

  << Flat parallel storage. For entry i: keyX/keyY/keyZ[i] is the integer cell,
     payload[i] is its label, and bucketHead/bucketNext form a singly linked
     chain per hash bucket so a lookup only walks entries that share a bucket.
     A cell holds at most one entry (insert overwrites the payload). >>
  int cellSize = 1;
  int buckets = 0;
  int[] bucketHead = new int[0];
  int[] keyX = new int[0];
  int[] keyY = new int[0];
  int[] keyZ = new int[0];
  int[] bucketNext = new int[0];
  String[] payload = new String[0];
  int size = 0;

  << Configure the grid: quantization cellSize (clamped to a minimum of 1) and
     the number of hash buckets (clamped to a minimum of 1). Clears all entries. >>
  void configure(int cell, int bucketCount) {
    cellSize = cell;
    if (cellSize < 1) { cellSize = 1; }
    buckets = bucketCount;
    if (buckets < 1) { buckets = 1; }
    bucketHead = new int[buckets];
    int i = 0;
    while (i < buckets) {
      arraySet(bucketHead, i, -1);
      i = i + 1;
    }
    keyX = new int[0];
    keyY = new int[0];
    keyZ = new int[0];
    bucketNext = new int[0];
    payload = new String[0];
    size = 0;
  }

  int getCellSize() { return cellSize; }
  int getBucketCount() { return buckets; }
  int length() { return size; }
  boolean empty() { return size == 0; }

  << Floor division of v by cellSize for a correct cell index with negative
     coordinates: floor(v / cellSize). Integer division truncates toward zero,
     so a negative remainder is corrected by stepping one cell down. >>
  int cellOf(int v) {
    int q = v / cellSize;
    int r = v - q * cellSize;
    if (r < 0) { q = q - 1; }
    return q;
  }

  << Non-negative bucket index for an integer cell. Mixes the three axes with
     odd multipliers, then folds to [0, buckets) with a sign correction. >>
  int bucketOf(int cx, int cy, int cz) {
    int h = cx * 73856093 + cy * 19349663 + cz * 83492791;
    int b = h % buckets;
    if (b < 0) { b = b + buckets; }
    return b;
  }

  << Index of the entry stored at integer cell (cx,cy,cz), or -1 when absent.
     Walks only the hash chain for that cell bucket. >>
  int findCell(int cx, int cy, int cz) {
    if (buckets < 1) { return -1; }
    int b = bucketOf(cx, cy, cz);
    int i = arrayGet(bucketHead, b);
    while (i >= 0) {
      if (arrayGet(keyX, i) == cx) {
        if (arrayGet(keyY, i) == cy) {
          if (arrayGet(keyZ, i) == cz) { return i; }
        }
      }
      i = arrayGet(bucketNext, i);
    }
    return -1;
  }

  << Insert or overwrite the payload for the cell containing point (x,y,z).
     Returns true when a new cell was created, false when an existing cell was
     overwritten. >>
  boolean insert(int x, int y, int z, String value) {
    int cx = cellOf(x);
    int cy = cellOf(y);
    int cz = cellOf(z);
    int existing = findCell(cx, cy, cz);
    if (existing >= 0) {
      arraySet(payload, existing, value);
      return false;
    }
    int b = bucketOf(cx, cy, cz);
    arrayPush(keyX, cx);
    arrayPush(keyY, cy);
    arrayPush(keyZ, cz);
    arrayPush(payload, value);
    arrayPush(bucketNext, arrayGet(bucketHead, b));
    arraySet(bucketHead, b, size);
    size = size + 1;
    return true;
  }

  << Payload of the cell containing point (x,y,z), or null when that cell is
     unoccupied. This is the near-O(1) point query. >>
  String queryPoint(int x, int y, int z) {
    int i = findCell(cellOf(x), cellOf(y), cellOf(z));
    if (i < 0) { return null; }
    return arrayGet(payload, i);
  }

  < True when the cell containing point (x,y,z) is occupied. >
  boolean contains(int x, int y, int z) {
    return findCell(cellOf(x), cellOf(y), cellOf(z)) >= 0;
  }

  << Collect into out every payload whose cell lies within the (2*radius+1)^3
     block of cells centred on the cell containing point (x,y,z). radius 1 scans
     the 3x3x3 = 27 neighbour cells. Returns the number of payloads appended.
     out is an SLList; existing contents are preserved. This visits only
     neighbour cells, never the whole populated set. >>
  int queryNeighbourhood(int x, int y, int z, int radius, SLList out) {
    if (out == null) { return 0; }
    int r = radius;
    if (r < 0) { r = 0; }
    int ccx = cellOf(x);
    int ccy = cellOf(y);
    int ccz = cellOf(z);
    int found = 0;
    int dz = 0 - r;
    while (dz <= r) {
      int dy = 0 - r;
      while (dy <= r) {
        int dx = 0 - r;
        while (dx <= r) {
          int i = findCell(ccx + dx, ccy + dy, ccz + dz);
          if (i >= 0) {
            out.add(arrayGet(payload, i));
            found = found + 1;
          }
          dx = dx + 1;
        }
        dy = dy + 1;
      }
      dz = dz + 1;
    }
    return found;
  }

  < Integer cell X of a point coordinate (exposed for callers that bucket themselves). >
  int cellX(int x) { return cellOf(x); }
  < Integer cell Y of a point coordinate. >
  int cellY(int y) { return cellOf(y); }
  < Integer cell Z of a point coordinate. >
  int cellZ(int z) { return cellOf(z); }
}