1-module(maze). 2-vsn('2002.0317'). 3-author('cpressey@catseye.mb.ca'). 4-copyright('Copyright (c)2002 Cat`s Eye Technologies. All rights reserved.'). 5 6%%% Redistribution and use in source and binary forms, with or without 7%%% modification, are permitted provided that the following conditions 8%%% are met: 9%%% 10%%% Redistributions of source code must retain the above copyright 11%%% notice, this list of conditions and the following disclaimer. 12%%% 13%%% Redistributions in binary form must reproduce the above copyright 14%%% notice, this list of conditions and the following disclaimer in 15%%% the documentation and/or other materials provided with the 16%%% distribution. 17%%% 18%%% Neither the name of Cat's Eye Technologies nor the names of its 19%%% contributors may be used to endorse or promote products derived 20%%% from this software without specific prior written permission. 21%%% 22%%% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 23%%% CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 24%%% INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 25%%% MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 26%%% DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27%%% LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, 28%%% OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 29%%% PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 30%%% OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 31%%% ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32%%% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33%%% OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34%%% POSSIBILITY OF SUCH DAMAGE. 35 36-include("maze.hrl"). 37 38-export([build/0, generate/1]). 39 40 41%%% BEGIN maze.erl %%% 42 43%%% A simple maze-drawing program. 44 45%% Driver function ----------------------------------------------------- 46 47build() -> 48 Tot = generate(#maze{}), 49 tot_print(Tot). 50 51%% Maze generation function -------------------------------------------- 52 53generate(#maze{}=M) -> 54 seed(), 55 {X, Y} = {random:uniform(M#maze.width div 2) * 2, random:uniform(M#maze.height div 2) * 2}, 56 57 R2 = tot_put(X, Y, tot_new(M#maze.width, M#maze.height, M#maze.wall), M#maze.space), 58 generate(M, R2, X, Y). 59 60generate(#maze{}=M, R, X, Y) -> 61 lists:foldl(fun({DX, DY}, A) -> 62 NX = X + DX * 2, NY = Y + DY * 2, 63 W = M#maze.wall, 64 case catch tot_get(NX, NY, A) of 65 W -> 66 M1 = tot_put(X + DX, Y + DY, A, M#maze.space), 67 M2 = tot_put(NX, NY, M1, M#maze.space), 68 generate(M, M2, NX, NY); 69 _ -> A 70 end 71 end, R, scramble([{-1,0}, {1,0}, {0,-1}, {0,1}])). 72 73%%% ToT (Tuple-of-Tuples) Utilities ------------------------------------ 74 75tot_new(W, H, Cell) -> 76 erlang:make_tuple(H, erlang:make_tuple(W, Cell)). 77 78tot_get(X, Y, Tot) -> 79 element(X, element(Y, Tot)). 80 81tot_put(X, Y, Tot, V) -> 82 setelement(Y, Tot, setelement(X, element(Y, Tot), V)). 83 84tot_print(ToT) -> 85 tot_print(1, ToT). 86tot_print(Y, ToT) when Y =< size(ToT) -> 87 tot_print_tuple(element(Y, ToT)), 88 io:fwrite("~n"), 89 tot_print(Y+1, ToT); 90tot_print(Y, ToT) -> ok. 91tot_print_tuple(T) -> 92 tot_print_tuple(1, T). 93tot_print_tuple(X, T) when X =< size(T) -> 94 io:fwrite("~s", [[element(X, T)]]), 95 tot_print_tuple(X+1, T); 96tot_print_tuple(X, T) -> ok. 97 98%%% Randomness Functions ----------------------------------------------- 99 100%% Seed the random number generator so that it will produce unpredictable 101%% values. Should be called once at startup, before using random numbers. 102 103seed() -> 104 {H,M,S} = time(), 105 random:seed(S,M,H), 106 random:uniform(23). % prime the pump - first number can be iffy 107 108%% Pick a random element from a tuple or a list (equal chance for every 109%% element.) 110 111pick(Tuple) when tuple(Tuple) -> 112 pick(tuple_to_list(Tuple)); 113pick(List) -> 114 lists:nth(random:uniform(length(List)), List). 115 116%% Mix up the order (shuffle or scramble) a tuple or list. 117 118scramble(Tuple) when tuple(Tuple) -> 119 list_to_tuple(scramble(tuple_to_list(Tuple))); 120scramble(List) -> 121 scramble(List, []). 122scramble([], Acc) -> Acc; 123scramble(List, Acc) -> 124 S = pick(List), 125 scramble(List -- [S], Acc ++ [S]). 126 127%%% END of maze.erl %%% 128