• Advertisement

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By francoisdiy
      So I wrote a programming language called C-Lesh to program games for my game maker Platformisis. It is a scripting language which tiles into the JavaScript game engine via a memory mapper using memory mapped I/O. Currently, I am porting the language as a standalone interpreter to be able to run on the PC and possibly other devices excluding the phone. The interpreter is being written in C++ so for those of you who are C++ fans you can see the different components implemented. Some background of the language and how to program in C-Lesh can be found here:

      http://www.codeloader.net/readme.html
      As I program this thing I will post code from different components and explain.
    • By isu diss
      I'm trying to duplicate vertices using std::map to be used in a vertex buffer. I don't get the correct index buffer(myInds) or vertex buffer(myVerts). I can get the index array from FBX but it differs from what I get in the following std::map code. Any help is much appreciated.
      struct FBXVTX { XMFLOAT3 Position; XMFLOAT2 TextureCoord; XMFLOAT3 Normal; }; std::map< FBXVTX, int > myVertsMap; std::vector<FBXVTX> myVerts; std::vector<int> myInds; HRESULT FBXLoader::Open(HWND hWnd, char* Filename, bool UsePositionOnly) { HRESULT hr = S_OK; if (FBXM) { FBXIOS = FbxIOSettings::Create(FBXM, IOSROOT); FBXM->SetIOSettings(FBXIOS); FBXI = FbxImporter::Create(FBXM, ""); if (!(FBXI->Initialize(Filename, -1, FBXIOS))) { hr = E_FAIL; MessageBox(hWnd, (wchar_t*)FBXI->GetStatus().GetErrorString(), TEXT("ALM"), MB_OK); } FBXS = FbxScene::Create(FBXM, "REALMS"); if (!FBXS) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the scene"), TEXT("ALM"), MB_OK); } if (!(FBXI->Import(FBXS))) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to import fbx file content into the scene"), TEXT("ALM"), MB_OK); } FbxAxisSystem OurAxisSystem = FbxAxisSystem::DirectX; FbxAxisSystem SceneAxisSystem = FBXS->GetGlobalSettings().GetAxisSystem(); if(SceneAxisSystem != OurAxisSystem) { FbxAxisSystem::DirectX.ConvertScene(FBXS); } FbxSystemUnit SceneSystemUnit = FBXS->GetGlobalSettings().GetSystemUnit(); if( SceneSystemUnit.GetScaleFactor() != 1.0 ) { FbxSystemUnit::cm.ConvertScene( FBXS ); } if (FBXI) FBXI->Destroy(); FbxNode* MainNode = FBXS->GetRootNode(); int NumKids = MainNode->GetChildCount(); FbxNode* ChildNode = NULL; for (int i=0; i<NumKids; i++) { ChildNode = MainNode->GetChild(i); FbxNodeAttribute* NodeAttribute = ChildNode->GetNodeAttribute(); if (NodeAttribute->GetAttributeType() == FbxNodeAttribute::eMesh) { FbxMesh* Mesh = ChildNode->GetMesh(); if (UsePositionOnly) { NumVertices = Mesh->GetControlPointsCount();//number of vertices MyV = new XMFLOAT3[NumVertices]; for (DWORD j = 0; j < NumVertices; j++) { FbxVector4 Vertex = Mesh->GetControlPointAt(j);//Gets the control point at the specified index. MyV[j] = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); } NumIndices = Mesh->GetPolygonVertexCount();//number of indices MyI = (DWORD*)Mesh->GetPolygonVertices();//index array } else { FbxLayerElementArrayTemplate<FbxVector2>* uvVertices = NULL; Mesh->GetTextureUV(&uvVertices); int idx = 0; for (int i = 0; i < Mesh->GetPolygonCount(); i++)//polygon(=mostly triangle) count { for (int j = 0; j < Mesh->GetPolygonSize(i); j++)//retrieves number of vertices in a polygon { FBXVTX myVert; int p_index = 3*i+j; int t_index = Mesh->GetTextureUVIndex(i, j); FbxVector4 Vertex = Mesh->GetControlPointAt(p_index);//Gets the control point at the specified index. myVert.Position = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); FbxVector4 Normal; Mesh->GetPolygonVertexNormal(i, j, Normal); myVert.Normal = XMFLOAT3((float)Normal.mData[0], (float)Normal.mData[1], (float)Normal.mData[2]); FbxVector2 uv = uvVertices->GetAt(t_index); myVert.TextureCoord = XMFLOAT2((float)uv.mData[0], (float)uv.mData[1]); if ( myVertsMap.find( myVert ) != myVertsMap.end() ) myInds.push_back( myVertsMap[ myVert ]); else { myVertsMap.insert( std::pair<FBXVTX, int> (myVert, idx ) ); myVerts.push_back(myVert); myInds.push_back(idx); idx++; } } } } } } } else { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the FBX Manager"), TEXT("ALM"), MB_OK); } return hr; } bool operator < ( const FBXVTX &lValue, const FBXVTX &rValue) { if (lValue.Position.x != rValue.Position.x) return(lValue.Position.x < rValue.Position.x); if (lValue.Position.y != rValue.Position.y) return(lValue.Position.y < rValue.Position.y); if (lValue.Position.z != rValue.Position.z) return(lValue.Position.z < rValue.Position.z); if (lValue.TextureCoord.x != rValue.TextureCoord.x) return(lValue.TextureCoord.x < rValue.TextureCoord.x); if (lValue.TextureCoord.y != rValue.TextureCoord.y) return(lValue.TextureCoord.y < rValue.TextureCoord.y); if (lValue.Normal.x != rValue.Normal.x) return(lValue.Normal.x < rValue.Normal.x); if (lValue.Normal.y != rValue.Normal.y) return(lValue.Normal.y < rValue.Normal.y); return(lValue.Normal.z < rValue.Normal.z); }  
    • By Karol Plewa
      Hi, 
       
      I am working on a project where I'm trying to use Forward Plus Rendering on point lights. I have a simple reflective scene with many point lights moving around it. I am using effects file (.fx) to keep my shaders in one place. I am having a problem with Compute Shader code. I cannot get it to work properly and calculate the tiles and lighting properly. 
       
      Is there anyone that is wishing to help me set up my compute shader?
      Thank you in advance for any replies and interest!
    • By fishyperil
      I'm looking for some references that could help me learn how to program some really basic 2D enemy behaviours.
      I wasn't sure whether to post this here or in the AI section but I think it might be more suitable to be posted here since it has more to do with basic maths than any AI related algorithms.
      Could anyone help recommend some resources (books, posts, videos) that could help me understand how to properly implement the basics of enemy movement in 2d games ? So far I've only managed to get them to chase the player character and to stop moving on collision, but the movement is pretty unrealistic and once the collision occurs the enemies all "pile up" on the player character. I'm doing this in C++ so no guides that explain how to script this using an engine api please.
    • By LifeArtist
      Good Evening,
      I want to make a 2D game which involves displaying some debug information. Especially for collision, enemy sights and so on ...
      First of I was thinking about all those shapes which I need will need for debugging purposes: circles, rectangles, lines, polygons.
      I am really stucked right now because of the fundamental question:
      Where do I store my vertices positions for each line (object)? Currently I am not using a model matrix because I am using orthographic projection and set the final position within the VBO. That means that if I add a new line I would have to expand the "points" array and re-upload (recall glBufferData) it every time. The other method would be to use a model matrix and a fixed vbo for a line but it would be also messy to exactly create a line from (0,0) to (100,20) calculating the rotation and scale to make it fit.
      If I proceed with option 1 "updating the array each frame" I was thinking of having 4 draw calls every frame for the lines vao, polygons vao and so on. 
      In addition to that I am planning to use some sort of ECS based architecture. So the other question would be:
      Should I treat those debug objects as entities/components?
      For me it would make sense to treat them as entities but that's creates a new issue with the previous array approach because it would have for example a transform and render component. A special render component for debug objects (no texture etc) ... For me the transform component is also just a matrix but how would I then define a line?
      Treating them as components would'nt be a good idea in my eyes because then I would always need an entity. Well entity is just an id !? So maybe its a component?
      Regards,
      LifeArtist
  • Advertisement