I remember playing this pencil and paper game as a kid and it served as a good past-time.
I’ve coded this game in Erlang, both Sequential and Concurrent. Below is the game output resulting from auto play.
- Core functions related to actual playing of the game: Set-up the game and players. Play one player at a time, manually. Functions used for manual play are:
dots/2, boxes/1, join/4. In case you want to render the game on screen, use draw/1.
-module (dots_and_boxes).
-export ([dots/2, boxes/1, join/4, draw/1, auto_play/3]).
-type point() :: {integer(),integer()}.
-type line() :: {atom(), point(), point(), boolean()}.
-type dots() :: [point()].
-type box() :: {atom(), [line()], string()}.
-type grid() :: [box()].
-spec dots(integer(), integer()) -> dots().
dots(XDots, YDots) ->
[{X,Y} || X <- lists:seq(0, XDots - 1), Y <- lists:seq(0, YDots - 1)].
-spec boxes(dots()) -> [box()].
boxes([]) -> [];
boxes(Ds) -> boxes(Ds, 1, length(Ds), []).
boxes(Dots, Begin, End, Bs) when Begin =< End ->
Dot = lists:nth(Begin, Dots),
BoxPts = box_points_for(Dot),
case all_present(BoxPts, Dots) of
true ->
B = {box, lines(BoxPts), []},
boxes(Dots, Begin + 1, End, [B | Bs]);
false ->
boxes(Dots, Begin + 1, End, Bs)
end;
boxes(_,_,_,Bs) -> lists:sort(Bs).
all_present(BoxPts, Pts) -> BoxPts -- Pts == [].
box_points_for(BottomLeft) ->
{X1, Y1} = BottomLeft,
BoxSize = 1,
X2 = X1 + BoxSize, Y2 = Y1 + 1,
BottomRight = {X2, Y1},
TopRight = {X2,Y2},
TopLeft = {X1,Y2},
[BottomLeft,TopLeft,TopRight,BottomRight].
lines([BottomLeft,TopLeft,TopRight,BottomRight]) ->
%clockwise lines in a box
[{line,BottomLeft,TopLeft,false},
{line,TopLeft,TopRight,false},
{line,TopRight,BottomRight,false},
{line,BottomRight,BottomLeft,false}].
-spec join(point(),point(),string(),grid()) -> {grid(), boolean()}.
% return pair contains a boolean to indicate
% take another turn for the last player.
join(D1, D2, Player, Grid) ->
NextG = [mark_box(B,D1,D2,Player) || B <- Grid],
{NextG, was_box_signed(Grid, NextG)}.
was_box_signed(PrevG, NextG) ->
PPs = [B || B <- PrevG, signed_box(B)],
NPs = [B || B <- NextG, signed_box(B)],
length(NPs) - length(PPs) == 1.
signed_box({box,_,P}) -> P /= [].
% 4 arg mark_box
mark_box(B = {box,Lines,[]}, D1, D2, Player) ->
PlayerLine = {line,D1,D2,false},
case contains(PlayerLine, Lines) of
true -> signBox(mark_box(D1,D2,B), Player);
false -> B
end;
mark_box(Box,_,_,_) -> Box.
signBox(MBox = {box,MLines,_}, Player) ->
case fourth_side_complete(MBox) of
true -> {box,MLines,Player};
false -> MBox
end.
% 3 arg mark_box
mark_box(D1, D2, {box,Lines,[]}) ->
MLines = lists:map(fun
({line,A,B,false}) when ((A==D1) and (B==D2)) -> join_dots(D1, D2);
({line,A,B,false}) when ((A==D2) and (B==D1)) -> join_dots(D2, D1);
(Line) -> Line
end, Lines),
{box,MLines,[]}.
contains(_, []) -> false;
contains(Line = {line,A,B,false}, [L|Ls]) ->
case L of
Line -> true;
{line,P,Q,false} when (A==Q) and (B==P) -> true;
_ -> contains(Line, Ls)
end.
fourth_side_complete({box,Lines,_}) ->
lists:all(fun({line,_,_,Marked}) -> Marked == true end, Lines).
join_dots({X,Y1}, {X,Y2}) when abs(Y2-Y1) == 1 ->
{line,{X,Y1},{X,Y2},true};
join_dots({X1,Y}, {X2,Y}) when abs(X2-X1) == 1 ->
{line,{X1,Y},{X2,Y},true};
join_dots(_, _) ->
badarg.
- Auto-play functions: Set-up the grid and players, call
auto_play/3 and watch the game run to completion. auto_play/3 uses draw/1 function.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% All Auto Play related functions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec auto_play([atom()], integer(), integer()) -> [any()].
auto_play(Players, XDots, YDots) when (XDots >= 2) and (YDots >= 2) and (length(Players) >= 2) ->
Grid = boxes(dots(XDots, YDots)),
% io:format("Initial Grid = ~p~n", [Grid]),
draw(Grid),
play(Players, Grid, fun() -> rand_dots_pair(XDots, YDots) end);
auto_play(_, _, _) ->
io:format("Choose more than 2 players and have number of dots in X and Y direction as atleast 2!~n").
play(Players, Grid, RandF) ->
case game_over(Grid) of
true -> show_results(Grid);
false -> continue_play(Players, Grid, RandF)
end.
continue_play(Players = [P|Ps], G, RandF) ->
io:format("~p playing...~n", [P]),
{NextG, SamePlayerTurn} = turn(P, G, RandF),
draw(NextG),
case SamePlayerTurn of
true ->
io:format("~p taking another turn!~n", [P]),
play(Players, NextG, RandF);
false ->
play(lists:append(Ps,[P]), NextG, RandF)
end.
show_results(Grid) ->
All = [{Winner, Score}|Losers] = results(Grid),
io:format("*** Game Over ***~n"),
case lists:keymember(Score, 2, Losers) of
true -> io:format("Game has Drawn!!~n");
false -> io:format("Winner => ~p~n", [Winner])
end,
io:format("Detailed Results: ~p~n", [All]).
results(Grid) ->
Ps = [P || {box,_,P} <- Grid],
Rs = frequency(Ps),
lists:reverse(lists:keysort(2, Rs)).
game_over(Grid) ->
lists:all(fun signed_box/1, Grid).
frequency(Xs) -> frequency(Xs, []).
frequency([], Acc) -> Acc;
frequency(Xs = [X|_], Acc) ->
{Ys,Ns} = lists:partition(fun(E) -> E == X end, Xs),
frequency(Ns, [{hd(Ys),length(Ys)} | Acc]).
turn(Player, Grid, RandomF) ->
{D1,D2} = RandomF(),
case line_not_exists(D1, D2, Grid) of
true -> join(D1, D2, Player, Grid);
false -> turn(Player, Grid, RandomF)
end.
line_not_exists(D1, D2, Grid) ->
Line = {line,D1,D2,false},
GLines = lists:foldr(fun({box, Lines, _}, A) -> lists:append(A, Lines) end, [], Grid),
contains(Line, GLines).
rand_dots_pair(XDots, YDots) ->
D1 = rand_dot(XDots,YDots),
D2 = rand_dot(XDots,YDots),
case distance(D1, D2) == 1 of
true -> {D1,D2};
false -> rand_dots_pair(XDots, YDots)
end.
distance({X1,Y1}, {X2,Y2}) ->
math:sqrt((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)).
rand_dot(XDots,YDots) -> {rand(XDots),rand(YDots)}.
rand(N) when N >= 2 -> rand:uniform(N) - 1.
- ASCII drawing related functions: This is the main function
draw/1 which consumes the grid to be drawn. The way it does this is by creating raster lines from grid data and renders it on screen as ASCII art. Game lines are partitioned as horizontal lines and vertical lines. For example – In a box, a horizontal line is one that joins two dots horizontally and a vertical line is on that joins two dots vertically. Rasterize renders the game with alternating horizontal and vertical lines. In the process, it also renders player initials (first 3-letters) inside a box, if that box belongs to the player.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% All drawing related functions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
rasterize(Grid) ->
GridLines = lists:flatmap(fun(B) ->
annotate_lines(B)
end, Grid),
Lines = lists:filter(fun({_,Aligned,_}) ->
Aligned /= vertical_left_ignore
end, GridLines),
{HLines,VLines} = lists:partition(fun({_, Aligned, _}) -> Aligned == horizontal end, Lines),
SortedHLines = lists:usort(HLines),
{{_,_,{X,Y},_},_,_} = lists:last(SortedHLines),
rasterize([], 0, 0, X, Y, SortedHLines, VLines).
rasterize(Acc, _, _, _, _, [], []) -> Acc;
rasterize(Acc, _, _, _, _, HLines, []) ->
lists:append(Acc, [[HLines,[]]]);
rasterize(Acc, X, Y, XMax, YMax, HLines, VLines) when (X =< XMax) or (Y =
{Hs,HLs} = lists:partition(
fun({{_,{_,Y1},{_,Y2},_},_,_}) ->
(Y1 == Y) and (Y2 == Y)
end, HLines),
{Vs, VLs} = lists:partition(
fun({{_,{_,Y1},{_,Y2},_},_,_}) ->
(Y == Y1) and (Y2 == (Y + 1))
end, VLines),
NewAcc = lists:append(Acc,[[Hs,lists:sort(Vs)]]),
rasterize(NewAcc,X+1,Y+1,XMax,YMax,HLs,VLs).
-spec annotate_lines(box()) -> [any()].
annotate_lines(B) ->
{box,[VLeft,HUpper,VRight,HLower],TakenBy} = B,
[
{sort_line(HLower),horizontal, []},
{sort_line(VRight),vertical_right, TakenBy},
{sort_line(HUpper),horizontal, []},
case VLeft of
{line, {0, _}, {0, _}, _} ->
{sort_line(VLeft),vertical_first_col, []};
_ ->
{sort_line(VLeft),vertical_left_ignore, []}
end
].
sort_line({line, D1, D2, Present}) when D1 > D2 ->
{line, D2, D1, Present};
sort_line(L) -> L.
draw(Grid) ->
% io:format("Grid = ~p~n", [Grid]),
RasterLines = rasterize(Grid),
% io:format("RasterLines = ~p~n", [RasterLines]),
lists:foreach(fun([RLines, CLines]) ->
draw_row_lines(RLines),
draw_col_lines(CLines)
end, RasterLines).
draw_row_lines(Lines) ->
lists:foreach(fun(Line) ->
case align(Line) of
horizontal -> io:format("+---");
horizontal_blank -> io:format("+ ")
end
end, Lines),
io:format("+~n").
draw_col_lines(Lines) ->
lists:foreach(fun(Line) ->
case align(Line) of
{vertical_blank, first_column} ->
io:format(" ");
{vertical, first_column} ->
io:format("|");
vertical_blank ->
io:format(" ");
vertical ->
io:format(" |");
{vertical, TakenBy} ->
io:format("~3s|", [TakenBy])
end
end, Lines),
io:format("~n").
align({Line, vertical_first_col, _}) ->
case Line of
{line,_,_,false} ->
{vertical_blank, first_column};
{line,_,_,true} ->
{vertical, first_column}
end;
align(LInfo = {_, vertical_right, TakenBy}) ->
case LInfo of
{{line,_,_,false},_,_} -> vertical_blank;
{{line,_,_,true},_,[]} -> vertical;
{{line,_,_,true},_,TakenBy} -> {vertical, TakenBy}
end;
align({Line, horizontal, _}) ->
case Line of
{line,_,_,false} -> horizontal_blank;
{line,_,_,true} -> horizontal
end.
- Generic functions: zip two lists using a function, transpose a matrix and find index of an item
The activities of playing a game and rendering are completely different and can happen in different processes. To that end, there are two server processes, one for playing the game, a.k.a. game_server and another for rendering the game as a text ui, a.k.a render_server.
In case any of the servers die, they are restarted by the supervisor. If a game_server dies all the clients associated with it die too (as the game server maintains games for all the clients and is thus carries state). However, if a render_server dies, no clients are affected and is also restarted by the supervisor.
Note: I’ve done Custom Server implementation, and next is Gen Server implementation that I plan to do next.
