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); }
}