poursuvrir.java

IA 算法问题

import java.util.ArrayList;
import java.awt.Color;
import java.lang.Math;

import javax.swing.JPanel;

public class Poursuvrir extends Object{
	ArrayList<Etat> ouvert,ferme,devp;
	Element jr,msr;
	Etat e,s;
	
	Echiquier echiquier;
	
	Poursuvrir(Echiquier er){
		super();
		ouvert=new ArrayList<Etat>();
		ferme=new ArrayList<Etat>();
		devp=new ArrayList<Etat>();
		echiquier=er;
		
		e=new Etat(echiquier.getMonsteur());
		ouvert.add(e);
		s=new Etat(echiquier.getJoueur());
		

	}
	
	ArrayList<Etat> Methode(){
		
		Etat n;

		while(!ouvert.isEmpty()){
			n=minArrayList(ouvert);
			
			ouvert.remove(n);
			
			ferme.add(n);
			
			if (n.x()==s.x() && n.y()==s.y()) return ferme;
			else{
				devp=devolopper(n,echiquier);
				Etat ni;
				for(int i=0;i<devp.size();i++){
					//System.out.print(devp.size());
					ni=(Etat)devp.get(i);
					ni.setH(FonctH(s,ni));
					
					//System.out.print(existe_dans_ArrayList(ni, ferme));
					if(!existe_dans_ArrayList(ni, ferme)){
						
						if(!existe_dans_ArrayList(ni, ouvert))
							ouvert.add(ni);
							
						else{
							Etat e=etat_existe_dans_ArrayList(ni, ouvert);
							if(e.getG()>ni.getG()){
								e.setG(ni.getG());
								e.setPere(n);
							} 
						}
					}
						
				}
			}
		}
		return ferme;
	
	}
	
	
	int FonctH(Etat jr, Etat msr){
		
		return (Math.abs(jr.x()-msr.x())+Math.abs(jr.y()-msr.y()));
	}
	
	Etat minArrayList(ArrayList<Etat> arry){
		Etat et=(Etat)arry.get(0);
		Etat min=et;
		for(int i=0;i<arry.size();i++){
			et=(Etat)arry.get(i);
			if (et.getF() < min.getF()) {
				min=et;
			}
		}
		return min;
	}
	public ArrayList<Etat> devolopper(Etat e, Echiquier er){
		int x=e.x();
		int y=e.y();
		
		ArrayList<Etat> n=new ArrayList<Etat>();
		//N S O E
		if (((x-1)>=0) && (!er.estMur(x-1,y)))
			n.add(new Etat((x-1),y,e,e.getG()+1, 0));
		if (((x+1)<er.getTaille()) && (!er.estMur(x+1,y)))
			n.add(new Etat((x+1),y,e,e.getG()+1, 0));
		if (((y-1)>=0) && (!er.estMur(x,y-1)))
			n.add(new Etat(x,(y-1),e,e.getG()+1, 0));
		if (((y+1)<er.getTaille()) && (!er.estMur(x,y+1)))
			n.add(new Etat(x,(y+1),e,e.getG()+1, 0));
		
		return n;
	}
	boolean existe_dans_ArrayList(Etat n, ArrayList<Etat> array){
		Etat e;
		for(int i=0;i<array.size();i++){
			e=array.get(i);
			if(n.x()==e.x() && n.y()==e.y()) return true;
		}
		return false;
	}
	Etat etat_existe_dans_ArrayList(Etat n, ArrayList<Etat> array){
		Etat e=null;
		for(int i=0;i<array.size();i++){
			e=array.get(i);
			if(n.x()==e.x() && n.y()==e.y()) return e;
		}
		return e;
	}
	
	
}