search

BucknellMARC / MicroMouse-Sim

OpenGL simulator for the MicroMouse competition
MIT License
2 stars 1 forks source link

Heuristic depth-first search on exploration #25

Open DepthDeluxe opened 9 years ago

DepthDeluxe commented 9 years ago

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 commented 9 years ago

@BoolLi what is your status on this?

BoolLi commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

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 notifications@github.com 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 https://github.com/BucknellMARC/MicroMouse-Sim/issues/25#issuecomment-62826985 .

BoolLi commented 9 years ago

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 commented 9 years ago

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

BoolLi commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

@BoolLi :+1:, 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 commented 9 years ago

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

DepthDeluxe commented 9 years ago

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 notifications@github.com 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 https://github.com/BucknellMARC/MicroMouse-Sim/issues/25#issuecomment-62834698 .