This is a tutorial that Leif Foged and I did for the AI summit at GDC on how to build your own finite-domain constraint solver using AC-3. It’s won’t solve the really hard problems that high-end SAT solvers can solve, but it’s very fast for problems with a lot of solutions; fast enough to run in a game engine:

http://www.cs.northwestern.edu/~ian/GDCConstraintsHowTo.pdf

Comments welcome. I intend to keep revising it, since it isn’t archivally published.

### Like this:

Like Loading...

*Related*

Hey, nice topic. I’m reading the paper but I’m not sure if there is a mistake or I’m not reading it right. You have the following:

newset = v.values & set

in the function

Narrow(v, set)

now, set = v \in v_i.values where v_i.values = v.values which means that the value of newset is set no matter what the values of the sets, v.values and set. Did you mean XOR? Or do I not understand what’s going on.

Thanks.

Good point. However, set won’t always be a subset of v’s current values. For example, if you have a propagate method that’s ensuring two variables x and y have different values and it notices that x has been narrowed to a single value, then it will narrow y to ~x.values (i.e. everything except x’s single value).

One could write it differently so that Narrow just updates v to be the set argument, but then in cases like the above, you need to remember always to manually intersect the new mask with the old values. Since doing the intersection is cheap, it makes more sense to do it automatically inside Narrow.

Ah, I see, yeah, I caught the reuse of the function later on. Should have kept reading.

I’m also not sure why every constraint contains a list of all variables? Is it not better to remove variables that have already been placed from the list or does this not make a difference in performance?

Does such a method work where the list of variables is infinite such as finding solutions to equations?

It’s just the variables that are involved in the constraint. So if you have a constraint like x = y+z, it would just be the variables x, y, and z. The constraint needs it so it knows what other variables to propagate to when one of the variables is narrowed.

Equations don’t generally have infinite numbers of variables, but the variables might have infinite numbers of possible values (again, x = y + z is an example). And no, this technique doesn’t work then. The tutorial is mostly just talking about “finite domain” solvers, and “finite domain” here means the set of possible values for the variables (their domains) is finite. And realistically, it also means the sets are small enough to be represented as a bitmask in a machine word.

The tutorial also talks briefly toward the end about how you can handle limited cases of floating-point variables by representing the current possible values for the variable using an interval (upper- and lower-bounds) rather than a bitmask. Our path function system uses that, although only in a very limited way. I’m working now on a system that has a much more general implementation of floating-point variables, although as with all this stuff, things get slow fast if you make the constraint solver work too hard. I ought to have a paper on it in time for the FDG conference.

Thanks, I think I understand now. Good luck with your submission.

I read the draft when it was first published and am finally getting around to implementing a solver in order to better understand it. I noticed that, Narrow, in the examples before the undo stack assigns the variable’s values attribute with newset. Yet in the “realish world” examples where you describe the Variable class I noticed that this line is missing and was wondering if that was intentional.

Nice work, btw. Really digging your work.

D’oh! Right you are. It’s fixed now. Do let me know if you see any other bugs or have any other questions. And thanks!