Heuristic depth-first search on exploration

[DepthDeluxe]

Implement heuristic depth-first search when the robot is exploring. Should be guided to the center but also able to explore an entire maze, regardless of its structure.

[DepthDeluxe]

@BoolLi what is your status on this?

[BoolLi]

@DepthDeluxe Sorry I was busy having interviews this week. I will definitely start working on this over this weekend. I will make sure I have something new by next Monday.

[BoolLi]

@DepthDeluxe This line here:
https://github.com/BucknellMARC/MicroMouse-Sim/blob/master/src/logic/Explore.c#L57

What if the robot starts at a position where there is only one way to go? The current logic will have the robot go back, but since it's the first step, there's no history to go back yet.

I will try to implement a recursive way to do depth-first search.

[mazemaker1]

According to the rules, the robot always starts in a spot surrounded by
walls on three sides with only on initial direction it can go.

On Wed, Nov 12, 2014 at 8:34 PM, Li Li [email protected] wrote:

This line here:

https://github.com/BucknellMARC/MicroMouse-Sim/blob/master/src/logic/Explore.c#L57

What if the robot starts at a position where there is only one way to go?
The current logic will have the robot go back, but since it's the first
step, there's no history to go back yet.

I will try to implement a recursive way to do depth-first search.

—
Reply to this email directly or view it on GitHub
#25 (comment)
.

[BoolLi]

Then the code won't work if this is the case. In the simulation, the robot always starts at the position where there are at least two ways to go. This is why this bug was not spotted before. I will try to fix it.

[DepthDeluxe]

@BoolLi good catch, that will be a problem. Could be causing some crashes as documented by #21

[BoolLi]

@DepthDeluxe I updated the code and fixed this potential cause of #21, but I haven't thought of an effective way to implement the heuristic yet. I will do it tomorrow.

[BoolLi]

@DepthDeluxe Because this fix is not related to the heuristic, I think you can consider merging this branch to master first.
Also can we assume that the robot will have to explore the whole maze before actually solving the maze? If not, we might need to change this method:
https://github.com/BucknellMARC/MicroMouse-Sim/blob/master/src/logic/Robot.c#L36

[DepthDeluxe]

@BoolLi 👍, send me a PR

no that method should only be run once the whole maze is explored. The explore_suggest() function should run until the robot has discovered the whole maze.

[BoolLi]

@DepthDeluxe I just meant that in the real competition, are we allowed to scan the whole maze with unlimited amount of time?

[DepthDeluxe]

We have 10 minutes to scan and make our best time. This should be enough
time to solve for the whole maze.

On Wed, Nov 12, 2014, 10:11 PM Li Li [email protected] wrote:

I just meant that in the real competition, are we allowed to scan the
whole maze with unlimited amount of time?

—
Reply to this email directly or view it on GitHub
#25 (comment)
.