Created
November 29, 2011 19:09
-
-
Save sixhat/1405998 to your computer and use it in GitHub Desktop.
A* novo da Aula de PCD
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment