I have some javascript i wrote to load a map created with azgaar fantasy map creator into tiled. When i run the code using nodejs in vs code it takes about 47 seconds to iterate the grid and find all the closest cells (via a quadtree). The same code when run in tiled runs forever, like 20-25 minutes, if it finishes. Tiled will sometimes crash.
What can i do to create a better performing plugin? I’ve noticed a couple of references to python for extensions, but i don’t really see any examples of making python plugins. What are my options for speed?
The test is below. quadtree is a javascript class i wrote (ported from some of my c# code). If i remove the “getClosest” method from the tiled plugin, everything runs in < 50ms, but with that, it takes 1400+ seconds.
map.json is any exported json file from Azgaar's Fantasy Map Generator
import { Quadtree, Rectangle } from './quadtree.mjs';
import { readFileSync } from 'fs';
var startTime = Date.now();
function logWithTime(message)
{
var elapsed = ((Date.now() - startTime) / 1000).toFixed(3);
console.log("[" + elapsed + "s] " + message);
}
const data = JSON.parse(readFileSync('./map.json', 'utf-8'));
const qt = new Quadtree(0, new Rectangle(0, 0, data.info.width, data.info.height));
logWithTime('Created quadtree');
for (var cellIndex in data.pack.cells)
{
var cell = data.pack.cells[cellIndex];
qt.insert({ coordinates: { x: cell.p[0], y: cell.p[1] }, data: cell });
}
logWithTime('Inserted cells into quadtree');
for(let x = 0; x < data.info.width; x++)
{
for(let y = 0; y < data.info.height; y++)
{
try
{
var mapX = (x + 0.5);
var mapY = (y + 0.5);
var cell = qt.getClosest({ x: mapX, y: mapY });
}
catch (e)
{
console.error(e);
}
}
}
logWithTime('Done');
class Quadtree
{
constructor(level, bounds, maxObjects = 4, maxLevels = 5)
{
this.maxObjects = maxObjects;
this.maxLevels = maxLevels;
this.level = level;
this.bounds = bounds;
this.objects = [];
this.nodes = [null, null, null, null];
this.parent = null;
}
clear()
{
this.objects = [];
for (let i = 0; i < this.nodes.length; i++)
{
if (this.nodes[i] !== null)
{
this.nodes[i].clear();
this.nodes[i] = null;
}
}
}
insert(obj, addToParent = true)
{
if (this.nodes[0] !== null)
{
const index = this.getIndex(obj.coordinates);
if (index !== -1)
{
this.nodes[index].insert(obj);
return;
}
}
this.objects.push({ point: obj.coordinates, data: obj });
if (this.objects.length > this.maxObjects && this.level < this.maxLevels)
{
if (this.nodes[0] === null)
{
this.split();
}
for (const o of [...this.objects])
{
const index = this.getIndex(o.point);
if (index !== -1)
{
this.nodes[index].insert(o.data, false);
}
}
}
if (addToParent)
{
let node = this.parent;
while (node !== null)
{
node.objects.push({ point: obj.coordinates, data: obj });
node = node.parent;
}
}
}
retrieve(returnObjects, point)
{
if (!returnObjects)
{
returnObjects = [];
}
const index = this.getIndex(point);
if (index !== -1 && this.nodes[0] !== null)
{
this.nodes[index].retrieve(returnObjects, point);
}
returnObjects.push(...this.objects.map(o => o.data));
return returnObjects;
}
getNode(point)
{
const index = this.getIndex(point);
if (index !== -1 && this.nodes[0] !== null)
{
return this.nodes[index].getNode(point);
}
return this;
}
split()
{
const subWidth = this.bounds.width / 2;
const subHeight = this.bounds.height / 2;
const x = this.bounds.x;
const y = this.bounds.y;
this.nodes[0] = new Quadtree(this.level + 1, new Rectangle(x + subWidth, y, subWidth, subHeight), this.maxObjects, this.maxLevels);
this.nodes[0].parent = this;
this.nodes[1] = new Quadtree(this.level + 1, new Rectangle(x, y, subWidth, subHeight), this.maxObjects, this.maxLevels);
this.nodes[1].parent = this;
this.nodes[2] = new Quadtree(this.level + 1, new Rectangle(x, y + subHeight, subWidth, subHeight), this.maxObjects, this.maxLevels);
this.nodes[2].parent = this;
this.nodes[3] = new Quadtree(this.level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight), this.maxObjects, this.maxLevels);
this.nodes[3].parent = this;
}
getIndex(point)
{
let index = -1;
const verticalMidpoint = this.bounds.x + (this.bounds.width / 2);
const horizontalMidpoint = this.bounds.y + (this.bounds.height / 2);
const topQuadrant = (point.y < horizontalMidpoint && point.y >= this.bounds.y);
const bottomQuadrant = (point.y >= horizontalMidpoint);
if (point.x < verticalMidpoint && point.x >= this.bounds.x)
{
if (topQuadrant)
{
index = 1;
} else if (bottomQuadrant)
{
index = 2;
}
} else if (point.x >= verticalMidpoint)
{
if (topQuadrant)
{
index = 0;
} else if (bottomQuadrant)
{
index = 3;
}
}
return index;
}
getObjects(point)
{
let node = this.getNode(point);
if (node.parent === null)
{
return node.objects.map(x => x.data);
}
while (node.parent !== null)
{
const r = new Rectangle(
Math.max(0, Math.min(node.bounds.width - (node.bounds.width / 2), node.bounds.width)),
Math.max(0, Math.min(node.bounds.height - (node.bounds.height / 2), node.bounds.height)),
node.bounds.width,
node.bounds.height
);
node = node.parent;
if (node.nodes.every(x => x && x.bounds.intersects(r)))
{
return node.objects.map(x => x.data);
}
}
return [];
}
getClosest(point)
{
const objects = this.getObjects(point);
if (objects.length === 0) return null;
return objects.reduce((closest, obj) =>
{
const dist = this.distance(obj.coordinates, point);
const closestDist = this.distance(closest.coordinates, point);
return dist < closestDist ? obj : closest;
});
}
distance(p1, p2)
{
const dx = p2.x - p1.x;
const dy = p2.y - p1.y;
return Math.sqrt(dx * dx + dy * dy);
}
}
class Rectangle
{
constructor(x, y, width, height)
{
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
contains(point)
{
return (point.x >= this.x && point.x <= this.x + this.width &&
point.y >= this.y && point.y <= this.y + this.height);
}
intersects(range)
{
return !(range.x > this.x + this.width ||
range.x + range.width < this.x ||
range.y > this.y + this.height ||
range.y + range.height < this.y);
}
}
export { Quadtree, Rectangle };