# Maze Generation

Jul 02 2018, 5:16 PM PST 2 min

Hunt-and-Kill is a maze generation algorithm. The Hunt-and-Kill algorithm goes along a random path until there is no other way to turn and then hunts for a new node to use. It is a simple algorithm that will, in most cases, end in long winding corridors.

### Procedure

• From current node, pick a random direction to go to.
• Delete wall between current node and the node in that direction.
• Make the new node the current node.
• Repeat until there are no more choices.
• Searching from the top down, find the first node that is next to a visited node and has not already been selected.
• Delete that wall in between the two nodes, make the new node the current node.
• Repeat from step 1 until no more choices are left.

### Pseudo Code

``````function Hunt_and_Kill(node)
node.visited = true

--Take visited neighbors out of the possible selections
local neighbors = node:neighbors()
for i=#neighbors,1,-1 do
if neighbors[i].visited then
table.remove(neighbors,i)
end
end
--if there are unvisited neighbors of node, select a random one
if #neighbors>0 then
local new_node = neighbors[math.random(#neighbors)]
--delete the wall between the two nodes
deleteBetween(node,new_node)
--repeat process on new_node
Hunt_and_Kill(new_node)

--if there are no unvisited neighbors, begin hunt for new neighbor
else
for y = 1, bottom_of_maze do
for x = 1, end_of_maze do
--if the node has not been visited and is next to a visited neighbor, select
if not maze[x][y].visited then
local visitedNeighbor = false
for _, neighbor in pairs(maze[x][y]:neighbors()) do
if v.visted then
visitedNeighbor = neighbor
break
end
end
--if found, begin process over again
if visitedNeighbor then
Hunt_and_Kill(visitedNeighbor)
end
end
end
end
end
end
``````
Tags:
• procedural