CODEWITHSUNDEEP
algorithmrandom
confucius
confucius

Reputation: 13327

algorithm to generate random position for game object

I want to generate a position for objects in random manner and i don't want them to overlap with each other . my screen width is 4.8 meter and height is 9.6 meter and the object width is 0.5,and height is 0.5 meter .

can any one put me on the right direction ,or any suggestion .

regards

Upvotes: 3

Views: 2801

Answers (5)

Gerhard Powell
Gerhard Powell

Reputation: 6185

Option 1:

bool found = false;
real x;
real y;
do
{
    x = random * (4.8 - 0.5); // Rather make it variables
    y = random * (9.6 - 0.5);

    found = false;
    foreach (obj in objs)
    {
        if (x > obj.x && x < x+0.5 && y > obj.y && obj.y < y+0.5)
        {
             found = true;
             break;
        }
    }
}
while (found == true)

Option 2: Create a 2D array of that represent the sceen. Make the type a ref to the objects. As you put down, ref to the objects. You can then just check the array if there is a collision.

With the second option collision detection is much quicker, but it uses more memory.

Upvotes: 0

Michael Goldshteyn
Michael Goldshteyn

Reputation: 74420

Possible algorithm:

1. Choose random coordinates for all objects.
2. Test for overlap. If it occurs, repeat step 1.

Possible improvements:

1. Reposition overlapping objects with new random coordinates until there is no 
   overlap.
2. Shift any overlapping objects to make them not overlap. Do this intelligently 
   to avoid bunching, if necessary.

Upvotes: 4

Jim Mischel
Jim Mischel

Reputation: 134065

If you can live with your "random" object positions being on a grid, then you can divide the space into 0.5 meter by 0.5 meter squares and pick a square. Your world is 9.6 meters by 4.8 meters. So you have a grid that is 19 x 8.

Put all of the grid positions into a list. For each object that you want to place, randomly pick a grid position from the list and remove it from the list.

If you want to avoid the strict grid appearance, you can alter the x and y positions of your grid centers slightly (add a little here and there). Logically you still have a grid, but the appearance would be less regular.

Upvotes: 2

java lava
java lava

Reputation: 81

As Michael Goldshteyn suggests, testing for overlap and generate new coordinates if overlap occurs is a good solotion.

If you just have just a few objects you could store them in a list and for every new object test for overlap .

One way to test for overlaps may be to use a boolean array, representing each pixel on the screen. The lookup would be fast then.

Btw isn't a 9.6 meter screen a very big screen?

Upvotes: 0

Duck
Duck

Reputation: 401

You don't happen to mention your programming environment or language, but assuming a function random() that returns a random value between 0.0 and 1.0 and assuming that you position the object by the upper left corner, you could use the following formula:

x = random() * (screenWidth - objectWidth);
y = random() * (screenHeight - objectHeight);

I apologize, your post must have changed to read overlap each other. When I initialy read it, it read overlap the screen width/height.

Upvotes: 1

Related Questions