4
\$\begingroup\$

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;
                                this.grid[neighbor.x][neighbor.y].addChildren(current);
                                break hunt;
                            }
                        }
                    }
                }
            if (!found)
                return this.buildMaze();

        } else {
            // Kill
            var next = neighbors[Math.floor(Math.random() * neighbors.length)];
            current.addChildren(next);
            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 = [];
}

HKNode.prototype.addChildren = function(node) {
    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>

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.