Having coded up two more complex algorithms, I analysed them to see how they compared, and then combined the two in an attempt (failed) to produce a hybrid algorithm that was faster than either of its parents.
Tag: <span>algorithms</span>
This was my first real challenge. I converted his code for the Binary Tree and Sidewinder two algorithms, and Aldous-Broder turned out to be pretty straightforward to implement, so my code looked a lot like his. However, Wilson’s algorithm was a different matter altogether. I had been reading the book at night, and didn’t have it by my side when I tackled this algorithm. I had read his description of the algorithm a few times, and it seemed easy enough. Ha, famous last words. My first attempt was pretty rubbish. The algorithm didn’t terminate, and what it produced along the way was not very impressive. Unsure what had gone wrong, I re-read his description (whilst avoiding the code) and realised that I had mis-read it, and had got two small, but significant points wrong. I could go into a lengthy discourse about how important it is to understand your requirements,…
The main part of Dijkstra’s algorithm is implemented in the Distances class. For the most part, my code didn’t look that much different from his. The main change was that I was able to use Linq to remove an if when traversing the frontier… I broke lines 6-8 into three to make it easier to read in this blog, but in the code, it’s just one line. Linq enabled me to avoid having to check if the next cell had already been linked. Adding the numbers to the text output was very simple, as I already added the facility to display cell contents (see part 2 of this series). The challenge was putting these numbers on the UI. This turned out to be much easier than I expected, and even worked first time, which surprised me! I added a method to the window’s code behind, passing in the distances collection…
Part 4 in my ongoing series of how I implemented the code from Mazes For Programmers by Jamis Buck in C#.
In this post, I explain how I implemented the first two maze-generation algorithms in C#, and show how parts of the code were improved by using Linq.
Leave a Comment