chromatic maze generator in ASP

chromatic-maze-generator.lp

%%%%
%%%% A chromatic maze generator
%%%%

% By Adam M. Smith (amsmith@soe.ucsc.edu)

% This answer set program was designed to work with the Potassco (the Potsdam
% Answer Set Solving Collection) tools, namely "clingo".

%% Chromatic Mazes

% In Daniel Ashlock's CIG 2010 paper "Automatic Generation of Game Elements via
% Evolution", the author defined Chromatic Mazes as a kind of maze where the
% passability between squares in a maze is represented only implicitly by the
% colors of the squares in the maze. Allowable moves can only be made between
% colors nearby on the color wheel.

%% Logically representing chromatic mazes

% This maze generator represents mazes with logical terms such as these:
%  - cell(red,0,0). cell(cyan,0,1). cell(magenta,0,2).
%  - start(5,0).
%  - finish(6,7).

% Visual reference: http://www.flickr.com/photos/rndmcnlly/4944422848/

%% Generating interesting mazes

% Following the inspiring paper, this generator aims to produce mazes with
% minimum solution lengths in a prescribed range. In a list of tweakable
% constants below, the total simulation timespan (measured in moves), and the
% allowable range of minimum solution lenghts can be varied. The side-length
% of mazes can also be easily modified.

% It is worth noting that mazes with the longest-shortest solutions are not
% actually all that interesting as mazes (as there isn't much room to get lost
% when nearly the entire board is filled with the snaking path of the shortest
% non-overlapping solution).

%% The ASP approach

% The approach taken by this generator is to specify an elementary grammar of
% possible maze designs and then to restrict this space with constraints on
% minimum solution length. Any ASP solver can then be used to efficiently
% generate example mazes from this design space.


%%%%
%%%% The actual generator starts here!
%%%%

%% Conventions for specifically named variables

#domain color(C).
#domain color(C1).
#domain color(C2).
#domain d(X).
#domain d(Y).
#domain d(SX).
#domain d(SY).
#domain t(T).
#domain t(T1).
#domain t(T2).

%% Values for shared constants

#const t_max = 35.
#const min_solution = 20.
#const max_solution = 35.
#const size = 6.

%% A range of space (d/1) and time (t/1) for the problem

d(0..size-1).
t(0..t_max).

%% Neighbor adjacency on the size-by-size grid

adjacent(X,Y,X+1,Y).
adjacent(X,Y,X-1,Y).
adjacent(X,Y,X,Y+1).
adjacent(X,Y,X,Y-1).

%% Theory of cycling colors displayable in the terminal

color(red;yellow;green;cyan;blue;magenta).

next(red,yellow).
next(yellow,green).
next(green,cyan).
next(cyan,blue).
next(blue,magenta).
next(magenta,red).

%% Allowable color transitions

ok(C,C).
ok(C1,C2) :- next(C1,C2).
ok(C1,C2) :- next(C2,C1).

%% Allowable steps considering adjacency and color

passable(SX,SY,X,Y) :-
        adjacent(SX,SY,X,Y),
        cell(C1,SX,SY),
        cell(C2,X,Y),
        ok(C1,C2).

%% Choice rules allowing the description of chromatic mazes

1 {  cell(Co,X,Y):color(Co) } 1.   % a color for every cell X,Y
1 {  start(Xp,Yp):d(Xp):d(Yp) } 1. % location of the start/entrance
1 { finish(Xp,Yp):d(Xp):d(Yp) } 1. % location of the finish/exit

%% A flood-fill style player exploration

% "Initially, the player is at the start."
player_at(0,X,Y) :- start(X,Y).

% "Thereafter, he can get somewhere at some time if he can get to another
% square the time before and that square is passable to this square. He will
% only do this if he has not already visited the square previously."
player_at(T,X,Y) :-
        T > 0,
        player_at(T-1,SX,SY),
        passable(SX,SY,X,Y),
        0 {player_at(0..T-1,X,Y)} 0.

%% The time of earliest completion

victory_at(T) :- player_at(T,X,Y), finish(X,Y).

%% That completion happened at all

victory :- victory_at(T).

%% Integrity constraints, requirements on all generated puzzles:

% "If it did occur, victory must have happened within the stated bounds."
:- victory_at(T), T < min_solution.
:- victory_at(T), max_solution < T.

% "Victory must always occur."
:- not victory.

%%%%
%%%% Visualization support logic
%%%%

% These declarations simply help an external program decide how to populate and
% color a termcolor'ed ascii-art depiction of the generated maze.

tile_grid(size,size).

tile_char(X,Y,T #mod 10) :- T > 0, player_at(T,X,Y), not start(X,Y), not finish(X,Y).
tile_char(X,Y,s) :- start(X,Y).
tile_char(X,Y,f) :- finish(X,Y).

tile_color(X,Y,C) :- cell(C,X,Y).

pretty.py

#!/usr/bin/python

import termcolor
import re
import sys

highlights = [arg.split(':') for arg in sys.argv if ':' in arg]

def print_plain(fact):
  print fact+'.'

def print_colored(fact):
  code = 'white'
  for prefix, color in highlights:
    if fact.startswith(prefix):
      code = color
  print termcolor.colored(fact+'.',code,attrs=['bold'])

if highlights:
  print_fact = print_colored
else:
  print_fact = print_plain

for line in sys.stdin.xreadlines():
    if line[0].islower():
        facts = line.split(' ')
        facts = map(lambda s: s.strip(), facts)
        facts.pop()
        facts.sort()
        map(print_fact, facts)
    else:
        print '% '+line.strip()

tile.py

#!/usr/bin/python
import re
import sys
import termcolor

tile_grid = re.compile(r"tile_grid\((\d+),(\d+)\)")
tile_char = re.compile(r"tile_char\((\d+),(\d+),([\w\d]+)\)")
tile_color = re.compile(r"tile_color\((\d+),(\d+),(\w+)\)")

size = (0,0)
contents = {}
colors = {}
for line in sys.stdin.xreadlines():

    if len(line) > 1 and not line.startswith('%') :
        fact = line.strip()
        grid_match = tile_grid.match(fact)
        if grid_match:
          wStr,hStr = grid_match.group(1,2)
          size = (int(wStr), int(hStr))

        char_match = tile_char.match(fact)
        if char_match:
           xStr,yStr,chStr = char_match.group(1,2,3)
           contents[(int(xStr),int(yStr))] = chStr

        color_match = tile_color.match(fact)
        if color_match:
           xStr,yStr,colorStr = color_match.group(1,2,3)
           colors[(int(xStr),int(yStr))] = colorStr

def format(x,y):
  loc = (x,y)
  sym = contents.get(loc,'.')
  color = colors.get(loc,'white')
  return termcolor.colored(sym,color)+' '

grid = "\n".join([''.join([format(x,y) for x in range(0,size[0])]) for y in range(0,size[1])])
print grid

usage.sh

time clingo chromatic-maze-generator.lp -n 1 --seed=$RANDOM  | ./pretty.py | ./tile.py

Example output here: http://www.flickr.com/photos/rndmcnlly/4944422848/