Jump to content
  • Advertisement
Sign in to follow this  
MarkS

Concerned about heap corruption with maze algorithm.

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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. blink.gif cool.gif

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!