Using RVOQuadtree to find neighbors of Agent

General
1

Hello,

I am developing an RTS game and currently use the RVO Simulator for local avoidance of all units. I noticed that the Simulator already tracks the location of all agents in the RVO Simulation and I was wondering if there was an easy way to query the QuadTree or another component to get all neighbors for an agent within a specific radius.

I am also looking into implementing a kd-tree or influence map but it seems that both solutions might produce redundant calculations as the location of each agent is already tracked as part of the RVO Simulation

2

Hi

Yes, this is possible.
If you are using the beta version then this is the relevant code:

var simulator = RVOSimulator.active.GetSimulator() as Pathfinding.RVO.SimulatorBurst;
var result = new NativeArray<int>(10, Allocator.Persistent);
var resultDistances = new NativeArray<float>(10, Allocator.Persistent);

var query = new RVOQuadtreeBurst.QuadtreeQuery {
    position = ...,
    speed = 0,
    timeHorizon = 0,
    agentRadius = float.PositiveInfinity,
    outputStartIndex = 0,
    maxCount = result.Length,
    result = result,
    resultDistances = resultDistances,
};
simulator.quadtree.QueryKNearest(query);

for (int i = 0; i < result.Length; i++) {
    int agentIndex = result[i];
    if (agentIndex == -1) break;
    var agentPosition = simulator.simulationData.position[agentIndex];
    Debug.DrawLine(query.position, agentPosition, Color.red);
}

It is kinda tricky to get from that back to the RVOController component and the associated GameObject though.

1 Like
3

Interesting
I was trying to make agents find a viable spot if multiple agents are say, attacking the same player
Probly gonna need its own function using this, instead of NN search (im using navmesh…so no simple “occupied grid cell” distinction)
This might be useful indeed

4

For that use case you might be interested in the RVOQuadtreeBurst.QueryArea(position, radius) method which returns the total agent area inside a circle. So a return value of 0 means there are no agents overlapping that circle.

5

However, in my experience it is often much easier and more robust to just pick say 6 points around the player in a circle and have the enemies reserve those points for when they want to attack.

1 Like
6

Hi Pizza,

Did you end up using that method to query the nearest neighbors by any chance?

7

I just upgraded to the beta specifically for this functionality but cannot figure out what this code is supposed to do. I just need to be able to target objects nearby an RVO agent and thought this would be the way to do it but :man_shrugging:

I would expect I make position be the position of the agent I want to query around but honestly have no idea what the other fields are for. I would expect to put in a radius? Probably too noob for this I suppose.

8

@aron_granberg bumping this thread to see if you could provide some more detail around that code or point me towards some examples of how to actually use Quadtrees to query for surrounding agents within a specific area?

9

@lemmons
Yeah, a lot of the parameters are not relevant for you. It’s not just a simple nearest neighbour query, it actually finds all agents another agent could potentially collide with, which has to take speed into account.

var query = new RVOQuadtreeBurst.QuadtreeQuery {
    position = ...,
    // Not relevant for you, just leave it at zero
    speed = 0,
    // Not relevant for you, just leave it at zero.
    timeHorizon = 0,
    // This is the range within you want to find agents
    // It's called agent radius because that's what this parameter is used as by the local avoidance algorithm, but you can ignore that.
    agentRadius = float.PositiveInfinity,
    // Where in the result list to start storing results
    outputStartIndex = 0,
    // Max number of results to store
    maxCount = result.Length,
    // Where to store the results
    result = result,
    // Where to store the distances to the agents
    resultDistances = resultDistances,
};

I hope this helps.
Note that this will return internal agent ids. There is however no link back from this id to which RVOController it corresponds to. However, you can access the agent id for an RVOController using rvocontroller.rvoAgent.AgentIndex so you can potentially build your own reverse-lookup.

1 Like
10

Thanks so much for this! I’ll try it out tonight. Just wondering though, I don’t mind the complexity but in terms of “best practices” and performance is this really the best way to go about finding nearest neighbors of a certain type?

I tried using trigger colliders for each unit but with 200+ units that was horribly unperformant, then I tried querying my list of enemy units ever [x] seconds using MultiTargetPath which was quite a bit better but the fact that the RVOSim was holding a lot of this info already made me think it was the best solution. Thoughts?

11

Note that this is a pure world-distance calculation. The MultiTargetPath would take things like walls into account. The quadtree will not do that.

To be honest, I would probably just use some off-the-shelf tree structure that you can find. Probably won’t be quite as performant as this one (the rvo quadtree is pretty well optimized, and you don’t have to spend time building 2 trees), but it will probably be less complex as you don’t have to dig into the A* Pathfinding Project Pro internals. Search online for a C# quadtree or kd-tree and you should be good to go.

1 Like