search

jamis / csmazes

Maze algorithms implemented in CoffeeScript, with an eye toward demonstrating how the algorithms work by animating them.
393 stars 42 forks source link

Eller's Maze Description In Your Book #3

Closed solomon-b closed 6 years ago

solomon-b commented 6 years ago

Hi. I'm not sure if this is the appropriate place to post this but I think there is a mistake in your Eller's maze description on pages 190 to 192 in your book "Mazes For Programmers."

On page 191 after carving south into the second row of the maze, you don't do anything to prevent loops from forming in the maze. Your illustration doesn't include any loops but in the last diagram on page 191 take a look at cells 6 and 1. There is no reason those two cells could not be joined together (they are adjacent and differen't sets) assuming your random integer is a 0. This would cause all four of the upper right corners of the maze to be connected in a loop.

EDIT: Ooops I made a mistake. Joining those cells like I suggested would NOT create a loop;

jamis commented 6 years ago

I'm glad you figured it out. :) I'm not going to lie; Eller's algorithm is a bit mind-bending. It's not my favorite! But it is rather fascinating to see how it comes together.

solomon-b commented 6 years ago

Thanks. Eller's is by far the hardest example so far for me. I understand it conceptually but its very confusing to debug. I'm using a disjoint set data structure which helps simplify things a bit--and made Kruskal's shockingly simple--but I'm still getting loops in my Eller mazes.

jamis commented 6 years ago

If an extra pair of eyes would help, feel free to email me directly! I'm jamis@jamisbuck.org. I'd be happy to help however I can.