Changeset View
Changeset View
Standalone View
Standalone View
ps/trunk/binaries/data/mods/public/maps/random/rmgen/TileClass.js
////////////////////////////////////////////////////////////////////// | /** | ||||
// RangeOp | * Class that can be tagged to any tile. Can be used to constrain placers and entity placement to given areas. | ||||
// | */ | ||||
// Class for efficiently finding number of points within a range | class TileClass { | ||||
// | |||||
////////////////////////////////////////////////////////////////////// | |||||
function RangeOp(size) | constructor(size) | ||||
{ | { | ||||
// Get smallest power of 2 which is greater than or equal to size | this.size = size; | ||||
this.nn = 1; | this.width = Math.ceil(size / 16); // Need one entry per 16 tiles as each tile takes a single bit | ||||
while (this.nn < size) { | this.inclusionGrid = new Uint16Array(this.size * this.width); | ||||
this.nn *= 2; | |||||
} | |||||
this.vals = new Int16Array(2*this.nn); // int16 | |||||
} | } | ||||
RangeOp.prototype.set = function(pos, amt) | /** | ||||
{ | * Returns true if the given position is part of the tileclass. | ||||
this.add(pos, amt - this.vals[this.nn + pos]); | */ | ||||
}; | has(position) | ||||
RangeOp.prototype.add = function(pos, amt) | |||||
{ | |||||
for(var s = this.nn; s >= 1; s /= 2) | |||||
{ | { | ||||
this.vals[s + pos] += amt; | if (position.x < 0 || position.x >= this.size || position.y < 0 || position.y >= this.size) | ||||
pos = Math.floor(pos/2); | return 0; | ||||
// x >> 4 == Math.floor(x / 16); used to find the integer this x is included in | |||||
// x & 0xF == x % 16; used to find the bit position of the given x | |||||
return this.inclusionGrid[position.y * this.width + (position.x >> 4)] & (1 << (position.x & 0xF)); | |||||
} | } | ||||
}; | |||||
RangeOp.prototype.get = function(start, end) | |||||
{ | |||||
var ret = 0; | |||||
var i = 1; | |||||
var nn = this.nn; | |||||
// Count from start to end by powers of 2 | /** | ||||
for (; start+i <= end; i *= 2) | * Adds the given position to the tileclass. | ||||
{ | */ | ||||
if (start & i) | add(position) | ||||
{ // For each bit in start | |||||
ret += this.vals[nn/i + Math.floor(start/i)]; | |||||
start += i; | |||||
} | |||||
} | |||||
// | |||||
while(i >= 1) | |||||
{ | |||||
if(start+i <= end) | |||||
{ | { | ||||
ret += this.vals[nn/i + Math.floor(start/i)]; | if (position.x < 0 || position.x >= this.size || position.y < 0 || position.y >= this.size) | ||||
start += i; | return; | ||||
this.inclusionGrid[position.y * this.width + (position.x >> 4)] |= 1 << (position.x & 0xF); | |||||
} | } | ||||
i /= 2; | |||||
} | |||||
return ret; | |||||
}; | |||||
/** | /** | ||||
* Class that can be tagged to any tile. Can be used to constrain placers and entity placement to given areas. | * Removes the given position to the tileclass. | ||||
*/ | */ | ||||
function TileClass(size) | remove(position) | ||||
{ | { | ||||
this.size = size; | if (position.x < 0 || position.x >= this.size || position.y < 0 || position.y >= this.size) | ||||
this.inclusionCount = []; | return; | ||||
this.rangeCount = []; | this.inclusionGrid[position.y * this.width + (position.x >> 4)] &= ~(1 << (position.x & 0xF)); | ||||
for (let i=0; i < size; ++i) | |||||
{ | |||||
this.inclusionCount[i] = new Int16Array(size); //int16 | |||||
this.rangeCount[i] = new RangeOp(size); | |||||
} | } | ||||
} | |||||
TileClass.prototype.has = function(position) | |||||
{ | |||||
return !!this.inclusionCount[position.x] && !!this.inclusionCount[position.x][position.y]; | |||||
}; | |||||
TileClass.prototype.add = function(position) | |||||
{ | |||||
if (!this.inclusionCount[position.x][position.y] && g_Map.validTile(position)) | |||||
this.rangeCount[position.y].add(position.x, 1); | |||||
++this.inclusionCount[position.x][position.y]; | /** | ||||
}; | * Count the number of tiles in the tileclass within the given radius of the given position. | ||||
* Can return either the total number of members or nonmembers. | |||||
TileClass.prototype.remove = function(position) | */ | ||||
{ | countInRadius(position, radius, returnMembers) | ||||
--this.inclusionCount[position.x][position.y]; | |||||
if (!this.inclusionCount[position.x][position.y]) | |||||
this.rangeCount[position.y].add(position.x, -1); | |||||
}; | |||||
TileClass.prototype.countInRadius = function(position, radius, returnMembers) | |||||
{ | { | ||||
let members = 0; | let members = 0; | ||||
let nonMembers = 0; | let total = 0; | ||||
let radius2 = Math.square(radius); | const radius2 = radius * radius; | ||||
const [x, y] = [position.x, position.y]; | |||||
for (let y = position.y - radius; y <= position.y + radius; ++y) | |||||
{ | const yMin = Math.max(Math.ceil(y - radius), 0); | ||||
let iy = Math.floor(y); | const yMax = Math.min(Math.floor(y + radius), this.size - 1); | ||||
if (radius >= 27) // Switchover point before RangeOp actually performs better than a straight algorithm | for (let iy = yMin; iy <= yMax; ++iy) | ||||
{ | { | ||||
if (iy >= 0 && iy < this.size) | const dy = iy - y; | ||||
{ | const dy2 = dy * dy; | ||||
let dx = Math.sqrt(Math.square(radius) - Math.square(y - position.y)); | const delta = Math.sqrt(radius2 - dy2); | ||||
const xMin = Math.max(Math.ceil(x - delta), 0); | |||||
let minX = Math.max(Math.floor(position.x - dx), 0); | const xMax = Math.min(Math.floor(x + delta), this.size - 1); | ||||
let maxX = Math.min(Math.floor(position.x + dx), this.size - 1) + 1; | |||||
const indexXMin = xMin >> 4; | |||||
let newMembers = this.rangeCount[iy].get(minX, maxX); | const indexXMax = xMax >> 4; | ||||
const indexY = iy * this.width; | |||||
members += newMembers; | for (let indexX = indexXMin; indexX <= indexXMax; ++indexX) | ||||
nonMembers += maxX - minX - newMembers; | { | ||||
} | const imin = indexX == indexXMin ? xMin & 0xF : 0; | ||||
} | const imax = indexX == indexXMax ? xMax & 0xF : 15; | ||||
else // Simply check the tiles one by one to find the number | total += imax - imin + 1; | ||||
{ | if (this.inclusionGrid[indexY + indexX]) | ||||
let dy = iy - position.y; | for (let i = imin; i <= imax; ++i) | ||||
if (this.inclusionGrid[indexY + indexX] & (1 << i)) | |||||
let xMin = Math.max(Math.floor(position.x - radius), 0); | |||||
let xMax = Math.min(Math.ceil(position.x + radius), this.size - 1); | |||||
for (let ix = xMin; ix <= xMax; ++ix) | |||||
{ | |||||
let dx = ix - position.x; | |||||
if (Math.square(dx) + Math.square(dy) <= radius2) | |||||
{ | |||||
if (this.inclusionCount[ix] && this.inclusionCount[ix][iy] && this.inclusionCount[ix][iy] > 0) | |||||
++members; | ++members; | ||||
else | |||||
++nonMembers; | |||||
} | |||||
} | |||||
} | } | ||||
} | } | ||||
if (returnMembers) | return returnMembers ? members : total - members; | ||||
return members; | } | ||||
else | |||||
return nonMembers; | |||||
}; | |||||
TileClass.prototype.countMembersInRadius = function(position, radius) | /** | ||||
* Counts the number of tiles marked in the tileclass within the given radius of the given position. | |||||
*/ | |||||
countMembersInRadius(position, radius) | |||||
{ | { | ||||
return this.countInRadius(position, radius, true); | return this.countInRadius(position, radius, true); | ||||
}; | } | ||||
TileClass.prototype.countNonMembersInRadius = function(position, radius) | /** | ||||
* Counts the number of tiles not marked in the tileclass within the given radius of the given position. | |||||
*/ | |||||
countNonMembersInRadius(position, radius) | |||||
{ | { | ||||
return this.countInRadius(position, radius, false); | return this.countInRadius(position, radius, false); | ||||
}; | } | ||||
} |
Wildfire Games · Phabricator