Hello GameDev.net. I've decided to make a GUI toolkit for fun. What I mean by a "GUI toolkit" is a library for creating windows, forms, and dialog boxes by combining elements such as buttons, labels, scroll-bars and checkboxes. But let's not focus on all that right now, what's important is what happens to the most basic element, a "frame", which is simply a rectangle of a given position and size.

I've encountered a design problem. Or maybe it's a math problem. I'm not sure.

I want to have several ways to change the position and size of the components:

The first is to statically set the size and position of an element.

The second is to click-and-drag the body or the edge of an element to change their position/size "by hand".

The third to tell the element to "set size to contents", where the element automatically shrinks or expands to exactly circumscribe all child elements.

The fourth is to set the size or position of an element as a percentage of parent element's size.

Additionally, an element may be moved around by it's parent to fit some additional constraint, for example "elements must be aligned horizontally without overlapping".

Each of these behaviors I have already coded and, individually, they work. The problems start when I try to make several of those to happen at the same time.

I do not know which order to "invalidate" elements in. By invalidating, I mean "tell the element to resize/reposition itself and reposition it's children in a way that all constraints are satisfied".

You probably see the problem by now. With so many dependencies/constraints, everything depends on everything! And since any element is only aware of the constraints that directly relate to it, by attempting to fix those constraints, it would break the constraints imposed on other elements. So I would have an infinite loop of things getting invalidated and then trying to fix themselves (this looks hilarious on the screen btw, you click on something and it just spirals out of control and flies beyond the edges of the screen).

Here's a very simple example: Frame A is a parent of Frame B. I initially set the size of both frames to 100. Then I tell A "size = to contents" and I tell B "size = 101% parent size". B would grow bigger, so A would grow bigger, so B would grow bigger, ad infinitum. Everything would freeze because two elements would play catch-up forever.

I think I have multiple circular dependencies. Or maybe a better way to look at this is like a system of N variables and M equations, and it's over-constrained.

TL;DR: My GUI elements have constraints on their relative positions and sizes and I don't know how to resolve them.

The best way I've seen to solve this kind of thing is two steps:

First, do a "how big do you want to be?" pass.
Second, do a "you are this big" pass.

And then you're done.

Since A is your root control, you ask it to measure how big it wants to be. It depends on its children, so it asks them the same question. B doesn't know, because it is relative to parent size, so it returns "infinite" (as in, I can take whatever size you want). A then says "I'm the same as B, so I return "infinite".

Your layout manager now knows that A (the only panel it knows about) can be any size it gives it. So now your layout manager determines some size to tell it to fit itself into (based on the size of the window, let's say) and tells A to size itself inside a 100x100 rectangle. A then tells B to size itself to a 100x100 rectangle, because A's size depends on B's size. So B says "Ok, I'm 101x101" (because it is 101% of the size it is told to be by its parent). Now A takes that size and sets itself to the size of the contents, 101x101.

And we're done.

If the person doing the UI layout didn't want that result, they shouldn't have done their UI layout in such a way that logically contradicts itself.

(Note, this is basically the method used by WPF's layout system, using the terms "Measure" and "Arrange")

I don't know, a two-pass system doesn't seem like it would really solve everything... I mean, wouldn't it essentially stop adjusting element positions before they stabilize, meaning they'd continue moving around the next time there was a new invalidation/layout pass for any reason?

I would like all the constraints to end up satisfied at the end of a frame, after all the layout passes are done. The two-pass approach looks like it would necessarily favor either "parent depends on child" or "child depends on parent" constraints, meaning, depending on the order of traversal, some constraints will be satisfied and some wont. Unless I don't really understand two-pass layouts and that sort of thing doesn't happen?

I imagine, since some sets of constraints are inherently unsatisfiable, maybe the GUI could forbid me from adding new constraints if doing so would render the whole system unsatisfiable...

How about this approach: I could make a helper class that would act as a "constraint system manager", and it's job would be to construct a dependency graph (element A depends on element B, element C doesn't depend on anything, etc), and it could ensure the system remains satisfiable if there are no circular dependency (i.e. no element in the graph is connected to itself). So when you try to add a new constraint, and that results in a loop in the graph, it would throw an error indicating that the constraints specified are impossible. Then, when one element's position or size changes, this manager would traverse the graph, starting at the element that was changed, and going in the direction of dependency until all elements that depend on this element are updated.

Would this be a good way to handle it or a bad way? Too complex / too much overhead? I mean, the whole problem would go away if I said something like "only child pos/size can depend on parents and not the other way around" but I really want to have cool, arbitrary relations so you can more easily express complex layouts with them.

Edit: Actually, my earlier points about the Two-Pass Layout may have been wrong. Reading about it more, my current understanding of the Two-Pass Layout system is that 1) during the Measure() pass, parent asks it's children for suggestions about what they want their positions and sizes to be; This is done recursively as they first ask the same question to their children. The suggested size is computed using only locally available information (i.e. "my parent, my children, my children's children, but not my neighbors or cousins or parent-of-parent"). 2) The parent assigns a size and position to it's children, and it is completely free to ignore those "suggestions" while doing so; This is also done recursively as once a child's position is set, it can not be changed. Then the child assigns positions and sizes to it's children, and so on.

What really bothers me is that NONE of the constraints seem to be guaranteed to be satisfied. It all looks like a bunch of suggestions that only get satisfied if you are lucky, and are only approximated in most other cases. I'm not sure why this doesn't seem to be a problem and doesn't cause wibbly-wobblyness of the GUI for programs currently made with WPF; Maybe they simply don't have any relations/constraints that could end up fighting each other like that?

What really bothers me is that NONE of the constraints seem to be guaranteed to be satisfied.

What you may be missing is guidelines into using your system. People generally don't add random things together and expect them to work by magic. I don't know the details of what you are doing, but I suspect each thing you have is useful, but only in some limited number of combinations with other things.

You are trying to make everything work with everything else in every combination, which is the hardest puzzle to solve. If you really want to do that, I would suggest reading about, or using, a constraint solver, as those systems are designed to do exactly what you are trying to achieve.

If you want a more DIY approach, perhaps you should first try to solve a smaller / simpler sub-set, and later try to extend.

Why don't you have a look at the code for QT

Bring a spork to jab out your eyes with. Qt's class interfaces are great, but their implementations are painful to read, at least to me (but I'm a noob when it comes to reading other peoples' codebases).