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:
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:
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
Comment #1 posted on 2015-09-17 13:43:39 by Mike Ray
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.
Above maze without the S spaces for clarity.
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
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
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.
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 :).