var cols, rows; var w = 30; var current; var search_current; var search_flg; var stack; var queue; var wall_c; var wall_c_str; var road_c; var road_c_str; var start_c; var goal_c; var goal_c_str; var current_c; var done_c; var done_c_str; var route_c; function setup() { //frameRate(10); wall_c = color(80, 80, 90); wall_c_str = wall_c.levels.toString(); road_c = color(25, 25, 30); road_c_str = road_c.levels.toString(); start_c = color(0, 200, 0); goal_c = color(0, 0, 200); goal_c_str = goal_c.levels.toString(); current_c = color(200, 0, 0); done_c = color(150, 150, 155); done_c_str = done_c.levels.toString(); route_c = color(220, 220, 0); cols = floor(windowWidth / w); rows = floor(windowHeight / w); if (cols % 2 == 0) cols = cols - 1; if (rows % 2 == 0) rows = rows - 1; createCanvas(cols * w, rows * w); //壁 for (var i = 0; i < cols; i++) { for (var j = 0; j < rows; j++) { noStroke(); fill(wall_c); rect(i * w, j * w, w, w); } } current = new Cell(1, 1); search_current = new BreadthFirst(1, 1); search_flg = true; stack = []; queue = []; } function countdown() { noLoop(); setTimeout(function () { setup(); loop(); }, 3000); } function draw() { // background(255); var next = current.checkNeighbors(); if (next) { current.show(); removeWalls(current, next); current.move(next); stack.push(next); current.highlight(); } else if (stack.length > 0) { current.show(); var prev = stack.pop(); current.move(prev); current.highlight(); } else { if (search_flg) { //迷路検索初回処理 search_flg = false; current.show(); current.start(); current.goal(); var next_search = search_current.search(); for (var i = 0; i < next_search.length; i++) { var rt = []; rt.push(next_search[i]); queue.push({ xy: next_search[i], rt: rt }); } } //迷路探索 if (queue.length > 0) { var q = queue.shift(); search_current.move(q.xy); search_current.show(); var next_search = search_current.search(); if (next_search == 'goal') { console.log("GOAL"); for (var i = 0; i < q.rt.length; i++) { search_current.move(q.rt[i]); search_current.route(); } countdown(); } else if (next_search) { for (var i = 0; i < next_search.length; i++) { var newrt = []; for (var j = 0; j < q.rt.length; j++) { newrt.push(q.rt[j]); } newrt.push(next_search[i]); queue.push({ xy: next_search[i], rt: newrt }); } } } else { noLoop(); frameRate(0); } /** */ } } function Cell(i, j) { this.i = i; this.j = j; this.move = function (vec) { this.i = vec[0]; this.j = vec[1]; } this.checkNeighbors = function () { var neighbors = []; var top = get(this.i * w, (this.j - 2) * w); var right = get((this.i + 2) * w, this.j * w); var bottom = get(this.i * w, (this.j + 2) * w); var left = get((this.i - 2) * w, this.j * w); if (top.toString() == wall_c_str && this.j - 2 > 0) { neighbors.push([this.i, this.j - 2]); } if (right.toString() == wall_c_str && this.i + 2 < cols - 1) { neighbors.push([this.i + 2, this.j]); } if (bottom.toString() == wall_c_str && this.j + 2 < rows - 1) { neighbors.push([this.i, this.j + 2]); } if (left.toString() == wall_c_str && this.i - 2 > 0) { neighbors.push([this.i - 2, this.j]); } if (neighbors.length > 0) { var r = floor(random(0, neighbors.length)); return neighbors[r]; } else { return undefined; } } this.highlight = function () { var x = this.i * w; var y = this.j * w; noStroke(); fill(current_c); rect(x, y, w, w); } this.show = function () { var x = this.i * w; var y = this.j * w; noStroke(); fill(road_c); rect(x, y, w, w); } this.start = function () { var x = 1 * w; var y = 1 * w; noStroke(); fill(start_c); rect(x, y, w, w); } this.goal = function () { var x = (cols - 2) * w; var y = (rows - 2) * w; noStroke(); fill(goal_c); rect(x, y, w, w); } } function BreadthFirst(i, j) { this.i = i; this.j = j; this.move = function (vec) { this.i = vec[0]; this.j = vec[1]; } this.search = function () { var neighbors = []; var top = get(this.i * w, (this.j - 1) * w); var right = get((this.i + 1) * w, this.j * w); var bottom = get(this.i * w, (this.j + 1) * w); var left = get((this.i - 1) * w, this.j * w); if (top.toString() == road_c_str && this.j - 1 > 0) { neighbors.push([this.i, this.j - 1]); } if (right.toString() == road_c_str && this.i + 1 < cols - 1) { neighbors.push([this.i + 1, this.j]); } if (bottom.toString() == road_c_str && this.j + 1 < rows - 1) { neighbors.push([this.i, this.j + 1]); } if (left.toString() == road_c_str && this.i - 1 > 0) { neighbors.push([this.i - 1, this.j]); } if (neighbors.length > 0) { return neighbors; } else { if (top.toString() == goal_c_str || right.toString() == goal_c_str || bottom.toString() == goal_c_str || left.toString() == goal_c_str) { return 'goal'; } return undefined; } } this.show = function () { var x = this.i * w; var y = this.j * w; noStroke(); fill(done_c); rect(x, y, w, w); } this.route = function () { var x = this.i * w; var y = this.j * w; noStroke(); fill(route_c); rect(x, y, w, w); } } function removeWalls(a, b) { var x = a.i - b[0]; if (x === 2) { var c = new Cell(a.i - 1, a.j); } else if (x === -2) { var c = new Cell(a.i + 1, a.j); } var y = a.j - b[1]; if (y === 2) { var c = new Cell(a.i, a.j - 1); } else if (y === -2) { var c = new Cell(a.i, a.j + 1); } c.show(); }

Maze 2