Creating maze/dungeon with in-depth search

[Ardenian]

I was lately directed to depth-first search and I would like to create such a system for my map project.
However, from basic reading I understand nothing. I know people here on Hiveworkshop successfully created maps with systems of this kind in the past, so I hope to receive some inital help.

Basically, I would like to create randomly generated maps, similar to this one:

Example

The generated maps should have halls and rooms and I should be able to interact with the generated room-structure.
How would I set up a system/algorithm like this ? ( Jass and/or GUI)

 

[Chaosy]

You could do it fairly easily if you don't care for performance nor perfection.

In C you can do this: It allows you to create a 2D map easily and more importantly visualize it.

int i [] = 
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

In your case you give each "0" a random generated number and when you loop through it you can say 1 = room, 2 = corridor 3 = something else

edit: In warcraft coding words this is basically a 2d array.

 

[Ardenian]

I do care as well for performance and perfection ^^

Thank you, so each 0 represents a tile or point, for example ?
So far so good, but why is it random ? If I manually assign values to it, then I have the same thing over and over again.
That's the point where I am clueless, how to make the whole thing become random.

So a 2d array is something like a grid/hashtable ?

 

[Chaosy]

I thought you wanted it to be random, hence the algorithm? Otherwise you can just manually place it on the map?

 

[Ardenian]

Yes, but I don't understand what's random at the moment.

The code thing you posted, it is like a 2d map of the area, isn't it ? All these numbers are positions in the area or not ?

 

[Chaosy]

You would have each number symbolize a certain kind of room. You can indeed view them as a tile or a grid.

For example:
1. Corridor
2. normal room
3. treasure room
4. boss room

Or whatever suits your needs.

edit: btw there are 2D arrays in Zinc.

real Z[200][200];
function x()
{
     Z[4][4] = 10;
}

 

[Ardenian]

See me as a stupid person who knows nothing about computer science and hardly something about Jass.

So, after your example:
1 = Corridor
2 = normal room
3 = treasure room
4 = boss room

Then:

int i [] = {1,2,3,4}

So i can be one of these four values, alright. But how do I get a generation from this ?

 

[The_Silent]

Depth first search iterates through nodes and "touches" them till it reaches a point where it can "touch" no more nodes (the end), then it goes back to the last previous node that has other "untouched" nodes around it at start over. It repeats this process till it has "touched" all nodes.

It is basically is a search method to search tree data structures.
Here is a video explaining it: https://www.youtube.com/watch?v=iaBEKo5sM7w

Here is a pseudocode example:

DFS(G,v)   ( v is the vertex where the search starts )
         Stack S := {};   ( start with an empty stack )
         for each vertex u, set visited[u] := false;
         push S, v;
         while (S is not empty) do
            u := pop S;
            if (not visited[u]) then
               visited[u] := true;
               for each unvisited neighbour w of u
                  push S, w;
            end if
         end while
END DFS()

You can simulate a stack using an array. "Pop" removes the top/first element, "Push" adds an element to the top.

------------------------------------------------------------------------------------------
I would not use this to generate dungeons however, only mazes, since there is far better dungeon generation algorithms. Such as:

http://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php

http://www.roguebasin.com/index.php?title=C++_Example_of_Dungeon-Building_Algorithm

It does require you to understand some coding and some math.

 

[Chaosy]

Basically this is what you do. You need to develop the generation further to make sure pathing between rooms is done properly but the base is simple as shown.

//! zinc
	library MapGen
	{
		integer rooms[50][50];
		function onInit()
		{
			integer i = 0;
			integer j = 0;
			//the string is just for debugging purposes
			string roomNames [];
			roomNames[0] = "Corridor";
			roomNames[1] = "normal room";
			roomNames[2] = "treasure room";
			roomNames[3] = "boss room";
			while(i < 50)
			{
				while(j < 50)
				{
					rooms[i][j] = GetRandomInt(0, 3);
					BJDebugMsg(roomNames[rooms[i][j]] + " created!");
					j += 1;
				}
				i += 1;
			}
		}
	}
//! endzinc

 

[Ardenian]

@The_Silent Thanks, the first link looks exactly like what I would like to achieve.
No idea about the second link though, too complicated for me.

@Chaosy Hm, I see, thank you, why do we need i and j ? From what I understood, we have 50 rooms in your example or 50 cells ?
'While' is a combination of 'loop' and 'if' ?

 

[Chaosy]

No we have 50x50 rooms. When I think about it you can do it with a normal array.

I just remember that we were told to use 2d arrays in class, but then again we were not going to randomize it we were after the visual declaration I showed you before with the zeros.

So yeah you can use one loop instead.

 

[Ardenian]

I think this topic might be over the top for me.
I am just going to write a pseudo-agorithm having less randomization, but being more understandable to me. Thanks a lot guys!

 

[Zwiebelchen]

Try the donjon dungeon generator:
http://donjon.bin.sh/d20/dungeon/

It also has the sourcecode in Python publicy available on the website. Just need to translate it to Jass.

 

[Ardenian]

A decent tool, thank you.
However, I doubt someone is ready to translate it to Jass ( not vJass by the way), even with less features than the original source code.

 

[Wareditor]

I think it is doable as any dungeon generator algorithm it is doable in vJass but before that you need to get decent at Jass.
I will try to make something and upload it for you.

 

[Ardenian]

That's kind of you, Wareditor!

I managed to create the first step myself in Jass, creating the rooms.
However, right now they can overlay each other, a severe issue I thought easy to be fixed, but it resists to get fixed.

 

[Wareditor]

Okay I created a maze generator but there are some issues that need to be fixed before going forward.

First you can't create cliffs in jass, but that's not a big issue as you can use destructables such as trees (or rocks) to simulate walls.
The most important issue that I am facing right now is that my code isn't able to create big mazes. Theoretically it should be able to create pretty big mazes (90x90x128x3) but the script stop midways for no apparent reason when I input big height or width (above 10).
Well I hope that by optimizing the code (and there is a lot to be done there, I haven't really tried yet), I can increase the max size. I have witness that even removing call BJDebug lines from the "big while part" of the script could help produce bigger mazes. Pretty strange.

Well, here is the demo map. It's not very readable but you can play with the Test trigger by changing the height/width of the dungeon created. Input "c" in the message box to generate the dungeon (well the maze).

Please don't judge the code too much, I just wanted to have something workable first (I used this tutorial as a framework)

 

[Ardenian]

Hey, great job!

If you would like to orientate yourself with my own values,
I myself don't need cliffs.
My rooms are not bigger than 20x20*128 and the whole maze is not bigger than 61x61*128 ( both at the moment).

You use vJass, right ? As I state in post #14, I would like to create it in Jass.
That's not a problem though. I learned a lot from the triggers you wrote and
it solved some problems I had with my own Jass system.

As far as I know we don't have a dungeon generator yet, so a final vJass product in the spell section is surely a great advantage.

 

[Wareditor]

Well when I build the final product it can alway be translated into classic Jass (vJass is still Jass). But why are you only using Jass and not vJass ?

Mind sharing what you got ?

I will keep you updated on my progress.

 

[Ardenian]

I don't use JNGP, that's it. I would like to not go deeper into detail, please.

Up to now, I only finished the basic room creation.

Room Creation

function GridPointX takes integer i, integer i2 returns real
    local real x = I2R(i2)/udg_RoomBreadth[i] - R2I(I2R(i2)/udg_RoomBreadth[i]-0.05)
    set x = x*udg_RoomBreadth[i] -1
    set x = udg_RoomX[i] + x*128
    return x
endfunction

function GridPointY takes integer i, integer i2 returns real
    local real y = R2I(I2R(i2)/udg_RoomBreadth[i] -0.05)
    set y = udg_RoomY[i] - y*128
    return y
endfunction

function GridPoint takes integer i, integer i2 returns location
    local real x = GridPointX(i,i2)
    local real y = GridPointY(i,i2)
    return Location(x,y)
endfunction

function CreateRooms takes nothing returns nothing 
    local integer i = 1
    local integer overlap = 1
    local real x
    local real y
    local real breadth
    local real length
    local boolean xycheck = false
    local real x2
    local real y2
    local boolean overlapcheck = false
    set udg_RoomCount = GetRandomInt( 3, 8) // total rooms

    loop
    exitwhen i > udg_RoomCount
        
        set xycheck = false
        
        // intial randomized room data
        loop
        exitwhen xycheck == true // check if there is an overlap
            set x = 0 + GetRandomReal( -41, 25)*128 // x coordinate of the intial room point
            set y = 0 + GetRandomReal( -25, 41)*128 // y coordinate of the inital room point
            set breadth = I2R(GetRandomInt( 6, 15)) // breadth of the room
            set length = I2R(GetRandomInt( 6, 15)) // length of the room
            set x2 = x + breadth*128 // last point in the room
            set y2 = y - length*128  // last point in the room
            
            set overlapcheck = false
            set overlap = 1
            
            loop
            exitwhen overlap == i or overlapcheck == true
                call BJDebugMsg( "Current room overlap check: "+I2S(overlap)) 
                if x2>udg_RoomX[overlap] and udg_RoomX[overlap] + 128*udg_RoomBreadth[overlap] > x then
                    call BJDebugMsg( "Detected overlapping rooms in x")
                    set overlapcheck = true
                elseif y2 > udg_RoomY[overlap] and udg_RoomY[overlap] - 128*udg_RoomLength[overlap] > y then
                    call BJDebugMsg( "Detected overlapping rooms in y")
                    set overlapcheck = true
                else 
                    set overlapcheck = false
                endif
                set overlap = overlap + 1
            endloop
            
            if overlapcheck == false then
                set xycheck = true
                call BJDebugMsg( "no overlap")
            endif
            
        endloop
        
        set udg_RoomX[i] = x
        set udg_RoomY[i] = y
        set udg_RoomRect[i] = Rect( x, y, x2, y2)
        set udg_RoomBreadth[i] = breadth
        set udg_RoomLength[i] = length
        call BJDebugMsg( "current room: "+I2S(i))
        set i = i + 1
        
        
    endloop
endfunction

function InitTrig_CreateRoom takes nothing returns nothing
endfunction

Not as efficient as it could be yet.

The grid point functions I use for testing whether it works.

It does work, but there are two problems
1. When checking for overlap, there seems to be a problem, as it always only detects a x overlap. I think I would have to check both x and y at the same time, but it is most likely too long, so I haven't re-written it yet.
2. I have no control over distance between rooms.

I am going to start with the 'Connect Rooms with floors' script now.
It is quite a challenge, there are multiple ways and I am not sure yet what I will choose.

Thank you, I will, too, if you want me to.

 

[Wareditor]

Okay I found a way to resolve my issue. The problem was that a thread has a limit of operations it can execute, with my huge loop I just blew it off. So now that I know that I have to start new threads in my code so that it don't go past the limit. I made that change an now I can create huge mazes. Next step is adding rooms and making it feel like a real dungeon!

Are you working with a pre existing algorithm or are you trying to build you own thing ?
I would have an idea how to control the distance between room but in vJass. I never used Jass without JNGP so I have no idea how to think in "Jass".

 

[Ardenian]

Great to hear!
Could you tell me a bit more about the limit of operations, please ?
I faced that, too, but I don't know how to avoid it/ structure my functions to avoid it.

I don't know whether we can call mine an 'agorithm'.
Basically, for a random amount of rooms, I choose a random location (x,y) anywhere on the map and a random breadth and length.
Then I check if this rectangle/square overlaps with an already existing one.
If not, it is a new dungeon room, if yes, then start over again.

About controlling distance, I have a vague idea for it.
I could write a function that moves existing rooms in a way they do not overlap,
but move nearer together, shortening distance.

 

[Wareditor]

I just start a new thread to reset the limit. In vJass I use functioname.execute(). But I think ExecuteFunc() should do the same job. In my code I use it in my big while loop (the one that generates the most action) So each cycle of the loop I run a new thread.
I have been coding the system but I need a break from it right now. I will come back to it this weekend.

 

[Ardenian]

Ahh, I understand, thank you!
I look forward to it