Jump to content
  • Advertisement
Sign in to follow this  
calculemus1988

What is the standard for neighbor agents search in games?

This topic is 2517 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In my game I need an agent to know its neighbors at all times. With simple grid-based space partitioning I manage to have 80 agents in the simulation that do Wander, Wall and Obstacle Avoidance steering behaviors and at the same time calculate their neighbors. Above 80 it gets nuts.

I have implemented Quad Trees before in non-game related context. So I will be able to implement things like that if you suggest so.

I dont know should I stick to grids for neighbors search or there are better methods out there?

Thanks

Share this post


Link to post
Share on other sites
Advertisement
Yes, you need some sort of space partitioning.
Depending on the use-case, the best choice would be an octree, a quadtree, Bounding Volume Hierarchy (BVH), KD tree, Bounding Interval Hierarchy (BIH) or a BSP tree. Generally speaking, either is fine, just go for the one you can get your hands on the fastest. If you can ignore one dimension (i.e. most of your world is flat and not a lot of people flying around), a quadtree will do the trick, else the octree or any of the other 3D space partitioning trees is a fine choice.

Share this post


Link to post
Share on other sites
Thank you for your quick answer. Yes my agents move mainly in XZ plane, so I guess I will go with quadtree. Should I expect drastic performance improvement compared to the grid method?

The grid method is basically you divide the world in cells, and you only search for neighbors in cells that intersect some bounding rectangle around your agent.

Share this post


Link to post
Share on other sites
The uniform grid is also a space partitioning method, and, given it's resolution does not give you trouble with memory or overly populated cells, it should be just fine. It is also the most simple approach to partitioning space. If you have bad performance, even with a uniform grid, there might be a bug in your code. Maybe you might want to profile it and find out what is making it so slow.
I remember the first time I touched OpenGL, I started watching the (sadly never updated) video tutorials at http://www.videotutorialsrock.com.
You might want to check out this particular bid: http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/home.php

Also, I recommend you to always first look online for data structure implementations before investing all the time of doing it yourself, saves you time and enables you to focus on the important parts :)

PS: Bounding rectangle? Usually you look for bounding spheres/circles, since the region of influence and perception of an entity usually has no corners.

Share this post


Link to post
Share on other sites
Yes I create a bounding rectangle in XZ around my agent and I test for intersection with cells. So you have rectangle-rectangle intersection tests. Then I only look for neighbors in those cells that intersect with the agent rectangle.

Here is the code, it is pretty easy http://pastebin.com/Zyd8Ynbt

Share this post


Link to post
Share on other sites
80 seems awfully low even for a brute force approach. I remember running flocking simulations with brute force neighbor search with close to 1000 agents at interactive rates. I found Grids are very good when done right and for a lot of use cases they are actually faster than quadtrees (i'm not sure why everyone is such a big fan of those anyway). How exactly does your grid approach work?

Share this post


Link to post
Share on other sites
http://pastebin.com/Zyd8Ynbt


Oh, I see. you are calculating the bounding box around the current agent and then test for all grid cells if they intersect that. That way you end up with a Agents*Gridcells complexity, which is even worse than bruteforcing when there are less objects than grid cells. But the point of a grid is that you can select the "candidate cells" directly without checking every single cell. You should calculate the start and end indices of the candidate grid cells from the agent bounding box (usually just by dividing by the grid spacing and rounding the result correctly).

Share this post


Link to post
Share on other sites
japro,

Here is my approach, well it is from the book Programming Game AI by Example.

1. Every agent updates his cell in his own Update call. That way every agent knows in which cell he is at all times.
2. Every agent updates his neighbors list on each Update call. I have posted the code for the function above, before your post.
To summarize, I only look for neighbors in those cells that intersect with the bounding rectangle of my agent. The size of that rectangle is basically how much you want the agent to see around him.

That is pretty much it. One thing to note is that things are ALREADY slow even without neighbors calculation. I have Wander, Obstacle and Wall Avoidance on my agents.

One improvement I can see is to look for neighbors only in nearby cells. I have 10x10 grid, that is 100 cells. Imagine every single agent at every frame, goes through ALL those cells to find which ones intersect with his rectangle, and then look for neighbors there.

I cant see other improvement than that for now. Let me know what you think.

EDIT: japro I just saw your post, we posted at the same time smile.png Thank you, I will fix this now.

Share this post


Link to post
Share on other sites

I manage to have 80 agents [...] Above 80 it gets nuts.
80 Agents should be perfectly fine. Are you sure it's not something else, or is this written in an interpreted language on an ultra-low-power handheld?

To do some math... brute forcing 80 distance calculations in the naivest way would be 80*79 = 6320 calculations. Exaggerating the absolutely worst case, one distance calculation takes, say, 20 cycles plus 500 cycles for memory access (assume we never get one cache hit on any of our data), so we're at 3286400 cycles. That's slightly over one millisecond on a single core of a typical desktop CPU. Realistically, the data for 80 agents will be entirely in L1 cache, so one would expect a few tens of microseconds.

That said, grids are in my opinion mighty fine beasts for spatial subdivision. They are dead simple, foolproof, and do the job. Also they have no "weird random" access patterns, which may make them competitive or possibly even faster than other solutions for large datasets. If you have too many agents, make the grid size smaller.

Share this post


Link to post
Share on other sites
japro I fixed that and I got from 80 now to 150 agents. Not bad but still bad :) I have Wander on all my agents, and I think that sucks the performance...

Now is a good time to try Unity's profiler.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!