Generate a 3D border from a 2D map

Hello everyone!

For a little side-project i am currently working on a procedural dungeon generator. It works similiar to cellular automata like game of life but it creates pseudo organic rooms from a 2D noise map.

At the current point i created the map, separated the rooms, connected the rooms by corridors and mapped out the borders, all on a 2D grid. You can see an example here:


Everything black is "empty", grey are the rooms and corridors. The blue squares are the border pixels.

The next step i was planning to do was to create a 3D representation of the borders as walls so i could use it as a kind of canyon environment. But i am stuck at this... I need to find a way to generate lines that have a vertex at the center of each border pixel and are continous around the rooms so i can create a 3D wall.
At the end i want to have 3D walls instead of blue border pixels...

I am not really sure if i made clear what i am trying to achieve...

So, do you guys have some ideas on how to do this? Preferably without using additional or external libraries...

Thank you!

 

Hello !

Cool little project you got there ^^, I'd base the calculation on adjacent blue points and extrapolate its upper points:


With this you can easily guess how to split it in 2 triangles to make a square (or more if you want to fancy up the shape a little bit later on).

You can also bend the upper position outwards by ponderating nearby grey squares into a direction vector you add to the upper point !

 

hey thanks for your reply!

I think with your idea i will run into problems very fast. First i would have to guess a good starting point and from there walk trough my rooms. If i find a good starting point it will be fine as long as i do not get to a 3 or more way crossing. And i have to admit, i cant think of a good way to pack it into an algorithm to include all those cases...

I am working on an approach right now, if this one fails i will try yours!

 

np

You can include the grey squares into the equation, search for 2 diagonal blue like on my image and 1 grey in middle, or search for 2 blue side by side and 2 matching grey ones, it should cover the small inner islands this way.

 

As soon as i posted my question i had an idea on how to do this, here is how it worked out:



The lines are dim at the beginning and get brighter towards the end, this way i can tell where a line starts and ends.

Here is a rough outline how it works at the moment:

You need a List<List<Vector2>> to hold every continous line that will be found.

Code (CSharp):

1. void FindBorderLines () {
2.         borderLines.Clear();
3.         for (int x = 0; x < width; x++) {
4.             for (int y = 0; y < height; y++) {
5.                 bool listed = false;
6.                 Vector2 nextVertex = new Vector2 ( (float)x, (float)y );
7.                 //Check if this border vertex was in a previous line.
8.                 for ( int i = 0; i < borderLines.Count; i++ ) {
9.                     for ( int j  = 0; j < borderLines[i].Count; j++ ) {
10.                         if ( borderLines[i][j] == nextVertex ) {
11.                             listed = true;
12.                         }
13.                         if ( listed ) break;
14.                     }
15.                     if ( listed ) break;
16.                 }
17.                 //If at the position x,y on the map is a border and if that border vertex was not listed, start a line here
18.                 if ( borders[x,y] == 1 && !listed ) {
19.                     //A new Line is created as a List<Vector2>
20.                     List<Vector2> currentBorder = new List<Vector2>();
21.                     //The line is followed by this function.
22.                     currentBorder = FollowBorder (x,y, currentBorder);
23.                     //When the line is complete, add it to the list. borderLines is a List<List<Vector2>>
24.                     borderLines.Add ( currentBorder );
25.                 }          
26.             }
27.         }
28.     }

and the other function is:

Code (CSharp):

1. List<Vector2> FollowBorder ( int x, int y, List<Vector2> currentBorder = null ) {
2.         if ( currentBorder == null ) currentBorder = new List<Vector2>();      
3.         currentBorder.Add(new Vector2((float)x, ((float)y)));
4.         //This controls how far away the next border vertex can be, 1 means one in each direction,
5.         //effectively a 3 x 3 grid
6.         int range = 1;
7.         Vector2 nextBorderPosition = Vector2.zero;
8.         for (int i = -range; i <= range; i++) {
9.             for (int j = -range; j <= range; j++) {
10.                 //proceed only if the coordinate to test lies within the boundaries and is not the center.
11.                 if ( !(i == 0 && j == 0) && x + i < width && x + i > 0 && y + j < height && y + j > 0 ) {  
12.                     //proceed only if the origin and the new vertex both are borders.
13.                     if ( borders[x,y] == 1 && borders[x + i, y + j] == 1 ){
14.                         Vector2 nextVertex = new Vector2((float)(x + i), ((float)(y + j)));
15.                         //Check if the vertex has been collected earlier in the same list.
16.                         bool inList = false;
17.                         for ( int k = 0; k < currentBorder.Count; k++ ) {
18.                             if ( currentBorder[k] == nextVertex ) {
19.                                 inList = true;
20.                             }
21.                             if ( inList ) break;
22.                         }
23.                         //Check if the vertex is in any other previous line.
24.                         if ( !inList ) {
25.                             for ( int k = 0; k < borderLines.Count; k++ ) {
26.                                 for ( int l = 0; l < borderLines[k].Count; l++ ) {
27.                                     if ( borderLines[k][l] == nextVertex ) {
28.                                         inList = true;
29.                                     }      
30.                                     if ( inList ) break;
31.                                 }
32.                                 if ( inList ) break;
33.                             }
34.                         }
35.                         //If it was in no other line, try to add it as a contestant to the current line.
36.                         if ( !inList ) {
37.                             if ( nextBorderPosition == Vector2.zero ) {
38.                                 nextBorderPosition = nextVertex;
39.                             } else {
40.                                 Vector2 borderCandidate = nextVertex;
41.                                 //Check if this vertex is closer than the last checked vertex, if it is
42.                                 //it becomes the new contestant. This leaves the vertex with
43.                                 //the shortest distant at the end of the loop.
44.                                 if ( (currentBorder[currentBorder.Count - 1] -  borderCandidate).magnitude < (currentBorder[currentBorder.Count - 1] -  nextBorderPosition).magnitude) {
45.                                     nextBorderPosition = borderCandidate;
46.                                 }
47.                             }
48.                         }
49.                     }
50.                 }
51.             }
52.  
53.         }
54.         //If a contestant for the next vertex was found, add it to the line and start over from that one.
55.         if ( nextBorderPosition != Vector2.zero ) {
56.             currentBorder.Add ( nextBorderPosition );
57.             //recursion ftw!
58.             currentBorder = FollowBorder ( (int)nextBorderPosition.x, (int)nextBorderPosition.y, currentBorder );
59.         }
60.         //When it fails,pass down the line to the previous function!
61.         return currentBorder;
62.     }

So, this is highly unpolished and dirty code, but it is working... i have to iron out some kinks here and there (gaps between lines... ) and i hope it will be the base for my 3d walls then...