Routing (Part Four)

05th-06th Dec 2012 - The 18th and 19th meeting dealed with routing. Being able to go from A to B without going back or repeating cells, unless forced.

 

Planning ahead

Making it go on his own

The act of going from A to B seems simple. Even more when you see where you're going. But all of us spent a couple of months or even a year in the early stages of our lives learning how to walk.  And if you can't see where you're going is a whole new degree. Your plan can only be made of expectations and assumptions. You must go and work your way through. So that's our robot like too. 

We already teached him how to "walk". He can  rotate, go from one cell to another, detects obstacles but going from one place to another without indicating every move is the new step of his robotic life.
To accomplish this we indicate a target. Then we make him "imagine" a route through the board with all he knows that exist in it, including barriers and the Toaster. If he knows of the mold's existence and where it is, it will take him in account. And the way we do this is to simulate his movement a cell at a time.

For each cell, from the one he's physically at, is to determine which valid cells are nearby. Having valid cells to use, we then determine what's the distance to the target from each one of them. We choose the closest one and repeat the process until the target is reached.

In case of a tie between 2 cells at the same target distance, we untie it with the priority (bottom, left, top, right) but only if it's not visited already. We're basically using the same priority we used in the beginning while describing the valid moves for the robot.
 
But now we realize it may have been a wrong choice, if we compare with the Mold priorities. Generically the robot will go from its initial position towards the bottom and to its left. So it would have been wise to use a counterclockwise priority like (bottom, right, top, left). In case of head to head encounter with the Mold, they'd go in opposite longitudinal directions.

Dead ends

In the course of "walking" through the maze, there are situations where the robot will be trapped in a dead end. Or you might imagine it like a "room" with only one exit. It can be a physical or virtual dead end.

A physical dead end happens if there's barriers or opponents that make a closed path where you can only go out by one way. The robot can start within such a "room" or can walk into one.

A virtual or logical dead end is when he's moving around and all cells around him have already been visited, it might happen even during simulation.
To solve this we always keep the last position used. We use the last real world position and during route calculation we use a virtual last position.
 
In case it detects a Physical Dead End, it will go back to the previous position and mark that cell with "-1" priority. This will prevent from the robot from using it again, as it will always have lower priority than another choice around. The Logical Dead End acts similarly, but it will only receive a "0" priority which means "visited cell". But in this case, we can rollback every simulated position up to the start of the junction and take another valid way without moving.

The physical dead end is more restricted because it only has that 1 cell "memory" rollback. It will solve most of the problems but maybe not all. We can make it reset all visited cells so it will always use the way back (unless it's caught by the mold first, of course).