3

What is a good way to generate 2D asteroids (top down) that don't overlap with each other? If you can provide code in any language similar to C# or JAVA I'd be thankful.

Howard
  • 3,648
  • 13
  • 58
  • 86

3 Answers3

7

I believe what you're looking for is 2D Collision Detection. Here's a good article about it with working sample code.

EDIT: Based on what you've described, if you had each asteroid represented as a Rectangle, then you could simply check for Intersection:

  1. Generate an asteroid that's represented as a Rectangle.
  2. Check against a list of existing asteroids to see if it Intersects.
  3. If it Intersects, go to 1, otherwise add it to the list.

Obviously this isn't perfect since there could be corners that should be allowed to overlap, but it would be a fairly quick way of generating what you'd want (depending on how many asteroids you wanted to place).

EDIT 2: If you just want the code that checks for rectangular overlap, it can be found here.

Community
  • 1
  • 1
CAbbott
  • 8,078
  • 4
  • 31
  • 38
  • I don't need collision detection. I'm just trying to generate them in pseudo random xy positions. They're not even moving. – Howard Mar 30 '12 at 19:37
  • Actually you would still be doing collision detection. You could generate a position for an asteroid and then check to see if it collides (overlaps) with any other existing ones. – CAbbott Mar 30 '12 at 19:40
  • I see what you mean. Is there a way to generate the asteroid's xy positions without post processing? – Howard Mar 30 '12 at 19:43
  • I've updated my answer to reference an XNA Rectangle that has a built-in way to check for intersection. – CAbbott Mar 30 '12 at 20:00
0

Depends how complex you need and want to make the solution. If you want to place lots of objects then iterating and hit testing each time could get you into an infinite loop if there is no space (pardon the pun) left for another asteroid.

An alternative would be to store a data structure of all possible positions that are left that an asteroid can fit in to. This would be like a list of locations and would start as the full list. Eg if you had a simple 3 x 3 grid the start list would have 9 locations. You then choose a random item from the list and use it, then remove it and any other locations that have now become invalidated by that new asteroid. That way you can tell when you have no space left.

Maybe overkill but an interesting problem i thought - good luck!

davidfrancis
  • 3,734
  • 2
  • 24
  • 21
-1

Simple solution:

for i = 1 to 10
{
   X = rand();
   Y = rand();
   drawCircle(X,Y, radius);
}

Complex solution:
You'll have to give us more to go on.

Kelly S. French
  • 12,198
  • 10
  • 63
  • 93
  • 1
    The example code you provided will create overlaps. Basically I'm trying to generate non-overlapping asteroids. – Howard Mar 30 '12 at 19:59