迷路生成

maze.pde

import java.util.*;

static final int h = 50, w = 50;

static final int MA = 10;
static final int S = 20;
static final int TH = h*S+MA;
static final int TW = w*S+MA;
static final int MH = TH+1+MA;
static final int MW = TW+1+MA;
static final int[] di = {-1,0,1,0};
static final int[] dj = {0,-1,0,1};

int rand(int n) { return int(random(n));}


void settings() {
  size(MH, MW);
}

void setup() {
  background(255);
  noLoop();
}

static final int hs = h*2+1, ws = w*2+1;
static final int n = hs*ws;
boolean[][] s = new boolean[hs][ws];

int[] uf = new int[n];
int root(int v) {
  if (uf[v] == -1) return v;
  uf[v] = root(uf[v]);
  return uf[v];
}
boolean unite(int a, int b) {
  a = root(a);
  b = root(b);
  if (a == b) return false;
  uf[a] = b;
  return true;
}

void gen_stick() {
  for (int i = 1; i < hs-1; i++) {
    for (int j = 1; j < ws-1; j++) {
      if (i == 1) s[i][j] = false;
      if (j == 1) s[i][j] = false;
    }
  }
  for (int i = 2; i < hs-1; i += 2) {
    for (int j = 2; j < ws-1; j += 2) {
      if (rand(2) == 0) {
        s[i+1][j] = false;
      } else {
        s[i][j+1] = false;
      }
    }
  }
}

void gen_uf() {
  for (int i = 0; i < n; i++) uf[i] = -1;
    int m = h*w-1;
  while (m > 0) {
    int i = rand(hs-2)+1;
    int j = rand(ws-2)+1;
    if (!s[i][j]) continue;
    if ((j&1) == 1) {
      int a = (i-1)*ws+j, b = (i+1)*ws+j;
      if (!unite(a,b)) continue;
    } else if ((i&1) == 1) {
      int a = i*ws+(j-1), b = i*ws+(j+1);
      if (!unite(a,b)) continue;
    } else continue;
    s[i][j] = false;
    m--;
  }
}

boolean[][] used;
void dfs(int i, int j) {
  used[i][j] = true;
  if (i == hs-2 && j == ws-2) return;
  boolean[] done = new boolean[4];
  for (int tm = 0; tm < 4; tm++) {
    while (true) {
      int v = rand(4);
      if (done[v]) continue;
      int ni = i+di[v], nj = j+dj[v];
      if (ni>0&&nj>0&&ni<hs-1&&nj<ws-1) {
        int mi = ni+di[v];
        int mj = nj+dj[v];
        if (!used[mi][mj]) {
          s[ni][nj] = false;
          dfs(mi,mj);
        }
      }
      done[v] = true;
      break;
    }
  }
}
void gen_dfs(boolean rev) {
  dfs(1,1);
  if (rev) {
    boolean[][] ps = new boolean[hs][ws];
    for (int i = 0; i < hs; i++) {
      for (int j = 0; j < ws; j++) {
        ps[i][j] = s[i][j];
      }
    }
    for (int i = 0; i < hs; i++) {
      for (int j = 0; j < ws; j++) {
        s[i][j] = ps[hs-i-1][ws-j-1];
      }
    }
  }
}

class P {
  int i, j;
  P(int _i, int _j) {
    i = _i;
    j = _j;
  }
}
void gen_expand(int mode) {
  ArrayList<P> q = new ArrayList<P>();
  q.add(new P(1,2));
  q.add(new P(2,1));
  boolean free = true;
  while (true) {
    int n = q.size();
    if (n == 0) break;
    int ri = rand(n);
    if (mode != 0 && !free) ri = n-1;
    free = true;
    P p = q.get(ri);
    q.set(ri, q.get(n-1)); q.remove(n-1);
    int i = p.i, j = p.j;
    if (!s[i][j]) continue;

    for (int v = 0; v < 4; v++) {
      int ni = i+di[v], nj = j+dj[v];
      if (s[ni][nj]) continue;
      if (used[ni][nj]) continue;
      s[i][j] = false;
      used[ni][nj] = true;
      if (ni == hs-2 && nj == ws-2) continue;

      boolean[] done = new boolean[4];
      for (int tm = 0; tm < 4; tm++) {
        int u = -1;
        while (true) {
          u = rand(4);
          if (done[u]) continue;
          done[u] = true;
          break;
        }
        int mi = ni+di[u], mj = nj+dj[u];
        if (mi>0&&mj>0&&mi<hs-1&&mj<ws-1) {
          int li = mi+di[u], lj = mj+dj[u];
          if (used[li][lj]) continue;
          q.add(new P(mi,mj));
          if (mode < 2 || rand(mode) != 0) free = false;
        }
      }
    }
  }
}

void generate() {
  for (int i = 0; i < hs; i++) {
    for (int j = 0; j < ws; j++) {
      if ((i&1) == 0 || (j&1) == 0) s[i][j] = true;
    }
  }
  used = new boolean[hs][ws];
  
  // gen_stick(); // too easy
  // gen_uf(); // difficult
  // gen_dfs(false); // easy
  // gen_dfs(true); // tricky easy
  // gen_expand(0); // bad
  // gen_expand(1); // soso
  gen_expand(7); // good
}

void draw_box() {
  for (int i = 0; i < hs; i++) {
    for (int j = 0; j < ws; j++) {
      if (s[i][j]) {
        int x = MA/2+S/2*i, y = MA/2+S/2*j;
        fill(200);
        rect(x,y,S/2,S/2);
      }
    }
  }
}

void draw_line() {
  line(MA,MA+S,MA,TH);
  line(TW,MA,TW,TH-S);
  line(MA,MA,TW,MA);
  line(MA,TH,TW,TH);
  for (int i = 1; i < hs; i += 2) {
    for (int j = 2; j < ws-1; j += 2) {
      if (s[i][j]) {
        int x = MA+S*(j/2), y = MA+S*(i/2);
        line(x,y,x,y+S);
      }
    }
  }
  for (int i = 2; i < hs-1; i += 2) {
    for (int j = 1; j < ws; j += 2) {
      if (s[i][j]) {
        int x = MA+S*(j/2), y = MA+S*(i/2);
        line(x,y,x+S,y);
      }
    }
  }
}

void draw() {
  generate();
  draw_line();
  // draw_box();
  save("maze.png");
}