Announcement

Collapse
No announcement yet.

Dungeon Generator

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Dungeon Generator

    I'm developing a Random Maze Generator for Project Fujita and Treasure Hunter VR Series. The DFS Maze Generator will be the basis of a greater Procedural Level Map Generator.

    Below is my rendition of Maze Generator in Unrealscript explained at http://www.mazeworks.com/mazegen/mazetut/index.htm. Simply use the console command GenerateDFS() to generate a maze. In its current form, the Generator is visually agnostic, it outputs a 8 x 8 Matrix (default) of Tab Separated Values (TSV) to the Log. Each TSV represents a Cell in the Maze Grid. The TSV is integer version of a binary value. The first 4 binary digits represents the 4 walls (NESW) of the cell. A digit value of 1 means the wall is up, a value of 0 means the wall is down. These integer values can be used to select and spawn a prefabricated room (mesh) or build rooms wall-by-wall.

    F6DepthFirstSearch.uc
    Code:
    /**
     * Depth-First Search Maze by F.L.Taylor 2013
     
     * Based on DFS Algorithm found at http://www.mazeworks.com/mazegen/mazetut/index.htm 
     
     * DFS Algorithm works like this:  
     *   1) Start at a random cell in the grid.  
     *   2) Look for a random neighbor cell you haven't been to yet.  
     *   3) If you find one, move there, knocking down the wall between the cells.   
     *      If you don't find one, back up to the previous Grid.  
     *   4) Repeat steps 2 and 3 until you've been to every cell in the grid.  
     Pseudocode:
        create a CellStack (LIFO) to hold a list of cell locations 
        set TotalCells = number of cells in grid 
        choose a cell at random and call it CurrentCell 
        set VisitedCells = 1 
          
        while VisitedCells < TotalCells 
        
            find all neighbors of CurrentCell with all walls intact  
            if one or more found 
            choose one at random 
            knock down the wall between it and CurrentCell 
            push CurrentCell location on the CellStack 
            make the new cell CurrentCell 
            add 1 to VisitedCells else 
            pop the most recent cell entry off the CellStack 
            make it CurrentCell endIf 
        
        endWhile   
        
     * When the while loop terminates, the algorithm is completed. Every cell has been   
     * visited and thus no cell is inaccessible. Also, since we test each possible move   
     * to see if we've already been there, the algorithm prevents the creation of any   
     * open areas, or paths that circle back on themselves.  
      
     * We can put the start and end points wherever we want. This is another advantage  
     * of a perfect maze. Since, by definition, one and only one path will exist between   
     * any two points in the maze, we know that given a start/end pair, a unique solution  
     *  to the maze must exist.  
      
     * Depth-First Search is the most common algorithm used in maze generation programs:   
     * it's simple to implement, works quickly, and generates very pretty mazes.   
     * The algorithm can also be used to solve mazes. This is how MazeGen generates   
     * solutions for all mazes, no matter which algorithm was used to create them.  
    
     * Reference: 
    
     *        backtrack     solution     border         walls
     *        0000        0000        0000        0000
     *         WSEN        WSEN        WSEN        WSEN
     
     *         WSEN
     *         0123
     *                   0,-1(N)
     *                    |
     *         -1, 0(W)  0, 0 +1, 0(E) 
     *                    |
     *                   0,+1(S)
     
     *         2) Multi-dimensional to Single Index, http://cs.smith.edu/~thiebaut/ArtOfAssembly/CH05/CH05-2.html
     *            array[col,row]: Element_Address = Base_Address + (colindex * row_size + rowindex) * Element_Size
    */
    
    Class F6DepthFirstSearch extends Object;
    
    var IntPoint Max;
    
    var array<IntPoint> NeighborPositionData;
    var array<int> NeighborKnockoutPositionData;
    
    function Generate(int GridMaxX, int GridMaxY, optional string Filename)
    {
        //create a CellStack (LIFO) to hold a list of Cell locations
        local array<IntPoint> Stack;
        
        //BinaryData
        //backtrack     solution     border         walls
        //0000        0000        0000        0000
        //WSEN        WSEN        WSEN        WSEN
        //CDEF          89AB            4567            0123
        //---------------------------------------------------
        //NESW        NESW        NESW        NESW
          //FDEC        BA98        7654        3210
          //                                              8421(Dec) 
         local array<int> Cell;
        local array<IntPoint> NeighborList;
        local array<byte> NeighborPosition;    
            
        local IntPoint Grid;
        local IntPoint Current;
        local IntPoint Neighbor;
        
        local int X_Y; //Multi-dim Index: X,Y (X * Max.Y + Y)
        
        local int rndIndex;
        local int KnockoutPositionDataIndex;
        local int OppositeKnockoutPositionDataIndex;
    
        local int TotalCells;
        local int VisitedCells;    
        local int AdjacentPosition;
        
        local string TSV; //Output map Tab-separated values
    
        //ref http://cs.smith.edu/~thiebaut/ArtOfAssembly/CH05/CH05-2.html
        //2d x * y_size + y
        //3d (z * x_size + x) * y_size + y
        
        Max.X = GridMaxX;
        Max.Y = GridMaxY;
    
        //set TotalCells = number of Cells in grid
        TotalCells = Max.X * Max.Y;
        
        //intialize Grid Cells with all walls intact
        for (VisitedCells = 0; VisitedCells < TotalCells; VisitedCells++)
        {
            Cell[Cell.Length] = 15;            //1111
        }
    
        //choose a cell at random and call it CurrentCell
        Current.X = Rand(Max.X);
        Current.Y = Rand(Max.Y);
    
        //set VisitedCells = 1
        VisitedCells = 1;
        
        //while VisitedCells < TotalCells
        while(VisitedCells < TotalCells)
        {
            
            //find all neighbors of CurrentCell with all walls intact
            
            //reset neighbor list
            NeighborList.Length = 0;
            NeighborPosition.Length = 0;
            
            //loop thru all adjacent neighbors WSEN
            for(AdjacentPosition = 0; AdjacentPosition < NeighborPositionData.Length; AdjacentPosition++)
            {
                //calculate neighbors
                Neighbor = default.NeighborPositionData[AdjacentPosition];
    
                Neighbor.X += Current.X;
                Neighbor.Y += Current.Y;
                
                //check if Cell is within borders
                //if so, check if walls are intact add to neighbor list
                if(Neighbor.X > -1 && Neighbor.X < Max.X && Neighbor.Y > -1 && Neighbor.Y < Max.Y)
                {
                    //All Walls intact
                    X_Y = Neighbor.X * Max.Y + Neighbor.Y;
                    
                    if(Cell[X_Y] == 15)
                    {    
                        //add to neighbor list
                        NeighborList.AddItem(Neighbor);
                        NeighborPosition.AddItem(AdjacentPosition);
                    }
                }
            }        
            
            //if one or more neighbor found
            if (NeighborList.Length > 0)
            {
                //choose one of the neighbors at random
                rndIndex = Rand(NeighborList.Length);
                
                Neighbor = NeighborList[rndIndex];
                
                //knockout opposite wall between Current and Neighbor 
                //skip 1, wrap NeighborKnockoutPositionData Index            
                KnockoutPositionDataIndex = NeighborPosition[rndIndex];
                OppositeKnockoutPositionDataIndex = (KnockoutPositionDataIndex + 2) % NeighborKnockoutPositionData.Length;
                
                X_Y = Neighbor.X * Max.Y + Neighbor.Y;
    
                if((Cell[X_Y] & default.NeighborKnockoutPositionData[KnockoutPositionDataIndex]) != 0)
                {
                    Cell[X_Y] -= default.NeighborKnockoutPositionData[KnockoutPositionDataIndex];
                }
    
                X_Y = Current.X * Max.Y + Current.Y;
    
                if((Cell[X_Y] & default.NeighborKnockoutPositionData[OppositeKnockoutPositionDataIndex]) != 0) 
                {
                    Cell[X_Y] -= default.NeighborKnockoutPositionData[OppositeKnockoutPositionDataIndex];
                }
                
                //push Current Cell location on the CellStack
                Stack[Stack.Length] = Current;
                
                //make the Neighbor CurrentCell
                Current.X = Neighbor.X;
                Current.Y = Neighbor.Y;
    
                //add 1 to VisitedCells
                VisitedCells++;
            }
            else
            {
                //pop the most recent Cell entry off the CellStack and make it CurrentCell
                Current = Stack[Stack.Length - 1];
                Stack.Length = Stack.Length - 1;
            }
        }
    
        //maze completed, id Cellbases
        //create Cells: BaseWall, BaseWallVariance (future use), Cell, BaseVariance(future use)
        //Note: Cellbase describes the the Cell pattern (See Diagram 1). A Cellbase contains upto 4 walls.
        //Each wall can be independent in shape/texture (variance).
        `log("Maze Output:");
        for(Grid.Y = 0;Grid.Y < Max.Y;Grid.Y++)
        {    
            for (Grid.X = 0;Grid.X < Max.X;Grid.X++)
            {
    
                X_Y = Grid.X * Max.Y + Grid.Y;
        
                //select variance
                //Variance type (1-127 Normal Wall)
                
                //Variance type (128 - 255 Borders)
                if ( Grid.X == 0 )         //W
                {
                    Cell[X_Y] += 16;
                    //Cell[X_Y] = Cell[X_Y] & ~(1<<5);//0001 0000
                }
                if(Grid.Y == Max.Y-1)        //S
                {
                    Cell[X_Y] += 32;
                    //Cell[X_Y] = Cell[X_Y] & ~(1<<6);//0010 0000
                }            
                if ( Grid.X == Max.X-1)        //E
                {    
                    Cell[X_Y] += 64;
                    //Cell[X_Y] = Cell[X_Y] & ~(1<<7);//0100 0000
                }    
                if(Grid.Y == 0)            //N
                {
                    Cell[X_Y] += 128;
                    //Cell[X_Y] = Cell[X_Y] & ~(1<<8);//1000 0000
                }
    
                TSV $= Cell[X_Y]$chr(9);
                //select mesh
            }
            TSV $= Cell[X_Y]$chr(13);
        }
        //Output Maze as tab separated value (integers)
        `log("TSV:"$chr(13)$TSV);
    }
    
    defaultproperties
    {
        
        //WSEN
        //0123
        //              0,-1(N:3)
        //               |
        //-1, 0(W:0) -- 0, 0 -- +1, 0(E:2) 
        //               |
        //              0,+1(S:1)                     KnockoutPositionData Index XRef
        NeighborPositionData.Add((X=-1,Y=0))        //W:0
        NeighborPositionData.Add((X=0,Y=1))        //S:1
        NeighborPositionData.Add((X=1,Y=0))        //E:2
        NeighborPositionData.Add((X=0,Y=-1))        //N:3
        
        //NESW
        //8421
        //position (opposite = (KnockoutPositionDataIndex + 2) % (NeighborKnockoutPositionData.Length-1))) 
        NeighborKnockoutPositionData.Add(4) //E:0100
        NeighborKnockoutPositionData.Add(8) //N:1000
        NeighborKnockoutPositionData.Add(1) //W:0001
        NeighborKnockoutPositionData.Add(2) //S:0010
    
    }
    CustomPlayerController.uc
    Code:
    //Techlord: Add for F6DepthFirstSearch
    exec function GenerateDFS(optional int GridMaxX, optional int GridMaxY, optional string Filename)
    {
        local F6DepthFirstSearch DFS;
    
        if(GridMaxX == 0)
        {
            GridMaxX = 8;
        }    
        if(GridMaxY == 0)
        {        
            GridMaxY = 8;
        }
        
        DFS = new(self) class'F6DepthFirstSearch';
        DFS.Generate(GridMaxX, GridMaxY, Filename);
    }
    Launch.log Output Example
    Code:
    [0031.67] ScriptLog: Maze Output:
    [0031.67] ScriptLog: TSV:
    153	136	142	137	138	138	138	204
    21	3	12	5	11	10	12	71
    21	9	4	3	10	12	3	76
    21	5	3	12	13	3	10	68
    21	3	12	3	2	8	14	69
    21	13	3	10	12	7	9	70
    21	5	9	10	6	9	6	77
    51	38	35	42	42	34	42	102
    [SHOT]https://arcadekomodo.com/home/wp-content/uploads/2013/10/DFSMaze.png[/SHOT]
    [SHOT]https://arcadekomodo.com/home/wp-content/uploads/2013/11/UDK-2013-11-17-04-46-07-00.png[/SHOT]

    #2
    Thanks for sharing.

    Comment


      #3
      How are you going to handle Lighting and AI navigation on a procedural level?

      Comment


        #4
        Originally posted by DanielSnd View Post
        How are you going to handle Lighting and AI navigation on a procedural level?
        Hi DanielSnd,

        Thank you for your interest. I'm employing a combination automatic/semi-automatic procedural generation methods. At this very moment I'm implementing a Procedural Dungeon based a similar technique described here. I believe all techniques can make use of Dynamic Lighting and Navigation, but, it will require some experimentation with performance being high priority. My current thoughts are to make use of UDK Gem's: Dynamic Normal Maps and Creating A Dynamic NavMesh Obstacle.

        Comment


          #5
          I doubt you'll get navmeshes to work with this. still interested in the outcome though

          DanielSnd: if I'm right (and the way I did it on my own procedural dungeons), it needs custom-made pathfinding code and fully dynamic lights

          Comment


            #6
            Dungeon Generator

            Below is my rendition of Procedural Dungeon Generator in Unrealscript inspired by http://gamedev.tutsplus.com/tutorial...n-cave-system/ to generate a Dungeon (A series of random sized and positioned 'Rooms' interconnected by 'Corridors'. The creation of Rooms and Corridors follows the algorithm below. This operates similar to technique described at gamedev.tutsplus, but, I replaced the bitmap Tile with a Cell/Wall as described in the DFS technique. This results in a simple Algorithm:
            1. Randomly place your Room into the game world, performing Collision Checks to place room in a location that does not over-lap another room.
            2. Place Corridors between Rooms so Players can reach Rooms.
            3. Remove undesired Room and Corridor Cells Walls.


            Like the Maze Generator, this Dungeon Generator is visually agnostic, it outputs a 16 x 16 Matrix (default) of Tab Separated Values (TSV) to the Log. Each TSV represents a Cell in the Dungeon Grid. The TSV is integer version of a binary value. The first 4 binary digits represents the 4 walls (NESW) of the cell. A digit value of 1 means the wall is up, a value of 0 means the wall is down. These integer values can be used to select and spawn a prefabricated room (mesh) or build rooms wall-by-wall. The output also takes in consideration of door placement.

            F6PCGDungeon.uc
            Code:
            /**
             * Procedural Content Generation Dungeon by F.L.Taylor 2013
             * Reference: http://gamedev.tutsplus.com/tutorials/game-design/create-a-procedurally-generated-dungeon-cave-system/
            
             * 		WSEN
             * 		0123
             * 		1248 
             * 		          0,-1(N)
             * 		           |
             * 		-1, 0(W)  0, 0 +1, 0(E) 
             * 		           |
             * 		          0,+1(S)
             
             Cell is the equivalent of a Tile, with 4 walls stored represented by a binary value.
             Room is defined by a specified Width and Height in Cells.
             Map is defined by a specified Width and Height of the total Space for all the Rooms
            */
            
            Class F6PCGDungeon extends Object;
            
            struct Room
            {
            	// width and height of room in terms of grid
            	var int Width;
            	var int Height;
            	
            	// these values hold grid coordinates for each corner of the room
            	var IntPoint Start;
            	var IntPoint Stop;
            
            	// Center point of the room
            	var IntPoint Center;
            
            };
            
            // Rooms will hold all Rooms created for the dungeon level
            var Array<Room> RoomList;
            var Array<Room> CorridorList;
            
            var array<IntPoint> NeighborPositionData;
            var array<int> NeighborKnockoutPositionData;
            
            var IntPoint MaxSize;
            // values to cap our random generation
            var int MaxRooms;
            var int MinRoomSize;
            var int MaxRoomSize;
            
            var vector StartPosition;
            var vector RoomSize;
            var vector WallPadding;	
            
            // constructor for creating new Rooms
            function Room NewRoom(int X, int Y, int Width, int Height)
            {
            	local Room RoomA;
            	
            `trace();
            `log("X="$X$",Y="$Y$",Width="$Width$",Height="$Height);
            
            	RoomA.Start.X = X;
            	RoomA.Stop.X = RoomA.Start.X + Width;
            	RoomA.Start.Y = Y;
            	RoomA.Stop.Y = RoomA.Start.Y + Height;
            
            	RoomA.Center.X  = (RoomA.Start.X + RoomA.Stop.X) / 2;
            	RoomA.Center.Y = (RoomA.Start.Y + RoomA.Stop.Y) / 2;
            
            `log("RoomA.Start.X="$RoomA.Start.X$",RoomA.Stop.X="$RoomA.Stop.X$",RoomA.Start.Y="$RoomA.Start.Y$",RoomA.Stop.Y="$RoomA.Stop.Y$",RoomA.Center.X="$RoomA.Center.X$",RoomA.Center.Y="$RoomA.Center.Y);
            	
            	return RoomA;
            }
            
            // carves out a room based on size and dimensions of a room
            function CreateRoom(out array<int> Cell, Room RoomA)
            {
            	local IntPoint Grid;
            	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
            	
            `trace();
            `log("{");
            `log("#1  RoomA.Start.X="$RoomA.Start.X$",RoomA.Stop.X="$RoomA.Stop.X$",RoomA.Start.Y="$RoomA.Start.Y$",RoomA.Stop.Y="$RoomA.Stop.Y);
            	for (Grid.Y = RoomA.Start.Y;  Grid.Y < RoomA.Stop.Y + 1;  Grid.Y++)
            	{
            		for(Grid.X = RoomA.Start.X;  Grid.X < RoomA.Stop.X + 1; Grid.X++)
            		{
            
            			X_Y = Grid.X * MaxSize.Y + Grid.Y;
            			
            			Cell[X_Y] = 0;
            			
            			//if Room border, add wall 			
            			if ( Grid.X == RoomA.Start.X) 	//W	0001	1
            			{
            				Cell[X_Y] += 1;			
            			}
            			if(Grid.Y == RoomA.Stop.Y)	//S	0010	2
            			{
            				Cell[X_Y] += 2;
            			}			
            			if ( Grid.X == RoomA.Stop.X)	//E	0100	4
            			{	
            				Cell[X_Y] += 4;
            			}	
            			if(Grid.Y == RoomA.Start.Y)	//N	1000	8
            			{
            				Cell[X_Y] += 8;
            			}
            
            `log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);			
            			
            		}
            	}
            `log("}");	
            }
            
            function CreateHorizontalCorridor(out array<int> Cell, int X1, int X2, int Y)
            {
            	local Room CurrentCorridor;
            	
            `trace();
            
            	
            	CurrentCorridor = NewRoom(min(X1, X2), Y, max(X1, X2) - min(X1, X2), 0);
            	CreateRoom(Cell, CurrentCorridor);
            	CorridorList.AddItem(CurrentCorridor);
            }
            
            // create vertical corridor to connect Rooms
            function CreateVerticalCorridor(out array<int> Cell, int Y1, int Y2, int X) 
            {
            	local Room CurrentCorridor;
            	
            `trace();
            
            	CurrentCorridor = NewRoom(X, min(Y1,Y2), 0, max(Y1,Y2) - min(Y1,Y2));
            	CreateRoom(Cell, CurrentCorridor);
            	CorridorList.AddItem(CurrentCorridor);
            }	
            
            function PlaceRooms(out array<int> Cell, int GridMaxX, int GridMaxY, int MaximumRooms)
            {
            	// variable for tracking Center of each room
            	local int R;
            	
            	local Room CurrentRoom;
            	local Room PreviousRoom;	
            	local Room OtherRoom;
            	local Room Corridor;
            	
            	local int Width;
            	local int Height;
            	local int X;
            	local int Y;
            	
            	// create room with randomized values
            	local bool bFailed;	
            
            `trace();	
            	
            	`log("MaximumRooms="$MaximumRooms);
            	
            	// randomize values for each room
            	for (R=0; R < MaximumRooms; R++)
            	{
            		
            		//Random Room Size
            		Width = default.MinRoomSize + Rand(default.MaxRoomSize - default.MinRoomSize);
            		Height = default.MinRoomSize + Rand(default.MaxRoomSize - default.MinRoomSize);
            		X = Rand(MaxSize.X - Width);
            		Y = Rand(MaxSize.Y - Height);
            		
            		// create room with randomized values
            		CurrentRoom = NewRoom(X, Y, Width, Height);
            		
            		bFailed = FALSE;
            		
            		foreach RoomList(OtherRoom)
            		{
            			//Does Rooms Intersect
            			if (CurrentRoom.Start.X <= OtherRoom.Stop.X && CurrentRoom.Stop.X >= OtherRoom.Start.X && CurrentRoom.Start.Y <= OtherRoom.Stop.Y && OtherRoom.Stop.Y >= OtherRoom.Start.Y)
            			{
            				`log("bFailed!");
            				bFailed = TRUE;
            				break;
            			}
            		}
            
            		if (!bFailed)
            		{
            			
            			// carve out new room
            			CreateRoom(Cell, CurrentRoom);			
            	
            			if(RoomList.length != 0)
            			{
            				// store Center of previous room
            				PreviousRoom = RoomList[RoomList.length - 1];
            				
            				Corridor.Start = PreviousRoom.Center;
            				Corridor.Stop = CurrentRoom.Center;
            
            				`log("PreviousRoom.Start.X="$PreviousRoom.Start.X$",PreviousRoom.Stop.X="$PreviousRoom.Stop.X$",PreviousRoom.Start.Y="$PreviousRoom.Start.Y$",PreviousRoom.Stop.Y="$PreviousRoom.Stop.Y$",PreviousRoom.Center.X="$PreviousRoom.Center.X$",PreviousRoom.Center.Y="$PreviousRoom.Center.Y);
            				`log("CurrentRoom.Start.X="$CurrentRoom.Start.X$",CurrentRoom.Stop.X="$CurrentRoom.Stop.X$",CurrentRoom.Start.Y="$CurrentRoom.Start.Y$",CurrentRoom.Stop.Y="$CurrentRoom.Stop.Y$",CurrentRoom.Center.X="$CurrentRoom.Center.X$",CurrentRoom.Center.Y="$CurrentRoom.Center.Y);
            				`log("Corridor.Start.X="$Corridor.Start.X$",Corridor.Stop.X="$Corridor.Stop.X$",Corridor.Start.Y="$Corridor.Start.Y$",Corridor.Stop.Y="$Corridor.Stop.Y$",Corridor.Center.X="$Corridor.Center.X$",Corridor.Center.Y="$Corridor.Center.Y);
            
            				// carve out corridors between Rooms based on centers
            				// randomly start with horizontal or vertical corridors
            			
            				if (Rand(2) == 1)
            				{
            					CreateHorizontalCorridor(Cell, Corridor.Start.X, Corridor.Stop.X, PreviousRoom.Center.Y);
            					CreateVerticalCorridor(Cell, Corridor.Start.Y, Corridor.Stop.Y, CurrentRoom.Center.X);
            				}
            				else
            				{
            					CreateVerticalCorridor(Cell, Corridor.Start.Y, Corridor.Stop.Y, PreviousRoom.Center.X);
            					CreateHorizontalCorridor(Cell, Corridor.Start.X, Corridor.Stop.X, CurrentRoom.Center.Y);
            				}
            				
            			}			
            
            			RoomList.AddItem(CurrentRoom);			
            		}
            
            	}
            	
            }
            
            function CleanRooms(out array<int> Cell)
            {
            	local Room RoomA;
            	
            	local Room CorridorA;
            	local Room CorridorB;
            
            	local array<IntPoint> NeighborList; //[x_y]
            	local array<byte> NeighborPosition;
            	local IntPoint Current;
            	local IntPoint Neighbor;
            	local int KnockoutPositionDataIndex;
            	local int OppositeKnockoutPositionDataIndex;
            	local int AdjacentPosition;
            	local int CorridorNeighbors;
            	
            	local IntPoint Grid;
            	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
            	
            `trace();
            
            	foreach RoomList(RoomA)
            	{
            		`log("#1  RoomA.Start.X="$RoomA.Start.X$",RoomA.Stop.X="$RoomA.Stop.X$",RoomA.Start.Y="$RoomA.Start.Y$",RoomA.Stop.Y="$RoomA.Stop.Y);
            		
            		for (Grid.Y = RoomA.Start.Y;  Grid.Y < RoomA.Stop.Y + 1;  Grid.Y++)
            		{
            			for(Grid.X = RoomA.Start.X;  Grid.X < RoomA.Stop.X + 1; Grid.X++)
            			{
            	
            				X_Y = Grid.X * MaxSize.Y + Grid.Y;
            				
            				//Interior
            				if (Grid.X > RoomA.Start.X && Grid.X < RoomA.Stop.X && Grid.Y > RoomA.Start.Y && Grid.Y < RoomA.Stop.Y)
            				{	
            					if(Cell[X_Y] > 0)
            					{
            						Cell[X_Y] = 240;	//1111 0000
            					}
            				}
            				else
            				//Exterior
            				{
            
            					//if Room border and Wall missing, create door 			
            					if ( Grid.X == RoomA.Start.X && bool(Cell[X_Y] & 1) == FALSE) 	//W	0001 0000	1
            					{
            						Cell[X_Y] = 16;
            					}
            					if( Grid.Y ==   RoomA.Stop.Y && bool(Cell[X_Y] & 2) == FALSE)	//S	0010 0000	2
            					{
            						Cell[X_Y] = 32;
            					}			
            					if ( Grid.X ==  RoomA.Stop.X && bool(Cell[X_Y] & 4) == FALSE)	//E	0100 0000	4
            					{	
            						Cell[X_Y] = 64;
            					}	
            					if(Grid.Y ==   RoomA.Start.Y && bool(Cell[X_Y] & 8) == FALSE)	//N	1000 0000	8
            					{
            						Cell[X_Y] = 128;
            					}					
            					
            				}
            				
            			}
            		}			
            	}
            
            	foreach CorridorList(CorridorA)
            	{	
            		//check each cell CorridorA
            		for (Current.Y = CorridorA.Start.Y;  Current.Y < CorridorA.Stop.Y + 1;  Current.Y++)
            		{
            			for(Current.X = CorridorA.Start.X;  Current.X < CorridorA.Stop.X + 1; Current.X++)
            			{
            				
            				//reset neighbor list
            				NeighborList.Length = 0;
            				NeighborPosition.Length = 0;
            					
            				//loop thru all adjacent neighbors WSEN
            				for(AdjacentPosition = 0; AdjacentPosition < NeighborPositionData.Length; AdjacentPosition++)
            				{
            					//calculate neighbors
            					Neighbor = default.NeighborPositionData[AdjacentPosition];
            				
            					Neighbor.X += Current.X;
            					Neighbor.Y += Current.Y;
            					
            					//check all other corridors
            					foreach CorridorList(CorridorB)
            					{
            						for (Grid.Y = CorridorB.Start.Y;  Grid.Y < CorridorB.Stop.Y + 1;  Grid.Y++)
            						{
            							for(Grid.X = CorridorB.Start.X;  Grid.X < CorridorB.Stop.X + 1; Grid.X++)
            							{
            								if(Neighbor.X == Grid.X && Neighbor.Y == Grid.Y)
            								{	
            									//add to neighbor list
            									NeighborList.AddItem(Neighbor);
            									NeighborPosition.AddItem(AdjacentPosition);
            								}	
            								
            							}
            						}
            					}					
            				}
            				
            				//neighbors
            				for (CorridorNeighbors=0; CorridorNeighbors < NeighborList.Length; CorridorNeighbors++)
            				{
            					Neighbor = NeighborList[CorridorNeighbors];
            					
            					//knockout opposite wall between Current and Neighbor 
            					//skip 1, wrap NeighborKnockoutPositionData Index			
            					KnockoutPositionDataIndex = NeighborPosition[CorridorNeighbors];
            					OppositeKnockoutPositionDataIndex = (KnockoutPositionDataIndex + 2) % NeighborKnockoutPositionData.Length;
            					
            					X_Y = Neighbor.X * MaxSize.Y + Neighbor.Y;
            					
            					if((Cell[X_Y] & default.NeighborKnockoutPositionData[KnockoutPositionDataIndex]) != 0)
            					{
            						Cell[X_Y] -= default.NeighborKnockoutPositionData[KnockoutPositionDataIndex];
            					}
            					
            					X_Y = Current.X * MaxSize.Y + Current.Y;
            					
            					if((Cell[X_Y] & default.NeighborKnockoutPositionData[OppositeKnockoutPositionDataIndex]) != 0) 
            					{
            						Cell[X_Y] -= default.NeighborKnockoutPositionData[OppositeKnockoutPositionDataIndex];
            					}
            				}				
            			}
            		}	
            	}
            /**/	
            }	
            	
            /** Generate PCG Dungeon Grid */
            function array<int> Generate(int GridMaxX, int GridMaxY, int MaximumRooms, optional string Filename)
            {
            	// map will hold all cells that make up our game map
             	local array<int> Cell; //[x_y] --> X,Y  --> X * max.X + Y	
            		
            	local IntPoint Grid;
            	
            	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
            
            	local int TotalCells;
            	local int VisitedCells;	
            
            	local string TSV; //Output map Tab-separated values	
            	
            `trace();
            	
            	// this for loop iterates through map, placing only wall cells
            	
            	MaxSize.X = GridMaxX;
            	MaxSize.Y = GridMaxY;
            	MaxRooms = MaximumRooms;	
            	
            	//set TotalCells = number of Cells in grid
            	TotalCells = MaxSize.X * MaxSize.Y;
            	
            `log("set TotalCells MaxSize.X="$MaxSize.X$",MaxSize.Y="$MaxSize.Y$",TotalCells="$TotalCells$",MaximumRooms="$MaximumRooms);	
            
            	//intialize Grid Cells with all walls intact
            	for (VisitedCells = 0; VisitedCells < TotalCells; VisitedCells++)
            	{
            		Cell[Cell.Length] = 0;			//1111
            	}
            	
            //	//table dump
            //	for(Grid.Y = 0;Grid.Y < MaxSize.Y;Grid.Y++)
            //	{	
            //		for (Grid.X = 0;Grid.X < MaxSize.X;Grid.X++)
            //		{
            //			X_Y = Grid.X * MaxSize.Y + Grid.Y;
            //			`log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);
            //		}
            //	}	
            
            	// call place Rooms to... place... Rooms
            	PlaceRooms(Cell, GridMaxX, GridMaxY, MaximumRooms);
            	
            	// clean up entry/exit (corridors)
            	CleanRooms(Cell);
            	
            	//Dungeon completed, id Cellbases
            	`log("Dungeon Output ("$MaxSize.X$"x"$MaxSize.Y$"):");
            	for(Grid.Y = 0;Grid.Y < MaxSize.Y;Grid.Y++)
            	{	
            		for (Grid.X = 0;Grid.X < MaxSize.X;Grid.X++)
            		{
            
            			X_Y = Grid.X * MaxSize.Y + Grid.Y;
            	
            //`log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);
            			
            			TSV $= Cell[X_Y]$chr(9);
            			//select mesh
            		}
            		TSV $= chr(13);
            	}
            	`log("TSV:"$chr(13)$TSV);
            	
            	return Cell;	
            	
            }
            
            defaultproperties
            {
            	
            	//WSEN
            	//0123
            	//              0,-1(N:3)
            	//               |
            	//-1, 0(W:0) -- 0, 0 -- +1, 0(E:2) 
            	//               |
            	//              0,+1(S:1)     		        KnockoutPositionData Index XRef
            	NeighborPositionData.Add((X=-1,Y=0))		//W:0
            	NeighborPositionData.Add((X=0,Y=1))		//S:1
            	NeighborPositionData.Add((X=1,Y=0))		//E:2
            	NeighborPositionData.Add((X=0,Y=-1))		//N:3
            	
            	//NESW
            	//8421
            	//position (opposite = (KnockoutPositionDataIndex + 2) % (NeighborKnockoutPositionData.Length-1))) 
            	NeighborKnockoutPositionData.Add(4) //E:0100
            	NeighborKnockoutPositionData.Add(8) //N:1000
            	NeighborKnockoutPositionData.Add(1) //W:0001
            	NeighborKnockoutPositionData.Add(2) //S:0010
            	
            	MaxRooms=16
            	MinRoomSize=2
            	MaxRoomSize=7
            	
            	StartPosition=(X=86000.000000,Y=74500.000000,Z=4240.000000)
            	RoomSize=(X=128.0,Y=128.0,Z=0.0)
            	WallPadding=(X=0.1,Y=0.1,Z=0.1)	
            }
            CustomPlayerController.uc
            Code:
            //Techlord: Add for F6PCGDungeon
            exec function GenerateDungeon(optional int GridMaxX, optional int GridMaxY, optional int MaximumRooms, optional string Filename)
            {
            	local F6PCGDungeon Dungeon;
            	local array<int> Cell;
            
            `trace();
            
            	if(GridMaxX == 0)
            	{
            		GridMaxX = 16;
            	}	
            	if(GridMaxY == 0)
            	{		
            		GridMaxY = 16;
            	}
            	if(MaximumRooms == 0)
            	{		
            		MaximumRooms = 8;
            	}
            	
            	Dungeon = new(self) class'F6PCGDungeon';
            	Cell = Dungeon.Generate(GridMaxX, GridMaxY, MaximumRooms, Filename);
            	Dungeon.Construct(Cell,self);
            }
            Launch.log Output Example
            Code:
            [0973.95] ScriptLog: Dungeon Output (16x16):
            [0973.95] ScriptLog: TSV:
            0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	
            0	0	0	0	0	9	8	8	8	8	12	0	0	0	0	0	
            0	0	0	0	0	1	0	0	0	0	4	0	0	0	0	0	
            0	0	0	0	0	1	0	240	240	240	64	10	12	0	0	0	
            0	0	0	0	0	1	0	0	0	0	4	0	5	0	0	0	
            0	0	0	0	0	3	2	2	2	2	6	0	5	0	0	0	
            0	0	0	0	0	0	0	0	0	0	0	0	5	0	0	0	
            9	8	8	8	8	12	0	0	0	0	0	0	5	0	0	0	
            1	0	0	0	0	4	0	0	0	0	0	0	5	0	0	0	
            1	0	0	0	0	4	0	0	0	9	8	8	128	8	8	12	
            1	0	240	0	0	4	0	0	0	1	0	0	240	0	0	4	
            1	0	240	0	0	4	0	0	0	1	0	0	240	0	0	4	
            1	0	240	240	240	64	10	10	10	16	240	240	240	0	0	4	
            3	2	2	2	2	6	0	0	0	1	0	0	0	0	0	4	
            0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	4	
            0	0	0	0	0	0	0	0	0	3	2	2	2	2	2	6
            [SHOT]https://arcadekomodo.com/home/wp-content/uploads/2013/11/PCGDungeon.png[/SHOT]
            [SHOT]https://arcadekomodo.com/home/wp-content/uploads/2013/11/UDK-2013-11-29-11-52-17-15.png[/SHOT]

            Comment


              #7
              i'm working too in a game with random mazes, the lighting is a problem, but i found one or two threads here at the forum to tweak the walls to let them get the pre computed lights, about the ai navigation (the hard part) i'm using custom path points and i'm moving my bots with my own game logic, i tried using navmesh with dynamic obstacles, but the problem is to generate/remove dynamic obstacles take some cpu process and my game will change the walls positions each 30 seconds, when i tried with the dynamic obstacles the remove/generation of the dynamic obstacle was frozen the walls animations, when the animation start again was almost at the end, very bad for me.

              Comment


                #8
                Best discussion ever on maze generation algorithms.

                Comment


                  #9
                  Cave Generator

                  Below is my rendition of Procedural Cave Generator in Unrealscript inspired by http://gamedevelopment.tutsplus.com/...--gamedev-9664 to generate a Cave. The creation of the Cave follows the Rules below. This operates similar to technique described at gamedevelopment.tutsplus, but, I replaced the bitmap Tile with a Cell/Wall as described in the DFS technique. I'm still pondering over uses for this, but, it was fairly easy to write.

                  Rules of Cellular Automation:
                  1. If a living cell has less than two living neighbors, it dies.
                  2. If a living cell has two or three living neighbors, it stays alive.
                  3. If a living cell has more than three living neighbors, it dies.
                  4. If a dead cell has exactly three living neighbors, it becomes alive.


                  Like the Maze Generator, this Dungeon Generator is visually agnostic, it outputs a 16 x 16 Matrix (default) of Tab Separated Values (TSV) to the Log. Each TSV represents a Cell in the Dungeon Grid. The TSV is integer version of a binary value. The first 4 binary digits represents the 4 walls (NESW) of the cell. A digit value of 1 means the wall is up, a value of 0 means the wall is down. These integer values can be used to select and spawn a prefabricated room (mesh) or build rooms wall-by-wall. The output also takes in consideration of door placement.

                  F6PCGCave.uc
                  Code:
                  /**
                   * Procedural Content Generation Cave by F.L.Taylor 2013
                   * Reference: http://gamedevelopment.tutsplus.com/tutorials/cave-levels-cellular-automata--gamedev-9664
                   
                   * Cellular Automaton
                   * Rules: 
                   * 1. If a living cell has less than two living neighbours, it dies.
                   * 2. If a living cell has two or three living neighbours, it stays alive.
                   * 3. If a living cell has more than three living neighbours, it dies.
                   * 4. If a dead cell has exactly three living neighbours, it becomes alive.
                  
                   * 		WSEN
                   * 		0123
                   * 		1248 
                   * 		          0,-1(N)
                   * 		           |
                   * 		-1, 0(W)  0, 0 +1, 0(E) 
                   * 		           |
                   * 		          0,+1(S)
                   
                   Cell is the equivalent of a Tile, with 4 walls stored represented by a binary value.
                   Room is defined by a specified Width and Height in Cells.
                   Map is defined by a specified Width and Height of the total Space for all the Rooms
                  */
                  
                  Class F6PCGCave extends Object;
                  
                  struct Room
                  {
                  	// width and height of room in terms of grid
                  	var int Width;
                  	var int Height;
                  	
                  	// these values hold grid coordinates for each corner of the room
                  	var IntPoint Start;
                  	var IntPoint Stop;
                  
                  	// Center point of the room
                  	var IntPoint Center;
                  
                  };
                  
                  // Rooms will hold all Rooms created for the dungeon level
                  var Array<Room> RoomList;
                  var Array<Room> CorridorList;
                  
                  var array<IntPoint> NeighborPositionData;
                  var array<int> NeighborKnockoutPositionData;
                  
                  var IntPoint MaxSize;
                  // values to cap our random generation
                  var int MaxRooms;
                  var int MinRoomSize;
                  var int MaxRoomSize;
                  
                  var int BirthLimit;
                  var int DeathLimit;
                  var float InitialChance;  
                  var int Steps;
                  
                  var vector StartPosition;
                  var vector RoomSize;
                  var vector WallPadding;	
                  
                  // constructor for creating new Rooms
                  function Room NewRoom(int X, int Y, int Width, int Height)
                  {
                  	local Room RoomA;
                  	
                  `trace();
                  `log("X="$X$",Y="$Y$",Width="$Width$",Height="$Height);
                  
                  	RoomA.Start.X = X;
                  	RoomA.Stop.X = RoomA.Start.X + Width;
                  	RoomA.Start.Y = Y;
                  	RoomA.Stop.Y = RoomA.Start.Y + Height;
                  
                  	RoomA.Center.X  = (RoomA.Start.X + RoomA.Stop.X) / 2;
                  	RoomA.Center.Y = (RoomA.Start.Y + RoomA.Stop.Y) / 2;
                  
                  `log("RoomA.Start.X="$RoomA.Start.X$",RoomA.Stop.X="$RoomA.Stop.X$",RoomA.Start.Y="$RoomA.Start.Y$",RoomA.Stop.Y="$RoomA.Stop.Y$",RoomA.Center.X="$RoomA.Center.X$",RoomA.Center.Y="$RoomA.Center.Y);
                  	
                  	return RoomA;
                  }
                  
                  // carves out a room based on size and dimensions of a room
                  function CreateRoom(out array<int> Cell, Room RoomA)
                  {
                  	local IntPoint Grid;
                  	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
                  	
                  `trace();
                  `log("{");
                  `log("#1  RoomA.Start.X="$RoomA.Start.X$",RoomA.Stop.X="$RoomA.Stop.X$",RoomA.Start.Y="$RoomA.Start.Y$",RoomA.Stop.Y="$RoomA.Stop.Y);
                  	for (Grid.Y = RoomA.Start.Y;  Grid.Y < RoomA.Stop.Y + 1;  Grid.Y++)
                  	{
                  		for(Grid.X = RoomA.Start.X;  Grid.X < RoomA.Stop.X + 1; Grid.X++)
                  		{
                  
                  			X_Y = Grid.X * MaxSize.Y + Grid.Y;
                  			
                  			Cell[X_Y] = 0;
                  			
                  			//if Room border, add wall 			
                  			if ( Grid.X == RoomA.Start.X) 	//W	0001	1
                  			{
                  				Cell[X_Y] += 1;			
                  			}
                  			if(Grid.Y == RoomA.Stop.Y)	//S	0010	2
                  			{
                  				Cell[X_Y] += 2;
                  			}			
                  			if ( Grid.X == RoomA.Stop.X)	//E	0100	4
                  			{	
                  				Cell[X_Y] += 4;
                  			}	
                  			if(Grid.Y == RoomA.Start.Y)	//N	1000	8
                  			{
                  				Cell[X_Y] += 8;
                  			}
                  
                  `log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);			
                  			
                  		}
                  	}
                  `log("}");	
                  }
                  
                  function CreateHorizontalCorridor(out array<int> Cell, int X1, int X2, int Y)
                  {
                  	local Room CurrentCorridor;
                  	
                  `trace();
                  
                  	
                  	CurrentCorridor = NewRoom(min(X1, X2), Y, max(X1, X2) - min(X1, X2), 0);
                  	CreateRoom(Cell, CurrentCorridor);
                  	CorridorList.AddItem(CurrentCorridor);
                  }
                  
                  // create vertical corridor to connect Rooms
                  function CreateVerticalCorridor(out array<int> Cell, int Y1, int Y2, int X) 
                  {
                  	local Room CurrentCorridor;
                  	
                  `trace();
                  
                  	CurrentCorridor = NewRoom(X, min(Y1,Y2), 0, max(Y1,Y2) - min(Y1,Y2));
                  	CreateRoom(Cell, CurrentCorridor);
                  	CorridorList.AddItem(CurrentCorridor);
                  }	
                  
                  function PlaceRooms(out array<int> Cell, int GridMaxX, int GridMaxY, int MaximumRooms)
                  {
                  	// variable for tracking Center of each room
                  	local int R;
                  	
                  	local Room CurrentRoom;
                  	local Room PreviousRoom;	
                  	local Room OtherRoom;
                  	local Room Corridor;
                  	
                  	local int Width;
                  	local int Height;
                  	local int X;
                  	local int Y;
                  	
                  	// create room with randomized values
                  	local bool bFailed;	
                  
                  `trace();	
                  	
                  	`log("MaximumRooms="$MaximumRooms);
                  	
                  	// randomize values for each room
                  	for (R=0; R < MaximumRooms; R++)
                  	{
                  		
                  		//Random Room Size
                  		Width = default.MinRoomSize + Rand(default.MaxRoomSize - default.MinRoomSize);
                  		Height = default.MinRoomSize + Rand(default.MaxRoomSize - default.MinRoomSize);
                  		X = Rand(MaxSize.X - Width);
                  		Y = Rand(MaxSize.Y - Height);
                  		
                  		// create room with randomized values
                  		CurrentRoom = NewRoom(X, Y, Width, Height);
                  		
                  		bFailed = FALSE;
                  		
                  		foreach RoomList(OtherRoom)
                  		{
                  			//Does Rooms Intersect
                  			if (CurrentRoom.Start.X <= OtherRoom.Stop.X && CurrentRoom.Stop.X >= OtherRoom.Start.X && CurrentRoom.Start.Y <= OtherRoom.Stop.Y && OtherRoom.Stop.Y >= OtherRoom.Start.Y)
                  			{
                  				`log("bFailed!");
                  				bFailed = TRUE;
                  				break;
                  			}
                  		}
                  
                  		if (!bFailed)
                  		{
                  			
                  			// carve out new room
                  			CreateRoom(Cell, CurrentRoom);			
                  	
                  			if(RoomList.length != 0)
                  			{
                  				// store Center of previous room
                  				PreviousRoom = RoomList[RoomList.length - 1];
                  				
                  				Corridor.Start = PreviousRoom.Center;
                  				Corridor.Stop = CurrentRoom.Center;
                  
                  				`log("PreviousRoom.Start.X="$PreviousRoom.Start.X$",PreviousRoom.Stop.X="$PreviousRoom.Stop.X$",PreviousRoom.Start.Y="$PreviousRoom.Start.Y$",PreviousRoom.Stop.Y="$PreviousRoom.Stop.Y$",PreviousRoom.Center.X="$PreviousRoom.Center.X$",PreviousRoom.Center.Y="$PreviousRoom.Center.Y);
                  				`log("CurrentRoom.Start.X="$CurrentRoom.Start.X$",CurrentRoom.Stop.X="$CurrentRoom.Stop.X$",CurrentRoom.Start.Y="$CurrentRoom.Start.Y$",CurrentRoom.Stop.Y="$CurrentRoom.Stop.Y$",CurrentRoom.Center.X="$CurrentRoom.Center.X$",CurrentRoom.Center.Y="$CurrentRoom.Center.Y);
                  				`log("Corridor.Start.X="$Corridor.Start.X$",Corridor.Stop.X="$Corridor.Stop.X$",Corridor.Start.Y="$Corridor.Start.Y$",Corridor.Stop.Y="$Corridor.Stop.Y$",Corridor.Center.X="$Corridor.Center.X$",Corridor.Center.Y="$Corridor.Center.Y);
                  
                  				// carve out corridors between Rooms based on centers
                  				// randomly start with horizontal or vertical corridors
                  			
                  				if (Rand(2) == 1)
                  				{
                  					CreateHorizontalCorridor(Cell, Corridor.Start.X, Corridor.Stop.X, PreviousRoom.Center.Y);
                  					CreateVerticalCorridor(Cell, Corridor.Start.Y, Corridor.Stop.Y, CurrentRoom.Center.X);
                  				}
                  				else
                  				{
                  					CreateVerticalCorridor(Cell, Corridor.Start.Y, Corridor.Stop.Y, PreviousRoom.Center.X);
                  					CreateHorizontalCorridor(Cell, Corridor.Start.X, Corridor.Stop.X, CurrentRoom.Center.Y);
                  				}
                  				
                  			}			
                  
                  			RoomList.AddItem(CurrentRoom);			
                  		}
                  
                  	}
                  	
                  }
                  
                  function CleanRooms(out array<int> Cell)
                  {
                  	local Room RoomA;
                  	
                  	local Room CorridorA;
                  	local Room CorridorB;
                  
                  	local array<IntPoint> NeighborList; //[x_y]
                  	local array<byte> NeighborPosition;
                  	local IntPoint Current;
                  	local IntPoint Neighbor;
                  	local int KnockoutPositionDataIndex;
                  	local int OppositeKnockoutPositionDataIndex;
                  	local int AdjacentPosition;
                  	local int CorridorNeighbors;
                  	
                  	local IntPoint Grid;
                  	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
                  	
                  `trace();
                  
                  	foreach RoomList(RoomA)
                  	{
                  		`log("#1  RoomA.Start.X="$RoomA.Start.X$",RoomA.Stop.X="$RoomA.Stop.X$",RoomA.Start.Y="$RoomA.Start.Y$",RoomA.Stop.Y="$RoomA.Stop.Y);
                  		
                  		for (Grid.Y = RoomA.Start.Y;  Grid.Y < RoomA.Stop.Y + 1;  Grid.Y++)
                  		{
                  			for(Grid.X = RoomA.Start.X;  Grid.X < RoomA.Stop.X + 1; Grid.X++)
                  			{
                  	
                  				X_Y = Grid.X * MaxSize.Y + Grid.Y;
                  				
                  				//Interior
                  				if (Grid.X > RoomA.Start.X && Grid.X < RoomA.Stop.X && Grid.Y > RoomA.Start.Y && Grid.Y < RoomA.Stop.Y)
                  				{	
                  					if(Cell[X_Y] > 0)
                  					{
                  						Cell[X_Y] = 240;	//1111 0000
                  					}
                  				}
                  				else
                  				//Exterior
                  				{
                  
                  					//if Room border and Wall missing, create door 			
                  					if ( Grid.X == RoomA.Start.X && bool(Cell[X_Y] & 1) == FALSE) 	//W	0001 0000	1
                  					{
                  						Cell[X_Y] = 16;
                  					}
                  					if( Grid.Y ==   RoomA.Stop.Y && bool(Cell[X_Y] & 2) == FALSE)	//S	0010 0000	2
                  					{
                  						Cell[X_Y] = 32;
                  					}			
                  					if ( Grid.X ==  RoomA.Stop.X && bool(Cell[X_Y] & 4) == FALSE)	//E	0100 0000	4
                  					{	
                  						Cell[X_Y] = 64;
                  					}	
                  					if(Grid.Y ==   RoomA.Start.Y && bool(Cell[X_Y] & 8) == FALSE)	//N	1000 0000	8
                  					{
                  						Cell[X_Y] = 128;
                  					}					
                  					
                  				}
                  				
                  			}
                  		}			
                  	}
                  
                  	foreach CorridorList(CorridorA)
                  	{	
                  		//check each cell CorridorA
                  		for (Current.Y = CorridorA.Start.Y;  Current.Y < CorridorA.Stop.Y + 1;  Current.Y++)
                  		{
                  			for(Current.X = CorridorA.Start.X;  Current.X < CorridorA.Stop.X + 1; Current.X++)
                  			{
                  				
                  				//reset neighbor list
                  				NeighborList.Length = 0;
                  				NeighborPosition.Length = 0;
                  					
                  				//loop thru all adjacent neighbors WSEN
                  				for(AdjacentPosition = 0; AdjacentPosition < NeighborPositionData.Length; AdjacentPosition++)
                  				{
                  					//calculate neighbors
                  					Neighbor = default.NeighborPositionData[AdjacentPosition];
                  				
                  					Neighbor.X += Current.X;
                  					Neighbor.Y += Current.Y;
                  					
                  					//check all other corridors
                  					foreach CorridorList(CorridorB)
                  					{
                  						for (Grid.Y = CorridorB.Start.Y;  Grid.Y < CorridorB.Stop.Y + 1;  Grid.Y++)
                  						{
                  							for(Grid.X = CorridorB.Start.X;  Grid.X < CorridorB.Stop.X + 1; Grid.X++)
                  							{
                  								if(Neighbor.X == Grid.X && Neighbor.Y == Grid.Y)
                  								{	
                  									//add to neighbor list
                  									NeighborList.AddItem(Neighbor);
                  									NeighborPosition.AddItem(AdjacentPosition);
                  								}	
                  								
                  							}
                  						}
                  					}					
                  				}
                  				
                  				//neighbors
                  				for (CorridorNeighbors=0; CorridorNeighbors < NeighborList.Length; CorridorNeighbors++)
                  				{
                  					Neighbor = NeighborList[CorridorNeighbors];
                  					
                  					//knockout opposite wall between Current and Neighbor 
                  					//skip 1, wrap NeighborKnockoutPositionData Index			
                  					KnockoutPositionDataIndex = NeighborPosition[CorridorNeighbors];
                  					OppositeKnockoutPositionDataIndex = (KnockoutPositionDataIndex + 2) % NeighborKnockoutPositionData.Length;
                  					
                  					X_Y = Neighbor.X * MaxSize.Y + Neighbor.Y;
                  					
                  					if((Cell[X_Y] & default.NeighborKnockoutPositionData[KnockoutPositionDataIndex]) != 0)
                  					{
                  						Cell[X_Y] -= default.NeighborKnockoutPositionData[KnockoutPositionDataIndex];
                  					}
                  					
                  					X_Y = Current.X * MaxSize.Y + Current.Y;
                  					
                  					if((Cell[X_Y] & default.NeighborKnockoutPositionData[OppositeKnockoutPositionDataIndex]) != 0) 
                  					{
                  						Cell[X_Y] -= default.NeighborKnockoutPositionData[OppositeKnockoutPositionDataIndex];
                  					}
                  				}				
                  			}
                  		}	
                  	}
                  /**/	
                  }
                  
                  //Returns the number of cells in a ring around (x,y) that are alive.
                  function int CountAliveNeighbours(out array<int> Cell, IntPoint Current)
                  {
                  	local int Count;
                  	local IntPoint Neighbor;
                  	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)	
                  	local int AdjacentPosition;
                  	
                  `trace();
                  			
                  	//loop thru all adjacent neighbors WSEN
                  	for(AdjacentPosition = 0; AdjacentPosition < NeighborPositionData.Length; AdjacentPosition++)
                  	{			
                              
                  		//calculate neighbors
                  		Neighbor = default.NeighborPositionData[AdjacentPosition];
                  					
                  		Neighbor.X += Current.X;
                  		Neighbor.Y += Current.Y;
                  			
                  		X_Y = Neighbor.X * MaxSize.Y + Neighbor.Y;			
                  
                  		//In case the index we're looking at it off the edge of the map
                  		if(Neighbor.X < 0 || Neighbor.Y < 0 || Neighbor.X >= MaxSize.X || Neighbor.Y >= MaxSize.Y)
                  		{
                  			Count++;
                  		}
                  		//Otherwise, a normal check of the neighbour
                  		else if(Cell[X_Y] > 0)
                  		{
                  			Count++;
                  		}
                  	}
                  	return Count;
                  }
                  
                  function DoSimulationStep(out array<int> Cell)
                  {
                  	// map will hold all cells that make up our game map
                   	local array<int> TempCell;
                   	local IntPoint Grid;
                  	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
                  	local int nbs;
                  	
                  `trace();
                  
                  	//Copy Previous Map into Temp
                  	for (X_Y = 0; X_Y < MaxSize.X * MaxSize.Y; X_Y++)
                  	{
                              TempCell[TempCell.Length] = Cell[X_Y];
                  	}
                  	
                  	for(Grid.Y=0; Grid.Y < MaxSize.Y; Grid.Y++)
                  	{
                  		for(Grid.X=0; Grid.X < MaxSize.X; Grid.X++)
                  		{
                  
                  			X_Y = Grid.X * MaxSize.Y + Grid.Y;
                  			
                  			nbs = CountAliveNeighbours(TempCell, Grid);
                  			//The new value is based on our simulation rules
                  			//First, if a cell is alive but has too few neighbours, kill it.
                  			if(TempCell[X_Y] > 0)
                  			{
                  				Cell[X_Y] = nbs < DeathLimit ? 0: 15;
                  			} 
                  			//Otherwise, if the cell is dead now, check if it has the right number of neighbours to be 'born'
                  			else
                  			{
                  				Cell[X_Y] = nbs > BirthLimit ? 15: 0;
                  			}
                  		}
                  	}
                  
                  		
                  }
                  
                  	
                  /** Generate PCG Dungeon Grid */
                  function array<int> Generate(int GridMaxX, int GridMaxY, int CellBirthLimit, int CellDeathLimit, int CellInitialChance, int NumberOfSteps, optional string Filename)
                  {
                  	// map will hold all cells that make up our game map
                   	local array<int> Cell; //[x_y] --> X,Y  --> X * max.X + Y	
                  		
                  	local IntPoint Grid;
                  	
                  	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
                  
                  	local int TotalCells;
                  	local int VisitedCells;
                  	
                  	local float ChanceToStartAlive;
                  	local int IterateSim;
                  	
                  	local string TSV; //Output map Tab-separated values	
                  	
                  `trace();
                  	
                  	// this for loop iterates through map, placing only wall cells
                  	
                  	MaxSize.X = GridMaxX;
                  	MaxSize.Y = GridMaxY;
                  	
                  	//set TotalCells = number of Cells in grid
                  	TotalCells = MaxSize.X * MaxSize.Y;
                  	
                  `log("set TotalCells MaxSize.X="$MaxSize.X$",MaxSize.Y="$MaxSize.Y$",TotalCells="$TotalCells);	
                  
                  	//intialize Grid Cells with same chance to be alive
                  	//We're going to start out by randomly setting each cell to either dead or alive.
                  	//Each cell will have the same random chance of being made alive, and you should 
                  	//make sure that this chance value is set in a variable somewhere, 
                  	//because we'll definitely want to tweak it later and having it somewhere 
                  	//easy to access will help us with that. I'll use 45% to start off with.	
                  	
                  	ChanceToStartAlive = 0.45f;
                  	
                  	for (VisitedCells = 0; VisitedCells < TotalCells; VisitedCells++)
                  	{
                              cell[Cell.Length] = frand() < ChanceToStartAlive ? 15: 0; //Alive:1111, Dead:0000
                  	}
                  	
                  	//table dump
                  	for(Grid.Y = 0;Grid.Y < MaxSize.Y;Grid.Y++)
                  	{	
                  		for (Grid.X = 0;Grid.X < MaxSize.X;Grid.X++)
                  		{
                  			X_Y = Grid.X * MaxSize.Y + Grid.Y;
                  			`log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);
                  		}
                  	}	
                  
                  	// call place Rooms to... place... Rooms
                  	//PlaceRooms(Cell, GridMaxX, GridMaxY, default.MaxRooms);
                  	
                  	// clean up entry/exit (corridors)
                  	//CleanRooms(Cell);
                  	for(IterateSim = 0;IterateSim < NumberOfSteps; IterateSim++)
                  	{	
                  		DoSimulationStep(Cell);
                  	}
                  	
                  	//Dungeon completed, id Cellbases
                  	`log("Cave Output ("$MaxSize.X$"x"$MaxSize.Y$"):");
                  	for(Grid.Y = 0;Grid.Y < MaxSize.Y;Grid.Y++)
                  	{	
                  		for (Grid.X = 0;Grid.X < MaxSize.X;Grid.X++)
                  		{
                  
                  			X_Y = Grid.X * MaxSize.Y + Grid.Y;
                  	
                  //`log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);
                  			
                  			TSV $= Cell[X_Y]$chr(9);
                  			//select mesh
                  		}
                  		TSV $= chr(13);
                  	}
                  	`log("TSV:"$chr(13)$TSV);
                  	
                  	return Cell;	
                  	
                  }
                  
                  /** Construct PGC Dungeon in World */
                  simulated function Construct(out array<int> Cell, actor other)
                  {
                  	
                  	local IntPoint Grid;
                  	local int X_Y; //Multi-dim Index: X,Y (X * MaxSize.Y + Y)
                  	local vector Position;
                  	local vector WallLocation; 
                  	local rotator WallRotation;
                  	local vector RoomHalfSize;
                  	//local vector WallPadding;
                  	local F6ApexDestructibleActor Wall;
                  	local Material WallMaterial[4];
                  
                  	`trace();
                  	
                  	`log("MaxSize.X="$MaxSize.X$"MaxSize.Y="$MaxSize.Y);
                  	
                  	Position.Z = default.StartPosition.Z;
                  	WallLocation.Z = Position.Z + 128;
                  	RoomHalfSize =  default.RoomSize / 2;
                  	WallMaterial[0] = Material'layout.layout03_Mat';
                  	WallMaterial[1] = Material'layout.layout01_Mat';
                  	WallMaterial[2] = Material'layout.layout02_Mat';
                  	WallMaterial[3] = Material'layout.layout04_Mat';
                  
                  	for(Grid.Y = 0;Grid.Y < MaxSize.Y;Grid.Y++)
                  	{	
                  		for (Grid.X = 0;Grid.X < MaxSize.X;Grid.X++)
                  		{
                  
                  			X_Y = Grid.X * MaxSize.Y + Grid.Y;
                  			`log("Grid["$Grid.X$","$Grid.Y$"] Cell["$X_Y$"]="$Cell[X_Y]);
                  
                  			Position.X = default.StartPosition.X + (Grid.X * RoomSize.X);
                  			Position.Y = default.StartPosition.Y + (Grid.Y * RoomSize.Y);	
                  			
                  			`log("Position.X="$Position.X$",Position.Y="$Position.Y);
                  
                  			//select variance
                  			//Variance type (1-127 Normal Wall)
                  			
                  			if ( Cell[X_Y] > 0 ) 		
                  			{
                  				WallLocation.X = Position.X;
                  				WallLocation.Y = Position.Y;
                  				WallRotation.Roll = -90.0 * DegToUnrRot;
                  				Wall = other.Spawn(class'F6ApexDestructibleActor',,, WallLocation, WallRotation);
                  				Wall.SetMaterial(WallMaterial[0],WallMaterial[0]);
                  				`log("Floor Wall"$chr(13)$"Object.Movement.Location (X="$Wall.Location.X$",Y="$Wall.Location.Y$",Z="$Wall.Location.Z$")"$chr(13)$"Object.Movement.Rotation (Pitch="$WallRotation.Pitch$",Yaw="$WallRotation.Yaw$",Roll="$WallRotation.Roll$")");
                  			}						
                  /*			
                  			//W
                  			if ( bool(Cell[X_Y] & 1) ) 		
                  			{
                  				WallLocation.X = Position.X - RoomHalfSize.X;
                  				WallLocation.Y = Position.Y;
                  				WallRotation.Yaw = 90.0 * DegToUnrRot;
                  				Wall = other.Spawn(class'F6ApexDestructibleActor',,, WallLocation, WallRotation);
                  				Wall.SetMaterial(WallMaterial[0],WallMaterial[0]);
                  				`log("West Wall"$chr(13)$"Object.Movement.Location (X="$Wall.Location.X$",Y="$Wall.Location.Y$",Z="$Wall.Location.Z$")"$chr(13)$"Object.Movement.Rotation (Pitch="$WallRotation.Pitch$",Yaw="$WallRotation.Yaw$",Roll="$WallRotation.Roll$")");
                  			}
                  			
                  			//S
                  			if( bool(Cell[X_Y] & 2) )		
                  			{
                  				WallLocation.X = Position.X;
                  				WallLocation.Y = Position.Y + RoomHalfSize.Y;
                  				WallRotation.Yaw = 180.0  * DegToUnrRot;
                  				Wall = other.Spawn(class'F6ApexDestructibleActor',,, WallLocation, WallRotation);
                  				Wall.SetMaterial(WallMaterial[1],WallMaterial[1]);
                  				`log("South Wall"$chr(13)$"Object.Movement.Location (X="$Wall.Location.X$",Y="$Wall.Location.Y$",Z="$Wall.Location.Z$")"$chr(13)$"Object.Movement.Rotation (Pitch="$WallRotation.Pitch$",Yaw="$WallRotation.Yaw$",Roll="$WallRotation.Roll$")");
                  			}
                  			
                  			//E			
                  			if ( bool(Cell[X_Y] & 4) )		
                  			{
                  				WallLocation.X = Position.X + RoomHalfSize.X;
                  				WallLocation.Y = Position.Y;
                  				WallRotation.Yaw = 270.0 * DegToUnrRot;
                  				Wall = other.Spawn(class'F6ApexDestructibleActor',,, WallLocation, WallRotation);
                  				Wall.SetMaterial(WallMaterial[2],WallMaterial[2]);
                  				`log("East Wall"$chr(13)$"Object.Movement.Location (X="$Wall.Location.X$",Y="$Wall.Location.Y$",Z="$Wall.Location.Z$")"$chr(13)$"Object.Movement.Rotation (Pitch="$WallRotation.Pitch$",Yaw="$WallRotation.Yaw$",Roll="$WallRotation.Roll$")");
                  			}
                  			
                  			//N
                  			if( bool(Cell[X_Y] & 8) )			
                  			{
                  				WallLocation.X = Position.X;
                  				WallLocation.Y = Position.Y - RoomHalfSize.Y;
                  				WallRotation.Yaw = 360.0  * DegToUnrRot;
                  				Wall = other.Spawn(class'F6ApexDestructibleActor',,, WallLocation, WallRotation);
                  				Wall.SetMaterial(WallMaterial[3],WallMaterial[3]);
                  				`log("North Wall"$chr(13)$"Object.Movement.Location (X="$WallLocation.X$",Y="$WallLocation.Y$",Z="$WallLocation.Z$")"$chr(13)$"Object.Movement.Rotation (Pitch="$WallRotation.Pitch$",Yaw="$WallRotation.Yaw$",Roll="$WallRotation.Roll$")");
                  			}
                  */
                  		}
                  
                  	}
                  
                  }
                  
                  defaultproperties
                  {
                  	
                  	//WSEN
                  	//0123
                  	//-1, -1(NW) -- 0,-1(N) -- +1, 0(NE)
                  	//               |
                  	//-1, 0 (W)  -- 0, 0    -- +1, 0(E) 
                  	//               |
                  	//-1, 0 (SW) -- 0,+1(S) -- +1, 0(SE)	        KnockoutPositionData Index XRef
                  	NeighborPositionData.Add((X=-1,Y=0))		//W:0
                  	NeighborPositionData.Add((X=0,Y=1))		//S:1
                  	NeighborPositionData.Add((X=1,Y=0))		//E:2
                  	NeighborPositionData.Add((X=0,Y=-1))		//N:3
                  	NeighborPositionData.Add((X=-1,Y=1))		//SW
                  	NeighborPositionData.Add((X=1,Y=1))		//SE
                  	NeighborPositionData.Add((X=1,Y=-1))		//NE
                  	NeighborPositionData.Add((X=-1,Y=-1))		//NW	
                  	
                  	//NESW
                  	//8421
                  	//position (opposite = (KnockoutPositionDataIndex + 2) % (NeighborKnockoutPositionData.Length-1))) 
                  	NeighborKnockoutPositionData.Add(4) //E:0100
                  	NeighborKnockoutPositionData.Add(8) //N:1000
                  	NeighborKnockoutPositionData.Add(1) //W:0001
                  	NeighborKnockoutPositionData.Add(2) //S:0010
                  
                  	MaxRooms=16
                  	MinRoomSize=2
                  	MaxRoomSize=7
                  	
                  	BirthLimit=4
                  	DeathLimit=3
                  	InitialChance=0.4  
                  	Steps=2
                  	
                  	StartPosition=(X=86000.000000,Y=74500.000000,Z=4240.000000)
                  	RoomSize=(X=128.0,Y=128.0,Z=0.0)
                  	WallPadding=(X=0.1,Y=0.1,Z=0.1)	
                  }
                  CustomPlayerController.uc
                  Code:
                  exec function GenerateCave(optional int GridMaxX, optional int GridMaxY, optional int CellBirthLimit, optional int CellDeathLimit, optional float CellInitialChance, optional int NumberOfSteps, optional string Filename)
                  {
                  	local F6PCGCave Cave;
                  	local array<int> Cell;
                  
                  `trace();
                  
                  	if(GridMaxX == 0)
                  	{
                  		GridMaxX = 16;
                  	}	
                  	if(GridMaxY == 0)
                  	{		
                  		GridMaxY = 16;
                  	}
                  	if(CellBirthLimit == 0)
                  	{
                  		CellBirthLimit = 4;
                  	}	
                  	
                  	if(CellDeathLimit == 0)
                  	{
                  		CellDeathLimit = 3;
                  	}	
                  	
                  	if(CellInitialChance == 0)
                  	{
                  		CellInitialChance = 0.4f;
                  	}	
                  	
                  	if(NumberOfSteps == 0)
                  	{
                  		NumberOfSteps = 2;
                  	}	
                  
                  	Cave = new(self) class'F6PCGCave';
                  	Cell = Cave.Generate(GridMaxX, GridMaxY, CellBirthLimit, CellDeathLimit, CellInitialChance, NumberOfSteps, Filename);
                  	Cave.Construct(Cell,self);
                  }
                  Launch.log Output Example
                  Code:
                  [0029.48] ScriptLog: TSV:
                  15	15	15	15	15	15	15	15	15	0	0	15	15	15	15	15	
                  15	15	15	0	15	15	15	0	0	0	0	0	15	15	15	15	
                  15	15	0	0	0	15	15	0	0	0	0	15	15	15	15	15	
                  15	15	0	0	0	15	15	0	0	15	15	15	15	15	15	15	
                  15	15	0	0	0	15	15	0	15	15	15	15	15	15	15	15	
                  15	15	0	0	0	15	0	0	15	15	15	15	15	15	15	15	
                  15	15	0	0	0	0	0	0	15	15	15	15	15	0	0	15	
                  15	15	0	0	0	0	0	15	15	15	15	15	15	0	0	15	
                  15	15	0	0	0	0	15	15	15	0	0	15	15	0	15	15	
                  15	15	15	0	0	0	0	15	0	0	0	0	0	0	0	15	
                  15	15	15	0	0	0	0	15	15	0	0	0	0	0	0	0	
                  15	15	0	0	0	0	15	15	15	15	15	15	0	0	0	0	
                  15	0	0	0	0	15	15	15	15	15	15	15	0	0	0	15	
                  15	0	0	15	15	15	15	15	15	15	0	0	0	0	15	15	
                  15	15	15	15	15	15	15	15	15	15	0	0	0	15	15	15	
                  15	15	15	15	15	15	15	15	15	15	0	0	15	15	15	15
                  [SHOT]https://arcadekomodo.com/home/wp-content/uploads/2013/11/PCGCave.png[/SHOT]
                  [SHOT]https://arcadekomodo.com/home/wp-content/uploads/2013/11/UDK-2013-12-01-00-39-15-56.png[/SHOT]

                  Comment

                  Working...
                  X