Random placement of objects on a track

Question

I am working on a simulation that requires an arbitrarily large amount of objects (100,000+) to be placed at random along a track, which is of an arbitrary shape.

In its simplest implementation, I started out using C++ and wrote a very naive function to place one node along the Track. In this case, the Track is a horizontal line with dimensions of 25 x 500. A node consists only of an X/Y coordinate and has dimensions of 5 x 5, so I wrote something like...

Node.x = rand()
Node.y = rand()
while (Node.x is not on the Track)
    Node.x = rand()
while (Node.y is not on the Track)
    Node.y = rand()

This very naive approach exemplifies what I need: a large amount of nodes to be instantiated at random locations along a track. I also tried having x and y be random numbers within the range of the track, but the track will be a random, complex, interconnected series of lines, such as a figure-8, a snaking line, a small square, a series of "islands", or the entire field. A node can NOT instantiate outside of the track.

What existing algorithms/methods can I use to instantiate these nodes on the track?

Answer 1

I think it would be best to pre-process your track in a way that maps an absolute position to some point on the track. This would probably mean taking each piece of the track and based on how it is defined, allocate a range of integers to that piece of track.

For instance, you might define the following segments of track:

• Line from point a to point b (Positions 0 through 100)
• Arc from point b to point c (Positions 101 to 200)
• Line from point c to point a (Positions 201 to 300)

When you create the random number, you figure out which segment of track it falls in and then based on how that segment is defined you figure out where on that segment it lands. If all of your segments have unique, non-overlapping ranges, you can then also keep a list of already placed nodes based on the random number to determine if something has already been placed in a given position. This would also support a branching track because it is totally based on the range of integers along a segment.

So using the above sample track, you would generate a random number between 0 and 300. If it comes up 105 for example, then you would look up that it is in the Arc segment and based on the definition of the arc you would determine that it is just off of point b along the arc.

If some basic sample code would help I can try to work some up at some point during the day today, but can't right now.

Answer 2

It all depends on how your track is represented. Let's assume it's represented as a list of "lines," and that the lines are really rectangles. Also, let's assume you want the objects placed uniformly by area. Here's what you can do:

Compute the area of all lines, just sum up width * height for all lines.
x = a random number between 0 and the total area.
For each line:
    if x < area of current line:
        place it in current line
        exit loop
    x = x - area of current line

That will tell you which line it should go in. Then you can use your existing algorithm.

If it's represented as a bitmap, you could just count the number of pixels that are traversable, then pick a number between 0 and that, and place the object at that pixel. By "traversable," you need to be able to place a 5x5 object there, i.e. the 5x5 pixels centered there need to all be "road."

Answer 3

First, it's best to parametrise your track with a single variable, let's say Node.position_along_the_track, choose "randomly" your nodes' positions according to that parameter, and then derive coordinates Node.x and Node.y from Node.position_along_the_track.

Second, you've got to define what "random" means in your case. Different simulations call for different distributions. For example, if you want to achieve random distances between consecutive objects on the track you should replace

Node.x = rand() 

with

Node.position_along_the_track = (rand() + PreviousNode.position_along_the_track) 
                                   % length_of_the_track