5
\$\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\$
3
  • 2
    \$\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, 2016 at 0:53
  • \$\begingroup\$ @JosephtheDreamer If you want to \$\endgroup\$
    – Bálint
    May 8, 2016 at 6:19
  • \$\begingroup\$ @Joseph weblog.jamisbuck.org/2011/1/24/… might help clarify the algorithm. \$\endgroup\$
    – ggorlen
    Apr 16 at 16:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.