List open=new ArrayList();
List closed=new ArrayList();
int rango=unidad.getMovementSpeed();
open.add(new Nodo(unidad.getPosition(),null,destino,unidad,new ArrayList()));
Nodo nodoAExplorar=null;
while(open.size()>0){
nodoAExplorar=buscarMenorF(open);
if (nodoAExplorar.getPunto().equals(destino))//encontre el camino
break;
if (closed.size()>100){
nodoAExplorar=buscarMenorF(closed);
break;
}
if (aRangoDeAccion){
if (nodoAExplorar.getPunto().distance(destino)<=unidad.getActionRange())
break;
}
closed.add(nodoAExplorar);
open.remove(nodoAExplorar);
//checheo los vecinos y los agrego a la open list si son validos
boolean puntoInvalido=false;
int centroX=nodoAExplorar.getPunto().getX();
int centroY=nodoAExplorar.getPunto().getY();
int limiteIzquierdo=(centroX-rango)>=0 ? centroX-rango : 0;
int limiteDerecho=(centroX+rango)<fortaleza.anchoMapa ? centroX+rango : fortaleza.anchoMapa-1;
int limiteSuperior=(centroY-rango)>=0 ? centroY-rango : 0;
int limiteInferior=(centroY+rango)<fortaleza.altoMapa ? centroY+rango : fortaleza.altoMapa-1;
for (int i = limiteIzquierdo; i<=limiteDerecho;i++ ){
for (int j=limiteSuperior;j<=limiteInferior;j++){
Point posibleSalto=new Point(i,j);
//chequeo que no este en la closed list ��
Iterator itClosed=closed.iterator();
boolean enClosed=false;
while (itClosed.hasNext()){
Nodo nodo=(Nodo)itClosed.next();
if (nodo.getPunto().getX()==i && nodo.getPunto().getY()==j){
enClosed=true;
break;
}
}
if (enClosed)
continue;
if ((!unidad.isFavorecerDiagonalesImperfectas() && !(i==centroX && j==centroY) && nodoAExplorar.getPunto().distance(posibleSalto)<=rango)
|| (unidad.isFavorecerDiagonalesImperfectas() && !(i==centroX) && !(j==centroY) && i!=j && nodoAExplorar.getPunto().distance(posibleSalto)<=rango)){
puntoInvalido=false;
List puntosIntermedios=new ArrayList();
int desplazamientoX=posibleSalto.getX()-centroX;
int desplazamientoY=posibleSalto.getY()-centroY;
int cantidadDiagonalesExactas=Math.min(Math.abs(desplazamientoX), Math.abs(desplazamientoY));
int diagonalX=desplazamientoX>0 ? 1: -1;
int diagonalY=desplazamientoY>0 ? 1: -1;
desplazamientoX=Math.abs(desplazamientoX-cantidadDiagonalesExactas*diagonalX);
desplazamientoY=Math.abs(desplazamientoY-cantidadDiagonalesExactas*diagonalY);
while (desplazamientoX>0){//es uno u el otro
puntosIntermedios.add(new Point(centroX+desplazamientoX*diagonalX,centroY));
desplazamientoX--;
}
while (desplazamientoY>0){//es uno u el otro
puntosIntermedios.add(new Point(centroX,centroY+desplazamientoY*diagonalY));
desplazamientoY--;
}
while (cantidadDiagonalesExactas>0){
cantidadDiagonalesExactas--;
puntosIntermedios.add(new Point(posibleSalto.getX()-diagonalX*cantidadDiagonalesExactas,posibleSalto.getY()-diagonalY*cantidadDiagonalesExactas));
}
//chequear camino a ese vecino
Iterator it=puntosInvalidos.iterator();
while (it.hasNext()){
MapElement invalido=(MapElement)it.next();
Iterator it2=puntosIntermedios.iterator();
while (it2.hasNext()){
Point wayPoint=(Point)it2.next();
if (invalido.getPosition().equals(wayPoint)){
puntoInvalido=true;
break;
}
}
if (puntoInvalido)
break;
}
if (!puntoInvalido){
// si no esta en la open list lo agrego, si esta y tiene mayor costo G cambio el padre por este
agregarNodo(open,posibleSalto,nodoAExplorar, destino,unidad,puntosIntermedios);
}
}
}
}
//termine con los vecions
}
if (open.size()==0){//si no tengo camino lo mando al punto cercano
List nodos=open;
nodos.addAll(closed);
Iterator menorH=nodos.iterator();
while (menorH.hasNext()){
Nodo nodo=(Nodo)menorH.next();
if (nodo.getFCost()<nodoAExplorar.getFCost()){
nodoAExplorar=nodo;
}
}
}
//rearmo el camino
Nodo padre=nodoAExplorar;
while (padre!=null){
camino.add(0,padre.punto);
padre=padre.getPadre();
}
if (camino.size()>1)
camino.remove(0);
return camino;
}