Rota perfeita: Desvendando labirintos com o algoritmo A* em Java e Swing!

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");
        }
    }
}
Ver mais

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();
    }
}
Ver mais

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;
    }
}
Ver mais

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.

Gif de labirinto com caminho traçado

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.

Deixe um comentário