PcoWSkbVqDnWTu_dm2ix
We use cookies on this site to enhance your user experience

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