Implement an efficient neighborhood search for the AgentManager
In !267 (merged), the AgentManager::neighbors_of
method was added, which simple iterates over all agents to determine their distance from a certain agent, leading to an overall quadratic complexity in agent number when doing this for all agents.
However, on the level of the AgentManager
, there are more elaborate algorithms possible that would achieve something like an \mathcal{O}(n \log n)
complexity:
- Let
AgentManager
maintain aCellManager
that "bins" agents into different cells - Upon neighborhood search, use the grid geometry to determine the bins that could contain candidate agents
- For some candidates, may need to explicitly check the interaction radius again
Open questions:
- How best to manage the update of the grid? Manually?
- How to determine grid resolution? Some measure depending on agent density seems reasonable, but probably need to benchmark this