Problema adyacencia de celdas en A Star search java

MrAw3s0m3 #1 May '13

Buenas,

Estoy haciendo un ejercicio que consiste en una sala con celdas. Por algunas puedes pasar (marcadas con un '1') y por otras no (marcadas con un '0'). Tienes un sitio por el que comienzas, 0.0, y uno por donde sales y tienes que buscar el camino.

Buscando un poco por internet encontre el algoritmo A Star y lo aplique y modifique para mi caso particular, pero el problema es que no consigo crear adyacencias entre celdas.

Si por ejemplo la sala fuera tal que asi:

1 0 0 0
1 0 0 0
1 0 0 0
1 1 1 1

Y tuviera que ir del 0.0 al 3.3 el camino obvio seria el de todo unos. Cuando creo cada una de las celdas para hacer una adyacencia entre ellas leo el contenido de la celda de abajo y de la derecha y si contienen un uno las hago adyacentes la una con la otra añadiendolas a un HashSet (o arraylist esto no importaria mucho).

Al ejecutarlo no me funciona, y haciendo un println del tamaño de cada uno de los hashset de cada celda da 0, por lo que no he conseguido añadir ninguna adyacencia.

No se muy bien si el problema estara ahi o en otra parte del codigo. Puedo pegarlo si hace falta.

Gracias.

elkaoD #2 May '13

#1 código!

1 respuesta

MrAw3s0m3 #3 May '13

#2

Clase Casilla:

spoiler


import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


public class Casilla {
	
private int x;
private int y;
private int contenido;
private boolean comienzo;
private boolean destino;
private Central central;
private double parentCost;
private double localCost;
private ArrayList<Casilla> adyacencias;

private Casilla parent;

/**
 * @param parent the parent to set
 */
public void setParent(Casilla parent) {
	this.parent = parent;
}

public Casilla(int x, int y, int c,Central central) {

	this.x = x;
	this.y = y;
	this.contenido=c;
	this.central = central;
	adyacencias=new ArrayList<Casilla>();
}

public void setComienzo(boolean r){
	this.comienzo=r;
}

public void setDestino(boolean r){
	this.destino=r;
}

public void calculaAdyacencias(){
	//int arriba=x-1;
	int abajo=x+1;
	//int izquierda=y-1;
	int derecha=y+1;
	
	if(abajo < central.getFilas()){
		//if(central.getCasilla(abajo, y).getContenido()==1){
			central.getCasilla(abajo, y).anhadeAdyacencia(this);
			this.anhadeAdyacencia(central.getCasilla(abajo, y));
		//}
	}
	
	if(derecha < central.getColumnas()){
		//if(central.getCasilla(x, derecha).getContenido()==1){
			central.getCasilla(x, derecha).anhadeAdyacencia(this);
			this.anhadeAdyacencia(central.getCasilla(x, derecha));
		//}	
	}
}

/**
 * @return the adyacencias
 */
public ArrayList<Casilla> getAdyacencias() {
	return adyacencias;
}

/**
 * @return the contenido
 */
public int getContenido() {
	return contenido;
}

public void anhadeAdyacencia(Casilla c) {

	adyacencias.add(c);
}

public boolean isStart(){
	return comienzo;
}

/**
 * @return the parent
 */
public Casilla getParent() {
	return parent;
}

public double getPassThrough(Casilla goal) {

	if (isStart()) {
		return 0.0;
	}

	return getLocalCost(goal) + getParentCost();
}

public double getParentCost() {

	if (isStart()) {
		return 0.0;
	}

	if (parentCost == 0.0) {
		parentCost = 1.0 + .5 * (parent.getParentCost() - 1.0);
	}

	return parentCost;
}

public double getLocalCost(Casilla goal) {

	if (isStart()) {
		return 0.0;
	}

	localCost = 1.0 * (Math.abs(x - goal.getX()) + Math.abs(y - goal.getY()));
	return localCost;
}

/**
 * @return the x
 */
public int getX() {
	return x;
}

/**
 * @return the y
 */
public int getY() {
	return y;
}

public boolean isEnd(){
	return destino;
}

public String toString(){
	String res = contenido+ " ";
	System.out.println("num: "+adyacencias.size());
	return res;
}

public Casilla itself(){
	return this;
}
	
	

}

Clase Central:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class Central {

private int filas;
private int columnas;
private int dX, dY;
private Casilla[][] casillas;
private Casilla destino;
//File fich=new File("");

private List<Casilla> opened = new ArrayList<Casilla>();
private List<Casilla> closed = new ArrayList<Casilla>();
private List<Casilla> bestList = new ArrayList<Casilla>();


public Central(int filas, int columnas, String fichero){
	this.filas=filas;
	this.columnas=columnas;
	casillas=new Casilla[filas][columnas];
	//init(fichero);
	creaCasillas(fichero);
	
	
}

/**
 * @return the bestList
 */
public List<Casilla> getBestList() {
	return bestList;
}

public void init(String fichero){
	creaCasillas(fichero);
	setComienzoYFinal(0,0,4,4);
	generaAdyacencias();
}

public void setComienzoYFinal(int cX, int cY, int dX, int dY){
	casillas[cX][cY].setComienzo(true);
	destino=casillas[dX][dY];
	destino.setDestino(true);
}

public void creaCasillas(String fichero) {
	
	
	//System.out.println("Holaaaaa");
	//System.out.println(System.getProperty("user.dir"));
	//System.out.println(new File("."));
	
	
	File fich = new File(fichero);
	System.out.println("1");
	System.out.println(fich.getPath());
	System.out.println("2");
	System.out.println(fich.getAbsolutePath());
	
	try{
		
        //int xi, y, xd;
        @SuppressWarnings("resource")
		Scanner sr = new Scanner(fich);
        int num=0;
        
        	for (int i = 0; i < filas; i++) {
    			for (int j = 0; j < columnas; j++) {
    				if(sr.hasNextInt()){
    					num=sr.nextInt();
    					casillas[i][j] = new Casilla(i, j, num,this);
    					System.out.print(num+" ");
    				}
    			}
    			System.out.println();
    		}
        	
        	System.out.println("--------------");
        	
        	for (int i = 0; i < filas; i++) {
    			for (int j = 0; j < columnas; j++) {
    				System.out.print(casillas[i][j]);
    				System.out.println();
    				System.out.println("--------------");
    				System.out.println("--------------");
    				System.out.println();
    				System.out.println(casillas[i][j].getAdyacencias().toString());
    				
    				System.out.println();
    				System.out.println("+++++++++++++++");
    				System.out.println("+++++++++++++++");
    				System.out.println();
    			}
    			System.out.println();
        	}
        	
        	//creaCasillas(fichero);
    		setComienzoYFinal(0,0,4,4);
    		generaAdyacencias();
        	
        
    }catch(Exception e){
    	//System.out.println("El archivoooooooooooooooo de entrada no exite.");
    	//System.exit(0);
    }    

	
}

public void generaAdyacencias() {

	for (int i = 0; i < filas; i++) {
		for (int j = 0; j < columnas; j++) {
			casillas[i][j].itself().calculaAdyacencias();
		}
	}
}

public Casilla getCasilla(int x, int y){
	return casillas[x][y].itself();
}

/**
 * @return the filas
 */
public int getFilas() {
	return filas;
}

/**
 * @return the columnas
 */
public int getColumnas() {
	return columnas;
}

public void findBestPath() {

	System.out.println("Calculating best path...");
	ArrayList<Casilla> adjacencies = casillas[0][0].getAdyacencias();
	for (Casilla adjacency : adjacencies) {
		adjacency.setParent(casillas[0][0]);
		if (adjacency.isStart() == false) {
			opened.add(adjacency);
		}
	}

	while (opened.size() > 0) {
		Casilla best = findBestPassThrough();
		opened.remove(best);
		closed.add(best);
		if (best.isEnd()) {
			System.out.println("Found Goal");
			populateBestList(destino);
			//draw();
			return;
		} else {
			ArrayList<Casilla> neighbors = best.getAdyacencias();
			for (Casilla neighbor : neighbors) {
				if (opened.contains(neighbor)) {
					Casilla tmpSquare = new Casilla(neighbor.getX(),
							neighbor.getY(), 0,this);
					tmpSquare.setParent(best);
					if (tmpSquare.getPassThrough(destino) >= neighbor
							.getPassThrough(destino)) {
						continue;
					}
				}

				if (closed.contains(neighbor)) {
					Casilla tmpSquare = new Casilla(neighbor.getX(),
							neighbor.getY(), 0,this);
					tmpSquare.setParent(best);
					if (tmpSquare.getPassThrough(destino) >= neighbor
							.getPassThrough(destino)) {
						continue;
					}
				}
				
				
				neighbor.setParent(best);

				opened.remove(neighbor);
				closed.remove(neighbor);
				opened.add(0, neighbor);
			}
		}
	}

	System.out.println("No Path to goal");
}

private void populateBestList(Casilla square) {

	bestList.add(square);
	if (square.getParent().isStart() == false) {
		populateBestList(square.getParent());
	}

	return;
}

private Casilla findBestPassThrough() {

	Casilla best = null;
	for (Casilla square : opened) {
		if (best == null
				|| square.getPassThrough(destino) < best.getPassThrough(destino)) {
			best = square;
		}
	}

	return best;
}

}

Es un poco lioso pero espero que se entienda!

1 respuesta

elkaoD #4 May '13

#3 resúmelo un poco please. Quita lo que ya hayas comprobado que funciona bien y/o indica donde falla

Puedes dejar el código completo, pero una versión aparte resumida con justo la parte que falla viene bien.

1 respuesta

MrAw3s0m3 #5 May '13

#4 ok, lo que creo que falla es esto:

spoiler

public void calculaAdyacencias(){
		//int arriba=x-1;
		int abajo=x+1;
		//int izquierda=y-1;
		int derecha=y+1;
		
	if(abajo < central.getFilas()){
		//if(central.getCasilla(abajo, y).getContenido()==1){
			central.getCasilla(abajo, y).anhadeAdyacencia(this);
			this.anhadeAdyacencia(central.getCasilla(abajo, y));
		//}
	}
	
	if(derecha < central.getColumnas()){
		//if(central.getCasilla(x, derecha).getContenido()==1){
			central.getCasilla(x, derecha).anhadeAdyacencia(this);
			this.anhadeAdyacencia(central.getCasilla(x, derecha));
		//}	
	}
}
public void anhadeAdyacencia(Casilla c) {

	adyacencias.add(c);
}

Edit: a base de system.out.println vi que no se añadia ninguna casilla al array de adyacencias ni nada y no se por que. La unica condicion que pongo es que el contenido de la celda sea = 1 (aunque ahora lo tenga comentado para que se añadiesen todas, pero ni con esas).

1 respuesta

Mewtwo #6 May '13

#5 ¿tienes que buscar solo un camino ? ¿o todos los posibles a la salida ?

¿segun me imagino el resultado quieres guardarlo en una matriz de tla forma que vas accediendo casilla a casilla ?

es decir puede que equivoque xD pero segun lo que creo que intentas es buscar el mejor camino en un laberinto.

TicTaK #7 May '13

#1 te falla el algoritmo por todos lados, principalmente por que lo intentas hacer iterativo y te vas a volver loco.

el algoritmo que necesitas es un algoritmo de backtracking ( RECURSION ), y una solucion como consecuencia de decisiones, y como si no sabes de lo que te hablo me voy a volver loco explicandolo si quieres te mando un pdf de como se soluciona ese problema exactamente, pasame tu correo

Problema adyacencia de celdas en A Star search java

Usuarios habituales

Tags