Diagonal Solver Flooding

By | January 6, 2013

FwdFloodThis post provides more details on how the flooding is done.

 

 

 

FwdWallFloodAssume the mouse is at the location “X” and the mouse is pointing at the number “1”. We will call that direction North.

We will use “N, E, S, W” to mean North, East, South and West. Similarly, we will use NE to mean North East, SE to mean South East, etc.

Given the wall configuration shown, the flooding algorithm will see if it can make a Right Straight to Diagonal 45 degree turn (RtSD45) by checking the states of walls 1, 2 and 3. It is obvious that walls 1 and 2 have to be missing.

The reason to check wall 3 is that if wall 3 is present, there is no next move after RtSD45. So, as an optimization, we check for all three walls and if all three are not there, then we add the RtSD45 end coordinate to the ExpandQueue for further expansion.

If the mouse is at location X and it wants to go:
• Forward, the wall at location “1” has to be missing.
• SSRT90, the walls at locations “1” and “2” have to be missing.
• SDRT45, the walls at locations “1”, “2” and “3” have to be missing.
• SSRT180, the walls at locations “1”, “2” and “4” have to be missing.
• SDRT135, the walls at locations “1”, “2”, “4” and “5” have to be missing.

Decoding turn description:
SDRT45 => A turn that starts on a straight and ends on a diagonal and the turn angle is 45 degrees.
SSRT90 => A turn that starts on a straight and ends on a straight and the turn angle is 90 degrees.
Etc.
I’m sorry the turn terminology is a little different than the picture in the previous post.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.