# Concerned about heap corruption with maze algorithm.

This topic is 2917 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am working on a maze-based game. (I know... ANOTHER one!) Anyway, each level is one row and column larger than the last. I am using the depth first search method to create perfect mazes and am using std::stack for the stack.

My concern comes from the fact that you can play this game until you run out of memory. As a test, I made a level 10,000 x 10,000 cells. It works fine, but the stack required 11% of the total cells as stack space. This means, in a 100,000,000 cell maze (unlikely to ever get played, but still...) more than 11,000,000 calls to new and delete. There doesn't seem to be a way to compact the heap and I am worried about the long term consequences of this.

Is this a legitimate concern? I am aware of stack-less maze generation algorithms, but they produce mazes that I find rather ugly.

##### Share on other sites
What makes you think the free store needs compaction?

##### Share on other sites
I really don't know. Truthfully, I have no idea what is going on behind the scenes with the heap and I want to make sure that this will not be a problem.

##### Share on other sites

[...]This means, in a 100,000,000 cell maze (unlikely to ever get played, but still...) more than 11,000,000 calls to new and delete.

Where does this 11,000,000 figure come from? Have you tried changing the underlying container that the stack is using to std::vector, rather than std::deque -- I'm not sure how/if deque retains allocated memory.

Is this a legitimate concern?[/quote]
No... until you can prove otherwise. If you don't think you'll be able to prove otherwise any time soon, then it definitely isn't a legitimate concern

##### Share on other sites
Just a thought: If you were to ever get to this point where large sizes are a concern, then you should consider changing your algorithm to generate a fractal of DSF mazes. That is, first generate an NxN maze where each cell represents another NxN maze, with the restriction that each cell can only have at most one single exit to each neighboring cell. From here, only the cells are needed to be known in advance, and each cell and maze can be generated as needed. If a small memory footprint is important, then there's always zlib...

##### Share on other sites

Where does this 11,000,000 figure come from? Have you tried changing the underlying container that the stack is using to std::vector, rather than std::deque -- I'm not sure how/if deque retains allocated memory.

I put some code to track the calls to new and delete to get a percentage of maximum stack space vs. total cell count. On the 100,000,000 cell maze, the maximum number of cells allocated by the stack was over 11,000,000.

I, at first, made the stack an array the same size as the cell array. This, of course, is very wasteful. I then move the code over to std::vector, but there is more functionality than I needed. I then discovered std::stack (not sure what std::deque is...). They both do similar things, but std::stack is more straightforward. Just Push and Pop.

[size=2]

Just a thought: If you were to ever get to this point where large sizes are a concern, then you should consider changing your algorithm to generate a fractal of DSF mazes. That is, first generate an NxN maze where each cell represents another NxN maze, with the restriction that each cell can only have at most one single exit to each neighboring cell. From here, only the cells are needed to be known in advance, and each cell and maze can be generated as needed.

[size=2]That is not a bad idea! I am going to have to look into this. Fractal compression.

##### Share on other sites

I, at first, made the stack an array the same size as the cell array. This, of course, is very wasteful. I then move the code over to std::vector, but there is more functionality than I needed. I then discovered std::stack (not sure what std::deque is...). They both do similar things, but std::stack is more straightforward. Just Push and Pop.

std::stack is implemented in terms of another container, which by default is std::deque.

You can also have it use an std::vector.

 std::stack<cell, std::vector<cell> > my_stack; 
This may reduce the overall number of allocations.

You can also ask std::vector to preallocate space with the reserve() method, which will reduce the number of overall allocations. Since vector's storage is contiguous, it's about as compact as you're going to get it.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 21
• 12
• 18
• 25
• 20