Jump to content
  • Advertisement
starfruit64

C++ Problem With Room Generation For Rougelike Game

Recommended Posts

Hello,

I'm programming a simple rougelike video game for fun. I'm running into a very difficult problem with my room generation code, specifically the part that deals with the maze-like hallway to connect the randomly placed rooms inside a dungeon, using the depth-first search method. The code I've written is kinda long and probably hard to read, but I seriously cannot figure out what is causing the issue so try to bear with me please.

Below is the header file for the Floor class, which generates the floor of the dungeon.

#ifndef FLOOR_H_
#define FLOOR_H_

#include <iostream>
#include <vector>
#include <algorithm>
#include "Cell.h"

class Floor {
private:
	int attempts; //Amount of attempts it tries to place a room before giving up. More attempts = more cramped.
	int maxdoor; //Maximum amount of doors on each room
	int maxroom; //Maximum number of rooms. 0 for 999.

	int maxheight, minheight;
	int maxwidth, minwidth;

	int maxbigroom;

	std::vector<std::vector<Cell> > region; //A collection of regions. A region is a collection of cells (rooms & hallway)
	std::vector<Cell> temp_region; //Used to fill the region.
	std::vector<Cell> temp_maze;
	std::vector<Cell> maze;


public:
	Floor();
	void init(int attempts, int maxdoor, int maxroom, int maxwidth, int minwidth, int maxheight, int minheight, int maxbigroom);
	void gen(Cell cell[120][60], SDL_Texture* tex);
	bool check_walls(Cell cell[120][60], int* x, int* y);
};




#endif

The main thing that is important in this header is the temp_maze vector, which is used to keep track of the current section of the maze that has been carved out, so that when the maze hits a dead end it can back track. is the Cell is a class that represents a cell in the 2D grid that the player can move on. For the issue of this post, just think of each Cell as having an X integer, a Y integer, and a Bool to keep track of whether or not the cell is opened up. 

Below is the part of the gen function that deals with the hallway generation.

//Hallway Generation

	int cur_x, cur_y; //Current cell being tested
	bool time_to_break;

	for (int i = 1; i < 119; i++) {
		for (int j = 1; j < 59; j++) {

			if (cell[i][j].return_blockade() == true
					&& cell[i + 1][j].return_blockade() == true
					&& cell[i][j + 1].return_blockade() == true
					&& cell[i - 1][j].return_blockade() == true
					&& cell[i][j - 1].return_blockade() == true) { //Start of a path

				cur_x = i;
				cur_y = j;

				while (true) {

					cell[cur_x][cur_y].set_bloc(false); //Opens up cell
					cell[cur_x][cur_y].set_tex(tex);
					cell[cur_x][cur_y].set_default_tex(tex);

					temp_maze.push_back(cell[cur_x][cur_y]);

					if (check_walls(cell, &cur_x, &cur_y) == false) {

						std::cout << "Entering nospace" << std::endl;
						std::cout << "Size of k: " << temp_maze.size()
								<< std::endl;

						for (int k = temp_maze.size() - 1; k > -1; k--) {

							int xte = temp_maze[k].return_rect().x / 15;
							int yte = temp_maze[k].return_rect().y / 15;

							std::cout << "k: " << k << std::endl;

							std::cout << "rect_x: "<< temp_maze[k].return_rect().x<< " rect_y : "<< temp_maze[k].return_rect().y<< std::endl;
							std::cout << "x_te: " << xte << " y_te: " << yte << std::endl;

							if (check_walls(cell, &xte, &yte) == true) {
								cur_x = xte;
								cur_y = yte;
								std::cout << "Exiting nospace via newblock"
										<< std::endl;
								break;
							}

							if (k == 0) {
								time_to_break = true;
								std::cout << "Exiting nospace via noviableblock"
										<< std::endl;
								break;
							}

						}
					}

					if (time_to_break == true) {
						time_to_break = false;
						temp_maze.clear();
						break;
					}

				}

			}

		}
	}

The broad idea is that, starting from the top-left cell, we scroll through them until we find a cell that is not blocked, nor has any neighbors that are blocked. Than we open that cell up, add it to the temp_maze vector, and check whether it has any viable neighbors. If it does, it moves cur_y and cur_x to that new cell and repeats. If it doesn't have any viable neighbors, than it goes through the temp_maze vector until either it finds a cell that has viable neighbors, or it reaches the end of the vector. This is accomplished with the check_walls function.

bool Floor::check_walls(Cell cell[120][60], int* x, int* y) {

	int ori_x = *x;
	int ori_y = *y;

	std::cout << "Entering checkwalls with x: " << ori_x << " y: " << ori_y
			<< std::endl;

	if (cell[ori_x][ori_y].return_blockade() == true) {
		std::cout << "Checkwalls returns false due to being blocked"
				<< std::endl;
		return false;
	}

	while (true) {

		*x = ori_x;
		*y = ori_y;

		bool upblock, rightblock, downblock, leftblock;
		int sidecount = 0;

		int dir = rand() % 4;

		if (dir == 0) {
			*y = (*y) - 1;
		} else if (dir == 1) {
			*x = (*x) - 1;
		} else if (dir == 2) {
			*y = (*y) + 1;
		} else if (dir == 3) {
			*x = (*x) + 1;
		}

		if (*x <= 0 || *y <= 0) {
			sidecount = 8;
			dir = 5;
			*x = ori_x;
			*y = ori_y;
		}

		if (cell[*x + 1][*y].return_blockade() == false) {
			sidecount++;
		}
		if (cell[*x - 1][*y].return_blockade() == false) {
			sidecount++;
		}
		if (cell[*x][*y + 1].return_blockade() == false) {
			sidecount++;
		}
		if (cell[*x][*y - 1].return_blockade() == false) {
			sidecount++;
		}

		if (sidecount <= 1) {
			std::cout << "Checkwalls returns true" << std::endl;
			return true;

		} else {
			if (dir == 0) {
				upblock = true;
			} else if (dir == 1) {
				leftblock = true;
			} else if (dir == 2) {
				downblock = true;
			} else if (dir == 3) {
				rightblock = true;
			}
		}

		if (upblock == true && leftblock == true && downblock == true
				&& rightblock == true) {
			*x = ori_x;
			*y = ori_y;
			std::cout << "Checkwalls returns false" << std::endl;
			return false;
		}

	}

}

The basic idea here is that if one of the neighbors are available, than it moves x & y to that cell and return true, and if there are none, than return false.

 

The problem is that when I run this the temp_maze  function seems to get filled with the same cell, and time_to_break never gets set to true, as the vector seems to never end. Once again I understand this is kind of a lot but I have looked at this for a couple days now and have no idea what i am doing wrong, so any help would be very much appreciated.

Share this post


Link to post
Share on other sites
Advertisement

Are you able to provide source code that I can compile and run? (People are usually more willing to assist if they can compile your code and see exactly what is going on.)

Normally when you're dealing with such an issue you should be running your debugger to see why temp_maze isn't getting filled with different cells, then step through it. You will also find out what condition is being set that allows it to skip time_to_break.

You also should make it a habit to always set variables. I can see the following: bool time_to_break; I do not see where you've set time_to_break to false by default. Assuming I'm reading your code right, you need to set bool time_to_break = false; It's just a good habit to get into.

You should also set cur_x, cur_y to 0. Always set your variables, do not assume they will be 0, it's simply not true, they hold garbage, and will have unintended effects if you're trying to use them prior to re-setting.

Are you using Visual Studio by chance? Normally you would get a flag on compile if your bool isn't set.

If you're able to reply back with something I can compile, I will run it through and let you know the problem.

Share this post


Link to post
Share on other sites
5 hours ago, Rutin said:

Are you able to provide source code that I can compile and run? (People are usually more willing to assist if they can compile your code and see exactly what is going on.)

Normally when you're dealing with such an issue you should be running your debugger to see why temp_maze isn't getting filled with different cells, then step through it. You will also find out what condition is being set that allows it to skip time_to_break.

You also should make it a habit to always set variables. I can see the following: bool time_to_break; I do not see where you've set time_to_break to false by default. Assuming I'm reading your code right, you need to set bool time_to_break = false; It's just a good habit to get into.

You should also set cur_x, cur_y to 0. Always set your variables, do not assume they will be 0, it's simply not true, they hold garbage, and will have unintended effects if you're trying to use them prior to re-setting.

Are you using Visual Studio by chance? Normally you would get a flag on compile if your bool isn't set.

If you're able to reply back with something I can compile, I will run it through and let you know the problem.

Thanks for replying Rutin! 

Here is the github repository for the project: https://github.com/Starfruit64/Paladin

Im not 100% if this is what you were asking for, so if it's not just say. And no, I'm not using Visual Studio, I'm using Eclipse. (p.s I'll keep what you said about initializing variables in mind)

Share this post


Link to post
Share on other sites

Thank you for posting the code. I need to setup my SDL2 to run this, but I did take a quick look and got a basic running version up.

Just to clarify, are you saying that temp_maze.push_back(cell[cur_x][cur_y]); will always add the same entry?

I looked briefly at your code, and it appears you have a few problems.

1. I noticed you do set every cell to true for blockade, but all your functions appear to use set_bloc(false); without ever setting it to true again. This becomes a problem for the #2.

2. In your Hallway Generation you have the following method called if (check_walls(cell, &cur_x, &cur_y) == false) once you enter this function you will never be able to return false because the following block of code is never met.

if (cell[ori_x][ori_y].return_blockade() == true) {
  std::cout << "Checkwalls returns false due to being blocked"
    << std::endl;
  return false;
}

 and lower down

if (upblock == true && leftblock == true && downblock == true
    && rightblock == true) {
  *x = ori_x;
  *y = ori_y;
  std::cout << "Checkwalls returns false" << std::endl;
  return false;
}

Because you can never satisfy check_walls to false, it essentially just continues to loop forever through your functions.

3. This is extremely important. Do not use while(true) loops without breaking! This is not proper, and if you're going to use something like this, you forgot to use break; by using any return statement you're leaving the function right away. Use something like while(looping).

Once this code hits:

if (sidecount <= 1) {
  std::cout << "Checkwalls returns true" << std::endl;
  return true;

}

It will just return out of the function as true, which again will not satisfy: if (check_walls(cell, &cur_x, &cur_y) == false)

This is why you can never satisfy that statement to go deeper. You never can return false in check_walls, and all your blockades being checked are always false because it appears to be set prior to false.

Let me know if I'm on to something here, it's been a long day so I couldn't go too much in depth with your code.

EDIT: I forgot to mention, in Floor.cpp you also did not initialize your boolean variables again.

bool upblock, rightblock, downblock, leftblock;

Edited by Rutin

Share this post


Link to post
Share on other sites
On 1/29/2018 at 9:28 PM, Rutin said:

Thank you for posting the code. I need to setup my SDL2 to run this, but I did take a quick look and got a basic running version up.

Just to clarify, are you saying that temp_maze.push_back(cell[cur_x][cur_y]); will always add the same entry?

I looked briefly at your code, and it appears you have a few problems.

1. I noticed you do set every cell to true for blockade, but all your functions appear to use set_bloc(false); without ever setting it to true again. This becomes a problem for the #2.

2. In your Hallway Generation you have the following method called if (check_walls(cell, &cur_x, &cur_y) == false) once you enter this function you will never be able to return false because the following block of code is never met.


if (cell[ori_x][ori_y].return_blockade() == true) {
  std::cout << "Checkwalls returns false due to being blocked"
    << std::endl;
  return false;
}

 and lower down


if (upblock == true && leftblock == true && downblock == true
    && rightblock == true) {
  *x = ori_x;
  *y = ori_y;
  std::cout << "Checkwalls returns false" << std::endl;
  return false;
}

Because you can never satisfy check_walls to false, it essentially just continues to loop forever through your functions.

3. This is extremely important. Do not use while(true) loops without breaking! This is not proper, and if you're going to use something like this, you forgot to use break; by using any return statement you're leaving the function right away. Use something like while(looping).

Once this code hits:


if (sidecount <= 1) {
  std::cout << "Checkwalls returns true" << std::endl;
  return true;

}

It will just return out of the function as true, which again will not satisfy: if (check_walls(cell, &cur_x, &cur_y) == false)

This is why you can never satisfy that statement to go deeper. You never can return false in check_walls, and all your blockades being checked are always false because it appears to be set prior to false.

Let me know if I'm on to something here, it's been a long day so I couldn't go too much in depth with your code.

EDIT: I forgot to mention, in Floor.cpp you also did not initialize your boolean variables again.

bool upblock, rightblock, downblock, leftblock;

I appreciate your help, but I don't think this is the issue. if(check_walls(cell, &cur_x, &cur_y) == false is actually satisfied. Whenever i run the program, in fact, it seems always returns false. The check_walls function is used to test if there are any available neighbors of the current cell. If there are it changes cur_x and cur_y. If there are none, it is supposed to iterate through vector until it wither finds a cell that returns true when passed into check_walls, or until it runs out of cells. 

if (upblock == true && leftblock == true && downblock == true
    && rightblock == true) {
  *x = ori_x;
  *y = ori_y;
  std::cout << "Checkwalls returns false" << std::endl;
  return false;
}

I don't understand why you say this can't be satisfied. If all four of the cells surrounding the current cell are blocked, it should set all four of those bools to true and return false.

Share this post


Link to post
Share on other sites

I ran your code through a debugger, and this is the information I got from each break point. I set several breaks with condition checks throughout your code, and I can never satisfy if(check_walls(cell, &cur_x, &cur_y) == false

Essentially your program never leaves the method floor.gen(board, floor_tex); in Main.cpp, it gets stuck while looping through. When I'm stating your arguments are not being satisfied, it's based on running over 20,000+ loops through if(check_walls(cell, &cur_x, &cur_y) == false I was not able to hit any of the return false blocks.

If you're getting different results, then I really don't know what to say as my debugging is telling me another story. Unless you can re-package this for Visual Studio and upload. Maybe something is going wrong when I ported it over to Visual Studio, but none of your code was altered, and I have SDL2 with all your extended libraries loading just fine.

Are you able to hit the draw code on your version?

Edited by Rutin

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!