Skip to content

Instantly share code, notes, and snippets.

@aman-tiwari
Last active May 29, 2020 17:35
Show Gist options
  • Save aman-tiwari/8a7b874cb1fd1270adc203b2af293f4c to your computer and use it in GitHub Desktop.
Save aman-tiwari/8a7b874cb1fd1270adc203b2af293f4c to your computer and use it in GitHub Desktop.
asp map generation with connectivity constraints
#const n = 5.
#const m = 5.
% define?
cell(1..m, 1..n).
% tiles, format:
% pdef((tile name, rotation in 90deg increments), bottom edge, right edge, top edge, left edge)
pdef((line_v, 0), empty, path, empty, path).
pdef((line_v, 1), path, empty, path, empty).
pdef((none,0), empty, empty, empty, empty).
pdef((plus,0), path, path, path, path).
pdef((corner,0), path, path, empty, empty).
pdef((corner,3), path, empty, empty, path).
pdef((corner,1), empty, path, path, empty).
pdef((corner,2), empty, empty, path, path).
pattern(P) :- pdef(P, _, _, _, _).
dx( 0, 1).
dx( 1, 0).
dx( 0,-1).
dx(-1, 0).
% any pattern can be placed on itself
legal(0, 0, P, P) :- pattern(P).
% P1 can be above P2 if P1's bottom edge and P2'
% top edge are connectable
legal(0, 1, P1, P2) :-
pdef(P1, E1, _, _, _),
pdef(P2, _, _, E2, _),
E1 == E2.
% P1 can be left of P2 if P1's right edge and P2's
% left edge are connectable
legal(1, 0, P1, P2) :-
pdef(P1, _, E1, _, _),
pdef(P2, _, _, _, E2),
E1 == E2.
% P1 can be below P2 if P1's top edge and P2's
% bottom edge are connectable
legal(0, -1, P1, P2) :-
pdef(P1, _, _, E1, _),
pdef(P2, E2, _, _, _),
E1 == E2.
% P1 can be right of P2 if P1's left edge and P2's
% right edge are connectable
legal(-1, 0, P1, P2) :-
pdef(P1, _, _, _, E1),
pdef(P2, _, E2, _, _),
E1 == E2.
% walkable means that it's possible to walk from
% p1 to p2 in direction (DX, DY)
walkable(0, 1, P1, P2) :-
pdef(P1, path, _, _, _),
pdef(P2, _, _, path, _).
walkable(1, 0, P1, P2) :-
pdef(P1, _, path, _, _),
pdef(P2, _, _, _, path).
walkable(0, -1, P1, P2) :-
pdef(P1, _, _, path, _),
pdef(P2, path, _, _, _).
walkable(-1, 0, P1, P2) :-
pdef(P1, _, _, _, path),
pdef(P2, _, path, _, _).
% there's an edge between two tiles if
% we can walk from that tile to the other
% (we'll use this to check for connectivity later)
edge((X1, Y1), (X2, Y2)) :-
assign(X1, Y1, P1),
assign(X2, Y2, P2),
walkable(X1- X2, Y1 - Y2, P1, P2).
edge(X,Y) :- edge(Y,X).
connected(X,Y):- edge(X,Y).
connected(X,Z):- edge(X,Y) ; connected(Y,Z).
% P1 can be left/below of P2 if P2 can be right/above P1
% legal(DX, DY, P1, P2) :- legal(-DX, -DY, P2, P1).
% two positions are adjacent if they are within cells and the difference
% in x and y is equal to dx and dy
adj(X1, Y1, X2, Y2, DX, DY) :-
cell(X1, Y1), cell(X2, Y2),
dx(DX, DY), (X1 - X2)==DX, (Y1 - Y2)==DY.
% generate?
1 { assign(X,Y,P):pattern(P) } 1 :- cell(X,Y).
% fail if two cells are adjacent and one of them is assigned P1 at X1 Y1
% but no legal assignment for X2 Y2 exists
:- adj(X1,Y1,X2,Y2,DX,DY), assign(X1,Y1,P1),
not 1 { assign(X2,Y2,P2):legal(DX,DY,P1,P2) }.
% every pattern must be present at least 1 times
:- pattern(P), not 1 { assign(X,Y,P):cell(X,Y) }.
% the top left corner and the bottom right corner must be connected
:- not connected((1, 1), (m, n)).
#show assign/3.
#show edge/2.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment