"moving furniture": collision resolution in 2d space (non-rotating shrinkable 2d rectangles)

Question

In 2d space we have a collection of rectangles.

Here's a picture:

Vertical line on the right is non-moveable "wall". Arrow on the left shows direction of movement. I need to move leftmost rectangle to the right.

1. Rectangles cannot rotate.
2. Rectangles are not allowed to overlap horizontally.
3. Rectangle can shrink (horizontally) down to a certain minimum width (which is set individually to each rectangle)
4. Rectangles can only move horizontally (left/right) and shrink horizontally.
5. Leftmost rectangle (pointed at by arrow) cannot shrink.
6. Widths and coordinates are stored as integers.

I need to move leftmost rectangle to the right by X units, pushing everything in its way to the right.

There are two problems:

1. I need to determine how far I can move leftmost rectangle to the right (it might not be possible to move for X units).
2. Move rect by X units (or if it is not possible to move by X units, move by maximum possible amount, smaller than X) and get new coordinates and sizes for every rectangle in the system.

Additional complications:

You cannot use Y coordinate and height of rectangle for anything, instead every rectangle has a list (implemented as pointers) of rectangles it will hit if you keep moving it to the right, you can only retrieve x coordinate, width, and minimum width. This data model cannot be changed. (technically, reppresenting this as a set of rectangles in 2d is simplification)

Important: Children from different levels and branches can have the same rectangle in the "potential collision" list. Here's initial picture with pointers displayed as red lines:

How can I do it?

I know a dumb way (that'll work) to solve this problem: iteratively. I.e.

1. Memorize current state of the system. If state of the system is already memorized, forget previously memorized state.
2. Push leftmost rect by 1 unit.
3. Recursively resolve collisions (if any).
4. If collision could not be resolved, return memorized state of the system.
5. If collisions could be resolved, and we already moved by X units, return current state of the system.
6. Otherwise, go to 1.

This WILL solve the problem, but such iterative solution can be slow if X is large. Is there any better way to solve it?

Answer 1

One possible solution that comes to mind:

You said that each rectangle holds pointers to all the objects it will hit when moving right. I would suggest, take the list of pointers from the big rectangle (the one pointed by the arrow), take all it's nodes (the rectangles it would collide), find the min width, then do the same of all the child nodes, add the widths for each branch recursively. Treat the problem like a tree depth problem. Every node has a min width value so the answer to your question would be the distance between the wall and the x value of the right edge of the big rectangle minus the GREATEST sum of the least width of the rectangles. Create a vector where the depth (sum of min widths) of each branch of the tree is stored and find the max value. Distance minus max is your answer.

imagine the same picture with 4 boxes. one to the left, one to the right and then the wall. lets name them box 1, box 2 (mid top), box 3 (mid bottom) and the last one box 4 (right). each box has a width of 4. all can shrink except the left one. box 2 can shrink by 2, box 3 can shrink by 1, box 4 can shrink by 2. Calculating the 2 branches gives * Branch 1 : 2 + 2 = 4 * Branch 2 : 3 + 2 = 5 * Only concerned with branch 2 because branch 1 is LESS than branch 2 hence will fit in the space parallel to branch 2and is available to shrink that much.