Site Map - skip to main content - dyslexic font - mobile - text - print

Hacker Public Radio

Your ideas, projects, opinions - podcasted.

New episodes Monday through Friday.


hpr1859 :: A Mouse in a Maze on the Raspberry PI

This podcast describes a little game that I learned in my first programming class.

<< First, < Previous, Latest >>

Host Image
Hosted by Gabriel Evenfire on 2015-09-17 is flagged as Clean and is released under a CC-BY-SA license.
Listen in ogg, spx, or mp3 format. | Comments (3)

Part of the series: Programming 101

A series focusing on concepts and the basics of programming

This podcast is about a little programming exercise I learned in my first programming class. The idea is to generate a random text-based maze and make mouse ('@') search the maze systematically to find the cheese ('V'). If it does so before it runs out of energy (moves) it wins ('$' == happy mouse). Otherwise it starves ('%' == dead mouse).

You can find my git repos for the Raspberry PI code including this program at these locations:

The Mouse-in-a-maze program also requires the catlib library as well which is at:

You may note that these directories are different from those in my previous RPI episodes. The repositories used to be on gitorious. However since gitlab acquired gitorious, I have migrated the repositories. They currently live on both github and gitlab and I have pushing updates to both for the time being. So I have been waffling about which one will be the ultimate master for these projects. But since, I am doing most all the work on this code myself, it doesn't much matter for the time being.

If this is your first time playing with bare metal programming in the RPI you can get more info and tips from HPR episodes 1619, 1630 and 1666. Note that the gitorious links in those episodes are outdated as mentioned above. The github links therein should still be fine though.

The mouse code itself is in the apps/mouse0 directory. If you haven't played with this environment before you'll need to do the following:

  • Get a compatible ARM toolchain up and running to build for the RPI. I recommend using: https://github.com/dwelch67/build_gcc/blob/master/build_arm
  • You'll need a USB-to-TTL serial cable to hook up to the RPI. I use: http://www.adafruit.com/products/954
  • You'll also need a small SD card to boot from.
  • Follow the steps in catrpi/README.txt to
    • create an SD-card with a loader on it.
    • build catlib for the RPI locally (a prereq for building mouse0.bin)
    • set up your serial connection to the RPI
    • start up a minicom instance to connect to the RPI

Once those prerequisites are taken care of you can:

  • change directory to /path/to/catrpi/apps/mouse0 type make to build
  • mouse0.bin power on the RPI at the loader prompt, type 'x' in the
  • serial console to start X-modem reception on the RPI
  • use your terminal program to send the mouse0.bin file via X-modem. In minicom you do this by CTRL-A followed by 's'. You then select 'xmodem' as the protocol and navigate to and select the file mouse0.bin to send.
  • when the transfer completes type 's' to start the program

These pages describe VT100 Terminal codes:

Sample traversal:

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

Comments

Subscribe to the comments RSS feed.

Comment #1 posted on 2015-09-17T13:43:39Z 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-07T17:36:28Z 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-14T02:18:40Z 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 :).

Provide feedback
Your Name/Handle:
Title:
Comment:
Anti Spam Question: What does the P in HPR stand for ?
Are you a spammer →
Who hosted this show →
What does HPR mean to you ?