P3: Grid Embedding

In this programming assignment, you will recreate the Grid Embedding tool described in A Case Study of Expressively Constrainable Level Design Automation Tools for a Puzzle Game Links to an external site.. Given a mission graph description such as the following, you should find a way to embed the grid into a 10-by-10 grid graph.

Example mission graph description:

type(a,splitter2).
type(b1,bender).
type(b2,bender).
type(c,combiner2).
graph_edge(a,b1).
graph_edge(a,b2).
graph_edge(b1,c).
graph_edge(b2,c).

Example result of embedding:

port(a,(0,lt),in) port(c,(0,lt),in) port(b2,(0,lt),in) port(c,(1,lt),in) port(b1,(1,lt),in) port(a,(0,gt),out) port(b1,(0,gt),out) port(a,(1,gt),out) port(c,(1,gt),out) port(b2,(1,gt),out) at(a,0,9) at(b1,0,9) at(b2,0,5) at(c,0,5) at(a,1,8) at(b1,1,7) at(b2,1,8) at(c,1,7)

Grading Criteria

A notebook is submitted containing an AnsProlog formulation (embedding.lp) that demonstrates passing the following sanity check cases (see details below):

[1 pt] st: 360, 90, 1800 (source/target only)
[1 pt] sbt: 240, 16200 (source/target/bender only)
[1 pt] tri: 0 (splitter2/combiner2/bender only)
[1 pt] quad: 8
[1 pt] paper: 1 (all types including blockers)

The formulation uses an efficient encoding (O(width) rather than O(width^2)) of the rule for checking if the coordinates of a piece are ordered on some axis. This will use a #sum expression with weights rather than directly comparing integers with an expression like X1 < X2.

[2 pts] efficient formulation

The notebook includes data wrangling logic to transform the JSON output of clingo into a DOT file that generates a PNG file with Graphviz.

[2 pt] An embedding of the paper scenario is visualized.
[1 pt] The visualization is nicely styled: Distractor pieces (with names starting with 'x') are displayed in gray, and all pieces are enclosed in a grid-rotationally symmetric shape such as a square or circle. Circles are pretty. The precise style details are up to you -- I just don't want to see an undifferentiated mass of white ovals.

Suggested Formulation

Create an AnsProlog file called embedding.lp starting with the following lines:

#const dimensions = 2.
#const width = 10.

Here are some suggested predicates to define. Each can be defined with a rule or two, potentially including an integrity constraint to enforce the semantics of the predicate. If the predicates are defined in the order given here, each predicate will only make use of predicates defined above it. Following this order isn't necessary, but it may help keep you focused.

Developing this formulation will take about 75 lines of code (depending on your commenting and whitespace style).

• axis(N)
  N is an integer 0..dimensions-1.
• ineq(Rel)
  Rel is an inequality relation either 'lt' or 'gt' (less-than or greater-than).
• dir((Axis,Rel))
  The pair defines a direction. The combination "axis 0, rel gt" might
  mean "horizontally increasing" or "to the right".
• opposite(D1,D2)
  D1 and D2 are opposite directions (same Axis, different Rel).
• ports(Type,Inputs,Outputs)
  This predicate provides a table mapping a type of piece to the number of
  input and output ports it should have. For Refraction, here's the table:
  source: 0 inputs, 1 output
  target: 1 input, 0 outputs
  bender: 1 input, 1 output
  splitter2: 1 input, 2 outputs
  splitter3: 1 input, 3 outputs
  combiner2: 2 inputs, 1 output
  combiner3: 3 inputs, 1 output
• type(P,T)
  Piece P has type T (where T is defined in the ports/3 table above). This predicate is defined in problem instances, not in the embedding rules.
• piece(P)
  P is some piece identifier. This is derivable from type/2 facts provided in
  individual problem instances.
• at(P,A,S)
  On axis A, piece P is on grid step S (S in 0..width-1).
  "at(0,s,4)" might mean "the piece called s has a horizontal coordinate of 4"
  Obviously, a piece can only be at one step on an axis at a time. Pieces should
  have a step for every axis. The nondeterministic definition of this predicate should use a choice rule.

-- With just the predicates above, you should be able to create a visualizer that confirms you can embed all of the pieces in a problem instance into the grid in a non-overlapping manner.

• piece_ports(P,Sense,Num)
  Piece P should have Num Sense-type ports (where Sense is 'in' or 'out').
  "piece_ports(s,out,1)" might say "the piece called s has one output port"
  Two rules for this predicate can be derived from type/2 and ports/3.
• port(P,D,S)
  Piece P in direction D has a port of Sense type.
  "port(s,(0,gt),out)" might mean "the piece called s has an output port pointed to the right"
  The nondeterministic definition of this predicate should use a choice rule.

Note: A direction may not be used as both an input and an output port. An integrity constraint should enforce this.

Note: If dimension>1, the output port of a bender must not be opposite the direction
of the input port (otherwise it doesn't bend!). An integrity constraint should enforce this.

• eq_coord(P1,P2,A)
  lt_coord(P1,P2,A)
  gt_coord(P1,P2,A)
  On axis A, P1 and P2 have equal coordinate values or coordinate values that are ordered less-than or greater-than. The rules for these predicate will depend on at/3.

The rules may be inefficiently implemented by getting the S1 and S2 steps for P1 and P2 on axis A and then directly comparing their values with =,<,>. This will create an O(width^2) term in the time/space required to ground the program, preventing the use of large grid widths. (When width=10, the cost is not bad.)

The rules may be more efficiently implemented by using a weight aggregate so that the #sum of S1 and -S2 can be compared to 0.

Note: Two distinct pieces P1 and P2 must not have equal coordinate values on every axis at the same time. This would mean the pieces are overlapping. An integrity constraint should enforce this.

• relative_dir(P1,P2,(A,Rel))
  The relative direction from P1 or P2 is described by a direction.
  The direction is defined by relative movement on one axis A.
  The pieces must have equal coordinate on all axes Ai other than A.
• portable(P1,P2,Dout)
  Piece P1 has an output port pointing the opposite direction of an input port on P2.
• blocked(P1,P2,D)
  Even though P1 is relative direction D from P2 and P1 is portable to P2 in that direction, the path is blocked by some other piece P such that P is D of P1 and P2 is D of P. (Requiring that P1 and P2 are portable here avoids wasted effort by the grouder considering all pairs of non-interactive asteroids in the roles of P1 and P2.) Because the rule for this predicate will involve three distinct pieces (P1,P,P2), it will cost O(pieces^3) time/space during grounding. This will likely dominate the total grounding cost for this project.
• grid_edge(P1,P2,D)
  P1 is relative direction D from P2, portable to it, and the way is not blocked. If P1 were to be powered, an beam would flow out of P1, in direction D, into a compatible port on P2. (The strength of laser powers is not modeled here, just the free paths a beam could take.)
• embedded_edge(P1,P2)
  There is a grid edge in some direction between P1 and P2.
• graph_edge(P1,P2)
  P1 and P2 are connected by a directed edge in the mission graph, and any embedding of this mission should contain a corresponding embedded edge. This predicate is defined in a problem instance, not in the embedding rules. However a constraint relating this predicate to embedded_edge/2 should certainly be in those rules.

Sanity Checking

instance-st.lp

#const include_edge = yes.
type(s,source).
type(t,target).
graph_edge(s,t) :- include_edge = yes.

Let's do some initial testing on a very simple world with a source and a target piece that should be connected.

If we don't include the edge and work in one dimension, there should be 10⋅9⋅2⋅2=360 solutions. That's 10 places to put the source, 9 places to put the target, 2 directions for the source output port and 2 directions for the target input port.

[st 360]
!clingo embedding.lp instance-st.lp -c dimensions=1 0 -c include_edge=no | grep Models
Models : 360

If we include the edge, there should be only 10⋅9=90 solutions because the pair of port directions are now fully determined by the positions of the pieces.

[st 90]
!clingo embedding.lp instance-st.lp -c dimensions=1 0 | grep Models
Models : 90

If we move up to two dimensions, we should get 2⋅10 copies of those 90 solutions (101 for each possible shift in the axis perpendicular to the laser and 2 to account for horizontal and vertical orientations), or 1800 total.

[st 1800]
!clingo embedding.lp instance-st.lp -c dimensions=2 0| grep Models
Models : 1800

instance-sbt.lp

type(s,source).
type(b,bender).
type(t,target).
graph_edge(s,b).
graph_edge(b,t).

Let's add a bender piece to make things interesting.

In one dimension we'll have 10⋅9⋅8 possible positions for which only 26 put the bender between the source and target. Thus, we expect 240 overall.

[sbt 240]
!clingo embedding.lp instance-sbt.lp 0 -c dimensions=1 | grep Models
Models : 240

Just one two-dimensional test here. In one dimension, we'll have 10 place to put the source, 9 places to put the bender, 10⋅2 ways to shift and rotate that picture, and finally 9 ways to place the target orthogonal to the input of the bender. Remember, benders must bend when there are more than one dimensions. So, thats 10⋅9⋅10⋅2⋅9=16200 expected solutions.

[sbt 16200]
!clingo embedding.lp instance-sbt.lp 0 -c dimensions=2 | grep Models
Models : 16200

instance-tri.lp

type(a,splitter2).
type(b,bender).
type(c,combiner2).
graph_edge(a,c).
graph_edge(a,b).
graph_edge(b,c).

Here's a tricky instance. This graph describes a triangle, but we can't express a triangle on the grid. It should be un-embeddable.

[tri 0]
!clingo embedding.lp instance-tri.lp | grep Models
Models : 0

instance-quad.lp

type(a,splitter2).
type(b1,bender).
type(b2,bender).
type(c,combiner2).
graph_edge(a,b1).
graph_edge(a,b2).
graph_edge(b1,c).
graph_edge(b2,c).

projection-grid.lp

#show grid_edge/3.

If we include another bender to the scenario above, we'll have a quadrilateral that we can embed into a rectangle on the grid. If we only count shapes at the level of the directions of edge on the grid (and not individual steps on the grid) there are 4 corners to put the splitter in and 2 ways to swap the positions of the benders. all other edge directions are determined by these. Together, we expect 4⋅2=8 distinct solutions under projection.

[quad 8]
!clingo embedding.lp instance-quad.lp projection-grid.lp --project 0 | grep Models
Models : 8

instance-paper.lp

type(src(1..2),source).
type(s2(1..2),splitter2).
type(b(1..7),bender).
type(c2(1..2),combiner2).
type(tgt(1..2),target).
type(xs2(1..5),splitter2).
type(xb(1..2),bender).
type(x(1..24),blocker).

graph_edge(src(2),s2(1)).
graph_edge(s2(1),s2(2)).
graph_edge(s2(1),b(7)).
graph_edge(b(7),c2(2)).
graph_edge(c2(2),b(5)).
graph_edge(b(5),b(6)).
graph_edge(b(6),tgt(2)).
graph_edge(s2(2),b(3)).
graph_edge(b(3),b(4)).
graph_edge(b(4),c2(2)).
graph_edge(s2(2),b(1)).
graph_edge(b(1),b(2)).
graph_edge(b(2),c2(1)).
graph_edge(src(1),c2(1)).
graph_edge(c2(1),tgt(1)).

This is almost the example mission graph used in A Case Study of Expressively Constrainable Level Design Automation Tools for a Puzzle Game Links to an external site.. The expander piece E2 was removed (expanders were dropped from the game design in Refraction 2).

DO NOT ATTEMPT TO PRINT ALL SOLUTIONS TO THIS PROBLEM! There are so many that your browser will quickly bog down and become unresponsive (and you won't be able to save your notebook).

[paper 1]
!clingo embedding.lp instance-paper.lp -q
SATISFIABLE
Models : 1+
Calls : 1
Time : 2.567s (Solving: 1.23s 1st Model: 1.23s Unsat: 0.00s)
CPU Time : 2.550s

(Note: With modest use of domain specific heuristics later, we could get the solving time for this instance down to less than 240ms. However, that would just make the grounding-time bottleneck more obvious.)

Visualization

Here's an example DOT file for an embedding of the "quad" problem instance. Note the use of the "pos" node attribute (including the bang "!") to manually position the nodes rather than letting the layout engine do it for you. Additionally, note the use of double quotes around the node names. For the node names involving parentheses in the "paper" problem instance, unquoted names will cause trouble.

digraph {
 "a" [pos="9,8!"];
 "c" [pos="5,7!"];
 "b1" [pos="9,7!"];
 "b2" [pos="5,8!"];
 "a" -> "b2";
 "b2" -> "c";
 "a" -> "b1";
 "b1" -> "c";
}