next »

[Armageddon]

So I'm doing a procedural game and each room is a 5x5 grid of walkable and non-walkable areas. I'm using a 2D array like so.

1, 1, 1, 1, 1
1, 1, 1, 1, 1
1, 1, 1, 1, 1
1, 1, 1, 1, 1
1, 1, 1, 1, 1

1 is walkable 0 is non-walkable. Okay so the problem is that when I punch obstacles into my map by randomly making coords equal 0 I end up with "floating" tiles, or non-connected tiles. One way I've found to fix this is with a flood fill check before adding an obstacle. And that works, I found this and am generally just doing what he does to solve it. But in most cases I need multiple tiles to always link to each other.

I'm doing a dungeon game and every room can have a north, east, south, and west entrance/exit. So I try to flood fill from each point. The problem is that it's treating each point as it's own separate area to fill from, so I get disconnected areas. The areas are 0,2 2,4 2,0 4,2 respective to n, e, s, w. I can't figure out how to get it to treat it as one area so I'm hoping someone can help or provide a different solution.

Code:

bool MapIsFullyAccessible(bool[,] obstacleArray, int currentObstacleCount, int[] currentRoom) {
	bool[,] mapFlags = new bool[obstacleArray.GetLength(0), obstacleArray.GetLength(1)];
	Queue<int[]> queue = new Queue<int[]>();
	int accessibleTileCount = 0;

	//These are north, east, south, and west toggles for exits
	if (currentRoom[0] == 1) {
		queue.Enqueue(new int[2] { 0, 2 } );
		mapFlags[0, 2] = true;
		accessibleTileCount++;
	}
	if (currentRoom[1] == 1) {
		queue.Enqueue(new int[2] { 2, 4 } );
		mapFlags[2, 4] = true;
		accessibleTileCount++;
	}
	if (currentRoom[3] == 1) {
		queue.Enqueue(new int[2] { 4, 2 } );
		mapFlags[4, 2] = true;
		accessibleTileCount++;
	}
	if (currentRoom[4] == 1) {
		queue.Enqueue(new int[2] { 2, 0 } );
		mapFlags[2, 0] = true;
		accessibleTileCount++;
	}
		
	while (queue.Count > 0) {
		int[] tile = queue.Dequeue();
		
		for (int x = -1; x <= 1; x++) {
			for (int y = -1; y <= 1; y++) {
				int neighbourX = tile[0] + x;
				int neighbourY = tile[1] + y;
				if (x == 0 || y == 0) {
					if (neighbourX >= 0 && neighbourX < obstacleArray.GetLength(0) && neighbourY >= 0 && neighbourY < obstacleArray.GetLength(1)) {
						if (!mapFlags[neighbourX, neighbourY] && !obstacleArray[neighbourX, neighbourY]) {
							mapFlags[neighbourX, neighbourY] = true;
							queue.Enqueue(new int[2] { neighbourX, neighbourY } );
							accessibleTileCount++;
						}
					}
				}
			}
		}
	}
	
	int targetAccessibleTileCount = obstacleArray.GetLength(0) * obstacleArray.GetLength(1) - currentObstacleCount;
	return targetAccessibleTileCount == accessibleTileCount;
}

Thanks!

[Armageddon]

Well I tried Prim's algorithm today. It also doesn't work when trying to ensure multiple grid points are generated to/connected.

[ghosted]

This may not be the response you want to hear but if it's only a 5x5 structure it might be better to just hand build 20-30 safe designs and then just pick one at random for each room. There's so little granularity in a 5x5 space that being able to say it's "procedural" surely isn't worth the headache?

In contrast, quickly creating some really nice layouts and then knowing they work can be done in no time and allow you to focus the content of the dungeons better. This would also help you to avoid the awkward edge cases that procedural generation creates. For example, Spelunky is procedural but the geometry is pulled from a list of pre-built chunks (a map is built of a 4x4 grid of these chunks). I played that game for months and never noticed the repetition.

[Dacke]

I'm not 100% sure I understand what the problem is.

But I think you're saying that:
1. You add a random obstacle
2. You want to know if that obstacle partitioned the open space?

In that case:
1. select any cell that is a 1
2. floodfill from that point and count the number of connected 1:s
3. if (floodfill count == total 1:s count) then no partition has occurred, but if (floodfill count != total 1:s count) then the floodfill couldn't reach every 1, and there is a partition

[bateleur]

Whilst I sort of agree with ghosted's answer, there's some really good stuff on maze generation here (scroll down to "Maze Creation Algorithms"): Maze Classification and Algorithms

[Armageddon]

I'm not 100% sure I understand what the problem is.

But I think you're saying that:
1. You add a random obstacle
2. You want to know if that obstacle partitioned the open space?

In that case:
1. select any cell that is a 1
2. floodfill from that point and count the number of connected 1:s
3. if (floodfill count == total 1:s count) then no partition has occurred, but if (floodfill count != total 1:s count) then the floodfill couldn't reach every 1, and there is a partition

Yes but the problem is that you can only floodfill from one tile when the room can have up to four exits and they all need to be reachable from each other. Floodfilling from multiple tiles ends up with multiple partitions.

Anyways I think ghosted is right, it'd be more effective to just make 20-30 pre-built/designed layouts that work well than making rules for something so small. I'll probably end up just randomizing loot and items and possibly enemy placements.

[Dacke]

Maybe I'm still not understanding the problem, but that wasn't what I suggested?

Don't start from different places. Just start from one place and see if you can reach all the other places.

1. Start from one of the exits
2. Floodfill and see if you reach all the other exits from that starting point

If you can reach all the other three, it works. If you can't reach all three, there is a partition.

Or what am I missing?

[valrus]

This is a very puzzling conversation.

But yes, listen to Dacke.  For any set of elements, doing *one* floodfill from any of them will tell you whether or not they can all be reached from each other.