Listing 6.5. The Game of Life.
% Operator for separating row::column in square specifiers.
:- op(200, xfx, ::).
% Top-level predicates
% life(Max_R, Max_C, Live_Cells, Some_future_gen):
% Given a board with Max_R rows and Max_C columns,
% where Live_Cells is a list of Row::Column cell specifiers,
% Some_future_gen is some future generation of the board.
life(Max_R, Max_C, Live_Cells, Some_future_gen) :-
% you dont have to use sort if you make sure Initial_RCs is
% always in reading order.
sort(Live_Cells, Board),
future_gen(Board, Max_R, Max_C, Some_future_gen).
% A future generation is either this generation (in which
% case the board should be printed), or some future generation
% of the next generation.
future_gen(Board, Max_R, Max_C, Board) :-
printboard(Board, Max_R, Max_C).
future_gen(Board, Max_R, Max_C, New_Board) :-
next_gen(Board, Max_R, Max_C, Mid_Board),
!,
future_gen(Mid_Board, Max_R, Max_C, New_Board).
% printboard/3
printboard(Board, Max_R, Max_C) :-
printboard(Board, 1, Max_R, 1, Max_C).
% printboard/5
% Could be made more efficient if make use of reading order.
printboard(_Board, R, Max_R, _, _) :-
R > Max_R,
!.
printboard(Board, R, Max_R, C, Max_C) :-
C > Max_C,
!,
nl,
R1 is R+1,
printboard(Board, R1, Max_R, 1, Max_C).
printboard(Board, R, Max_R, C, Max_C) :-
( on(Board, R, C) ->
write( @) ;
write( .)
),
C1 is C+1,
printboard(Board, R, Max_R, C1, Max_C).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Basic engine
% Board, Adds, and Deletes are all lists of pairs R::C,
% ordered in reading order (top to bottom, left to right).
% next_gen/4:
next_gen(Board, Max_R, Max_C, New_Board) :-
updates(Board, 1, Max_R, 1, Max_C, Adds, Deletes),
updated_version(Board, Adds, Deletes, New_Board).
updates(_Board, R, Max_R, _C, _Max_C, Adds, Deletes) :-
R > Max_R,
!,
Adds = [],
Deletes = [].
updates(Board, R, Max_R, C, Max_C, Adds, Deletes) :-
C > Max_C,
R1 is R+1,
!,
updates(Board, R1, Max_R, 1, Max_C, Adds, Deletes).
updates(Board, R, Max_R, C, Max_C, Adds, Deletes) :-
number_of_neighbours(Board, R, C, N),
updates1(N, Board, R, C, Adds, Later_adds, Deletes, Later_deletes),
C1 is C+1,
updates(Board, R, Max_R, C1, Max_C, Later_adds, Later_deletes).
% 2 neighbours: do nothing.
updates1(2, _Board, _R, _C, Adds, Adds, Deletes, Deletes) :-
!.
% 3 neighbours, one already there: do nothing.
updates1(3, Board, R, C, Adds, Later_adds, Deletes, Later_deletes) :-
on(Board, R, C),
!,
Later_adds = Adds,
Later_deletes = Deletes. % unifs at end for efficiency
% 3 neighbours, none there right now: add.
updates1(3, _Board, R, C, [R::C|Later_adds], Later_adds,
Deletes, Deletes) :-
!.
% < 2 or > 3 neighbours, one there: delete.
updates1(_N, Board, R, C, Adds, Later_adds, Deletes, Later_deletes) :-
on(Board, R, C),
!,
Adds = Later_adds,
Deletes = [R::C|Later_deletes].
% < 2 or > 3 neighbours, none there: do nothing.
updates1(_N, _Board, _R, _C, Adds, Adds, Deletes, Deletes).
% Does a merge of 1st and 2nd args, ignoring deletes. Exploits
% the fact that all the lists are in reading order.
updated_version([], Adds, _Deletes, Adds).
% If first add is before first in board, use it first
updated_version([R::C|Board], [R1::C1|Adds], Deletes, New_Board) :-
(R1 < R ; (R1 = R, C1 < C)),
!,
New_Board = [R1::C1|New_Board1],
updated_version([R::C|Board], Adds, Deletes, New_Board1).
% Otherwise, try first in board, but if it is really to be deleted,
% the delete will be the first in the list of deletes
updated_version([R::C|Board], Adds, [R::C|Deletes], New_Board) :-
!,
updated_version(Board, Adds, Deletes, New_Board).
% Otherwise, use first in board.
updated_version([R::C|Board], Adds, Deletes, [R::C|New_Board]) :-
updated_version(Board, Adds, Deletes, New_Board).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Utilities
number_of_neighbours(Board, R, C, N) :-
sum_number_on(
[ (R-1)::(C-1),(R-1)::C,(R-1)::(C+1),
R ::(C-1), R ::(C+1),
(R+1)::(C-1),(R+1)::C,(R+1)::(C+1) ],
Board,
0,
N
).
sum_number_on([], _Board, Sofar, Sofar).
sum_number_on([Row::Col|Pairs], Board, Sofar, N) :-
R is Row,
C is Col,
( on(Board, R, C) ->
( Sofar1 is Sofar+1,
sum_number_on(Pairs, Board, Sofar1, N)
) ;
sum_number_on(Pairs, Board, Sofar, N)
).
% Requires R and C to be input; exploits the fact that the board
% is ordered in reading order.
on([R::C|_], R, C) :- % found it
!.
on([R::C1|Board], R, C) :- % same row, later column
C1 < C,
!,
on(Board, R, C).
on([R1::_C1|Board], R, C) :- % later row
R1 < R,
on(Board, R, C).
|