#include <vector>#include <queue>#include <pair>#include <cassert>#include <cstdlib>// What a tile is. Silly numeric values, but we don't care.enum tile_type {  START = 33,  END = 77,  BORDER = 66  WALL = 22,  PASS = 55};// What a map is. We assume here that maps are always of fixed size. template<int Width, int Height>class map{  // The tiles inside the map. It is a private member, so we  // access its values using operator()  tile_type tiles[Width][Height];  public:   // Access a map tile as read/write  tile_type & operator()(int x,int y)   {    assert (x >= 0);    assert (x < Width);    assert (y >= 0);    assert (y < Height);        return this->tiles[x][y];  }    // Access a map tile as read-only  const tile_type & operator()(int x,int y) const  {    assert (x >= 0);    assert (x < Width);    assert (y >= 0);    assert (y < Height);        return this->tiles[x][y];  }    // A static function for returning a freshly initialized  // map.   static map setup_map()  {    map created;    generate_borders(created);    place_start_end(created);    compute_path(created);    return created;  }  private:  // Private implementation of the first step of map generation:  // we initialize a border around the map, and anything  // else to a wall.    static void generate_borders(map & where)  {    for (int x = 0; x < Width; ++x)      for (int y = 0; y < Height; ++y)      {        where(x,y) = WALL;        if (x == 0 || x == Width - 1 || y == 0 || y == Width - 1)          where(x,y) = BORDER;      }  }    // Private implementation of the second step of map generation:  // we place a "start" and "end" tile on our map.    static void place_start_end(map & where)  {    where(0,1) = START;    where(Width-1,Height-2) = END;  }    // Private implementation of the third step of map generation:  // we find a connex set of passable tiles which joins the start  // and end tiles.     // The algorithm consists in exploring the map from the  // top left corner. Each tile has a threshold value   // computed initially, which we use to determine which   // tile is computed next. Once we have reached the bottom  // right tile (and the exit), we cease exploration.    typedef std::pair<int,int> pos;    // The sole purpose of the thresholds is to compare the  // positions in the priority queue. So, we store them as  // part of a comparison structure between positions. So:  class comp  {    // Data    unsigned int tresholds[Width][Height];      public:      // Constructor    comp()    {      for (int x = 0; x < Width; ++x)        for (int y = 0; y < Height; ++y)        {          tresholds[x][y] = std::rand();        }          }        // Comparator    bool operator()(const pos & a, const pos & b) const    {      return (thresholds[a.first][a.second] < tresholds[b.first][b.second]);    }  };    static void compute_path(map & where)  {        // The priority queue is used to determine which wall should     // be turned into a passable element next. It is initialized with    // the top left element.        std::priority_queue<pos,std::vector,comp> candidates;    candidates.push(pos(1,1));        // Explore until we find the exit.    for(;;)    {      pos next = candidates.top();      candidates.pop();            int x = next.first, y = next.second;            // This tile has already been explored      if (where(x,y) == PASS) continue;            where(x,y) = PASS;            // We have reached the exit!      if (next = pos(Width-2,Height-2)) break;            // Otherwise, explore the adjacent tiles.       pos around[] = { pos(x-1,y), pos(x,y-1), pos(x+1,y), pos(x,y+1) };      for (int i = 0; i < 4; ++i)       {        // To determine if they are worth adding to the candidates        // (i.e. they have not been explored yet)        if (where(around.first,around.second) == WALL)        {          candidates.push(around);        }      }    }  }  }; // map<W,H> class

type tile = Wall | Pass | Border | Start | End(* Aspect of a single tile *)let aspect = function  | Wall | Border -> "#"  | Pass -> " "  | Start -> "S" | End -> "E"(* Print the obtained maze *)let print_maze =   Array.iter     (fun line ->       Array.iter (fun x -> print_string (aspect x)) line;       print_newline())(* Generate a new fixed-size maze *)let create_maze() =  let maze = Array.make_matrix 10 10 Border in    (* Step 1 *)  for x = 1 to 8 do     for y = 1 to 8 do      maze.(y).(x) <- Wall    done  done;    (* Step 2 *)  maze.(1).(0) <- Start;  maze.(8).(9) <- End;  (* Step 3 *)  let (put_slow,get_slow) = (* Slow exploration *)    let queue = Queue.create() in     (fun x -> Queue.push x queue),(fun () -> Queue.pop queue)  and (put_fast,get_fast) = (* Tendrils *)    let stack = Stack.create() in     (fun x -> Stack.push x stack),(fun () -> Stack.pop stack)   in     put_fast (1,1);    while maze.(8).(8) <> Pass do    let (x,y) = try get_fast () with Stack.Empty -> get_slow () in      maze.(y).(x) <- Pass;        (* Examine neighbors in random order *)    let neighbors =       List.sort         (fun _ _ -> Random.int 3 - 1)        [ (x+1,y); (x,y+1); (x-1,y); (x,y-1) ]            in List.iter      (fun (x,y) ->         if maze.(y).(x) = Wall then         if Random.int 10 > 0 then put_fast (x,y)         else put_slow (x,y))      neighbors;  done;    (* Return the obtained maze *)  maze    let _ = print_maze (create_maze ())