map skeleton improved

#const min_segments_between_nodes = 1.
#const max_segments_between_nodes = 2.
#const min_road_segment_length = 1.
#const max_road_segment_length = 6.

% symbol:
% N = node index
% E = edge index (connection between nodes)
% R = road segment index (each edge has some number of horizontal/vertical segments)

%
% DEFINITION
%

% interior node - connected to at least 2 other nodes
interior_node(N) :- node(N), 2 { connected(N,_) }.
% leaf node - node that is only connected to one other node
leaf_node(N) :- node(N), not interior_node(N).

% edge index - ID of the connection between two nodes
edge_index(E) :- connection(E,N1,N2).
% allowed length of a segment
allowed_length(L) :- L=min_road_segment_length..max_road_segment_length.

% unique road segment index. this combines the edge ID and the segment ID.
seg_index(R) :- NE = #sum [ edge_index(E) ], R = 0..NE*(max_segments_between_nodes+1).
% road ID <=> (edge ID, segment index)
make_seg_index(E,S,R) :- seg_index(R), edge_index(E), S=0..max_segments_between_nodes, R = E*(max_segments_between_nodes+1) + S.

% whether two nodes are directly connected 
connected(N1,N2) :- connection(E,N1,N2).
connected(N2,N1) :- connection(E,N1,N2).

output_edge(N,E) :- connection(E,N,_).
input_edge(N,E) :- connection(E,_,N).

node_edge(N,E) :- input_edge(N,E).
node_edge(N,E) :- output_edge(N,E).

% the direction that the edge goes into this node.
direction_into_node(N,E,D) :- output_edge(N,E), make_seg_index(E,0,R), segment_direction(R,D).
direction_into_node(N,E,D) :- input_edge(N,E), edge_segments(E,ES), make_seg_index(E,ES-1,R), segment_direction(R,OD), opposite_direction(OD,D).

% map boundaries
axis(x;y).
dim(x, 0..width-1).
dim(y, 0..height-1).
cell(X,Y) :- dim(x,X), dim(y,Y).

border(x,0;width-1).
border(y,0;height-1).

border_at(X,Y) :- dim(x,X), border(y,Y).
border_at(X,Y) :- dim(y,Y), border(x,X).

% movement
step(-1;1).
step(0,-1;;0,1;;1,0;;-1,0).
adjacent(X,Y,X+SX,Y+SY) :- step(SX,SY), dim(x,X;X+SX), dim(y,Y;Y+SY).

% direction
direction(e;w;n;s).
turn_direction(e;w,n;s;;n;s,e;w).
opposite_direction(e,w;;w,e;;n,s;;s,n). 

% axis that should remain constant for a given direction (e.g. y axis for horizontal segments)
constant_axis_for_dir(e;w,y;;n;s,x).
varying_axis_for_dir(e;w,x;;n;s,y).

% direction of movement along varying axis for a given direction
move_dir(e,1;;w,-1;;s,1;;n,-1).

%
% each road has min_segments_between_nodes..max_segments_between_nodes vertices
%

first_edge_point(E,R) :- edge_index(E), make_seg_index(E,0,R).
last_edge_point(E,R) :- edge_segments(E,S), make_seg_index(E,S,R).

first_edge_segment(E,R) :- edge_index(E), make_seg_index(E,0,R).
last_edge_segment(E,R) :- edge_segments(E,S), make_seg_index(E,S-1,R).

previous_segment(R,PR) :- make_seg_index(E,I,R), I > 0, make_seg_index(E,I-1,PR).
next_segment(R,NR) :- previous_segment(NR,R).

% road segments that are connected to each other
segments_connected(R,R) :- seg_index(R).
segments_connected(R1,R2) :- previous_segment(R1,R2).
segments_connected(R1,R2) :- next_segment(R1,R2).
segments_connected(R1,R2) :- output_edge(N,E1), output_edge(N,E2), E1 != E2, first_edge_segment(E1,R1), first_edge_segment(E2,R2).
segments_connected(R1,R2) :- output_edge(N,E1), input_edge(N,E2), E1 != E2, first_edge_segment(E1,R1), last_edge_segment(E2,R2).
segments_connected(R1,R2) :- input_edge(N,E1), input_edge(N,E2), E1 != E2, last_edge_segment(E1,R1), last_edge_segment(E2,R2).
segments_connected(R1,R2) :- input_edge(N,E1), output_edge(N,E2), E1 != E2, last_edge_segment(E1,R1), first_edge_segment(E2,R2).

% a vertex of a connection
road_point(R) :- make_seg_index(E,I,R), edge_segments(E,S), I=0..S.
% a horizontal or vertical line segment of a connection
road_segment(R) :- make_seg_index(E,I,R), edge_segments(E,S), I=0..S-1.

% segments that should originate from the border of the map
border_road_segment(R) :- output_edge(N,E), border_node(N), first_edge_segment(E,R).
border_road_segment(R) :- input_edge(N,E), border_node(N), last_edge_segment(E,R).

% plot a road segment (axis, road ID, coord, length)
plot(Axis,R,Coord,0) :- segment_coord(Axis,R,Coord).
plot(Axis,R,Coord,Len) :- 
  segment_coord(Axis,R,Coord),
  segment_direction(R,Dir), varying_axis_for_dir(Dir,Axis),
  move_dir(Dir,CDelta),
  plot(Axis,R,Coord+CDelta,Len-1),
  allowed_length(Len), Len > 0.

% each road has 2+ vertices. The first vertex always starts at the output node's origin, and the last is constrained
% to end at the input node's origin.
segment_vertex(Axis,R,C) :- output_edge(N,E), first_edge_point(E,R), node_coord(Axis,N,C).

% constant axis for segment direction (i.e., the Y axis for a horizontal edge)
segment_vertex(Axis,R,C) :- road_point(R), dim(Axis,C),
  previous_segment(R,PrevR),
  segment_axis(PrevR,PrevAxis), Axis != PrevAxis,
  segment_vertex(Axis,PrevR,C), 
  segment_coord(Axis,PrevR,C).

% varying axis for segment direction (i.e., the X axis for a horizontal edge)
segment_vertex(Axis,R,C) :- road_point(R), dim(Axis,C),
  previous_segment(R,PrevR),
  segment_direction(PrevR,PrevDir), varying_axis_for_dir(PrevDir,Axis),
  segment_vertex(Axis,PrevR,PrevC), segment_length(PrevR,Len),
  plot(Axis,PrevR,PrevC,Len),
  move_dir(PrevDir,Delta),
  C = PrevC + Delta*Len.

% extrude segment area by one pixel to find adjacent segments
reserved_area(Axis,R,C+IC) :- segment_coord(Axis,R,C), dim(Axis,C+IC), IC=-1..1.

% segments adjacent on given axis that should not be directly adjacent
segments_adjacent(Axis,R1,R2) :- reserved_area(Axis,R1,C), segment_coord(Axis,R2,C), dim(Axis,C).

%
% GENERATE
%

% each node has an origin
1 { node_coord(Axis,N,C) : dim(Axis,C) } 1 :- node(N), axis(Axis).
node_origin(N,X,Y) :- node_coord(x,N,X), node_coord(y,N,Y).

% Each node connection has some number of segments
1 { edge_segments(E,S) : S=min_segments_between_nodes..max_segments_between_nodes } 1 :- edge_index(E).

% each segment moves along an axis, and each following segments swaps the axis
1 { segment_axis(R,A) : axis(A) } 1 :- edge_index(E), first_edge_point(E,R).
segment_axis(R,A) :- previous_segment(R,PR), segment_axis(PR,PA), axis(A), A != PA.

% each segment has a direction
1 { segment_direction(R,D) : varying_axis_for_dir(D,A) } 1 :- segment_axis(R,A).

% each segment has a length
1 { segment_length(R,L) : allowed_length(L) } 1 :- road_segment(R).

% each segment has some number of points
{ segment_coord(Axis,R,C) : dim(Axis,C) } :- road_segment(R).

% each road is potentially wide
road_wide(N1,N2,0..S) :- connection(E,N1,N2), edge_segments(E,S).

%
% TEST
%

% each node output should have a unique direction.
:- node_edge(N,E), node_edge(N,F), E != F, direction_into_node(N,E,D), direction_into_node(N,F,D).

% each segment needs a start/end vertex
:- road_point(R), axis(Axis), { segment_vertex(Axis,R,C) : dim(Axis,C) } 0.

% the road always ends at the destination node's origin
:- input_edge(N,E), last_edge_point(E,R), axis(Axis), node_coord(Axis,N,C), not segment_vertex(Axis,R,C).

% roads can't be adjacent to a road they aren't connected to.
:- segments_adjacent(x,R1,R2), segments_adjacent(y,R1,R2), not segments_connected(R1,R2).

% border nodes should have roads leaving the border
:- border_road_segment(R), segment_direction(R,D), constant_axis_for_dir(D,Axis), segment_vertex(Axis,R,C), border(Axis,C).

% ensure non-border leaf nodes are not on the border.
:- leaf_node(N), not border_node(N), node_origin(N,X,Y), border_at(X,Y).

% ensure border leaf nodes are on the border.
:- border_node(N), node_origin(N,X,Y), not border_at(X,Y).

%
% OUTPUT
%

road_vertex(N1,N2,I,X,Y) :- connection(E,N1,N2), make_seg_index(E,I,R), segment_vertex(x,R,X), segment_vertex(y,R,Y).

#hide.
#show node_origin/3.
#show road_vertex/5.
#show road_wide/3.
#show goal_placement/3.
#show edge_segments/2.