starwing / amoeba Goto Github PK
View Code? Open in Web Editor NEWa Cassowary constraint solving algorithm implements in pure C.
License: MIT License
a Cassowary constraint solving algorithm implements in pure C.
License: MIT License
I see quite a few asserts here and there in the code. Does that mean that if for example the solver is overconstrained the program will crash and exit? Or if I try to remove a constraint which hasn't been added it will crash and exit?
I made a quite simple test of the constraint solver which tries to distribute nodes of the binary tree on the plane (like mentioned at the section 3.2 of the article written Cassowary authors).
And on adding "Unsatisfied" constraint the library causes "Assertion failed at amoeba.h line 935"
I created a gist with the test code:
https://gist.github.com/hsa-online/bd69ddb7147eb20d55ce7fc95faa80d5
P.S. When all constraints are "correct" solver seems to be working properly
I'm trying make a layout system for games and amoeba is really looking very nice for this role (C interface, small one header lib ๐ ), while I was doing simple layouts everything was fine, but when I moved to a grid layout I noticed constants asserts. After a few days of digging through my constraint generation code I started to suspect some issues with amoeba itself, and unfortunately it might be a case.
So a specific of grid layout is that whole grid cannot be smaller than min size of every cell, yet every cell depends on size of whole grid (flexible cells), this kinda creates cycling dependencies, and a whole strong point of cassowary algorithm is to circumvent around cycling dependencies.
Minimal repro case that I've figured out would be va = vb = vc = vd = va, last constraint is reported as unbound.
am_Solver * solver = am_newsolver(NULL, NULL);
am_Variable * va = am_newvariable(solver);
am_Variable * vb = am_newvariable(solver);
am_Variable * vc = am_newvariable(solver);
am_Variable * vd = am_newvariable(solver);
int ret = 0;
am_addedit(va, AM_STRONG);
// vb == va
{
ret = 0;
am_Constraint * c = am_newconstraint(solver, AM_REQUIRED);
ret |= am_addterm(c, vb, 1.0);
ret |= am_setrelation(c, AM_EQUAL);
ret |= am_addterm(c, va, 1.0);
ret |= am_add(c);
assert(ret == AM_OK);
}
// vb == vc
{
ret = 0;
am_Constraint * c = am_newconstraint(solver, AM_REQUIRED);
ret |= am_addterm(c, vb, 1.0);
ret |= am_setrelation(c, AM_EQUAL);
ret |= am_addterm(c, vc, 1.0);
ret |= am_add(c);
assert(ret == AM_OK);
}
// vc == vd
{
ret = 0;
am_Constraint * c = am_newconstraint(solver, AM_REQUIRED);
ret |= am_addterm(c, vc, 1.0);
ret |= am_setrelation(c, AM_EQUAL);
ret |= am_addterm(c, vd, 1.0);
ret |= am_add(c);
assert(ret == AM_OK);
}
// vd == va
{
ret = 0;
am_Constraint * c = am_newconstraint(solver, AM_REQUIRED);
ret |= am_addterm(c, vd, 1.0);
ret |= am_setrelation(c, AM_EQUAL);
ret |= am_addterm(c, va, 1.0);
ret |= am_add(c);
assert(ret == AM_OK); // asserts here
}
Similar thing implemented with https://github.com/nucleic/kiwi works, so either I'm missing something or is it really a bug? I would love to use this implementation :)
PS. This is how it looks with kiwi (used from python):
from kiwisolver import Solver, Variable
s = Solver()
a = Variable('a')
b = Variable('b')
c = Variable('c')
d = Variable('d')
s.addEditVariable(a, 'strong')
s.addConstraint(a == b)
s.addConstraint(b == c)
s.addConstraint(c == d)
s.addConstraint(a == d)
s.suggestValue(a, 2)
s.updateVariables()
print(a.value()) # all variables are 2
print(b.value())
print(c.value())
print(d.value())
I found another problem about a minute ago.
It's necessary to add to test.c after the code:
// Ycur = Yprev_row + 10
pC = am_newconstraint(pSolver, AM_REQUIRED);
am_addterm(pC, arrY[nCurrentRowFirstPointIndex + nPoint], 1.0);
am_setrelation(pC, AM_EQUAL);
am_addterm(pC, arrY[nCurrentRowFirstPointIndex - 1], 1.0);
am_addconstant(pC, 10.0);
nResult = am_add(pC);
assert(nResult == AM_OK);
These lines:
// Add these to test.c line 282
pC = am_newconstraint(pSolver, AM_REQUIRED);
am_addterm(pC, arrX[nCurrentRowFirstPointIndex + nPoint], 1.0);
am_setrelation(pC, AM_GREATEQUAL);
am_addconstant(pC, 0.0);
nResult = am_add(pC);
assert(nResult == AM_OK);
And it causes an access violation at amoeba.h line 289
P.S. I also found some strange situations when X-variables are became negative but still testing these ones.
I am looking into creating a wrapper around this api in Swift. I'm facing some difficult choices.
All variables are created using a solver and the solvers am_Allocf. This makes it hard to create an object oriented model as they are tied to the solver pretty closely. This is seen throughout the API as well. Example:
AM_API int am_add (am_Constraint *cons)
To me I now think it is not feasible to create an object oriented swift model around Amoeba unless variables, terms and constraints can be created independently from the solver.
Methods like
AM_API int am_add (am_Constraint *cons)
would have to be rewritten to
AM_API int am_add (am_Constraint *cons, am_Solver *solver)
This is not a request to change anything. I'm just thinking loudly :) amoeba.lua is not a wrapper, but the whole implementation written in Lua if I understand correctly?
I am using amoeba for a GUI framework, and I'm very happy with it. But there is one particular case that is failing for me.
The scenario is a splitter view that has left and right child views and a splitter bar that can be dragged left or right. The bar is constrained to always remain fully visible within the splitter view. The right child may have various hierarchical constraints, but its right edge is always constrained at or beyond the right edge of the splitter view. The left child has a fixed width of 256, but its left edge is unconstrained. (The splitter, left child, splitter bar, and right child each constrain their right edge to their left edge plus their width.)
The left edge of the splitter bar is the only thing that I change, and I do that with am_suggest(splitter_bar_l, pos)
.
Perhaps this is user error or perhaps I am missing something, but as far as I can tell, my constraints are entirely feasible.
In the attached code, if the #if 0
in line 75 is replaced by #if 1
, then the (enter.id != 0)
assertion in am_dual_optimize()
fails. I do not believe it should fail.
With #if 0
in line 75, I avoid the assertion failure, but amoeba insists on holding the left edge of the left child equal to zero instead of letting it equal the right edge minus 256. That should not happen because as I mentioned above, the left edge is unconstrained, apart from being offset from the right edge.
Can you help me understand what I am doing wrong, or how I should approach this problem? My actual scenario is more complex because the child views may contain all kinds of internal constraints, but the code that follows demonstrates the problem.
#include <stdio.h>
#include <stdarg.h>
#define AM_IMPLEMENTATION
#include "amoeba.h"
#define END 0
am_Constraint* new_constraint(am_Solver* in_solver, double in_strength, am_Variable* in_term1,
double in_factor1, int in_relation, double in_constant, ...) {
int result;
va_list argp;
am_Constraint* c;
assert(in_solver && in_term1);
c = am_newconstraint(in_solver, in_strength ? in_strength : AM_REQUIRED);
if(!c) return 0;
am_addterm(c, in_term1, in_factor1);
am_setrelation(c, in_relation);
if(in_constant) am_addconstant(c, in_constant);
va_start(argp, in_constant);
while(1) {
am_Variable* va_term = va_arg(argp, am_Variable*);
double va_factor = va_arg(argp, double);
if(va_term == 0) break;
am_addterm(c, va_term, va_factor);
}
va_end(argp);
result = am_add(c);
assert(result == AM_OK);
return c;
}
int main(int argc, const char * argv[]) {
double delta = 0;
double pos;
am_Solver* solver = am_newsolver(0, NULL);
am_Variable* splitter_l = am_newvariable(solver);
am_Variable* splitter_w = am_newvariable(solver);
am_Variable* splitter_r = am_newvariable(solver);
am_Variable* left_child_l = am_newvariable(solver);
am_Variable* left_child_w = am_newvariable(solver);
am_Variable* left_child_r = am_newvariable(solver);
am_Variable* splitter_bar_l = am_newvariable(solver);
am_Variable* splitter_bar_w = am_newvariable(solver);
am_Variable* splitter_bar_r = am_newvariable(solver);
am_Variable* right_child_l = am_newvariable(solver);
am_Variable* right_child_w = am_newvariable(solver);
am_Variable* right_child_r = am_newvariable(solver);
/* splitter_r = splitter_l + splitter_w */
/* left_child_r = left_child_l + left_child_w */
/* splitter_bar_r = splitter_bar_l + splitter_bar_w */
/* right_child_r = right_child_l + right_child_w */
am_Constraint* c1 = new_constraint(solver, AM_REQUIRED, splitter_r, 1.0, AM_EQUAL, 0.0,
splitter_l, 1.0, splitter_w, 1.0, END);
am_Constraint* c2 = new_constraint(solver, AM_REQUIRED, left_child_r, 1.0, AM_EQUAL, 0.0,
left_child_l, 1.0, left_child_w, 1.0, END);
am_Constraint* c3 = new_constraint(solver, AM_REQUIRED, splitter_bar_r, 1.0, AM_EQUAL, 0.0,
splitter_bar_l, 1.0, splitter_bar_w, 1.0, END);
am_Constraint* c4 = new_constraint(solver, AM_REQUIRED, right_child_r, 1.0, AM_EQUAL, 0.0,
right_child_l, 1.0, right_child_w, 1.0, END);
/* splitter_bar_w = 6 */
/* splitter_bar_l >= splitter_l + delta */
/* splitter_bar_r <= splitter_r - delta */
/* left_child_r = splitter_bar_l */
/* right_child_l = splitter_bar_r */
am_Constraint* c5 = new_constraint(solver, AM_REQUIRED, splitter_bar_w, 1.0, AM_EQUAL, 6.0, END);
am_Constraint* c6 = new_constraint(solver, AM_REQUIRED, splitter_bar_l, 1.0, AM_GREATEQUAL,
delta, splitter_l, 1.0, END);
am_Constraint* c7 = new_constraint(solver, AM_REQUIRED, splitter_bar_r, 1.0, AM_LESSEQUAL,
-delta, splitter_r, 1.0, END);
am_Constraint* c8 = new_constraint(solver, AM_REQUIRED, left_child_r, 1.0, AM_EQUAL, 0.0,
splitter_bar_l, 1.0, END);
am_Constraint* c9 = new_constraint(solver, AM_REQUIRED, right_child_l, 1.0, AM_EQUAL, 0.0,
splitter_bar_r, 1.0, END);
#if 0
/* This should be valid but fails the (enter.id != 0) assertion in am_dual_optimize() */
int strength1 = AM_REQUIRED;
int strength2 = AM_REQUIRED;
int width = 76;
#else
/* This mostly works, but still insists on forcing left_child_l = 0 which it should not */
int strength1 = AM_STRONG;
int strength2 = AM_WEAK;
int width = 76;
#endif
/* right_child_r >= splitter_r + 1 */
/* left_child_w = 256 */
am_Constraint* c10 = new_constraint(solver, strength1, right_child_r, 1.0, AM_GREATEQUAL, 1.0,
splitter_r, 1.0, END);
am_Constraint* c11 = new_constraint(solver, strength2, left_child_w, 1.0, AM_EQUAL, 256.0, END);
/* splitter_l = 0 */
/* splitter_r = 76 */
am_Constraint* c12 = new_constraint(solver, AM_REQUIRED, splitter_l, 1.0, AM_EQUAL, 0.0, END);
am_Constraint* c13 = new_constraint(solver, AM_REQUIRED, splitter_r, 1.0, AM_EQUAL, width, END);
for(pos = -10; pos < 86; pos++) {
am_suggest(splitter_bar_l, pos);
printf("pos: %4g | ", pos);
printf("splitter_l l=%2g, w=%2g, r=%2g | ", am_value(splitter_l),
am_value(splitter_w), am_value(splitter_r));
printf("left_child_l l=%2g, w=%2g, r=%2g | ", am_value(left_child_l),
am_value(left_child_w), am_value(left_child_r));
printf("splitter_bar_l l=%2g, w=%2g, r=%2g | ", am_value(splitter_bar_l),
am_value(splitter_bar_w), am_value(splitter_bar_r));
printf("right_child_l l=%2g, w=%2g, r=%2g | ", am_value(right_child_l),
am_value(right_child_w), am_value(right_child_r));
printf("\n");
}
(void) c1; (void) c2; (void) c3; (void) c4; (void) c5; (void) c6; (void) c7; (void) c8;
(void) c9; (void) c10; (void) c11; (void) c12; (void) c13;
return 0;
}
Can you add a license file for what you're licensing the code under?
There is a typo "clear_constrants" on lines with
AM_API void am_resetsolver (am_Solver *solver, int clear_constrants);
AM_API void am_resetsolver(am_Solver *solver, int clear_constrants) {
if (!clear_constrants) return;
I would like to ask the solver wether a variable is underconstrained or not. Maybe I can try to add a constraint for a variable and see if I get an error? Is there better ways?
Please add documentation for how to use the API.
I'd like to use amoeba as an external library in Smalltalk but don't know how to generate a DLL from the header file.
Is there a one line script for doing so with gcc or other C compiler?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.