:- dynamic cell/2.
:- dynamic maze/3.
:- dynamic path/1.

maze_solve(Lig,Col) :-
	retractall(cell(_,_)),
	retractall(maze(_,_,_)),
	retractall(path(_)),

	% initialisation of the neighbours of the cells
	forall(between(0, Lig, I),
	       (   forall(between(0, Col, J), assert(maze(I, J, []))))),

	% creation of the window of the maze
	new(D, window('Maze')),
	forall(between(0,Lig, I),
	       (XL is  50, YL is I * 30 + 50,
		XR is Col * 30 + 50,
		new(L, line(XL, YL, XR, YL)),
		send(D, display, L))),

	forall(between(0,Col, I),
	       (XT is  50 + I * 30, YT is 50,
		YB is Lig * 30 + 50,
		new(L, line(XT, YT, XT, YB)),
		send(D, display, L))),

	SX is Col * 30 + 100,
	SY is Lig * 30 + 100,
	send(D, size, new(_, size(SX, SY))),
	L0 is random(Lig),
	C0 is random(Col),
	assert(cell(L0, C0)),
	\+search(D, Lig, Col, L0, C0),
	send(D, open),

	% we look for a path from cell(0, 0) to cell(Lig-1, Col-1)
	% creation of the entrance
	erase_line(D, -1, 0, 0, 0),

	% creation of the exit
	Lig1 is Lig-1,
	Col1 is Col-1,
	erase_line(D, Lig1, Col1, Lig, Col1),

	% seraching the path
	assert(path([[0, 0], [-1, 0]])),
	walk(Lig, Col),
	path(P),
	display_path(D, P).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
walk(Lig, Col) :-
	path([[L, C] | _R]),
	L is Lig - 1,
	C is Col - 1,
	retract(path(P)),
	assert(path([[Lig, C]|P])).

walk(Lig, Col) :-
	retract(path([[L, C] | R])),
	maze(L, C, Edge),
	member([L1, C1], Edge),
	\+member([L1, C1], R),
	assert(path([[L1,C1], [L, C] | R])),
	walk(Lig, Col).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
display_path(_, []).

display_path(D, [[L, C] | R]):-
	new(B, box(10,10)),
	send(B, fill_pattern, new(_, colour(@default, 0,0,0))),
	X is C * 30 + 60,
	Y is L * 30 + 60,
	send(D, display, B, point(X,Y)),
	display_path(D, R).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
search(D, Lig, Col, L, C) :-
	Dir is random(4),
	nextcell(Dir, Lig, Col, L, C, L1, C1),
	assert(cell(L1,C1)),
	assert(cur(L1,C1)),

	retract(maze(L, C, Edge)),
	assert(maze(L, C, [[L1, C1] | Edge])),
	retract(maze(L1, C1, Edge1)),
	assert(maze(L1, C1, [[L, C] | Edge1])),

	erase_line(D, L, C, L1, C1),
	search(D, Lig, Col, L1, C1).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
erase_line(D, L, C, L, C1) :-
	(   C < C1 -> C2 = C1; C2 = C),
	XT is C2  * 30 + 50,
	YT is L * 30 + 51, YR is (L+1) * 30 + 50,
	new(Line, line(XT, YT, XT, YR)),
	send(Line, colour, white),
	send(D, display, Line).

erase_line(D, L, C, L1, C) :-
	XT is  51 + C * 30, XR is 50 + (C + 1) * 30,
	(   L < L1 -> L2 is L1; L2 is L),
	YT is L2 * 30 + 50,
	new(Line, line(XT, YT, XR, YT)),
	send(Line, colour, white),
	send(D, display, Line).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nextcell(Dir, Lig, Col, L, C, L1, C1) :-
	next(Dir, Lig, Col, L, C, L1, C1);
	(   Dir1 is (Dir+3) mod 4,
	    next(Dir1, Lig, Col, L, C, L1, C1));
	(   Dir2 is (Dir+1) mod 4,
	    next(Dir2, Lig, Col, L, C, L1, C1));
	(   Dir3 is (Dir+2) mod 4,
	    next(Dir3, Lig, Col, L, C, L1, C1)).

% 0 => northward
next(0, _Lig, _Col, L, C, L1, C) :-
	L > 0,
	L1 is L - 1,
	\+cell(L1, C).

% 1 => rightward
next(1, _Lig, Col, L, C, L, C1) :-
	C < Col - 1,
	C1 is C + 1,
	\+cell(L, C1).

% 2 => southward
next(2, Lig, _Col, L, C, L1, C) :-
	L < Lig - 1,
	L1 is L + 1,
	\+cell(L1, C).

% 3 => leftward
next(2, _Lig, _Col, L, C, L, C1) :-
	C > 0,
	C1 is C - 1,
	\+cell(L, C1).