// Generally returns a bit (only a bit) more intelligent looking routes than
// the basic version. Not a true distance image (which would increase CPU
// load) level of intelligence though.
// List of Visited Nodes
CellNodeMap known = CellNodeMap.newInstance();
// List of Nodes to Visit
ArrayList<Node> to_visit = L2Collections.newArrayList();
to_visit.add(start);
known.add(start);
try
{
int targetx = end.getNodeX();
int targety = end.getNodeY();
int targetz = end.getZ();
int dx, dy, dz;
boolean added;
int i = 0;
while(i < 3500)
{
if(to_visit.isEmpty())
{
// No Path found
return null;
}
Node node = to_visit.remove(0);
i++;
node.attachNeighbors();
if(node.equals(end))
{
//path found! note that node z coordinate is updated only in attach
//to improve performance (alternative: much more checks)
//System.out.println("path found, i:"+i);
return constructPath(node);
}
Node[] neighbors = node.getNeighbors();
if(neighbors == null)
continue;
for(Node n : neighbors)
{
if(!known.contains(n))
{
added = false;
n.setParent(node);
dx = targetx - n.getNodeX();
dy = targety - n.getNodeY();
dz = targetz - n.getZ();
n.setCost(dx * dx + dy * dy + dz / 2 * dz/*+n.getCost()*/);
for(int index = 0; index < to_visit.size(); index++)
{
// supposed to find it quite early..
if(to_visit.get(index).getCost() > n.getCost())
{
to_visit.add(index, n);
added = true;
break;
}
}
if(!added)
to_visit.add(n);
known.add(n);
}
}
}
//No Path found
//System.out.println("no path found");