Jump to content
  • Advertisement
Sign in to follow this  
speciesUnknown

Pregenerating a list of cells in a spatial partioning system for each radius

This topic is 2478 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

I have a grid of cells in a spatial hash system. When I do queries involving a radius component, I first need to gather a list of all cells that fall within the given radius of the given point. To do this, I want to pregenerate adjacency matrices moving up to an arbitrary number of adjacent cells.


Here i s a diagram:
adjacency.png

If the centre point of the query lies somewhere in the red cell, it is possible for the query to fall into the orange cells, which is a simple adjacency list to hard code. However, if the radius is larger, it begins to fall into the next levels, for example, a query with a radius of 3 units could overlap with the purple set of cells. The matrix for this query would have to include fallbacks into the green, yellow, orange, and red cells also.

What I want is an algorithm which can pregenerate adjacency sets for the common radii. I'm currently planning on using something in the order of 256^2 cells, for queries having a diamater of up to 2048. Beyond that I'll find another solution, but that should be rare as nothing in the game should have that range or radius of interest. So, I need to pregenerate, to start with, adjacency lists for a radius of up to 4 units ( a radius of 1024, or a diameter of 2048).

Edit:
For the time being I'm just using a square with sides of diameter + 1, what I'm looking for is something that can snip off the corners.

edit:
You can tell Im not a mathematician. That should be diameter + 2.

Share this post


Link to post
Share on other sites
Advertisement
Hi!

Not sure whether I get your questions right. (It’s too late and I should definitely go to bed. smile.png)
I think you could precompute some sort of priority queue, by doing a breadth-first search. Starting from the center you use the breadth-first search to add the indices of the nodes to the priority queue that have a distance to the center smaller than radius r. The priority would be the distance to the center. You could keep a hash map telling you at which index a new radius in the priority queue begins. Then you iteratively increase the search radius and continue your breadth-first search until nothing else was found for the respective radius.

For your range queries you could simply traverse your priority queue until you reach the maximum index stored for your search radius in the hash-map. With this hash map you could also do range queries in a ring around the center (only for discrete search radii).
If you store the nodes relative to the center you can move the pattern like a filter around.

Is that what you’ve been looking for?
The data structure is not perfect for iterations in terms of performance, since the order of the nodes in the priority queue is in no way aligned to the layout of the memory.
Perhaps a better option would be to just store for each radius a list of start indices per row and a length of the row. Cache coherence would be much better, if you iterate this way. (You could find the indices by a breadth-first search, too, which means you can build up the data structure for an arbitrary number of radii in O(n)).

Cheers!

Share this post


Link to post
Share on other sites
What I want is an algorithm which can pregenerate adjacency sets for the common radii.[/quote]

What do you mean by common radii? Or do you mean all radii?

Since you're pregenerating this just once, why not just bruteforce it? You don't really care if it runs for a few minutes while you go get a drink, since the users of your games will never experience this.

Brute-force solution (roughly accurate):

1. For each cell in the given color matrix, (keep incrementing RADIUS in desired range)
|-- a. iterate from (cell_x - RADIUS, cell_y - RADIUS) to (cell_x + RADIUS, cell_y + RADIUS):
|----- i. check if the given coordinate satisfies the circle equation, i.e. (cell_x - point_x)^2 + (cell_y - point_y)^2 <= RADIUS^2. [1]
|----- ii. If yes, add the coordinate (point_x, point_y) to a temporary list.
|-- b. Add the list as the value in a temporary hash, with the key being the RADIUS value. This hash then becomes the value to a master hash with the key (cell_x + "," + cell_y).


You can use priority lists to keep the cell coordinates sorted by color if you want.

I'd just say keep this simple, since it's easy to get carried away for precomputing things and write unnecessarily elaborate solutions.

[1] http://en.wikipedia.org/wiki/Circle#Equations

Share this post


Link to post
Share on other sites

What I want is an algorithm which can pregenerate adjacency sets for the common radii.


What do you mean by common radii? Or do you mean all radii?

[/quote]
I mean some of the most common ones, so that I can pick the smallest one that encompasses my own and use that.


Since you're pregenerating this just once, why not just bruteforce it? You don't really care if it runs for a few minutes while you go get a drink, since the users of your games will never experience this.

[/quote]
I'll look at the circle equations section you linked. Thanks.



Brute-force solution (roughly accurate):

1. For each cell in the given color matrix, (keep incrementing RADIUS in desired range)
|-- a. iterate from (cell_x - RADIUS, cell_y - RADIUS) to (cell_x + RADIUS, cell_y + RADIUS):
|----- i. check if the given coordinate satisfies the circle equation, i.e. (cell_x - point_x)^2 + (cell_y - point_y)^2 <= RADIUS^2. [1]
|----- ii. If yes, add the coordinate (point_x, point_y) to a temporary list.
|-- b. Add the list as the value in a temporary hash, with the key being the RADIUS value. This hash then becomes the value to a master hash with the key (cell_x + "," + cell_y).


You can use priority lists to keep the cell coordinates sorted by color if you want.

I'd just say keep this simple, since it's easy to get carried away for precomputing things and write unnecessarily elaborate solutions.

[1] http://en.wikipedia....ircle#Equations
[/quote]

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!