########################################
  #+0****## #+#...###...#..$ ##  #  #    #
  ##+###+## #+++......#...# ##       #   #
  # #.+++++#....#   #      #    #      # #
  #  #+++++#+.+..#  #  #          #      #
  #  #.##.+++#+.### #     #   #   ##     #
  #  ###.+.##++.##     #   ###     #   # #
  ####+.#..#++#.##   #      #####   ##   #
  #++#.#.###+.##    ##       ##    #   # #
  #++++++.##.++.#   #  ##     #  # #  # ##
  #+++++#..##.##      ## #  #### # #    ##
  #+.....#..#.  ##   #      #     ##  ## #
  #+..+.......   # #      #      #  ##   #
  #+...#..###       # #  #          ##  ##
  #.#..#.........# # # # ##### # #    ## #
  #.......##  ##....  #        ###   ##  #
  ##......# ##   ##..#  #####          # #
  #.+.#...###    ###. ##          ##  # ##
  ##.+...#  #      ####      #   ##    # #
  ########################################
  Mouse found the cheese!  :)  Press any key to restart!

Comments

Subscribe to the comments RSS feed.

Comment #1 posted on 2015-09-17 13:43:39 by Mike Ray

Welcome return

Great episode Gabriel and great to see you back with more bare-metal programming.

Looking forward to episodes about sound rendering on the GPU

Comment #2 posted on 2015-10-07 17:36:28 by Eric

A better maze

Here is my code for creating a maze in Excel. It is actually fairly easy to make a true maze without any blocked sections. Basically, it grows out the walls from the edges. As long as they don't connect with other walls, you'll end up with a graph where every space can be visited from every other space.
Askimet doesn't seem to like me posting code, so I'll just describe the algorithm.


Create a square of x rows and y columns. x and y must be odd numbers.


Put a W in each cell of row 1, row x, column 1, and column x.

For each cell whose row and column is even, put an S.

Put an O in all the other cells.

W = Wall of maze

S = Space in maze

O = Open, not processed

P = Possible next wall. We will determine these soon.



All cells whose row and column are even has to be a space. All cells whose row and column are odd will be a wall. I will call those pillars. The rest of the cells have an odd row and even column or even row and odd column. I will call them partitions. The algorithm will repeatedly pick another random partition to put between pillars in the maze.

Initialized maze.
WWWWWWWWWWW
WSOSOSOSOSW
WOOOOOOOOOW
WSOSOSOSOSW
WOOOOOOOOOW
WSOSOSOSOSW
WOOOOOOOOOW
WSOSOSOSOSW
WOOOOOOOOOW
WSOSOSOSOSW
WWWWWWWWWWW

Possible finished maze.
WWWWWWWWWWW
WSSSSSSSWSW
WWWWWWWSWSW
WSWSWSSSWSW
WSWSWWWSWSW
WSSSSSSSWSW
WSWWWSWSSSW
WSWSSSWSWSW
WSWSWWWSSSW
WSWSWSSSWSW
WWWWWWWWWWW

Above maze without the S spaces for clarity.
WWWWWWWWWWW
W W W
WWWWWWW W W
W W W W W
W W WWW W W
W W W
W WWW W W
W W W W W
W W WWW W
W W W W W
WWWWWWWWWWW



Note that the pillar and partition cells will initially be marked as open (O). An open partition is an undetermined cell that will be either a wall (W) or space (S). An open pillar is a pillar that has is not next to a wall.

While there are still open spaces (O), loop.
For each partition cell in the maze
if the partition cell has two walls next to it, mark it as a space (S)
if the partition cell has one wall (W) next to it, mark it as possible (P)
otherwise leave it as Open (O)
end the for loop
Pick a random P and change it to W
End the loop.

Comment #3 posted on 2015-10-14 02:18:40 by Gabriel Evenfire

Maze generation

That's an interesting algorithm. I can intuitively see why it works, but want to think of how I could prove it. One could put a start and endpoint to the maze in that case.

The traversal algorithm through a maze generated like that would probably just be a right-hand-rule variant since the walls would be a single connected component. The purely random generation that I mentioned in the podcast does not guarantee that of course meaning the right-hand rule could just lead the mouse in a circle forever.

Two ways that immediately spring to mind for ensuring the mouse always makes it to the cheese (barring running out of energy, eaten by cat, etc..) are:
* scan the maze and mark the connected components and ensure that the mouse and the cheese land in the same connected component
* scan the maze, mark the connected components and then take pairs of independent connected components and break walls between them to connect them until the maze is a single connected component.

Your generation approach produces a much more sane and generally pleasing looking maze. I'm wondering if there's a good way to then take that and "shake it up a little" to allow for disconnected wall segments, and such while retaining much of the pleasingness.

Of course there's another possibility: add the notion of "teleporters" to the maze. :)

Thanks for the insight and the algorithm. That's what I like best about this little exercise: there are so many variations that one can make on it.

Leave Comment

Note to Verbose Commenters
If you can't fit everything you want to say in the comment below then you really should record a response show instead.

Note to Spammers
All comments are moderated. All links are checked by humans. We strip out all html. Feel free to record a show about yourself, or your industry, or any other topic we may find interesting. We also check shows for spam :).