Archived

This topic is now archived and is closed to further replies.

Betrayer_of_Code

Lee maze solving algorithm

Recommended Posts

I was looking up the Lee maze solving algorithm and I found one that explains MOST of it in good detail, but the problem is, it doesnt say how to assign each space a Lee number, so I am kinda confused. Anyone who has heard of or used this algorithm can probably help me, but I dont know how. http://icebear.cmsa.wmin.ac.uk/~alison/mouse/leesalg.html Thats where I heard of it. [edited by - betrayer_of_code on January 22, 2004 5:31:37 PM]

Share this post


Link to post
Share on other sites
Zahlman    1682
quote:
Original post by Betrayer_of_Code
I was looking up the Lee maze solving algorithm and I found one that explains MOST of it in good detail, but the problem is, it doesnt say how to assign each space a Lee number, so I am kinda confused.


quote:
Section 3.2 from the page you cited
The algorithm can be written as follows. It relies on the fact that the code for EMPTY is bigger than any valid Lee number.

Set all squares' Lee numbers to EMPTY
Set target square(s) to 0
REPEAT
go through all the squares:
record that no changes have been made in this pass
n = EMPTY (largest possible value)
IF no wall to North, and square to North has Lee number n = Lee number of square to North
IF no wall to East, and square to East has Lee number n = Lee number of square to East
IF no wall to South, and square to South has Lee number n = Lee number of square to South
IF no wall to West, and square to West has Lee number n = Lee number of square to West
(n is now the smallest accessible Lee value)
IF n < EMPTY
IF n + 1 < current Lee number of square
Set Lee number of square to n + 1
record that a change has been made
UNTIL no changes have been made in this pass




What's the problem?


[edited by - Zahlman on January 23, 2004 4:08:37 AM]

Share this post


Link to post
Share on other sites