A* novo da Aula de PCD

astar.java

/**
* Contém 4 Classes com a Demo da aula.
* A classe importante é a classe AStar que recebe um mapa de Casas e utilizando PriorityQueues 
* devolve um LinkedList com a Path a seguir (invertida).
* 
* Devem adapatar o código às vossas necessidades nomeadamente tendo em atenção que neste demo há alguns valores
* que estão escritos directamente no código e que servem apenas para este exemplo (por exemplo as dimensões do mapa).
*/
import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;

public class AMain {
    Casa[][] mapa;

    public AMain() {
        JFrame janela = new JFrame("A*");
        janela.setSize(400, 400);
        janela.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        Container painel = janela.getContentPane();
        painel.setLayout(new BorderLayout());
        buildMapa();
        final Picture label = new Picture(mapa);
        label.addMouseListener(label);
        JButton bt = new JButton("Start");
        bt.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent arg0) {
                label.go();
            }
        });
        JButton rs = new JButton("Reset");
        rs.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent arg0) {
                buildMapa();
                label.reset(mapa);
            }
        });
        painel.add(label, BorderLayout.CENTER);
        painel.add(bt, BorderLayout.SOUTH);
        painel.add(rs, BorderLayout.NORTH);
        janela.setVisible(true);
    }

    private void buildMapa() {
        // TODO Auto-generated method stub
        mapa = new Casa[20][20];
        for (int y = 0; y < 20; y++) {
            for (int x = 0; x < 20; x++) {
                mapa[x][y] = new Casa(x, y);
            }
        }
    }

    public static void main(String[] args) {
        new AMain();
    }
}
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Rectangle;

public class Casa implements Comparable<Casa> {
    public int  y;
    public int  x;
    public Casa father = null;
    double      dist   = 0.0;
    double      cost   = 0.0; // cost = dist + heuristic
    int         tipo   = 0;

    public Casa(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void draw(Graphics g) {
        Rectangle dims = g.getClipBounds();
        int a = Math.min(dims.height, dims.width) / 20;
        switch (tipo) {
        case 1:
            g.setColor(Color.yellow);
            g.fillRect(x * a, y * a, a, a);
            break;
        case 2:
            g.setColor(Color.blue);
            g.fillRect(x * a, y * a, a, a);
            break;
        case 3:
            g.setColor(Color.black);
            g.fillRect(x * a, y * a, a, a);
            break;
        case 4:
            g.setColor(Color.red);
            g.fillRect(x * a, y * a, a, a);
            break;
        default:
            g.setColor(Color.black);
            g.drawRect(x * a, y * a, a, a);
        }
        if (cost > 0.0) {
            g.setColor(Color.black);
            g.setFont(new Font("Arial", Font.BOLD, 8));
            g.drawString("" + dist, x * a, y * a + a / 2);
            g.setFont(new Font("Arial", Font.ITALIC, 8));
            g.drawString("" + cost, x * a, y * a + a);
        }
    }

    public void setOrigem() {
        tipo = 1;
    }

    public void setDestino() {
        tipo = 2;
    }

    public void setObstaculo() {
        tipo = 3;
    }

/**
* Método que implementa a Comparação entre dois Objectos do tipo Casa da interface Comparable.
*/ 
    public int compareTo(Casa o) {
        return Double.compare(cost, o.cost);
    }
}
import java.awt.Graphics;
import java.awt.Point;
import java.awt.Rectangle;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.ArrayList;

import javax.swing.JLabel;

public class Picture extends JLabel implements MouseListener {
    private Casa[][] mapa;
    Rectangle        dims;
    int              nClicks = 0;
    Casa             start;
    Casa             target;

    public Picture(Casa[][] mapa) {
        this.mapa = mapa;
    }

    @Override
    protected void paintComponent(Graphics g) {
        // TODO Auto-generated method stub
        super.paintComponent(g);
        dims = g.getClipBounds();
        for (int y = 0; y < 20; y++) {
            for (int x = 0; x < 20; x++) {
                mapa[x][y].draw(g);
            }
        }
    }

    public void mouseClicked(MouseEvent e) {
        Point p = e.getPoint();
        int a = Math.min(dims.width, dims.height) / 20;
        int cx = p.x / a;
        int cy = p.y / a;
        nClicks++;
        switch (nClicks) {
        case 1:
            mapa[cx][cy].setOrigem();
            start = mapa[cx][cy];
            break;
        case 2:
            mapa[cx][cy].setDestino();
            target = mapa[cx][cy];
            break;
        default:
            mapa[cx][cy].setObstaculo();
            break;
        }
        repaint();
    }

    public void mouseEntered(MouseEvent e) {
    }

    public void mouseExited(MouseEvent e) {
        // TODO Auto-generated method stub
    }

    public void mousePressed(MouseEvent e) {
        if (nClicks > 2) {
            Point p = e.getPoint();
            int a = Math.min(dims.width, dims.height) / 20;
            int cx = p.x / a;
            int cy = p.y / a;
            mapa[cx][cy].setObstaculo();
        }
    }

    public void mouseReleased(MouseEvent e) {
        // TODO Auto-generated method stub
    }

    public void go() {
        AStar a = new AStar(mapa, start, target);
        LinkedList<Casa> path = a.calcPath();
        repaint();
        // Nao vou utilizar a path para nada nesta demo... mas no jogo é utilizada para o movimento das vossas peças.
    }

    public void reset(Casa[][] mapa2) {
        mapa = mapa2;
        nClicks = 0;
        repaint();
    }
}


import java.util.LinkedList;
import java.util.PriorityQueue;

public class AStar {
    private final Casa[][]      mapa;
    private final Casa          start;
    private final Casa          target;
    private PriorityQueue<Casa> open;
    private PriorityQueue<Casa> closed;

    public AStar(Casa[][] mapa, Casa start, Casa target) {
        this.mapa = mapa;
        this.start = start;
        this.target = target;
    }

    public LinkedList<Casa> calcPath() {
        LinkedList path = new LinkedList<Casa>();
        open = new PriorityQueue<Casa>();
        closed = new PriorityQueue<Casa>();
        start.cost = Math.abs(target.x - start.x) + Math.abs(target.y - start.y);
        open.add(start);
        while (open.peek() != target && !open.isEmpty()) {
            Casa current = open.poll();
            closed.add(current);
            // Determinar os vizinhos da casa current
            Casa norte = null, este = null, sul = null, oeste = null;
            if (current.y > 0)
                norte = mapa[current.x][current.y - 1];
            if (current.x < 19)
                este = mapa[current.x + 1][current.y];
            if (current.x > 0)
                oeste = mapa[current.x - 1][current.y];
            if (current.y < 19)
                sul = mapa[current.x][current.y + 1];
            Casa[] viz = { norte, este, sul, oeste };
            double dist2 = current.dist + 1.0;
            for (Casa vizinho : viz) {
                if (vizinho == null) {
                    continue;
                }
                if (vizinho.tipo > 2) {
                    continue;
                }
                if (open.contains(vizinho) && dist2 < vizinho.dist) {
                    open.remove(vizinho);
                    vizinho.dist = 0;
                    vizinho.cost = 0;
                    vizinho.father = null;
                }
                if (closed.contains(vizinho) && dist2 < vizinho.dist) {
                    closed.remove(vizinho);
                    vizinho.dist = 0;
                    vizinho.cost = 0;
                    vizinho.father = null;
                }
                if (!open.contains(vizinho) && !closed.contains(vizinho)) {
                    // Calcular a heuristica
                    double h = Math.abs(target.x - vizinho.x) + Math.abs(target.y - vizinho.y);
                    vizinho.dist = dist2;
                    vizinho.cost = dist2 + h;
                    vizinho.father = current;
                    open.add(vizinho);
                }
            }
        }
        // Reconstruir a path a partir do target.
        if (target.father != null) {
            path.add(target);
            Casa current = target;
            while (current.father != start) {
                path.add(current.father);
                current = current.father;
                current.tipo = 4;
            }
            return path;
        } else {
            return null;
        }
    }
}