Generates two-dimensional map with paths ("2"s). The "1"s and "0"s - are blocks or walls

a_map_generator.js

// i and j current coordinates of the point
// a is two-dimensional array of points
// n is rows number
// m is columns number
// point is a number: 0 - free, 1 - block, 2 - path

// directions:
// 0 - left
// 1 - up
// 2 - right
// 3 - down

// free cell
var FREE = 0;
var BLOCK = 1;
var OCCUPIED = 2;

function exploreDirection(i, j, a, n, m) {
  if (i<0 || j<0 || i>=n || j>=m)
    return false;
  
  if (a[i][j] != FREE)
    return false;
  
  if (checkClusters(i, j, a, n, m))
    return false;
  
  else {
    // occupy point
    a[i][j] = OCCUPIED;
    
    var directions = generateDirection(i, j, a, n, m); 
    
    while (directions.length > 0) {
      // get direction and remove it from the list
      var r = randomDirection(directions, i, j, a, n, m, true);
      removeDirection(r, directions);
      // place block and remove direction
      var b = placeBlockAtRandomDirection(i, j, directions, a, n, m);
      removeDirection(b, directions);
      
      if (r == 0)
        exploreDirection(i, j-1, a, n, m, r);
      else if (r == 1)
        exploreDirection(i-1, j, a, n, m, r);
      else if (r == 2)
        exploreDirection(i, j+1, a, n, m, r);
      else if (r == 3)
        exploreDirection(i+1, j, a, n, m, r);
    }
    
    return true;
  }
}

// e is except (except specified direction)
function generateDirection(i, j, a, n, m) {
  var d = new Array();
  
  if (i<0 || j<0 || i>=n || j>=m)
    return d;
  
  if (j-1 >= 0 && a[i][j-1] == 0)
    d.push(0);
  
  if (i-1 >= 0 && a[i-1][j] == 0)
      d.push(1);
  
  if (j+1 < m && a[i][j+1] == 0)
    d.push(2);
  
  if (i+1 < n && a[i+1][j] == 0)
    d.push(3);
  
  return d;
}

// cc is checkClusters
// for random direction for the block we switch it off, as it can have clusters of "1"s
function randomDirection(directions, i, j, a, n, m, cc) {
  if (directions.length == 0)
    return -1;
  
  var min = 0;
  var max = directions.length-1;
  var index = Math.floor(Math.random() * (max - min + 1)) + min;
  
  return directions[index];
}

function placeBlockAtRandomDirection(i, j, directions, a, n, m) {
  if (i<0 || j<0 || i>=n || j>=m)
    return false;
  
  var r = randomDirection(directions, i, j, a, n, m, false);
  
  if (r == 0 && i-1 >= 0)
    a[i][j-1] = BLOCK;
  else if (r == 1 && j-1 >= 0)
    a[i-1][j] = BLOCK;
  else if (r == 2 && i+1 < n)
    a[i][j+1] = BLOCK; 
  else if (r == 3 && j+1 < m)
    a[i+1][j] = BLOCK;
  
  return r;
}

// directions are 0, 1, 2, 3
function removeDirection(r, directions) {
  if (directions.length == 0)
    return false;
  
  if (r < 0)
    return false;
  
  var index = directions.indexOf(r);
  if (index > -1) {
    directions.splice(index, 1);
  }
}

function checkClusters(i, j, a, n, m) {
  // for direction 0
  if ((i-1 >= 0 && j-1 >= 0 && a[i-1][j-1] == OCCUPIED && a[i-1][j] == OCCUPIED) 
      || (i+1 < n && j-1 >= 0 && a[i+1][j-1] == OCCUPIED && a[i+1][j] == OCCUPIED))
    if (a[i][j-1] == OCCUPIED)
      return true;
  
  // for direction 1
  if ((i-1 >= 0 && j-1 >= 0 && a[i-1][j-1] == OCCUPIED && a[i][j-1] == OCCUPIED) 
      || (i-1 >= 0 && j+1 < m && a[i-1][j+1] == OCCUPIED && a[i][j+1] == OCCUPIED))
    if (a[i-1][j] == OCCUPIED)
      return true;
  
  // for direction 2
  if ((i-1 >= 0 && j+1 < m && a[i-1][j+1] == OCCUPIED && a[i-1][j] == OCCUPIED) 
      || (i+1 < n && j+1 < m && a[i+1][j+1] == OCCUPIED && a[i+1][j] == OCCUPIED))
    if (a[i][j+1] == OCCUPIED)
      return true;
  
  // for direction 3
  if ((i+1 < n && j+1 < m && a[i+1][j+1] == OCCUPIED && a[i][j+1] == OCCUPIED) 
      || (i+1 < n && j-1 >= 0 && a[i+1][j-1] == OCCUPIED && a[i][j-1] == OCCUPIED))
    if (a[i+1][j] == OCCUPIED)
      return true;
  
  return false;
}

b_building_map_example.js

/***************************/
/***** Generate example*****/
/***************************/

var n = 10;
var m = 20;
var a = new Array(n);
for (i=0; i<n; i++)
  a[i] = new Array(m);

// fill array with 0
for (i=0; i<n; i++)
  for (j=0; j<m; j++)
    a[i][j] = 0;

// explore directions
exploreDirection(0, 0, a, n, m);

//printMap(a, n, m);
printHtmlMap(a, n, m);
console.log("has clusters: " + hasClusters(a, n, m));

function printMap(a, n, m) {
  for (i=0; i<n; i++) {
    str = "";
    for (j=0; j<m; j++) {
      str += a[i][j] + " ";
    }

    console.log(i + " - " + str);
  }
}

function printHtmlMap(a, n, m) {
  var html = "<table>"
  for (i=0; i<n; i++) {
    html += "<tr>";
    for (j=0; j<m; j++) {
      html += "<td>" + ((a[i][j] == 2)?"&#9632;":"&#9633;") + "</td>";
    }
    html += "</tr>";
  }
  
  console.log(html + "</table>");
}

function hasClusters(a, n, m) {
  count = 0;
  for (i=0; i<n-1; i++) {
    for (j=1; j<m; j++) {
      if (a[i][j-1] == 2 && a[i+1][j-1] == 2 && a[i+1][j] == 2 && a[i][j] == 2)
        count++;
    }
  }
  
  return count;
}