Quadtree

Last modification on 2019-03-14

Introduction

Agent's in Ecosim need the ability to sense other agents within their vicinity. Below is a simple way of doing this:

  1. For each agent (a):
    1. For each other agent (t)
      1. If t is in range, save to agent a's local agent array
However, this is very inefficient. The time complexity of doing this would be O(n2), meaning if we have 100 agents doing 100 checks every frame, we would have 100000 checks per frame. This will cause some serious performance issues. The solution?

The Quadtree

A quadtree is a datastructure much like a regular binary tree, but rather than simply having 2 branches it has four. These quads represents sections of 2 dimensional space, so we can use them to store point data. Once a point is inserted into the tree, it is stored in the branch which is responsible for that section of space. If a the amount of point data being stored in any branch exeeds a predefined threshold, the quad will split into 4 new quads.
Fig1. A point quadtree[1]
This is very useful for Ecosim, as it means we don't have to go through each agent in the agent array. Only agents in near and neighbouring quads need to be checked. This greatly reduces the time complexity of the problem, from O(n) to O(log(n).

Screenshot

Below is a screenshot of the agents inserted into the quadtree. (Note there is not much variance in quad sizes, as the agents are distributed in quite a uniform way)
Fig2. A screenshot

References

[1] - Wikipedia.org - Category:Quadtrees