I’m working on a tool that will allow an end user to reposition rectangles on a design surface. It’s ultimate use is for the layout of industrial equipment, but it shares a lot of principles with Tetris or those puzzles where you slide squares. Here’s an image that shows a layout and how it might change as a user interacts with it.
In A, the user decides to move the blue rectangle up. In B, the blue rectangle has moved up and the red rectangle has dropped beneath it. In C, the user drags the red rectangle down. In D it is still moving down, but the purple rectangle has popped up above it (since the red rectangle intruded on its space). In E, the red rectangle has stopped moving and the green rectangle has also popped up above red rectangle.
The way I think about it is that there is always gravity pulling the rectangles down. As a rectangle is moved up and down, it may change its position in the stack, but the rectangles above and below will always be pulled down until they hit something that prevents them from moving any further.
There are a couple constraints:
The rectangles are always one or two units wide. I added some spacing to make the diagram easier to read, but the width of the blue, green, and purple rectangles will always be 1 and the red and gray rectangle will be 2.
The height of the rectangles vary and are not measured in whole units. A rectangle might be 1.4356 units high and another might be 0.78 units high.
The design is for a layout surface that is two units wide. However, I’m trying to come up with a solution that can be generalized for 1 to n units wide. Not a hard requirement, but a nice to have.
Rectangles that are more narrow than the layout area can be dragged into other columns. For example, the green rectangle could be dragged above the purple rectangle.
Here are my questions:
Is anyone aware of any algorithms or pieces of software that implement something similar? It’s a bit similar to the knapsack or stock cutting problem, but it adds the element of it being an editable layout. Any prior art on this sort of tool would be useful.
What data structure would you use to represent the rectangles positioned on the layout surface? The layout will be fed into a backend process, so a pure visual representation isn’t enough. If there is no better way, then I guess some sort of spatial representation could be used, but I’m thinking something more abstract (a graph, maybe?) might make more sense. I guess the representation in the layout tool could be different than what is fed into the backend, provided there was some easy way to convert between the two representations.
Any pointers on approaching this soft of algorithm functionally?
Ah, dashboard layouts. That’s a great analog. Most of the dashboard layout tools I’ve seen assume an even unit for height and width, but starting there and then generalizing for an arbitrary height might be the right start. Thanks!
Seems to me that there could be a pretty nice data structure, at least for the 2-column case, by splitting things into ‘rows’ and ‘columns’. A ‘row’ can either be a single wide block or two columns of narrow blocks side by side, and a full design is simply a list of ‘rows’, something like:
type alias BlockProperties =
{ id : Int
, height : Float
}
type WideBlock
= WideBlock BlockProperties
type NarrowBlock
= NarrowBlock BlockProperties
type Row
= SingleColumn WideBlock
| TwoColumns (List NarrowBlock) (List NarrowBlock)
type Design
= Design (List Row)
Then you could have operations like
moveBlockUp : Int -> Design -> Design
moveBlockDown : Int -> Design -> Design
moveBlockLeft : Int -> Design -> Design
moveBlockRight : Int -> Design -> Design
which would attempt to find a block with the given ID and then attempt to move it in the desired direction.
Your blocks are nodes in a tree. The grey block is the root.
So E would be:
root - red - green - blue
- magenta
Additionally, you may want to model which block is active, and whether it’s being dragged or settled. In your graphics, you indicated this with the arrow and the octagon. The corresponding type is a tree-zipper, and it’s a nifty data structure I recommend diving into. It cuts your tree into the part that leads to root (usually called the context) and the other branches that lead to the leaves, in you case upwards.
For implementation, I’d look at intersections while dragging, and then compare the y position of the intersecting blocks to know whether the dragging or the touched block will have to make way. “Making way”, in the context of a tree, of course means to move a node to a different spot and then, if nescessary, take over a branch…
Looks like a fun problem that nicely fits the elm type system
I like this a lot. My hunch is that a tree or a graph would be the best data structure. I’ll look into tree-zippers. I haven’t come across them before, but there’s such a rich history of tree data structures and algorithms that operate on them that I wouldn’t be surprised if this does the trick.
If you have a zipper, just travel to the root and apply your algorithm that expects a tree, then travel back to your focus. The advantage of the zipper is that the type system makes sure your focus is inside the tree. If you use the tree instead of the zipper, you have to make sure your paths are always inside the tree. But that’s feasible, too
