# Hunt n' Kill algorithm

Last day I implemented the Hunt and Kill algorithm in JavaScript, using HTML5 without any libraries. I would like my code to be reviewed.

How it works

I start with a 2D array filled with walls (1-s), then I pick a random point in it, and mark it as visited. First, I get all unvisited neighbors of that specific cell, then I pick a random one out of those, mark it as visited, and I make it the child of the node before it. I repeat it until a node has no neighbors.

If the node is a dead end, I go from the top left corner of the maze, and scan it trough in horizontal direction. The first unvisited cell, wich has at least 1 visited neighbor becomes the new current cell, and I make it one of his neighbor's child. Then I go back to the third step.

At then end of the generation, when there are no unvisited cells anymore, I end up with a huge tree out of nodes. Then I visualise them, by making the wall between the node and it's child disappear.

function HuntnKill(size) {
this.size = size;
this.grid = [];
for (var x = 0; x < this.size; x++) {
this.grid[x] = [];
for (var y = 0; y < this.size; y++) {
this.grid[x][y] = new HKNode(x, y);
}
}
}

HuntnKill.prototype.getMaze = function() {
var start = this.grid[Math.floor(Math.random() * this.size)][Math.floor(Math.random() * this.size)];
start.visited = true;
var current = start;
while (true) {;
var neighbors = current.getNeighbors(this.grid, this.size);
if (neighbors.length == 0) {
// Hunt
var found = false;

hunt:
for (var y = 0; y < this.size; y++) {
for (var x = 0; x < this.size; x++) {
var node = this.grid[x][y];
if (!node.visited) {
var neighbors = node.getVisitedNeighbors(this.grid, this.size);
if (neighbors.length != 0) {
found = true;
var neighbor = neighbors[Math.floor(Math.random() * neighbors.length)];
current = node;
this.grid[current.x][current.y].visited = true;
break hunt;
}
}
}
}
if (!found)
return this.buildMaze();

} else {
// Kill
var next = neighbors[Math.floor(Math.random() * neighbors.length)];
current = next;
this.grid[current.x][current.y].visited = true;
current.visited = true;
}
}
}

HuntnKill.prototype.buildMaze = function() {
var maze = [];
for (var x = 0; x < this.size * 2 + 1; x++) {
maze[x] = [];
for (var y = 0; y < this.size * 2 + 1; y++) {
maze[x][y] = 1;
}
}

for (var x = 0; x < this.size; x++) {
for (var y = 0; y < this.size; y++) {
if (this.grid[x][y].visited) {
maze[x * 2 + 1][y * 2 + 1] = 0;
var children = this.grid[x][y].children;
for (var child of children) {
if (child.x < x) {
maze[x * 2][y * 2 + 1] = 0;
}
if (child.x > x) {
maze[x * 2 + 2][y * 2 + 1] = 0;
}
if (child.y < y) {
maze[x * 2 + 1][y * 2] = 0;
}
if (child.y > y) {
maze[x * 2 + 1][y * 2 + 2] = 0;
}
}
}
}
}
return maze;
}

function HKNode(x, y) {
this.x = x;
this.y = y;
this.visited = false;
this.children = [];
}

this.children.push(node);
}

HKNode.prototype.getNeighbors = function(grid, size) {
var neighbors = [];
if (this.x > 0 && !grid[this.x - 1][this.y].visited) {
neighbors.push(grid[this.x - 1][this.y]);
}
if (this.x < size - 1 && !grid[this.x + 1][this.y].visited) {
neighbors.push(grid[this.x + 1][this.y]);
}
if (this.y > 0 && !grid[this.x][this.y - 1].visited) {
neighbors.push(grid[this.x][this.y - 1]);
}
if (this.y < size - 1 && !grid[this.x][this.y + 1].visited) {
neighbors.push(grid[this.x][this.y + 1]);
}
return neighbors;
}

HKNode.prototype.getVisitedNeighbors = function(grid, size) {
var neighbors = [];
if (this.x > 0 && grid[this.x - 1][this.y].visited) {
neighbors.push(grid[this.x - 1][this.y]);
}
if (this.x < size - 1 && grid[this.x + 1][this.y].visited) {
neighbors.push(grid[this.x + 1][this.y]);
}
if (this.y > 0 && grid[this.x][this.y - 1].visited) {
neighbors.push(grid[this.x][this.y - 1]);
}
if (this.y < size - 1 && grid[this.x][this.y + 1].visited) {
neighbors.push(grid[this.x][this.y + 1]);
}
return neighbors;
}

//This stuff doesn't matter, it's only here to make the snippet runnable.
var c = document.getElementById("canvas");
c.width = 505;
c.height = 505;
var ctx = c.getContext("2d");
var huntnKill = new HuntnKill(50);

var maze = huntnKill.getMaze();
for (var x = 0; x < maze.length ; x++) {
for (var y = 0; y < maze[x].length; y++) {
if (maze[x][y])
ctx.fillRect(x * 5, y * 5, 5, 5);
}
}
<canvas id="canvas"></canvas>

• If you don't mind, can you explain what the code does? All I see is a maze. Is it all that it does? – Joseph May 8 '16 at 0:53
• @JosephtheDreamer If you want to – Bálint May 8 '16 at 6:19