maze.ii

// maze solver

// make a maze out of a "picture" of a maze.
//  '*' is a wall, 'S' is start, 'F' is finish, ' ' is a walk space.
//  no newlines or other characters allowed.
//  the array must have at least h strings each of at least w characters.
makeMaze(text:array[string], w:int, h:int):Maze

interface Maze {
	// solve the maze using the given algorithm
	solve(x:SolverAlgorithm)
	// put the maze back into unsolved form
	reset()
	// draw an ascii picture of the maze
	//   for a solved maze, there will be a trail marked through
	//   the maze if a solution is possible
	//   for an unsolved maze, or if no solution is possible,
	//   just draws the maze
	asText():array[string]
}

interface SolverAlgorithm {
	solve(m:MazeHelper)
}

interface MazeHelper {
	mazeWidth():int
	mazeHeight():int
	mazeStart():array[int]
	m(x,y:int):MazeBlock
}

interface MazeBlock {
	isWall():bool
	isFloor():bool

	isFinish():bool

	isMarked():bool
	mark(set:bool)
}

simpleSolver():SolverAlgorithm

maze.im

// Maze solver

uses conv.atos, conv.stoa

makeMaze(text:array[string], w:int, h:int):Maze =
	((new MazeImpl).init(text))

findStart(m:array[array[int]]):array[int] = (
	x:int = 0;
	y:int = 0;
	h:int = length m;
	w:int = length m[0];
	while (y < h) (
		while (x < w) (
			if (m[y][x] == 83 /*S*/) (
				rv:array[int] = new int[2](x);
				rv[1] = y;
				return rv;
			);
			x++;
		);
		x = 0;
		y++;
	);
	new int[2](0);
)


class MazeImpl implements Maze {
	m:array[array[int]]
	start:array[int]

	init(m_:array[string]):MazeImpl = (
		x:int = -1;
		y:int = -1;
		h:int = length m_;
		w:int = length m_[0];
		m = new array[int][h]( (y++;stoa(m_[y])) );
		start = findStart(m);
		this
	)

	reset() = (
		x:int = 0;
		y:int = 0;
		h:int = length m;
		w:int = length m[0];
		while (y < h) (
			while (x < w) (
				if (m[y][x] != 42 /***/ &
				    m[y][x] != 83 /*S*/ &
				    m[y][x] != 70 /*F*/)
					m[y][x] = 32; /* */
				x++;
			);
			x = 0;
			y++;
		)
	)

	asText():array[string] = (
		y:int = -1;
		new string[length m]( (y++; atos(m[y])) )
	)

	solve(s:SolverAlgorithm) =
		s.solve((new MazeHelperImpl).init(this))
}

class MazeHelperImpl implements MazeHelper {
	maze:MazeImpl

	init(maze_:MazeImpl):MazeHelperImpl = (maze = maze_; this)

	mazeWidth():int = length maze.m[0]

	mazeHeight():int = length maze.m

	mazeStart():array[int] = maze.start

	m(x,y:int):MazeBlock = (
		b:int = maze.m[y][x];
		if (b == 42)
			return wallBlock()
		else if (b == 83 | b == 70)
			return specialBlock(b==70)
		else
			return floorBlock(maze, x, y);
	)
}

wallBlock():MazeBlock = (new Wall).init()

specialBlock(isFinish:bool):MazeBlock = (new Special).init(isFinish)

floorBlock(m:MazeImpl, x:int, y:int):MazeBlock =
	(new Floor).init(m, x, y)

class Wall implements MazeBlock {

	init():Wall = this

	isWall():bool = true
	isFloor():bool = false

	isFinish():bool = false

	isMarked():bool = false
	mark(set:bool) = ()

}

class Special implements MazeBlock {
	finish:bool

	init(finish_:bool):Special = (finish = finish_; this)

	isWall():bool = false
	isFloor():bool = true

	isFinish():bool = finish

	isMarked():bool = false
	mark(set:bool) = ()
}

class Floor implements MazeBlock {
	m:MazeImpl
	x:int
	y:int

	init(m_:MazeImpl, x_:int, y_:int):Floor = (
		m = m_; x = x_; y = y_;
		this
	)

	isWall():bool = false
	isFloor():bool = true

	isFinish():bool = false

	isMarked():bool = m.m[y][x] != 32
	mark(set:bool) = (m.m[y][x] = (if (set) 46 else 32))
}

simpleSolver():SolverAlgorithm = (new SimpleSolver).init()

class SimpleSolver implements SolverAlgorithm {
	solved:bool

	init():SimpleSolver = this

	solve(m:MazeHelper) = (
		start:array[int] = m.mazeStart();
		solved = false;
		s(start[0], start[1], m);
	)

	s(x,y:int, m:MazeHelper) = (
		if (solved | x < 0 | y < 0 | x >= m.mazeWidth() |
			y >= m.mazeHeight()) return;
		b:MazeBlock = m.m(x,y);
		if (b.isFinish()) (
			solved = true;
			return;
		);
		if (b.isWall() | b.isMarked())
			return;
		if (!b.isFloor())
			return;
		b.mark(true);
		s(x-1, y, m);
		if (solved) return;
		s(x+1, y, m);
		if (solved) return;
		s(x, y-1, m);
		if (solved) return;
		s(x, y+1, m);
		if (solved) return;
		b.mark(false);
	)
}

maze_test.im

uses maze.Maze, maze.makeMaze, maze.simpleSolver, io.print

printArray(s:array[string]) = (
	h:int = length s;
	i:int = 0;
	while (i < h) (
		print(s[i]);
		print("\N");
		i++
	)
)

main(args:array[string]):int = (
	maze:array[string] = new string[15]("");

maze[ 0] = "**************************************************";
maze[ 1] = "*S              *                                *";
maze[ 2] = "** **  **  *  * * ************ ****     *   ***  *";
maze[ 3] = "*   ** *   *    *    *      ** *  ********       *";
maze[ 4] = "* *     **** *******   ****   *     *       ******";
maze[ 5] = "*   ** *** * **  *** * * * * ***  * **** ****    *";
maze[ 6] = "* ****               * * ****** *** *  * *    *  *";
maze[ 7] = "*   ********* ******** * *          * ** ******  *";
maze[ 8] = "*       *   * *        *   ********** *       *  *";
maze[ 9] = "*****   * * *** * * *  * *   *        * *** * * **";
maze[10] = "*   *** * * *   * ***  * *** *   *  ***** *** *  *";
maze[11] = "* *  *  * *     *   *  *   * * ***    *       *  *";
maze[12] = "***  **** ********* ******** * * ** * ********** *";
maze[13] = "*                 *                 *           F*";
maze[14] = "**************************************************";

	m:Maze = makeMaze(maze, length maze[0], length maze);

	m.reset();
	print("\N\NEmpty Board:\N");
	printArray(m.asText());
	m.solve(simpleSolver());
	print("\N\NSolved Board:\N");
	printArray(m.asText());
	0
)