Is there a good way to, for instance, place a number of trees randomly 
without having them overlap?

Currently, I use an array to store the positions and compare each new 
tree to all the previous ones. This is however very slow.

I could also create a multi-dimensional B-tree array that divides the 
world into a grid, thereby reducing the number of items to look up. I 
wonder if that would speed things.


-- 
http://isometricland.com

Post a reply to this message

On 6/4/2010 3:45 PM, SharkD wrote:
> Is there a good way to, for instance, place a number of trees randomly
> without having them overlap?
>
> Currently, I use an array to store the positions and compare each new
> tree to all the previous ones. This is however very slow.
>
> I could also create a multi-dimensional B-tree array that divides the
> world into a grid, thereby reducing the number of items to look up. I
> wonder if that would speed things.
>
>


On second thought I don't think this will work because array sizes must 
be known beforehand, and with a B-tree sorting method there's no 
guarantee how many items a node will hold.

-- 
http://isometricland.com

Post a reply to this message

SharkD wrote:

> Is there a good way to, for instance, place a number of trees randomly 
> without having them overlap?

one possible way is to iterate over a grid of possible positions and
then deciding randomly or based on a distribution function whether this
particular cell should contain a tree. The actual tree position can
then be varied within the cell to avoid an obvious grid spacing.

Post a reply to this message

On 6/4/2010 4:27 PM, Christian Froeschlin wrote:
> SharkD wrote:
>
>> Is there a good way to, for instance, place a number of trees randomly
>> without having them overlap?
>
> one possible way is to iterate over a grid of possible positions and
> then deciding randomly or based on a distribution function whether this
> particular cell should contain a tree. The actual tree position can
> then be varied within the cell to avoid an obvious grid spacing.


Thanks, that sounds like it would work.

-- 
http://isometricland.com

Post a reply to this message

SharkD <mik### [at] gmailcom> wrote:
> Is there a good way to, for instance, place a number of trees randomly
> without having them overlap?
>
> Currently, I use an array to store the positions and compare each new
> tree to all the previous ones. This is however very slow.

I'd start with a halton sequence (I find myself using them everywhere...) and
seeing if it does a better job of not overlapping the trees:

#macro halton( index, base )
 #local out = 0.0;
 #local fraction = 1.0 / base;
 #local i = index;
 #while( i > 0 )
  #local remainder = mod( i, base );
  #local out = out + (fraction * remainder);
  #local i = int(i / base);
  #local fraction = fraction / base;
 #end

 out
#end

#macro halton2D( n )
 #local baseX = 2;
 #local baseY = 3;

 < halton( n, baseX ), halton( n, baseY ), halton( n, baseZ ) >
#end

You additionally take the values returned by the halton2D() macro, and test them
against a pigment function to decide whether to place a tree - this would give
you non-overlapping randomness on the small scale, and some clumping of trees on
the larger scale. My guess is that that would look quite natural, but you'd have
to give it a try to find out.

Cheers,
Edouard.

Post a reply to this message

"Edouard" <pov### [at] edouardinfo> wrote:

Opps - I mean:

#macro halton2D( n )
 #local baseX = 2;
 #local baseY = 3;

 < halton( n, baseX ), halton( n, baseY ), 0 >
#end

Post a reply to this message

On 6/4/2010 5:31 PM, Edouard wrote:
> "Edouard"<pov### [at] edouardinfo>  wrote:
>
> Opps - I mean:
>
> #macro halton2D( n )
>   #local baseX = 2;
>   #local baseY = 3;
>
>   <  halton( n, baseX ), halton( n, baseY ), 0>
> #end


Could you provide an example of how to use it? Thanks.

-- 
http://isometricland.com

Post a reply to this message

SharkD <mik### [at] gmailcom> wrote:
> On 6/4/2010 5:31 PM, Edouard wrote:
> > "Edouard"<pov### [at] edouardinfo>  wrote:
> >
> > Opps - I mean:
> >
> > #macro halton2D( n )
> >   #local baseX = 2;
> >   #local baseY = 3;
> >
> >   <  halton( n, baseX ), halton( n, baseY ), 0>
> > #end
>
>
> Could you provide an example of how to use it? Thanks.

I'll try!

The halton macro returns a number from 0..1, and halton2D() returns a vector
where the X is 0..1, Y is 0..1 and the Z = 0.

You call halton2D() with an incrementing integer, so it works best in a loop.

If you had a macro called PlaceTree(), you could loop through values from
halton2D calling the tree macro like this:

#declare n = 1;
#while( n < number_of_trees_wanted )
  #declare position = halton2D( n );
  // position is <0..1, 0..1, 0> - scale the vector here
  // to the size you need for PlaceTree
  PlaceTree( position )
  #declare n = n + 1;
#end

Does my explanation make sense?

Cheers,
Edouard.

Post a reply to this message

Edouard wrote:
> SharkD <mik### [at] gmailcom> wrote:
>> On 6/4/2010 5:31 PM, Edouard wrote:
>>> "Edouard"<pov### [at] edouardinfo>  wrote:
>>>
>>> Opps - I mean:
>>>
>>> #macro halton2D( n )
>>>   #local baseX = 2;
>>>   #local baseY = 3;
>>>
>>>   <  halton( n, baseX ), halton( n, baseY ), 0>
>>> #end
>>
>> Could you provide an example of how to use it? Thanks.
> 
> I'll try!
> 
> The halton macro returns a number from 0..1, and halton2D() returns a vector
> where the X is 0..1, Y is 0..1 and the Z = 0.
> 
> You call halton2D() with an incrementing integer, so it works best in a loop.
> 
> If you had a macro called PlaceTree(), you could loop through values from
> halton2D calling the tree macro like this:
> 
> #declare n = 1;
> #while( n < number_of_trees_wanted )
>   #declare position = halton2D( n );
>   // position is <0..1, 0..1, 0> - scale the vector here
>   // to the size you need for PlaceTree
>   PlaceTree( position )
>   #declare n = n + 1;
> #end
> 
> Does my explanation make sense?
> 
> Cheers,
> Edouard.
> 
> 
This is very useful! I see that the increasing integer eliminates the 
overlap of points.  Is there a relationship between the size of the 
object and the size of the increment that can be used to prevent 
objects intersecting?

Post a reply to this message

Jim Charter <jrc### [at] msncom> wrote:
> Edouard wrote:
> > SharkD <mik### [at] gmailcom> wrote:
> >> On 6/4/2010 5:31 PM, Edouard wrote:
> >>> "Edouard"<pov### [at] edouardinfo>  wrote:
> >>>
> >>> Opps - I mean:
> >>>
> >>> #macro halton2D( n )
> >>>   #local baseX = 2;
> >>>   #local baseY = 3;
> >>>
> >>>   <  halton( n, baseX ), halton( n, baseY ), 0>
> >>> #end
> >>
> >> Could you provide an example of how to use it? Thanks.
> >
> > I'll try!
> >
> > The halton macro returns a number from 0..1, and halton2D() returns a vector
> > where the X is 0..1, Y is 0..1 and the Z = 0.
> >
> > You call halton2D() with an incrementing integer, so it works best in a loop.
> >
> > If you had a macro called PlaceTree(), you could loop through values from
> > halton2D calling the tree macro like this:
> >
> > #declare n = 1;
> > #while( n < number_of_trees_wanted )
> >   #declare position = halton2D( n );
> >   // position is <0..1, 0..1, 0> - scale the vector here
> >   // to the size you need for PlaceTree
> >   PlaceTree( position )
> >   #declare n = n + 1;
> > #end
> >
> > Does my explanation make sense?
> >
> > Cheers,
> > Edouard.
> >
> >
> This is very useful! I see that the increasing integer eliminates the
> overlap of points.  Is there a relationship between the size of the
> object and the size of the increment that can be used to prevent
> objects intersecting?

Unfortunately not - all it does is generate numbers that have a distribution
that looks random, but have the property that they don't clump together. As you
generate more numbers, each new item fills a position that was empty, and as you
generate more and more numbers in the sequence, space gets filled denser and
denser.

If your objects aren't too closely packed, a halton sequence is a very easy
replacement for rand(), and may work well. I posted it mainly because it should
be very easy to try out for the problem described.

Cheers,
Edouard.

Post a reply to this message