Re: Just a few highlights and points...

On Wed, September 28, 2005 11:03 am, Brian Davis wrote:
> In lugnet.org.us.laflrc, Steve Hassenplug wrote:
>> Assuming you can identify an intersection, all the robot
>> really needs to know is where to go when it gets to an
>> intersection... doesn't need to track intersections [along
>> dead-ends]... doesn't need to know the distance[s]...
>> doesn't need to identify ["pure"] turns...
>
>    Agreed. What it does right now is look for turns or intersections, making
> choices only there. If it's just a turn (a "pure" turn), it makes it and doesn't
> bother updating the memory of the path. Ideally (in other words, the untested
> portion) when it hits a dead-end, it back-tracks to the last node in the tree,
> pruning off this "dead branch" and choosing again - if there are no valid paths
> to explore off this last node, it returns to the parent node in the tree,
> pruning the newly-dead node from the tree again. Essentially, it's a depth-first
> search of a graph or tree representation of the maze that is built dynamicly as
> the robot traverses branches.
>    It also means, currently, there are three things each node needs to have
> recorded. The "structure" (compass heading of valid paths to explore from the
> node - four bits), the last direction the node was left from (2 bits; this way
> we know which direction to "prune" from the node if we are sent back here by a
> deadend), and the heading back to the parent of this node (again, 2 bits). That
> works out nicely to 8 bits per node, meaning I can pack two nodes of info into a
> single NQC variable.

I must have done something wrong.  I'm only keeping 2 bits per node, instead of 8.

Steve