| |
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
|
|
Message has 1 Reply:
Message is in Reply To:
13 Messages in This Thread:
  
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
