Hacker News new | past | comments | ask | show | jobs | submit login

I don't understand this - I saw the Wilson's algorithm [1] generate huge loops as it hit the existing maze. Does it subsequently erase them?

I couldn't see how the tree could possibly handle loops.

[1]: http://bl.ocks.org/mbostock/11357811




Where do you see the loops?

The algorithm uses "loop-erased" random walks.

It starts at a node that isn't in the tree and randomly walks.

If it hits itself while randomly walking (remember it isn't part of the tree yet), it erases the loop that it created and continues walking from that node again.

If the walk hits the tree, connect the walked path to the tree, pick another node and start again.


If you look closely at the huge loops Wilson’s algorithm is generating, you'll see they are not really loops at all: they only join up to the existing maze at the end, and there is a small gap at the start.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: