Map Generator in Unity C# _ 3 Connecting rooms

There are 2 kinds of  tiles in the map matrix:

1.  not walk-able ,value 1;  2. walk-able, value 0;  

The target is make a walk-able rout, value 0 on the map matrix to  connect all rooms so that they are all accessible.

Normal way of doing it is calculating the distance between two tiles from two rooms and pick the nearest two to make route from as shown on the image below.

But I used another way to do it.

The thought is very simple: each time, enlarge the room by 1 unit until the room meet other rooms. From the contact unit, find the rout. 

To illustrate it: 

Expand the edge tiles

As can be seen. The edge units expand by 1, if there's no contacts, the units created by last expand expand again. This process repeats until all routs are found. Then we come across with another problem: when do we know we have all the routs and stop expanding?

numbers of routs

the target is : making all the rooms accessible, this means all rooms are connected into one area. 

If we have n rooms, at least n-1 routs should be used to connect them. Can we say, if we have n-1 routs all rooms are connected ? Yes, with one condition : not routs are redundant. But what is a redundant rout? A redundant rout is a rout that connects two rooms which are already connected in other way. Here's an example: 

A B C D are four rooms. The line between two rooms stand for a rout. 

As can be seen, in the left example, 1 2 3 connect all four rooms, but in the right example, 1 2 4 can not connect four rooms. D is isolated. Because 4 is a redundant rout that connects room C and B which are already connected through 1 2 and A.

       

To implement this is very simple. When a new rout is created, two rooms which are connected by the rout is marked as connected. Before creating another new rout, check the two rooms that will be connected by the rout. If there is at least one unconnected room, this is not a redundant rout and can be created.

Illustrate this with the right side example: red rooms are connected rooms. When rout 1 is created , A and B are marked, when rout 2 is created, C is marked as well. Before making new rout 4,  B and C are checked for connected mark, but as B and C are all marked as connected, so rout 4 is not a valid rout, need to find another room.

get the rout from contact point

There is still one problem need to be solve before I can start with designing the functions: 

When we get the contact tile, how to find out other tiles on the rout.

When enlarging the room, a tile get the four neighbor tiles around it. if the neighbor tiles do not belong to the room, they are added to the enlarge list. In other word, each expanded tile has base tiles from where it is created. Thus it is possible to search back all the tiles until we meet the room. The contact tile will have two base tiles. 

In the following example, the contact tile where B and C meet is marked with thick outline. The arrows between the tiles shows from which tile the new tile is created. The number on the tiles stand for index of the tile.  For room C, tile 0 expand to tile 1, tile 1 expand to tile 3 which is the contact tile. To search back, tile 3 's base tile is tile 2, tile 2's base tile is tile 1, tile 1 's base class is tile 0, tile 0 belong to room C. So the rout connect room C and B on C's side is [tile 1, tile 2, tile 3]  

To store this structure, just add two properties to the already existed CoordTile class (The CoordTile class is used to store information for each tiles includes coordinator of the tile, walk-ability of the tile)

CoordTile parent1;

CoordTile parent2;

Use these two properties to store from which tile this tile is enlarged.

Design the functions

1. makeRout : iterate through a list of routs, get each tile from the rout and make                               the tile 0 (walkable) on the map matrix

2. getRoutList : get route by enlarging all rooms until all routs are found

3. swellRoom : enlarge all the rooms by one unit, if there are any contact point, get                             the rout from that point

4. getRoutViaTile : from the contact point search back for all the tiles on the rout.

The result

I close the function of deleting small isolated room, as I want more rooms to test.

As can be seen, all the rooms are connected even it only has one tile.

The Code

you can find the source here:

find rout by enlarging room

Map Generator in Unity C# _ 2

When to use recursive. 

I have been working on the map generation project / tutorial for a while. My way of doing the tutorial is briefly understand how to solve a problem and then try to figure out the functions / class / structure myself and then go back to read the tutorial code to see if there are any differences.

As I was working on identifying connected area in the map, I broke down my question to several layers:

Function1 : A function that return a list of connected area list.
void getAreaList(int[,] myMap, List<List<CoordTitle>> targetList )
the function iterates map[,], get the unchecked tiles, get the area list that connected to the given tile(Function2)

Function2:  get the area list that connected to the given tile
void getAreaTile(CoordTitle myRefTile, List<CoordTitle> resultTileList)

I started to think about recursive function here, as the algorithm is quite straight forward.  The function search the four neighbor tiles around it, and add the target tiles in the list, then iterate each result tile in the list, call the same function (recursive).

My first try is the recursive function :

It does the job. However I notice that in the tutorial, the author used a queue to store all the target tiles and do the checking process to all that in the queue. 

Here's the new function I made using the tutorial's algorithm.

So I asked myself, why not using recursive but queue in this situation. I did some research on other situations when recursive is the only solution ： Tower of Hanoi, Fibonacci Sequence.

One key different element in connecting tiles problem is that : 

the calculation result of tile(n) does not rely on the result of tile(n-1). Instead of recursive, the connecting tiles function does the same thing to a collection, while the elements of collection is changing over time. The key problem to solve is pushing and popping correct elements from the collection.

The source code can be found here

both two functions can be found in the code.

Also, please forgive my Chinese comment, most of the Chinese comment are pseudocode written for myself before implementing the real functions.

map Generator in Unity C# _1

I am currently working on a map generator project.

The generator can generate different setting of maps each time when play is clicked. The setting of the map , eg, width, height, size of the walk-able space can be adjust in the public parameter.

It uses random function to generate a matrix of on and off nodes,
smooth the value of the nodes according to its surround nodes, and finally use Unity mesh generator to create floor and walls.

It is still in a WIP stage.