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.
- 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.
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