Jump to content
  • Advertisement

Object placement in O(1)

Recommended Posts

Today I started implementing Poisson Disc generator, however halfway through the implementation I realized this was not what I was using 5 years ago. First off, while I can implement this with a min and max radius, it doesn't help me fill in the void (so to speak) if I should generate a wrappable array from this data.

So, this is what I need to know the name of:

1. The algorithm probaby uses poisson-disc to start with

2. It then creates a power-of-2 sized array

3. It fills the array with radius-values, distanced so that if you access the array at any position modulo the array size, you can use lequal to know if you can place your object.

An example row: [1, 2, 3, 2, 1, 2, 6, 2, 1, 2, ...] <-- if i remembered the specifics I wouldnt be asking :)

4. This is O(1) because an object can be try_placed with `array(wrap(x), wrap(y)) < radius`

Anyone know the name of this procedure? Any help would be appreciated.

Edited by Kaptein

Share this post

Link to post
Share on other sites

If you have a dense 2D array where the values are the distance from the closest object (0 where objects are located) additional data is needed to place another object or prove there's no room left in constant time.

With the simplifying assumption that all objects have the same radius, you could instead maintain a set of all eligible placement positions (not too close to already placed objects).

If stored as a set of empty spans, line by line, placing an object requires choosing a random line with some room left, a random span on that line, and a random point in the span, then accessing nearby lines (inside the object radius) and, in each, creating at most one new span, updating one or two, and removing a number of spans proportional to the object's radius.

This would degrade a little because of binary search over the empty spans of a line, but the number of spans is tightly limited.

Edited by LorenzoGatti

Share this post

Link to post
Share on other sites

This is for try-placing objects, so no searching is necessary. For each position (x, z) in the world, read a seamless pre-computed array of radius-values and compare lequal against radius of object you're trying to place. This was 5 years ago, but I don't remember the details unfortunately. I ended up finishing the poison-disc generator and now my objects are try-placed properly in O(1), and seamlessly wraps around on the arrays. One (singular) array can't be used with many objects of many sizes, though, but I'll live.

The bottom line here is that I can't use my poisson-disc array to place both big and small objects interchangeably. Instead I would have to create two arrays to support two object sizes, or one array where the one object affects placements of other objects, which is also unwanted.

The primary reason for having something like this is just being able to use the same array to place any kind of size object from a single array shared across all threads.

Edited by Kaptein

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!