Historical errata for Mazes for Programmers

dijkstra.rb - line 8 - new variable distances unused - either not needed or perhaps it was intended to assign it to grid.distances in line 10 ?

I can’t run this code, I did download the book source but when I try to instantiate the PolarGrid the code gets in some sort of infinite loop and never returns… I would really like to see this fixed soon because I’m actually stuck trying to understand how the calculation is being done, I was trying to have an instance so I could look on the generated data, but since the code is not working I can’t base myself on it or it’s results (which are none) to understand it.

“It, it all”

path[(position + 1)..–1] = []

“If we’ve created a loop, the cell will already be present in our path, with all the cells after it forming the loop, so we remove the loop by truncating the path after that cell (line 18).”

It is also hard to follow the Ruby code even reading the description. There are many places where I have to stop and try to figure out what is going on. It would be nice if the code used less Ruby specific code. Or if there was code in other languages.

The colored maze on p.52 doesn’t reflect the colors produced by the code on p.51; ChunkyPNG::Color.rgb(0, intensity, 0) will produce shades between black (intensity = 0) and pure green (intensity = 255), but the maze shows colors between pure green and white.

Code examples with line numbers would read more nicely in the kindle version if you label the first line “1” instead of “Line 1”.

As it is currently, the extra characters mess up the formatting of the first line in each of the code examples that have line numbers.

Spent a lot of time getting the sample code to run with Ruby. It seems that the require statement has changed since Ruby 1.9 to not include the local directory. Supposed to use require_relative instead. This was fixed quite a while ago in Ruby since 1.9 due to security issue. Not sure why the code is still using the old format?

Text “(for example, binary_tree_demo.rb or wilsons.rb)”. It should read wilsons_demo.rb.

Quoting from the text:

Each iteration of that loop examines all of the linked
neighbors of the current cell (line 8), looking for one that is closer to the root
(line 9).

This, however, does not seem to be (strictly speaking) the case, since the code includes a break at line 12.

I think the result will be the same, since this is a perfect maze, but I was a bit confused by this.

The rationale for the column value in the random_cell method would be useful to explain. It took me awhile to realize it was for non-rectangular grids, since you didn’t just use

column = rand(@columns)

Parameters use the equal sign to assign default values.
So the method declaration should read:
def to_png( cell_size = 10 )

The vertical bias in attributed to the recursive subdivision algorithm is consequence of the implementation rather than the nature of the algorithm itself

The code for the recursive subdivision algorithm (page 200 & online) indicates that a section is split horizontally if & only if the section height is greater than its width, otherwise it it split vertically. As a result, any case in which the section width & height are equal, the section will always be split vertically. The lack of random chance in the case of equality results in biasing the maze to have vertical passages. Changing the code to give square sections a 50/50 chance to split vertically or horizontally will remove the bias.

Subsequently, the comparison of recursive subdivision algorithm to other algorithms in Appendix 2 (pages 260-261), describes & illustrates the bias found in the implementation as given in the text, but would be incorrect if the implementation is fixed as described above.

Dijkstra’s name is misspelled in the header on this page. “Dikstra”

The code of `to_s` contains `\
` twice. In the current font, that backslash is wuiteclose to a pipe character, `|`.

The implementation of random_cell chooses a random cell and then randomly chooses a cell in that row. But, because the maze is now constructed of adaptive sized cells, some rows have more (many more) cells than other rows. This means the cells in the center of the maze will be chosen far more often than those at the rim. For instance, the PolarGrid of size 8 on the next page has 48 cells in the rim, but only one at the center. That center will be randomly selected 1/8th of the time. A particular cell on the rim will be selected 1/8 * 1/48th of the time.