jaredpearson/vacworld — Issue #2: Closest node algorithm doesn't account for diagonals
Author: jaredpearson
Created: 2012-02-12 04:39:18+00:00
State: open

The current closest node algorithm only finds nodes orthogonal to the start. Given a node map to the diagram below, node b (since left bias) should be closest. The current algorithm finds that node (-3, 0) is closest even though its a shorter distance to b.

```

/**
*

* --- --- --- --- ---
* | | | a | | |
* --- --- --- --- ---
* | | | v | | |
* --- --- --- --- ---
* | | b | v | c | |
* --- --- --- --- ---
* | v | v | ^ | v | v |
* --- --- --- --- ---
* where
* ^ = current agent
* v = visited
* a,b,c = unvisited
*

*/
@Test
public void testSelectClosestDiagonal() {
//set up the agent's memory
NodeMap nodeMap = new NodeMap();
Node forwardNode = nodeMap.getNode(0, 1);
forwardNode.setVisited(true);
forwardNode.setType(NodeType.OPEN);
Node forward1Node = nodeMap.getNode(0, 2);
forward1Node.setVisited(true);
forward1Node.setType(NodeType.OPEN);
Node forward3Node = nodeMap.getNode(0, 3);
forward3Node.setVisited(true);
forward3Node.setType(NodeType.OPEN);
Node leftNode = nodeMap.getNode(-1, 0);
leftNode.setType(NodeType.OPEN);
leftNode.setVisited(true);
Node left2Node = nodeMap.getNode(-2, 0);
left2Node.setType(NodeType.OPEN);
left2Node.setVisited(true);
Node rightNode = nodeMap.getNode(1, 0);
rightNode.setType(NodeType.OPEN);
rightNode.setVisited(true);
Node right2Node = nodeMap.getNode(2, 0);
right2Node.setType(NodeType.OPEN);
right2Node.setVisited(true);
Node leftForwardNode = nodeMap.getNode(-1, 1);
leftForwardNode.setType(NodeType.UNKNOWN);
leftForwardNode.setVisited(false);
Node rightForwardNode = nodeMap.getNode(1, 1);
rightForwardNode.setType(NodeType.UNKNOWN);
rightForwardNode.setVisited(false);

//set up the world and agent
VacAgent agent = new VacAgent(nodeMap);
Percept percept = new PerceptBuilder()
.withAgent(agent)
.build();
agent.see(percept);

//ask agent for action
Action action = agent.selectAction();
Assert.assertEquals("Expected forward action because it is the closest unvisited", GoForward.class, action.getClass());
}
```