2

Anybody know of an efficient algorithm for moving rectangles in a square which contains obstacles?

Rectangles:

  • can rotate
  • can move/teleport
  • must not collide with obstacles (black squares)

Obstacles:

  • can't be moved
  • can be added anywhere

Goal: when obstacle is added, try to move rectangles so that they don't collide with any of obstacles.

State 1

State 2

State 3

State 4

State 5

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
redman
  • 2,115
  • 5
  • 32
  • 59
  • @Henk Holterman: yes, they can TelePort. The objective is to move them if you can or otherwise to return false (can't move them in the way they don't collide with obstacles). – redman Mar 26 '10 at 10:58
  • 1
    How? With teleport/moving them and rotation How often? Only when new obstacle is added Where? Somewhere on the field, the rectagles just must not collide with obstacles. Why? A battleship-like game, when you move your ships until you can - when you can move them anymore you leave them there and say hit to the opponent. – redman Mar 26 '10 at 11:15

1 Answers1

1

Take a look at this: Dynamic programming - Largest square block
Basically, given the rectangles, you add an obstacle, and remove the square that the obstacle interferes with.
Then, run the linked algorithm(with the "limiters" being the obstacles and existing squares), and if a place was found that can fit a square of NxN size (N is the large part of the rectangle), and add the rectangle).
This can be optimized a bit further, and I entrust you with doing so. (Basically - the rectangles won't always be put in the most optimal place. This can be remedied, at least to some degree)
This solution will give you O(n) time and space for each obstacle added.
Possible modification you should also look into: Don't rebuild the array for each obstacle, but build it for the void-of-obstacles array, and modify it as you go along. This will save going through the entire array for every single obstacle.

Community
  • 1
  • 1
Rubys
  • 3,167
  • 2
  • 25
  • 26