relative performance of berg kd spatial vs navmesh spatial queries.

[pgruenbacher]

I've been debating on which of the spatial structures would have the better performance for larger crowds with many obstacles. I had been running tests with the berg kd spatial class but now I'm curious if the navmesh localization would have better performance for both obstacle and agent queries, at the cost of higher memory for the navmesh. @MengeCrowdSim have you had any initial impressions of performance. I figured I'd ask before I benchmark to validate.

[curds01]

It's been a while since I considered this, but if my memory is accurate I'd say the following:

• kdtree is faster (the nav mesh has a lot of simple implementations that haven't been optimized in any way).
• kdtree has a bug -- as I remember it, in some cases, visibility queries produce the wrong answer.
• If you're really interested in performance, this might be the time to create an Eulerian grid (assuming that your scenarios can be projected onto a plane in a meaningful way). It also offers the best ability to tune memory vs performance.

[pgruenbacher]

yea ok I agree kdtree should be simpler. By Eulerian grid I presume you mean a spatial hash map, which yes should be quite fast assuming the grid can be both large enough and resolute enough to fit the needs of the scenario.

[curds01]

Yep; spatial hashing. A quad-tree would be a more complex, but more memory-efficient alternative to a uniform grid. And it still has the performance/memory tuneable knob by defining how small the leaf divisions can be (or, conversely, how many agents can be contained in a leaf).

Yet another alternative I've meant to add would be a 2D BVH using AABB for agents.

I'd strongly recommend, no matter which direction you go, to distinguish between static elements (e.g., obstacles) and dynamic objects (agents). You can afford to spend more in instantiating the former if it improves your run-time lookups, but the latter needs to have a fast update.

[pgruenbacher]

well I extended your AgentKDTree to include hierarchical AABB for all the nodes. It's quite performant for agent ray-querying. I also tried a quick QuadTree spatial structure for the static obstacles and it was 5x slower than the ObstacleKDTree (which is really a BSP tree I think if my definition knowledge is correct). I wonder if i should I just use the ObstacleKDTree for visibility querying, but then use the uniform grid for agent <->obstacle proximity queries, since agents checking their obstacle proximity is used every step.

[curds01]

The ObstacleKDTree for visibility querying is precisely where the bug that I'm aware of is manifest. In the maze demo, a breakdown in the visiblity query would lead an agent to produce a path that attempted to walk through a wall.

Furthermore, I hate the kd-tree for obstacles. One of the artifacts of that abstraction is single line segments can get chopped into mulitple segments. This has various issues:

• Force-based agent models which would ordinarily see one wall and produce one force now see multiple walls and produce multiple forces (and the sum of those forces don't necessarily lead to the same resultant force.)
• This can lead to infinitesimally small walls (this may be the source of the visibility error).

For those reasons, I'd prefer some kind of BVH for the obstacles -- the obstacle primitives remain as they were specified and errors can be more directly tied to the specification and not under-the-hood bookkeeping. After all, the structures are optimizations -- they should merely allow me to arrive at the same answer faster and not produce different answers.

Now I'll get off my soapbox. :) (Can you tell I inherited that code?)

BTW: in the name of trivia: BSP trees don't require axis-aligned division of space, kd-trees do. But otherwise, you are correct in their similarity.

[pgruenbacher]

I think my plan to try is to make a high resolution uniform grid for agent and a high/coarse resolution grid for small/large obstacles respectively.

to speed up ray-marching queries on the grid, I could a) compute nearest obstacle distance for each grid position to speed up the marching steps or b) precompute distances at fixed angles. https://arxiv.org/pdf/1705.01167.pdf

[pgruenbacher]

that CDDT encoding above i attached is really interesting actually but very different use-case I think (storing ray sensor data of real-world environment).

[curds01]

That was my suspicion; they're using it for SLAM which is all about uncertainty. If there's inherently error in your sensor data and your algorithms are already introducing a safety buffer to account for that, then introducing some representation error can still keep the error within your buffer. I wondered how precise you needed your distance queries.