[ Ссылка ]

This robot is able to solve every solvable maze and find shortest way from start to finish. Start is located in bottom right corner and finish is located in bottom left corner.
In first step robot explores maze, creating map of possible moves. When all accessible fields have been visited at least once, robot stops exploration. Thanks to created map, it is able to find shortest way back to start point, and then shortest way from start to finish point.

Program have been written in Brixcc in NXT language.

Unfortunately some variables and procedures names are in
Polish, so it can be a little confusing.
First step is creating map of entire maze. Each tile of maze have its ID. Start tile ID is 5, the tile on the left X-1 (4), the tile on the right is X+1 (6) and the tile above is X+10 (15). It would be better if we could use two dimensional coordinates (X,Y), but our Lego Mindstorm Brick somehow hasn't work correctly with 2D arrays and we had to work it out in our own way.

So, robot checks if it can move from current tile to some other, and creates map of possible moves. Each visited tile is also flagged as visited. Robot moves using right hand rule. If robot gets to a place from which he could not go to unvisited tile, it goes back along its patch until it gets to a tile from which it can go to unvisited tile. If all tiles are flagged as visited, robot finds shortest way to start and then from start to finish tile.
Here is link to movie showing how finding shortest way works.

It "floods" maze with numbers representing lowest number of moves required to access these tiles. When a number is written in target tile "flooding" stops and we goes from a highest number to lowest creating shortest path.
And that is all.

The real magic is to force these dumb Lego Mindstorms to go straight and turn nicely ;)
Best regards.

свернуть