4
\$\begingroup\$

I am generating positions in a random fashion.

In the game world, instantiated elements have a radius, and shouldn't overlap.

The problem is that they will overlap because I use a usual random number generator combined with other fanciness. I can't use other random number generation algorithms where I can guarantee that the elements will never overlap.

A way to solve this is to use a spatial data structure and search for the nearest neighbors in that tree. When I insert an element into that tree, I update it accordingly.

This solution would do the work and it would be fast but my question is:

Is there a dedicated algorithm without that Tree implementation complexity which is faster than O(n²)?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This question makes very little sense. Why can't you use other RNG algorithms? Why can't you use the algorithm you know works and is fast? \$\endgroup\$
    – Steven Stadnicki
    Commented Jan 8, 2014 at 5:15

2 Answers 2

Reset to default
4
\$\begingroup\$

You already have the answer:

A way to solve this is to use a spatial data structure and search for the nearest neighbors in that tree. When I insert an element into that tree, I update it accordingly.

You need a tree data structure to actually get a better worst case using scenario, this will give you an O(log N) for nearest neighbor searches.

Grids on the other hand will still give you a better average solution, so you only need to check the adjacent cells, but this will not be as good as the tree structure.

I can also think of spatial hashing but am not particularly sure that a nearest neighbor problem can be solved and give a better performance that trees since I didn't try it myself. You can also check this wikipedia page for the common nearest neighbor search algorithms.

Regarding your number generation I want to point out to this article, that says that using your RNG or grid sampling won't give you points that really look naturally random (will be either too messy or too regular) and why you should use a Poisson point disk sampling instead.

enter image description here

http://devmag.org.za/2009/05/03/poisson-disk-sampling/

\$\endgroup\$
6
  • \$\begingroup\$ i know the solutions with the tree and i know jitered grid and poisson disc and variations. the question just was if there is an special algorithm to handle the neightbor problem without using a tree (as an add-hoc solution). Its actually a "is there a special algorithm for this special case" rather than "how can i realize it" \$\endgroup\$
    – Quonux
    Commented Jan 9, 2014 at 21:58
  • \$\begingroup\$ @Quonux check my edit. \$\endgroup\$
    – concept3d
    Commented Jan 9, 2014 at 22:12
  • \$\begingroup\$ the spartial hashing is actually a solution besides a complete tree, the time complexity for an access is theoretically O(1). A neightbor check is also simple to realize, thx, i hadn't think of that data-structure :) \$\endgroup\$
    – Quonux
    Commented Jan 9, 2014 at 22:23
  • \$\begingroup\$ "won't give you points that really look naturally random" actually I think the first image looks more natural (it looks like the night sky) although less uniformly distributed. I guess it depends on the use case which end result is more desirable. \$\endgroup\$
    – jhocking
    Commented Jan 20, 2014 at 13:38
  • \$\begingroup\$ @jhocking I think you are right. my wording wasn't particularly in-accurate, to be honest I couldn't find a better word. If you suggest a better wording I will edit it. \$\endgroup\$
    – concept3d
    Commented Jan 20, 2014 at 13:47
0
\$\begingroup\$

option 1 divide your area up into a grid and assign each object to a cell according to there position, now you only have to check the cell it is in and the neighbouring cells (those only if the new object gets close enough)

option 2 sort the objects according to 1 axis and then you can easily find all objects that overlap a certain interval on that axis (this breaks down in dimensions higher than 2 though)

\$\endgroup\$
1
  • \$\begingroup\$ Both of these are still O(n²) in the worst case, though considerably better on average than the naive approach. \$\endgroup\$
    – MooseBoys
    Commented Jan 8, 2014 at 1:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .