I've written a Xonix clone in Javascript/Canvas. It seems to work fine. However I would like to refactor the code of detecting conquered regions which seems to be bulky (see methods conquer, _conquer, _findOutline and _buildConquerRects).
Below is the relevant code. The full code is available on GitHub.
// cell attributes:
var CA_CLEAR = 1 << 0; // is cell cleared (conquered)?
var CA_TRAIL = 1 << 1; // does cell belong to the cursor trail?
// The playing field grid (set of available cells):
var cellset = {
nW: 0, // drawable area width in cells
nH: 0, // drawable area height in cells
nWx: 0, // total grid width in cells
nConquered: 0, // number of conquered cells
dirTrail: 0, // last direction of the cursor trail (movement)
cellPreTrail: 0, // index of cell preceding the cursor trail cells
aCells: [], // array mapping cell index in the grid to a value indicating type of this cell
aTrail: [], // array of the cursor trail cells' indices
aTrailNodes: [], // array of the cursor trail node cells' indices
aTrailRects: [], // array of rectangles comprising the cursor trail line
reset: function() {
var nW = this.nW = Math.floor(width / sizeCell);
var nH = this.nH = Math.floor(height / sizeCell);
var n = (this.nWx = nW+4)* (nH+4);
this.nConquered = 0;
this.aCells = [];
var aAll = [];
for (var i = 0; i < n; i++) {
var pos = this.pos(i), x = pos[0], y = pos[1];
this.aCells.push(x >= 0 && x < nW && y >= 0 && y < nH? 0 : CA_CLEAR);
aAll.push(i);
}
fillCellArea(cfgMain.colorFill, 0, 0, nW, nH);
},
render: function() {
if (this.aTrailRects.length) {
for (var i = this.aTrailRects.length-1; i >= 0; i--) {
fillCellArea.apply(null, [cfgMain.colorFill].concat(this.aTrailRects[i]));
}
this.aTrailRects = [];
}
},
isPosValid: function(x, y) {
return x >= -2 && x < this.nW+2 && y >= -2 && y < this.nH+2;
},
// get index of given cell in the grid
index: function(x, y) {
return this.isPosValid(x, y) ? (this.nWx)*(y+2) + x+2 : -1;
},
// convert index of a cell to appropriate position (coordinates) in the grid
pos: function(i) {
return [i % this.nWx - 2, Math.floor(i / this.nWx)-2];
},
posMap: function(arr) {
var _this = this;
return arr.map(function(v) { return _this.pos(v) });
},
value: function(x, y) {
var i = this.index(x,y);
return i >= 0? this.aCells[i] : 0;
},
set: function(x, y, v) {
var i = this.index(x,y);
if (i >= 0) this.aCells[i] = v;
return i;
},
setOn: function(x, y, v) {
var i = this.index(x,y);
if (i >= 0) this.aCells[i] |= v;
return i;
},
setOff: function(x, y, v) {
var i = this.index(x,y);
if (i >= 0) this.aCells[i] &= ~v;
return i;
},
applyRelDirs: function(x, y, dir, aDeltas) {
var ret = [];
for (var n = aDeltas.length, i = 0; i < n; i++) {
var d = (dir + aDeltas[i] + 360) % 360;
var vec = dirset.get(d), xt, yt;
ret.push([xt = x + vec[0], yt = y + vec[1], d, this.value(xt, yt)]);
}
return ret;
},
add2Trail: function(x, y, dir) {
var i = this.setOn(x, y, CA_TRAIL);
if (i < 0) return;
var n = this.aTrail.length;
if (!n || dir !== this.dirTrail) {
var iNode = n? this.aTrail[n-1] : i;
if (!n || iNode != this.aTrailNodes[this.aTrailNodes.length-1])
this.aTrailNodes.push(iNode);
if (!n) {
var aPos = this.applyRelDirs(x, y, dir, [180]);
this.cellPreTrail = this.index(aPos[0][0], aPos[0][1]);
}
}
this.aTrail.push(i);
this.dirTrail = dir;
},
lastTrailLine: function() {
var pos0 = this.pos(this.aTrailNodes[this.aTrailNodes.length-1]),
pos = this.pos(this.aTrail[this.aTrail.length-1]);
return [
Math.min(pos[0], pos0[0]), Math.min(pos[1], pos0[1]),
Math.abs(pos[0] - pos0[0])+1, Math.abs(pos[1] - pos0[1])+1
];
},
clearTrail: function() {
this.aTrailRects = this._buildTrailRects();
for (var n = this.aTrail.length, i = 0; i < n; i++) {
this.aCells[this.aTrail[i]] &= ~CA_TRAIL;
}
this.aTrail = []; this.aTrailNodes = [];
},
getPreTrailCell: function() {
return this.cellPreTrail;
},
// wrapper of conquered regions detection procedure:
conquer: function() {
var nTrail = this.aTrail.length;
if (!nTrail) return;
if (nTrail > 1)
this.aTrailNodes.push(this.aTrail[nTrail-1]);
var aConqRects = this._conquer() || this._buildTrailRects();
this.aTrail = []; this.aTrailNodes = [];
if (!aConqRects || !aConqRects.length) return;
for (var n = aConqRects.length, i = 0; i < n; i++) {
var rect = aConqRects[i];
var x0 = rect[0], y0 = rect[1], w = rect[2], h = rect[3];
for (var x = 0; x < w; x++) {
for (var y = 0; y < h; y++) {
if (this.value(x + x0, y + y0, CA_CLEAR) & CA_CLEAR) continue;
this.set(x + x0, y + y0, CA_CLEAR);
this.nConquered++;
}
}
}
for (i = 0; i < n; i++) {
clearCellArea.apply(null, aConqRects[i]);
}
aConqRects = [];
},
// conquered regions (polygons) detection:
_conquer: function() {
var nTrail = this.aTrail.length, nNodes = this.aTrailNodes.length;
var aOutlineset = []; // outlines (boundaries) of found regions
var delta;
var bClosedTrail = nNodes >= 4 &&
((delta = Math.abs(this.aTrailNodes[0] - this.aTrailNodes[nNodes-1])) == 1 || delta == this.nWx);
if (bClosedTrail) { // if the cursor trail is self-closed
aOutlineset.push([this.aTrailNodes, 1]);
}
var bAddTrailRects = false;
var posPre = this.pos(this.cellPreTrail), posCr = cursor.pos();
var aDeltas = [-90, 90];
for (var side = 0; side < 2; side++) {
delta = aDeltas[side];
var iLastNode = 0;
var sum = 0, bNonTangent = false, bEndAtNode = false;
for (var l = 0; l < nTrail && sum < nTrail; l++) {
var cellStart = this.aTrail[l];
var pos = this.pos(cellStart);
var pos0 = l? this.pos(this.aTrail[l - 1]) : posPre;
var x = pos[0], y = pos[1];
var dir = (dirset.find(x - pos0[0], y - pos0[1]) + delta + 360) % 360;
var aDirs = bEndAtNode? [] : [dir];
if (this.aTrailNodes.indexOf(cellStart) >= 0) {
var pos2 = l < nTrail - 1? this.pos(this.aTrail[l + 1]) : posCr;
dir = (dirset.find(pos2[0] - x, pos2[1] - y) + delta + 360) % 360;
if (dir != aDirs[0]) aDirs.push(dir);
}
if (this.aTrail[l] == this.aTrailNodes[iLastNode+1]) ++iLastNode;
var ret = 0;
for (var nDs = aDirs.length, j = 0; j < nDs && !ret; j++) {
dir = aDirs[j];
var vec = dirset.get(dir);
var xt = x + vec[0], yt = y + vec[1];
var v = this.value(xt, yt);
if (v & CA_CLEAR || v & CA_TRAIL) continue;
ret = this._findOutline(xt, yt, dir, l, iLastNode);
}
bEndAtNode = false;
if (!ret) continue;
var aNodes = ret[0], len = ret[1], lenTangent = ret[2];
if (ret.length > 3) {
iLastNode = ret[3];
l = ret[4];
bEndAtNode = ret[5];
}
aOutlineset.push([aNodes, len]);
sum += lenTangent;
if (!lenTangent) bNonTangent = true;
}
if (!sum && !bNonTangent && !bClosedTrail) return false;
if (sum < nTrail && !bClosedTrail) bAddTrailRects = true;
}
if (!aOutlineset.length)
return false;
aOutlineset.sort(function (el1, el2) {
return el1[1] - el2[1];
});
var aRects = [], n = aOutlineset.length, bUnbroken = true;
for (var i = 0; i < (bUnbroken? n-1 : n); i++) {
ret = this._buildConquerRects(aOutlineset[i][0]);
if (ret)
aRects = aRects.concat(ret);
else
bUnbroken = false;
}
if (!aRects.length)
return false;
return bAddTrailRects? aRects.concat(this._buildTrailRects()) : aRects;
},
// find outline of conquered region (polygon)
// from given cell position (x0, y0) and starting direction (dir)
// as well as indices of starting cell and last node cell in the trail:
_findOutline: function(x0, y0, dir, iStartCell, iLastNode) {
function isClear(arr) {
return arr[3] & CA_CLEAR;
}
var aNodes = [], aUniqNodes = [], aUsedDirs = [], aBackDirs = [];
var x = x0, y = y0,
lim = 6 * (this.nW + this.nH), n = 0, bClosed = false;
do {
bClosed = n && x == x0 && y == y0;
var cellCurr = this.index(x,y), iUniq = aUniqNodes.indexOf(cellCurr);
var aCurrUsed = iUniq >= 0? aUsedDirs[iUniq] : [];
var aCurrBack = iUniq >= 0? aBackDirs[iUniq] : [];
var aPosOpts = this.applyRelDirs(x,y, dir, [-90, 90, 0]);
var aTestDirs = [180+45, -45, 45, 180-45, -45, 45];
var aPassIdx = [], aPassWeight = [];
for (var i = 0; i < 3; i++) {
var d = aPosOpts[i][2];
if (aCurrUsed.indexOf(d) >= 0) continue;
if (isClear(aPosOpts[i])) continue;
var aTestOpts = this.applyRelDirs(x,y, dir, aTestDirs.slice(i*2,i*2+2));
var b1 = isClear(aTestOpts[0]), b2 = isClear(aTestOpts[1]);
var b = b1 || b2 || (i == 2? isClear(aPosOpts[0]) || isClear(aPosOpts[1]) : isClear(aPosOpts[2]));
if (!b) continue;
aPassIdx.push(i);
aPassWeight.push(
(b1 && b2? 0 : b1 || b2? 1 : 2) + (aCurrBack.indexOf(d) >= 0? 3 : 0)
);
}
var nPass = aPassIdx.length;
var min = false, idx = false;
for (i = 0; i < nPass; i++) {
if (!i || aPassWeight[i] < min) {
min = aPassWeight[i]; idx = aPassIdx[i];
}
}
var pos = nPass? aPosOpts[idx] : this.applyRelDirs(x,y, dir, [180])[0];
var dir0 = dir;
x = pos[0]; y = pos[1]; dir = pos[2];
if (pos[2] == dir0) continue;
nPass? aNodes.push(cellCurr) : aNodes.push(cellCurr, cellCurr);
dir0 = (dir0 + 180) % 360;
if (iUniq < 0) {
aUniqNodes.push(cellCurr);
aUsedDirs.push([dir]);
aBackDirs.push([dir0]);
}
else {
aUsedDirs[iUniq].push(dir);
aBackDirs[iUniq].push(dir0);
}
}
while (n++ < lim && !(this.value(x, y) & CA_TRAIL));
if (!(n < lim)) return false;
if (bClosed) {
aNodes.push(cellCurr);
if (aNodes[0] != (cellCurr = this.index(x0,y0))) aNodes.unshift(cellCurr);
var nNodes = aNodes.length;
if (nNodes % 2 && aNodes[0] == aNodes[nNodes-1]) aNodes.pop();
return [aNodes, n+1, 0];
}
var cellStart = this.aTrail[iStartCell], cellEnd = this.index(x,y);
aNodes.push(cellEnd);
var nTrail = this.aTrail.length;
var aTangentNodes = [cellStart];
for (var l = iStartCell+1; l < nTrail && this.aTrail[l] != cellEnd; l++) {
if (this.aTrail[l] == this.aTrailNodes[iLastNode+1])
aTangentNodes.push(this.aTrailNodes[++iLastNode]);
}
var bEndAtNode = this.aTrail[l] == this.aTrailNodes[iLastNode+1];
if (bEndAtNode) l--;
var lenTangent = l - iLastNode;
return [
aNodes.concat(aTangentNodes.reverse()), n+1+lenTangent, lenTangent,
iLastNode, l, bEndAtNode
];
},
// break the cursor trail line into a set of rectangles:
_buildTrailRects: function() {
if (this.aTrailNodes.length == 1)
this.aTrailNodes.push(this.aTrailNodes[0]);
var aRects = [];
for (var n = this.aTrailNodes.length, i = 0; i < n-1; i++) {
var pos1 = this.pos(this.aTrailNodes[i]), pos2 = this.pos(this.aTrailNodes[i+1]);
var x0 = Math.min(pos1[0], pos2[0]), y0 = Math.min(pos1[1], pos2[1]);
var w = Math.max(pos1[0], pos2[0]) - x0 + 1, h = Math.max(pos1[1], pos2[1]) - y0 + 1;
var rect = [x0, y0, w, h];
aRects.push(rect);
}
return aRects;
},
// break region specified by its outline into a set of rectangles:
_buildConquerRects: function(aOutline) {
// checks if rectangle contains at least one ball (enemy):
function containBall(rect) {
var x1 = rect[0], x2 = x1+ rect[2] - 1;
var y1 = rect[1], y2 = y1+ rect[3] - 1;
for (var i = 0; i < nBalls; i++) {
var o = aBalls[i], x = o.x, y = o.y;
if (x >= x1 && x <= x2 && y >= y1 && y <= y2) return true;
}
return false;
}
if (aOutline.length < 4) return false;
var aNodes = this.posMap(aOutline);
var n = aNodes.length;
if (n > 4 && n % 2 != 0) {
var b1 = aNodes[0][0] == aNodes[n-1][0], b2;
if (b1 ^ aNodes[0][1] == aNodes[n-1][1]) {
b2 = aNodes[n-2][0] == aNodes[n-1][0];
if (!(b2 ^ b1) && b2 ^ aNodes[n-2][1] == aNodes[n-1][1])
aNodes.pop();
b2 = aNodes[0][0] == aNodes[1][0];
if (!(b2 ^ b1) && b2 ^ aNodes[0][1] == aNodes[1][1])
aNodes.shift();
}
b1 = aNodes[0][0] == aNodes[1][0]; b2 = aNodes[1][0] == aNodes[2][0];
if (!(b1 ^ b2) && b1 ^ aNodes[0][1] == aNodes[1][1] && b2 ^ aNodes[1][1] == aNodes[2][1])
aNodes.shift();
}
if (aNodes.length % 2 != 0) return false;
var aRects = [];
for (var l = 0; l < 10 && aNodes.length > 4; l++) {
n = aNodes.length;
var dim1 = 0, dim2 = 0, iBase = 0, iCo = 0;
var posB1, posB2, posT1, posT2;
for (var i = 0; i < n; i++) {
posB1 = aNodes[i]; posB2 = aNodes[(i+1)%n];
posT1 = aNodes[(i-1+n)%n]; posT2 = aNodes[(i+2)%n];
var dir = dirset.find(posT1[0]-posB1[0], posT1[1]-posB1[1]);
if (dir != dirset.find(posT2[0]-posB2[0], posT2[1]-posB2[1])) continue;
var dirTest = Math.floor((dirset.find(posB2[0]-posB1[0], posB2[1]-posB1[1])+ dir) / 2);
var vec = dirset.get(dirTest - dirTest% 45);
if (this.value([posB1[0]+ vec[0], posB1[1]+ vec[1]]) & CA_CLEAR) continue;
var b = false, t, w, k;
if ((t = Math.abs(posB1[0]-posB2[0])) > dim1) {
b = true; k = 0; w = t;
}
if ((t = Math.abs(posB1[1]-posB2[1])) > dim1) {
b = true; k = 1; w = t;
}
if (!b) continue;
var k2 = (k+1)%2;
vec = dirset.get(dir);
var sgn = vec[k2];
var co2 = posB1[k2];
var left = Math.min(posB1[k], posB2[k]), right = Math.max(posB1[k], posB2[k]);
var min = Math.min(sgn* (posT1[k2]- co2), sgn* (posT2[k2]- co2));
for (var j = i% 2; j < n; j+= 2) {
if (j == i) continue;
var pos = aNodes[j], pos2 = aNodes[(j+1)%n], h;
if (pos[k2] == pos2[k2] && (h = sgn*(pos[k2]- co2)) >= 0 && h < min &&
pos[k] > left && pos[k] < right && pos2[k] > left && pos2[k] < right)
break;
}
if (j < n) continue;
dim1 = w; dim2 = sgn*min;
iBase = i; iCo = k;
}
var iB2 = (iBase+1)%n, iT1 = (iBase-1+n)%n, iT2 = (iBase+2)%n;
posB1 = aNodes[iBase];
posB2 = aNodes[iB2];
posT1 = aNodes[iT1];
posT2 = aNodes[iT2];
var aDim = [0, 0], pos0 = [];
var iCo2 = (iCo+1)%2;
aDim[iCo] = dim1;
aDim[iCo2] = dim2;
pos0[iCo] = Math.min(posB1[iCo], posB2[iCo]);
pos0[iCo2] = Math.min(posB1[iCo2], posB2[iCo2]) + (aDim[iCo2] < 0? aDim[iCo2]: 0);
var rect = [pos0[0], pos0[1], Math.abs(aDim[0])+1, Math.abs(aDim[1])+1];
var bC = Math.abs(posT1[iCo2] - posB1[iCo2]) == Math.abs(dim2);
if (containBall(rect)) return false;
aRects.push(rect);
if (bC) {
posB2[iCo2] += dim2;
aNodes.splice(iBase,1);
aNodes.splice(iT1 < iBase? iT1 : iT1-1, 1);
}
else {
posB1[iCo2] += dim2;
aNodes.splice(iT2,1);
aNodes.splice(iB2 < iT2? iB2 : iB2-1, 1);
}
}
var aX = aNodes.map(function(v) {return v[0]});
var aY = aNodes.map(function(v) {return v[1]});
var x0 = Math.min.apply(null, aX);
var y0 = Math.min.apply(null, aY);
rect = [x0, y0, Math.max.apply(null, aX)-x0+1, Math.max.apply(null, aY)-y0+1];
if (containBall(rect)) return false;
aRects.push(rect);
return aRects;
}
};
// The set of available directions:
var dirset = {
vecs: {
0: [1, 0], 45: [1, 1], 90: [0, 1], 135: [-1, 1], 180: [-1, 0], 225: [-1, -1], 270: [0, -1], 315: [1, -1]
},
get: function(v) {
return v in this.vecs? this.vecs[v] : [0, 0];
},
find: function(x, y) {
x = x == 0? 0 : (x > 0? 1 : -1);
y = y == 0? 0 : (y > 0? 1 : -1);
for (var v in this.vecs) {
var vec = this.vecs[v];
if (vec[0] == x && vec[1] == y) return parseInt(v);
}
return false;
}
};
Some explanation
Instead of using one of the general flood-fill algorithms to detect conquered regions, I've decided to write custom algorithm taking into account information about the cursor trail in order to reduce the runtime of detection.
The main point is that the cursor movement trail divides the current drawable area into polygons, some of them may become conquered regions which depends on whether a polygon not contains any ball inside. These polygons are formed on both sides of the cursor trail. Each polygon contains the cursor trail entirely or partially.
Most of the time only two polygons are formed, each of them contains the entire cursor trail (see Fig. 1). But in certain cases there could be many more polygons some of them contain the cursor trail partially (see Fig. 2). Furthermore, the cursor trail might form a polygon per se (see Fig. 3).
Fig. 1
Fig. 2
Fig. 3
Algorithm of conquered regions detection comprises two procedures:
- find outlines (polygonal chains) of divided polygons.
- for each found outline break its polygon into a set of rectangles.
Procedure 1 (informal description):
Iterate over two sides of the cursor trail (level 1). For each side iterate over all cells of the cursor trail (level 2) until the cell on the current side of the current trail cell is not cleared. Remember the found side cell. This cell belongs to one of the sought-for outlines. In order to get this outline we have to go from this cell in a direction such that at least one cleared or trail cell is on either side of the current cell... And so on, until the current cell is trail cell which mean that outline is about to be closed. In order to close the outline we have to add the range of the trail cells from the last iterated cell of the deepest loop to the currently iterated cell of the cursor trail loop (level 2). Then we resume the cursor trail loop and then, as it finished, we resume the sides loop (level 1).
In the case shown on Fig. 3 we have to add outline formed by the cursor trail to a set of found outlines.
Procedure 2 (informal description):
The main idea is to cut salient rectangle with maximum width or height from the current polygon on each iteration. Here salient rectangle mean a rectangle three vertices of which belong to set of vertices of the current polygon.
On first iteration we find the greatest side of polygon which is also side of salient rectangle. So we have one (first) side of sought-for rectangle. Now we have to find the rest of rectangle sides. The second side is the least one of two polygon sides adjacent to the first side. In order to find third side we have to find projection of the second vertex of the second rectangle side on opposite side of polygon (the greatest of the above adjacent sides). By connecting found point to the closest vertex of the first side, we get the third side, and therefore, the whole sought-for rectangle. In order to cut this rectangle from the polygon we have to remove the first two found sides and their vertices from the polygon. Then we add found projection point and connect it to the vertex which has been previously connected to the second side. As a result we get a polygon having by 2 vertices fewer than the source polygon. On next iteration we deal with cut-down polygon in the same way as on the first iteration... And so on, until we get a polygon of 4 vertices. All cut-off rectangles comprise the interior (body) of the source polygon.
