Like Tree1Likes
  • 1 Post By Nominal Animal

How to create a Maze Generator in C?

This is a discussion on How to create a Maze Generator in C? within the C Programming forums, part of the General Programming Boards category; Hey guys, I was wondering how best to go about creating a simple Maze Generator in C. I have read ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    1

    Question How to create a Maze Generator in C?

    Hey guys, I was wondering how best to go about creating a simple Maze Generator in C. I have read around the area and found that implementing the Depth First Search (DFS) algorithm is a good strategy.

    My question is, how would one initially go about doing this? I am new to C and I am finding it difficult to start from scratch, however I am confident that, once pointed in the right direction, I can progress.

    Any help would be greatly appreciated.

    Cheers.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,765
    Perhaps start with a web search for "maze generator algorithm"
    Maze generation algorithm - Wikipedia, the free encyclopedia
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    872
    Quote Originally Posted by kknehra View Post
    Hey guys, I was wondering how best to go about creating a simple Maze Generator in C. I have read around the area and found that implementing the Depth First Search (DFS) algorithm is a good strategy.
    Yes, it is a good strategy. It is basically a "mole" that digs passages through the given volume, until there are no more possibilities to dig. Every point in such a maze is reachable from any other point within the maze.

    First, however, you need to decide whether you want thin or thick walls:
    Code:
    ╶─┬───┬───┐     ▒▒▒▒▒▒▒▒▒▒▒
    ╷ │ ╷ ╵ ╷ │       ▒ ▒   ▒ ▒
    │ │ └───┴─┤     ▒   ▒ ▒▒▒ ▒
    │ │ ╶─┐ ╷ │     ▒ ▒   ▒   ▒
    │ └─┐ └─┴─┤     ▒ ▒ ▒ ▒ ▒▒▒
    ├─╴ ├─╴ ╶─┤     ▒ ▒▒▒ ▒   ▒
    │ ╶─┘ ┌─╴ ╵     ▒   ▒   ▒   
    └─────┴───╴     ▒▒▒▒▒▒▒▒▒▒▒
    It seems like an unimportant detail, but the implementation details between the two do differ, and you'll just save yourself a lot of grief if you decide it first.

    Thick walls are easier to implement.

    You'll need a data structure that can describe each cell or tile in your maze. For thick walls, you only need one bit per cell. For thin walls, you need two bits per cell, one bit for horizontal walls and one bit for vertical walls. Usually it is easier to use a char per cell.

    Note: If you use thin walls, I recommend you keep the "up" and "left" walls in the cell. Then, the "right" wall is the "left" wall in the cell one step to right, and the "down" wall is the "up" wall on the cell one step down. If you store all four walls for each cell, your walls are effectively doubled; it's not any easier that way. Also note you'll need an extra cell down and right when using thin walls, for the rightmost and bottommost walls.

    When you start creating a maze, you fill it up with walls. Then, you place your "mole" at the starting position, and let it chew away.

    For each "mole" step, you check the four directions, to see if the mole can chew through walls that way. You only look at unchewed walls: you can progress that direction only if the cell there is unvisited.

    For thick walls, you only look at the six cells towards the target cell. For example, to check if the "mole" M can go right:
    Code:
    . . . . .
    . . 1 2 .
    . M X 3 .
    . . 5 4 . 
    . . . . .
    If all the six cells (1, 2, 3, 4, 5, X) have walls in them, then you can chew from M into X. The same logic applies to the three other directions, just rotate the image.

    For thin walls, the cell is unvisited if the four walls surrounding it are all still intact.

    If you have only one possible direction, you go that way. If you have two or more -- in a planar maze, four is only possible at the very first step -- you save that position in a stack, and pick one direction at random.

    When your "mole" gets stuck, with no possibilities to chew into, you pop off the last position stored in the stack (basically teleporting the mole back to the previous location it could make a choice), and re-check that. Note that you do need to check the maze, you cannot just remember the choices you then had available, because the maze has changed after that. It is not even guaranteed you can progress from that point at all.

    When you have no more possible directions, and the stack is empty, you're done.

    As an incentive, here's a 40-column, 25-row maze I created using the above logic:
    Code:
    ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
    ▒▒      ▒▒  ▒▒                      ▒▒▒▒  ▒▒      ▒▒▒▒  ▒▒                    ▒▒
    ▒▒▒▒▒▒      ▒▒  ▒▒▒▒  ▒▒▒▒▒▒▒▒▒▒▒▒    ▒▒      ▒▒        ▒▒▒▒▒▒  ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
    ▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒    ▒▒    ▒▒  ▒▒▒▒  ▒▒▒▒▒▒  ▒▒▒▒▒▒▒▒    ▒▒    ▒▒            ▒▒
    ▒▒      ▒▒  ▒▒▒▒▒▒  ▒▒▒▒▒▒        ▒▒    ▒▒▒▒      ▒▒▒▒▒▒  ▒▒▒▒      ▒▒  ▒▒▒▒  ▒▒
    ▒▒  ▒▒  ▒▒  ▒▒▒▒    ▒▒      ▒▒▒▒  ▒▒▒▒    ▒▒▒▒▒▒  ▒▒  ▒▒    ▒▒▒▒▒▒▒▒▒▒  ▒▒    ▒▒
    ▒▒  ▒▒  ▒▒  ▒▒    ▒▒▒▒▒▒  ▒▒▒▒    ▒▒▒▒▒▒  ▒▒▒▒    ▒▒  ▒▒▒▒          ▒▒▒▒▒▒  ▒▒▒▒
    ▒▒  ▒▒  ▒▒  ▒▒  ▒▒▒▒  ▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒  ▒▒    ▒▒▒▒    ▒▒▒▒▒▒▒▒▒▒    ▒▒▒▒    ▒▒
    ▒▒  ▒▒      ▒▒  ▒▒          ▒▒▒▒      ▒▒      ▒▒▒▒▒▒▒▒          ▒▒▒▒        ▒▒▒▒
    ▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒  ▒▒▒▒▒▒▒▒▒▒    ▒▒▒▒▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒▒▒  ▒▒▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒
    ▒▒  ▒▒▒▒        ▒▒      ▒▒▒▒    ▒▒▒▒▒▒      ▒▒▒▒          ▒▒▒▒  ▒▒  ▒▒        ▒▒
    ▒▒    ▒▒▒▒▒▒▒▒  ▒▒  ▒▒▒▒▒▒    ▒▒▒▒      ▒▒        ▒▒▒▒▒▒  ▒▒    ▒▒  ▒▒  ▒▒▒▒▒▒▒▒
    ▒▒▒▒  ▒▒        ▒▒▒▒▒▒      ▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒  ▒▒▒▒  ▒▒  ▒▒    ▒▒
    ▒▒▒▒  ▒▒▒▒  ▒▒▒▒▒▒▒▒    ▒▒      ▒▒▒▒      ▒▒▒▒▒▒▒▒    ▒▒  ▒▒  ▒▒    ▒▒      ▒▒▒▒
    ▒▒    ▒▒▒▒  ▒▒    ▒▒  ▒▒▒▒  ▒▒    ▒▒▒▒▒▒    ▒▒▒▒    ▒▒▒▒  ▒▒      ▒▒▒▒▒▒▒▒  ▒▒▒▒
    ▒▒  ▒▒▒▒    ▒▒▒▒        ▒▒  ▒▒▒▒    ▒▒▒▒▒▒        ▒▒▒▒    ▒▒▒▒▒▒  ▒▒    ▒▒    ▒▒
    ▒▒        ▒▒▒▒▒▒▒▒▒▒▒▒  ▒▒    ▒▒▒▒▒▒▒▒      ▒▒  ▒▒▒▒    ▒▒▒▒      ▒▒▒▒  ▒▒▒▒  ▒▒
    ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒      ▒▒  ▒▒▒▒        ▒▒▒▒▒▒▒▒▒▒    ▒▒▒▒    ▒▒          ▒▒  ▒▒
    ▒▒      ▒▒  ▒▒▒▒    ▒▒▒▒▒▒  ▒▒    ▒▒▒▒▒▒▒▒▒▒        ▒▒▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒
    ▒▒  ▒▒            ▒▒▒▒      ▒▒  ▒▒▒▒▒▒  ▒▒    ▒▒▒▒  ▒▒      ▒▒      ▒▒▒▒▒▒▒▒  ▒▒
    ▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒    ▒▒  ▒▒  ▒▒▒▒    ▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒  ▒▒▒▒▒▒▒▒▒▒        ▒▒
    ▒▒  ▒▒      ▒▒    ▒▒▒▒▒▒▒▒▒▒▒▒        ▒▒▒▒  ▒▒▒▒  ▒▒    ▒▒        ▒▒▒▒  ▒▒▒▒▒▒▒▒
    ▒▒  ▒▒  ▒▒  ▒▒  ▒▒▒▒▒▒      ▒▒▒▒  ▒▒    ▒▒    ▒▒      ▒▒▒▒▒▒▒▒▒▒  ▒▒          ▒▒
    ▒▒      ▒▒  ▒▒          ▒▒        ▒▒▒▒  ▒▒▒▒      ▒▒          ▒▒      ▒▒  ▒▒  ▒▒
    ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
    iMalc likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Create a traffic generator
    By khpuce in forum Networking/Device Communication
    Replies: 2
    Last Post: 10-02-2003, 02:57 PM
  2. Random maze generator
    By Bingo The Clown in forum C++ Programming
    Replies: 1
    Last Post: 04-10-2003, 10:15 AM
  3. maze generator
    By datainjector in forum C Programming
    Replies: 2
    Last Post: 11-20-2002, 06:35 PM
  4. IDEA: Maze Generator
    By ygfperson in forum Contests Board
    Replies: 2
    Last Post: 09-09-2002, 09:43 PM
  5. Maze game, complete with maze editor and an example maze!
    By Brian in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-20-2002, 03:27 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21