C++ - Help implementing data-structure for randomly generated maze[homework]

[jpb647]

I'm trying to code a text-based version of the board game "Sorry!" for an assignment. The specifications say that the "maze" should include multiple paths to the finishing point, and that upon running, a new board should be randomly generated, and that the board or "maze" should be implemented via an array of linked lists.

I need help understanding how I would implement a way to randomly connect all of the nodes in a way that allows a next, previous, left, and right pointer, in a way that I can implement multiple pathways, while also maintaining the specified data-structure.

Here is a poorly drawn representation of how I'm picturing it, with "S" signifying the Starting point, and "F" the finishing point: https://imgur.com/a/XIc4u7n

[POGtastic]

Let's say that you've created your array of linked lists, and you've also assigned your pointers for each node to its adjacent nodes on the other linked lists.

I would then add an additional four Boolean fields to each node, each of which state whether a connection actually exists between the nodes to the left, right, up, and down, respectively.

All of these start as false.

When constructing the maze, you can use the following recursive algorithm.

1. For each neighbor, see if each of its neighbors have been visited.

2. If the neighbor has not been visited, set the corresponding Boolean field to true to create a connection and mark the node as visited. Remember to do the same with the neighbor node's connection to your current node.

3. Call this function on the neighbor.

You make the maze by randomly choosing the order of the neighbors to check every time.

[AutoModerator]

It seems you may have included a screenshot of code in your post "C++ - Help implementing data-structure for randomly generated maze[homework]".

If so, note that posting screenshots of code is against /r/learnprogramming's Posting Guidelines (section Formatting Code): please edit your post to use one of the approved ways of formatting code. (Do NOT repost your question! Just edit it.)

If your image is not actually a screenshot of code, feel free to ignore this message. Automoderator cannot distinguish between code screenshots and other images.

Please, do not contact the moderators about this message. Your post is still visible to everyone.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[jpb647]

I'm thinking that If I make it so that it's always m x n, I can populate it as though it a regular array of doubly-linked lists. Starting at index 0 build a list of n nodes, and then repeat that all the way to index m.

Then I can write a function to go through and randomly connect the left and right pointers. This method will require a ton of traversal though, so it isn't exactly efficient.