Olá, exploradores da programação! Hoje vamos levar nosso gerador de labirintos a um novo nível, adicionando um poderoso recurso: a busca de caminhos usando o algoritmo A* em Java. Além disso, vamos aprimorar nossa interface gráfica com campos para definir as dimensões do labirinto, botões para gerar o labirinto e encontrar o caminho, e o mais importante, uma animação para visualizar o caminho encontrado! Preparem-se para uma experiência ainda mais imersiva e desafiadora!
Se você não acompanhou a primeira parte, é aconselhável que você siga os passos anteriores para ter o código pronto para as alterações sugeridas neste artigo.
Por que o algoritmo A*?
Para encontrar o caminho mais eficiente em um labirinto, precisamos de um algoritmo de busca que seja rápido e capaz de lidar com labirintos de qualquer tamanho. O algoritmo A*, também conhecido como A-estrela, é uma excelente escolha devido à sua combinação de eficiência e precisão.
O A* é um algoritmo de busca em grafos que encontra o caminho de menor custo entre dois nós. Ele usa uma função heurística para estimar o custo do caminho a partir de um determinado nó até o destino, combinando essa estimativa com o custo real do caminho percorrido até o momento. Isso o torna ideal para encontrar a rota mais rápida e com menor custo em labirintos complexos. Nesse contexto, sua velocidade o torna ótimo para labirintos grandes e complexos, e sua garantia de encontrar o melhor caminho, o faz ideal para nossa aplicação.
Assim, escolhemos o A* por sua combinação de velocidade, precisão e capacidade de lidar com diferentes tamanhos e complexidades de labirintos. Dessa forma, vamos adicionar essa funcionalidade ao nosso gerador.
Próximos passos: Interface gráfica e animação
Primeiramente, precisamos criar uma interface que possibilite que o usuário insira as dimensões do labirinto e acione a geração e a busca do melhor caminho.
Em seguida, adicionaremos um visualizador que ilustre a busca do melhor caminho em tempo real, exibindo os caminhos já percorridos pelo algoritmo, até que o ponto final seja encontrado. Essa visualização ajudará na compreensão do A* em ação e tornará o uso da aplicação mais intuitivo.
Mãos à obra: O código com a magia do A* e interface aprimorada!
Para começarmos, vamos atualizar algumas classes do projeto e adicionar novas:
Classe Main.java (atualizada)
import java.awt.BorderLayout;
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.List;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;
import javax.swing.SwingUtilities;
public class Main {
private static int rows = 20;
private static int cols = 30;
private static JFrame frame;
private static MazePanel mazePanel;
private static MazeGenerator generator;
private static JTextField rowsField;
private static JTextField colsField;
public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
createGUI();
});
}
private static void createGUI() {
frame = new JFrame("Gerador de Labirintos");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
JPanel panel = new JPanel(new FlowLayout());
rowsField = new JTextField(String.valueOf(rows),5);
colsField = new JTextField(String.valueOf(cols),5);
panel.add(new JLabel("Linhas:"));
panel.add(rowsField);
panel.add(new JLabel("Colunas:"));
panel.add(colsField);
generator = new RecursiveBacktrackerGenerator();
JButton generateButton = new JButton("Gerar Labirinto");
JButton findPathButton = new JButton("Encontrar Caminho");
generateButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
try {
rows = Integer.parseInt(rowsField.getText());
cols = Integer.parseInt(colsField.getText());
if(rows <= 0 || cols <= 0){
JOptionPane.showMessageDialog(null, "Por favor, insira valores positivos maiores que 0");
return;
}
} catch (NumberFormatException ex) {
JOptionPane.showMessageDialog(null, "Entrada inválida. Use apenas números inteiros.");
return;
}
Cell[][] maze = generator.generateMaze(rows, cols);
if(mazePanel != null){
frame.remove(mazePanel);
}
mazePanel = new MazePanel(maze);
frame.add(mazePanel,BorderLayout.CENTER);
frame.pack();
frame.setLocationRelativeTo(null); // Centraliza a janela
findPathButton.setEnabled(true);
}
});
findPathButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if(mazePanel!= null){
findPathButton.setEnabled(false);
new Thread(() -> {
findAndAnimatePath();
findPathButton.setEnabled(true);
}).start();
}
}
});
findPathButton.setEnabled(false);
panel.add(generateButton);
panel.add(findPathButton);
frame.add(panel, BorderLayout.NORTH);
frame.pack();
frame.setLocationRelativeTo(null); // Centraliza a janela
frame.setVisible(true);
}
private static void findAndAnimatePath() {
AStarSearch aStar = new AStarSearch();
List<Cell> path = aStar.search(
mazePanel.getMaze(),
mazePanel.getInitialCellRow(),
mazePanel.getInitialCellCol(),
mazePanel.getFinalCellRow(),
mazePanel.getFinalCellCol()
);
if(path != null){
for (Cell cell : path){
mazePanel.addToPath(cell.row, cell.col);
try {
Thread.sleep(20);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
mazePanel.repaint();
}
} else{
JOptionPane.showMessageDialog(null,"Caminho não encontrado");
}
}
}
Como resultado, as modificações no Main.java trazem as seguintes novidades:
- Campos de texto (JTextField) para que o usuário insira as dimensões do labirinto.
- Botões para gerar o labirinto e para acionar a busca do melhor caminho.
- Um tratador de evento para o botão de “Gerar Labirinto”, para criar o painel MazePanel usando os valores nos campos de texto e para o botão de “Encontrar Caminho” aciona uma nova thread para executar o algoritmo A* para que a interface não fique congelada.
- Execução do algoritmo A* em uma thread separada, com pausa para criar a animação do caminho.
- Um método findAndAnimatePath para iniciar a busca do caminho e adicionar as células no caminho do labirinto para que seja possível ver a animação.
Classe MazePanel.java (atualizada)
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JPanel;
public class MazePanel extends JPanel {
private Cell[][] maze;
private int cellSize = 20;
private final int borderWidth = 8;
private int initialCellRow;
private int initialCellCol;
private int finalCellRow;
private int finalCellCol;
private List<Point> path = new ArrayList<>();
public MazePanel(Cell[][] maze) {
this.maze = maze;
setPreferredSize(new Dimension(maze[0].length * cellSize + 2 * borderWidth, maze.length * cellSize + 2 * borderWidth));
this.initialCellRow = 0;
this.initialCellCol = 0;
this.finalCellRow = maze.length - 1;
this.finalCellCol = maze[0].length - 1;
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
g.setColor(Color.WHITE);
g.fillRect(0, 0, getWidth(), getHeight());
// Desenha as células e as paredes
for (int row = 0; row < maze.length; row++) {
for (int col = 0; col < maze[0].length; col++) {
drawCell(g, maze[row][col], col, row);
}
}
// Desenha o caminho sobre o labirinto, depois de desenhar as paredes.
drawPath(g);
drawStartingAndFinalPositions(g);
}
private void drawPath(Graphics g) {
g.setColor(Color.BLUE);
for (Point p : this.path) {
int cellX = borderWidth + p.y * cellSize;
int cellY = borderWidth + p.x * cellSize;
g.fillOval(cellX + cellSize / 4, cellY + cellSize / 4, cellSize / 2, cellSize / 2);
}
}
private void drawStartingAndFinalPositions(Graphics g) {
g.setColor(Color.GREEN);
int startX = borderWidth + initialCellCol * cellSize;
int startY = borderWidth + initialCellRow * cellSize;
g.fillRect(startX, startY, cellSize, cellSize);
g.setColor(Color.RED);
int endX = borderWidth + finalCellCol * cellSize;
int endY = borderWidth + finalCellRow * cellSize;
g.fillRect(endX, endY, cellSize, cellSize);
}
public Cell[][] getMaze() {
return this.maze;
}
private void drawCell(Graphics g, Cell cell, int x, int y) {
int cellX = borderWidth + x * cellSize;
int cellY = borderWidth + y * cellSize;
Graphics2D g2d = (Graphics2D) g;
g2d.setStroke(new BasicStroke(borderWidth));
g2d.setColor(Color.BLACK);
if (cell.wallNorth) {
g2d.draw(new Line2D.Float(cellX, cellY, cellX + cellSize, cellY));
}
if (cell.wallEast) {
g2d.draw(new Line2D.Float(cellX + cellSize, cellY, cellX + cellSize, cellY + cellSize));
}
if (cell.wallSouth) {
g2d.draw(new Line2D.Float(cellX, cellY + cellSize, cellX + cellSize, cellY + cellSize));
}
if (cell.wallWest) {
g2d.draw(new Line2D.Float(cellX, cellY, cellX, cellY + cellSize));
}
}
public int getInitialCellCol() {
return initialCellCol;
}
public int getInitialCellRow() {
return initialCellRow;
}
public int getFinalCellCol() {
return finalCellCol;
}
public int getFinalCellRow() {
return finalCellRow;
}
public void addToPath(int row, int col) {
this.path.add(new Point(row, col));
}
public void clearPath() {
this.path.clear();
}
}
As modificações no MazePanel.java adicionam:
- Uma lista de Points representando o caminho (path) que o A* irá retornar.
- O método drawPath é chamado em paintComponent para iterar em todas as células do caminho, e então, exibir em azul o caminho correto.
- Métodos para adicionar pontos no caminho e para limpar o caminho.
Classe AStarSearch.java
import java.util.*;
public class AStarSearch {
public List<Cell> search(Cell[][] grid, int startRow, int startCol, int endRow, int endCol) {
Cell start = grid[startRow][startCol];
Cell end = grid[endRow][endCol];
PriorityQueue<Cell> openSet = new PriorityQueue<>(Comparator.comparingInt(this::fScore));
Map<Cell, Integer> gScore = new HashMap<>();
Map<Cell, Integer> fScore = new HashMap<>();
gScore.put(start, 0);
fScore.put(start, heuristic(start,end));
openSet.add(start);
while(!openSet.isEmpty()){
Cell current = openSet.poll();
if (current == end) {
return reconstructPath(current);
}
List<Cell> neighbors = getNeighbors(grid,current);
for(Cell neighbor: neighbors){
int tentantiveGScore = gScore.get(current) + 1;
if(tentantiveGScore < gScore.getOrDefault(neighbor, Integer.MAX_VALUE)){
neighbor.previousCell = current;
gScore.put(neighbor, tentantiveGScore);
fScore.put(neighbor, tentantiveGScore + heuristic(neighbor,end));
if(!openSet.contains(neighbor)){
openSet.add(neighbor);
}
}
}
}
return null;
}
private List<Cell> getNeighbors(Cell[][] grid, Cell cell) {
int row = cell.row;
int col = cell.col;
int[][] neighborsPosition = {{row - 1,col},{row, col+1},{row+1,col},{row,col-1}};
java.util.List<Cell> neighbors = new java.util.ArrayList<Cell>();
for (int[] pos: neighborsPosition){
int newRow = pos[0];
int newCol = pos[1];
if (isValid(grid, newRow,newCol)){
Cell n = grid[newRow][newCol];
boolean wall = hasWall(cell,n);
if(!wall) {
neighbors.add(n);
}
}
}
return neighbors;
}
private List<Cell> reconstructPath(Cell cell){
List<Cell> path = new ArrayList<>();
Cell current = cell;
while (current!=null){
path.add(current);
current = current.previousCell;
}
Collections.reverse(path);
return path;
}
private boolean hasWall(Cell current, Cell neighbor) {
int row = current.row - neighbor.row;
int col = current.col - neighbor.col;
if (row == 1 && current.wallNorth ) return true;
if (row == -1 && current.wallSouth ) return true;
if (col == 1 && current.wallWest) return true;
if (col == -1 && current.wallEast) return true;
return false;
}
private int heuristic(Cell a, Cell b){
return Math.abs(a.row - b.row) + Math.abs(a.col - b.col);
}
private boolean isValid(Cell[][] grid, int row, int col) {
return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
}
private int fScore(Cell cell){
return cell.row + cell.col;
}
}
Nesse caso, o código da classe AStarSearch implementa o algoritmo de busca de caminhos A*:
- Abre uma fila de prioridade openSet que mantém as células para avaliação do caminho.
- gScore e fScore são mapas que mantém o custo de start até a célula analisada e a estimativa de custo de start até a célula final.
- Os métodos getNeighbors, reconstructPath e heuristic são usados para iterar pelas células vizinhas, reconstruir o caminho e calcular o valor heurístico respectivamente.
Código em ação: Encontrando o caminho perfeito!
Com todas as modificações, seu programa agora tem uma interface intuitiva, com campos de entrada para definir as dimensões do labirinto, botões para gerar o labirinto e iniciar a busca do melhor caminho, e a animação em tempo real para exibir a ação do algoritmo. Dessa maneira, a experiência do usuário se torna ainda mais dinâmica e envolvente.
Em suma, você agora tem um gerador de labirintos em Java completo, com uma base sólida, implementando o poderoso algoritmo A* para encontrar o melhor caminho.

Reflexões finais e próximos passos
Com o novo código, o usuário tem ainda mais autonomia para interagir com a aplicação. Assim, o programa se torna mais flexível e responsivo, oferecendo ao usuário diversas formas de usar a aplicação.
Em outras palavras, você agora tem um projeto sofisticado com funcionalidades bem definidas, pronto para servir de base para projetos ainda mais elaborados. Deixe seu comentário abaixo e compartilhe suas impressões. Sua opinião é muito importante para a melhoria do código!
Espero que este guia tenha sido útil e inspirador. Continue explorando e desafiando seus limites! Nos encontramos na próxima aventura.
O código fonte do projeto está disponível no meu github através deste link.