Dungen
There are many dungeon generation algorithms out there, but my favorite by far is what Phi Dinh of Tiny Keep was able to do with Delaunay Triangulation and minimum spanning trees.
#############################################################
########### # # # ###########
## ## # # # ###########
## ## # # # # #
## ## # # # # #
## #
## ## # # # # #
## ## # # # # #
## ## # # # ##### #####
########### # # # ##### #####
############### ################### ################### #####
############### ############### # ## ##
############# ############# # ## ##
########### ########### # # #
########### ########### # # #
########### ########### #
########### ########### # # #
########### ########### # # #
############# ############# # ## ##
############### ############### # ## ##
############### ############################# ######### #####
### ##### ######################## #### ###
### ##### #### ############# ### ##
### ### ## ############# ## #
### ### ## ############# ## #
### ############# #
### ### ## ############# ## #
### ### ## ############# ## #
### ##### #### ############# ### ##
### ##### ####### ################ #### ###
##### ######### ######### ############################# #####
# # ##### ###### ### #### ###
# # ## ### ### #### ###
# # ## ### ### #### ###
# # ## ### ### #### ###
# ## ###
# # ## ### ### #### ###
# # ## ### ### #### ###
# # ## ### ### #### ###
# # ############ ### #### ###
##### #######################################################
##### ###### ### ################################
## ### ### ################################
## ### ### ################################
## ### ### ################################
## ################################
## ### ### ################################
## ### ### ################################
## ### ### ################################
############ ### ################################
############### ######### ###################################
############ ### ############## #############
############ ### ############## ##### ###
############ ### ############## #### ##
############ ### ############## #### ##
############ ### ############## ##
############ ### ############## #### ##
############ ### ############## #### ##
############ ### ############## ##### ###
############ ### ############## ####### #####
############### ######### ################### ######### #####
# ### #### ############## ####### #####
# ## ## # ### #### ##
# ## ## # ## ### ##
# ## ## # ## ### ##
# ## ### ##
# ## ## # ## ### ##
# ## ## # ## ### ##
# ## ## # ### #### ##
# ### #### ###### ####### ####### #####
##### ############################# ######### ######### #####
# ######################### ######### ##### #
# ####################### ##### ### #
# ####################### #### ## #
# ####################### #### ## #
# ####################### #
# ####################### #### ## #
# ####################### #### ## #
# ####################### ##### ### #
# ######################################### #
##### ################################################# #####
##### ##### ### ##### ############# #
# # ## #### ############# #
# # ## #### ############# #
# # ## #### ############# #
# ############# #
# # ## #### ############# #
# # ## #### ############# #
# # ## #### ############# #
########### ### ##### ############# #
############### ######### ######### ################### #####
########### ##### ##### # ##### #####
########### ## ## # ## ##
########### ## ## # ## ##
########### ## ## # ## ##
########### ## ## ##
########### ## ## # ## ##
########### ## ## # ## ##
########### ## ## # ## ##
########### ########### # ###########
#############################################################
This implementation uses Kruskal’s Reverse Delete algorithm, only that each edge has a reversed duplicate edge, and the algorithm is applied on a sorted-by-length list of edges. Reverse edge cousins may not be perfectly grouped in pairs of two after the sort, creating chances for circularly connected edges.
Once the spanning tree is generated, a room is placed at the points of each edge, and the edge length is used as a step vector for placing the corridors.
It’s MIT - Phi’s brain child before all.
If you are further interested, check out Andvaranaut on github. It uses this to generate 32 large connected rooms, and renders them so in a 2.5D Doom like first person fashion.
