Flocc

Agent-based modeling in JavaScript in the browser or on the server. [v0.4.8]

KDTree

Overview

The base flocc.KDTree class (from here on, just KDTree) is a data structure for agents in 2- or 3-dimensional environments. It’s useful for models where agents take actions depending on their nearest neighbors. Without a KDTree, it would be necessary for every agent to loop over every other agent in the environment and only use those whose distance to the first agent is under a certain threshold. A KDTree reduces the computational complexity from O(n2) to O(n log n) for these models, allowing simulations to be run with a greater number of agents.

After setting up an environment and adding agents to it, a KDTree can be instantiated by calling:

const tree = new KDTree(environment.getAgents(), 2);

Where the first parameter is all of the agents whose locations should be stored in the tree (using their xy, and z data), and the second parameter is the number of dimensions (2 or 3).

Then, to make sure that your environment recognizes and can make use of the KDtree, make sure you call: environment.use(tree) (where tree is the instance of the KDTree you created earlier). This step is necessary to ensure that the KDTree updates with new agent data over time, keeping it balanced and accurate.

Methods

.agentsWithinDistance(agent | vector | point, distance)

Get an array of agents whose distance to the given agent, vector (using utils.distance), or point is less than or equal to the given distance.

const agentNeighbors = tree.agentsWithinDistance(agent, 20);

const vectorNeighbors = tree.agentsWithinDistance(new Vector(1, 2, 3), 20);

const pointNeighbors = tree.agentsWithinDistance({ x: 1, y: 2, z: 3 }, 20);

// all return an array of Agents whose distance is 20 or less to the
// first parameter (if an Agent is the first parameter, it is
// excluded from the result)

.nearestNeighbor(agent | vector | point)

Find the nearest neighbor (an agent) to the given agent, vector, or point.

const agentNearest = tree.nearestNeighbor(agent);

const vectorNearest = tree.nearestNeighbor(new Vector(1, 2, 3));

const pointNearest = tree.nearestNeighbor({ x: 1, y: 2, z: 3 });

// all return a single Agent that is the nearest neighbor