I'm Still Here

It's been a bit quiet around here. But there's still a lot going on.

Something Cool
A few weeks ago, I was in Detroit MI for Detroit.Code(). I showed my friend Cameron Presley (@pcameronpresley) some of the things I've been doing with mazes (code and articles). When I ran the sample, I got the longest path I've seen yet:

Pretty cool. It starts in the middle and loops around almost the entire maze before it gets to the end in the lower left corner.

The heat map isn't quite as interesting:

But you can see the lightest in the center and the darkest in the lower left.

#SpeakerConfessions
Something interesting happened this past week with the #SpeakerConfessions tag on Twitter. This was started by my friends Sarah Withee (@geekygirlsarah) and Nate Taylor (@taylonr), and it went around the world. It was really interesting to hear things from a lot of my speaker friends and a lot of speakers I don't know.

A couple of my articles from this past year seemed particularly relevant. I sent out this one: Help Those Behind You, which talks about the dangers of comparing yourself to other people. We should really focus on helping others. The only comparison that is valid is comparing yourself now to yourself in the past. Refocus on the things that are moving yourself forward.

I was also happy to see other folks replying with this article: Speakers, Let's Change Our Terminology: No More Rejections. This is something I've had to struggle with in the past (very recent past), and it's kind of nice to see that I'm not the only one. But we've still got a long way to go.

In addition, there's an article that I will (hopefully) write in the next day or so that to tell some of my struggles with submitting to events, striving for the wrong things, and focusing on where my strengths really are. We'll see if I can get that out before I go to Kansas City.

KCDC
And speaking of Kansas City, I've been frantically preparing for the Kansas City Developer Conference which is happening next week. I've got a full day workshop on Asynchronous Programming in C#, and I'm making sure the labs, samples, and materials are all in good shape. I've still got a ways to go with that, but things will be ready on time.

In addition to the workshop, I get to do two of my favorite talks: Clean Code: Homicidal Maniacs Read Code, Too! and DI Why? Getting a Grip on Dependency Injection.

A lot of my friends will be there, and I'm looking forward to meeting lots of new folks, too. It should be a really great week.

Other Distractions
I've had a lot of distractions that have kept me busy. About 6 weeks ago, I moved to Washington state. And it's really beautiful out here. It's strange how many things you have to do when you change states. The good news is that I do have a Washington driver's license, and I've also got Washington plates on my car. So I won't have anyone scowling at my California plates anymore.

In addition to my 2 cats, I'm now living with 2 dogs.

The move is part of something bigger that is coming up real soon. It's the answer to High Risk vs. Low Risk (and Update: High Risk vs. Low Risk) that I wrote about last year. I did make the decision, and I'll have an update to that in a few weeks.

I'll have more content soon. Once things get settled a bit more, I'll be able to concentrate on adding great things on a regular basis. Until then, make sure you stay focused on the important things in life.

Happy Coding!

More Maze Programming: Adding Some Bias for Longer Paths

Okay, so I know that I said I might be done with Mazes for Programmers, But, I went one chapter further and picked up a couple of more algorithms: Hunt and Kill, and Recursive Backtracker.

As a reminder, you can pick up the code here: GItHub - jeremybytes/mazes-for-programmers.

The reason these are interesting is that they add a bit of bias. Last time, we saw an unbiased algorithm that is completely random. This was better than the very biased algorithms that we had seen previously, but it was also a bit slow since it relies on random walks to fill an entire grid.

This works great, but good mazes are more than random events. So by adding a bit of bias, we can make longer paths, twistier paths, and fewer dead-ends. This makes a maze more interesting to solve.

Hunt and Kill
The first slightly-biased algorithm is Hunt and Kill. This scans the cells from the top left corner. When it finds a cell that has "unvisited neighbors" (meaning there are no links to the cell), then it makes a random connection and moves to the next cell. When it can't go any further (such as when it loops into a dead end), it goes back to scanning to find a cell with unvisited neighbors so that it can start again.

Because this is not completely random, it is much faster than the Aldous-Broder algorithm that we saw last time. And it creates some longer passages. Here's a graphical version:

And here's a text version:

It's particularly easy to spot the longer passage here when we look at the path from the center to the lower right corner.

It also makes nice patterns for larger mazes:

I find myself getting lost in some of the images. The dark areas represent the spots furthest from the center. So the top image has lots of things "furthest" away. The bottom image has a few things "furthest" away.

Recursive Backtracker
The other slightly-biased algorithm is the Recursive Backtracker. Like Hunt and Kill, this creates longer passages with fewer dead ends. But it operates a bit differently. When it hits a dead end, it doesn't start scanning for a new starting point (like Hunt and Kill). Instead, it keeps track of all the cells that have been visited by using a stack. If it comes to a dead end, it pops cells off the stack until it finds one that has an unvisited neighbor (meaning, another path to be started). When all of the cells are popped off the stack, that means we've visited each cell and we're done.

Here's the graphical version of Recursive Backtracker on a small grid:

And here's the text version:

Again, we can see a pretty long, twisty path from the center to the corner. And this is just as interesting when we create larger mazes:

I kind of like these because you'll find these twisty paths of one color running through the middle of a section with a lighter or darker color.

Differences
In addition to the slightly different patterns that come out of these algorithms, there are a few performance differences. I've noticed that the Hunt and Kill takes a little bit longer to complete. The Recursive Backtracker is a little bit faster, but it consumes more memory since it's keeping track of every single cell on the stack. Each of these has pros and cons, and if you're interested, pick up your own copy of Mazes for Programmers (Amazon link).

What's Next
As you can see, I've switched up the colors a little for these samples. But this is done by changing values in the code. Now that I'm seeing the interesting patterns that are created by these, I'm going to explore adding some more interesting color elements as well.

I've always been intrigued by pseudo-randomly created pictures. I can see that I'm going to be running quite a few of these in the future.

As always, keep playing and keep exploring.

Happy Coding!

More Maze Programming: A Non-Biased Algorithm

So back to Mazes for Programmers, this time looking at a non-biased algorithm. This is where I start thinking about repurposing this whole maze-building thing.

As a reminder, you can get the code here: GitHub - jeremybytes/mazes-for-programmers. I added some comments to the "Program.cs" file so that you can do some experimentation with different algorithms, grids, and grid sizes.

Biased Algorithms
The two algorithms previously implemented were Sidewinder and Binary Tree. These both have biases, meaning there are certain patterns that repeat based on the algorithm. For example, the binary tree algorithm tends to create a diagonal across the maze. This is visible with a 15x15 maze:

But it's even more obvious when we have a larger maze (155 x 155):

Another thing is that this produces a straight path along the top (north) edge of the maze as well as the right (east) edge of the maze.

Non-Biased Algorithms
Mazes for Programmers presents 2 non-biased algorithms. I've implemented one of them: the Aldous-Broder algorithm. This was independently developed by David Aldous and Andrei Broder. It uses a random walk to create a non-biased algorithm.

One of the important points for a maze algorithm is that is should not create loops, and this algorithm does ensure that while still creating random paths. Basically, it creates random paths until they link up. If a loop is created, then that path is discarded.

Here's the Ruby code from the book:

And here's my implementation in C#:

This produces a random path. Here's a text representation showing the shortest path from the center to the lower-left corner:

And here's a graphical representation showing a heat map of distances from the center:

What's interesting is that if we run this multiple times, we won't see a pattern forming (such as the diagonal pattern formed with the Binary Tree). Here are several runs with a larger grid:

This starts to look pretty interesting. Unfortunately, because of the random nature of the algorithm, it gets much slower the larger the grid, and I don't think there's an easy way to parallelize the process.

As a side note, the other non-biased algorithm presented in the book, Wilson's algorithm, uses a random walk as well, and it suffers from a similar performance issue. The difference is that while Aldous-Broder has slowness at the end (while it tries to hook up the last few cells), Wilson's has slowness at the front (where it tries to hook up the first cell). I haven't done any performance analysis, and I think that's outside the scope of my interest right now.

Accidental Art
Here's a 255 x 255 grid. This took several minutes to produce on my machine. But because it uses random numbers, the time to produce it is non-deterministic.

This is really cool. I think it's time for me to repurpose this and start creating interesting visual patterns. I could probably set up some color transitions in addition to the shade transitions of the heat map. I'll be playing with this quite a bit in the near future.

Wrap Up
I don't know how much further I'll get in the Mazes for Programmers book. I think I may have gotten the information I need regarding the algorithms and how things work. This is a good jumping off point for me to explore on my own.

I'll be playing with the heat map quite a bit. It's easy to remove the maze lines and just have the colors (I did that accidentally last night). And adding some color transitions would be pretty cool.

I also need to go through the F# code that Steve Gilham put together. It looks like I'll need to decompose things a bit to make it work with various display output (it does text right now, but I'd want to add the graphical display) as well as to support the distance calculations that make the paths and heat maps possible. So I've got lots to play with.

I've also got lots of real work to do as well. But it's also good to play and explore from time to time. That's part of the learning process.

Happy Coding!

More Maze Programming: Heat Map

It's been a while since I've pulled out Mazes for Programmers (it looks like it was March). I picked it up again tonight to do a bit of programming. This time, I added the code to create a heat map of a maze.

You can get the current code here: GitHub - jeremybytes/mazes-for-programmers.

Here's a sample of the output:

This uses the center square as the "start". The colors get darker as the path to each square is further away.

The code in its current state produces 2 outputs. The example above is a .png file that is saved to the file system (and automatically shown by the console application).

The console application also generates a text output:

If you compare this to the graphic output, you can see that these are the same maze. The numbers here are a bit different. Instead of creating a heat map of distances, this shows the shortest path from the start (the center of the grid) to the finish (the lower left corner). By following the path, this shows that 34 steps are required to get from the center to the finish.

The code isn't great at this point. The reason is that I'm doing a straight-across port from the Ruby code that is presented in the book. And I'm also not a big fan of the way the objects are put together in the book code. But I'm still working on the underlying concepts of mazes, and then I can work on making the code a bit better.

As stated previously, I'd like to get some F# code in here, and I've gotten some great contributions from the community including this sample from Steve Gilham: Steve's F# Implementation. I haven't had a chance to dig through Steve's sample. From my initial look, I can tell that I need to think about breaking down problems in a different way than I'm used to.

I'm looking forward to diving into that more.

Happy Coding!