I'm trying to implement a maze, where you need to find a better way to get to the exit (without facing the wall). The labyrinth has already been implemented, the structure is almost ready (it runs through the entire labyrinth).
But I would like it to run only from input to output, and for that I used Dijkstra to perform this course.
Here are the classes and their codes:
Labyrinth Class:
import java.util.Collections;
import java.util.Arrays;
public class Labirinto {
private final int x;
private final int y;
private final int[][] maze;
private static char[][] drawnMaze;
private static Grafo grafoLabirinto;
private final static int TAMANHO = 4; //PARA AUMENTAR O TAMANHO DO LABIRINTO, BASTA MODIFICAR ESTA VARIÁVEL.
private final static int ENTRADAX = 0;
private final static int ENTRADAY = 1;
private final static int SAÍDAX = (TAMANHO*2);
private final static int SAÍDAY = (TAMANHO*2-1);
public Labirinto(int x, int y) {
this.x = x;
this.y = y;
maze = new int[this.x][this.y];
drawnMaze = new char [TAMANHO*2+1][TAMANHO*2+1];
generateMaze(0, 0);
}
Class Edge:
public class Aresta {
private Vértice origem;
private Vértice destino;
public Aresta(Vértice origem, Vértice destino) {
this.origem = origem;
this.destino = destino;
}
public Vértice getOrigem(){
return this.origem;
}
public Vértice getDestino(){
return this.destino;
}
}
Vertice Class:
import java.util.ArrayList;
public class Vértice {
private String id;
int x;
int y;
private ArrayList <Aresta> adj;
public Vértice(String id, int x, int y){
this.id = id;
this.x = x;
this.y = y;
this.adj = new ArrayList <Aresta>();
}
public void addAdj(Aresta e) {
adj.add(e);
System.out.println(adj.size());
}
public String getId(){
return this.id;
}
public int getX(){
return this.x;
}
public int getY(){
return this.y;
}
public ArrayList <Aresta> getArestas(){
return adj;
}
}
Dijkstra class:
/*
* Classe para calular o caminho minimo entre dois vértices
* Usando o algoritmo de Dijkstra
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Dijkstra {
// Atributos usados na funcao encontrarMenorCaminho
Vértice menorCaminho = new Vértice(null, 0, 0);
// Variavel que recebe os vértices pertencentes ao menor caminho
Vértice verticeCaminho = new Vértice(null, 0, 0);
// Variavel que guarda o vértice que esta sendo visitado
Vértice atual = new Vértice(null, 0, 0);
// Variavel que marca o vizinho do vértice atualmente visitado
Vértice vizinho = new Vértice(null, 0, 0);
// Lista dos vertices que ainda nao foram visitados
List<Vértice> naoVisitados = new ArrayList<Vértice>();
// Algoritmo de Dijkstra
public List<Vértice> encontrarMenorCaminhoDijkstra(Grafo grafo, Vértice v1,
Vértice v2) {
// Adiciona a origem na lista do menor caminho
menorCaminho.getId();
// Colocando a distâncias iniciais
for (Grafo ) {
// Vértice atual tem distância zero, e todos os outros,
// ("infinita - qualquer valor")
if (grafo.getVertices().get(i).getDescricao()
.equals(v1.getDescricao())) {
grafo.getVertices().get(i).setDistancia(0);
} else {
grafo.getVertices().get(i).setDistancia(9999);
}
// Insere o vertice na lista de vertices nao visitados
this.naoVisitados.add(grafo.getVertices().get(i));
}
Collections.sort(naoVisitados);
// O algoritmo continua ate que todos os vertices sejam visitados
while (!this.naoVisitados.isEmpty()) {
// Toma-se sempre o vertice com menor distancia, que eh o primeiro
// da
// lista
atual = this.naoVisitados.get(0);
System.out.println("Pegou esse vertice: " + atual);
/*
* Para cada vizinho (cada aresta), calcula-se a sua possivel
* distancia, somando a distancia do vertice atual com a da aresta
* correspondente. Se essa distancia for menor que a distancia do
* vizinho, esta eh atualizada.
*/
for (int i = 0; i < atual.getArestas().size(); i++) {
vizinho = atual.getArestas().get(i).getDestino();
System.out.println("Olhando o vizinho de " + atual + ": "
+ vizinho);
if (!vizinho.verificarVisita()) {
// Comparando a distância do vizinho com a possível
// distância
if (vizinho.getDistancia() > (atual.getDistancia() + atual
.getArestas().get(i).getPeso())) {
vizinho.setDistancia(atual.getDistancia()
+ atual.getArestas().get(i).getPeso());
vizinho.setPai(atual);
/*
* Se o vizinho eh o vertice procurado, e foi feita uma
* mudanca na distancia, a lista com o menor caminho
* anterior eh apagada, pois existe um caminho menor
* vertices pais, ateh o vertice origem.
*/
if (vizinho == v2) {
menorCaminho.clear();
verticeCaminho = vizinho;
menorCaminho.addAdj(vizinho);
while (verticeCaminho.getPai() != null) {
menorCaminho.add(verticeCaminho.getPai());
verticeCaminho = verticeCaminho.getPai();
}
// Ordena a lista do menor caminho, para que ele
// seja exibido da origem ao destino.
Collections.sort(menorCaminho);
}
}
}
}
// Marca o vertice atual como visitado e o retira da lista de nao
// visitados
atual.visitar();
this.naoVisitados.remove(atual);
/*
* Ordena a lista, para que o vertice com menor distancia fique na
* primeira posicao
*/
Collections.sort(naoVisitados);
System.out.println("Nao foram visitados ainda:"+naoVisitados);
}
return menorCaminho;
}
}
public static void main(String[] args) {
int x = args.length >= 1 ? (Integer.parseInt(args[0])) : TAMANHO;
int y = args.length == 2 ? (Integer.parseInt(args[1])) : TAMANHO;
Labirinto maze = new Labirinto(x, y);
maze.display();
//maze.displaySkeleton();
maze.displayStringMaze();
grafoLabirinto = BFS.gerarGrafo(new Vértice("0", 0, 1), drawnMaze);
System.out.println(grafoLabirinto.toString());
}
public void displaySkeleton(){
for(int i=0; i < maze.length; i++){
for(int j=0; j < maze.length; j++){
System.out.print(maze[i][j]);
}
System.out.println("");
}
}
public void displayStringMaze(){
for(int i=0; i < TAMANHO*2+1; i++){
for(int j=0; j < TAMANHO*2+1; j++){
System.out.print(drawnMaze[i][j]);
}
System.out.println("");
}
}
public void display() {
int lineIterator = 0;
int colIterator = -1;
for (int i = 0; i < y; i++) {
// draw the north edge
for (int j = 0; j < x; j++) {
if((maze[j][i] & 1) == 0){
drawnMaze[lineIterator][++colIterator] = '█';
drawnMaze[lineIterator][++colIterator] = '█';
}else{
drawnMaze[lineIterator][++colIterator] = '█';
drawnMaze[lineIterator][++colIterator] = ' ';
}
}
drawnMaze[lineIterator++][++colIterator] = '█';
colIterator = -1;
// draw the west edge
for (int j = 0; j < x; j++) {
if((maze[j][i] & 8) == 0){
drawnMaze[lineIterator][++colIterator] = '█';
drawnMaze[lineIterator][++colIterator] = ' ';
}else{
drawnMaze[lineIterator][++colIterator] = ' ';
drawnMaze[lineIterator][++colIterator] = ' ';
}
}
drawnMaze[lineIterator++][++colIterator] = '█';
colIterator = -1;
}
// draw the bottom line
for (int j = 0; j < x; j++) {
drawnMaze[lineIterator][++colIterator] = '█';
drawnMaze[lineIterator][++colIterator] = '█';
}
drawnMaze[lineIterator][++colIterator] = '█';
//draw entrance & exit
drawnMaze[ENTRADAX][ENTRADAY] = 'e';
drawnMaze[SAÍDAX][SAÍDAY] = 's';
}
private void generateMaze(int cx, int cy) {
DIR[] dirs = DIR.values();
Collections.shuffle(Arrays.asList(dirs));
for (DIR dir : dirs) {
int nx = cx + dir.dx;
int ny = cy + dir.dy;
if (between(nx, x) && between(ny, y)
&& (maze[nx][ny] == 0)) {
maze[cx][cy] |= dir.bit;
maze[nx][ny] |= dir.opposite.bit;
generateMaze(nx, ny);
}
}
}
private static boolean between(int v, int upper) {
return (v >= 0) && (v < upper);
}
private enum DIR {
N(1, 0, -1), S(4, 0, 1), E(4, 1, 0), W(8, -1, 0);
private final int bit;
private final int dx;
private final int dy;
private DIR opposite;
// use the static initializer to resolve forward references
static {
N.opposite = S;
S.opposite = N;
E.opposite = W;
W.opposite = E;
}
private DIR(int bit, int dx, int dy) {
this.bit = bit;
this.dx = dx;
this.dy = dy;
}
};
/*
public static void encontraCaminho(){
int k = 0;
int pos;
int aux = 0;
for(int i = 0; i < TAMANHO ; i ++){
for(int j = 0; j<TAMANHO-1;j++){
if(k==0){ //verificando se é a primeira execução
k++;
grafoLabirinto[ENTRADAX][ENTRADAY] = 2; // mudar espaço vago para um espaço percorrido
grafoLabirinto[SAÍDAX][SAÍDAY] = 2;
j = ENTRADAY;
i = ENTRADAX;
}
if(grafoLabirinto == 0){
grafoLabirinto[i][j] = 2;
if(grafoLabirinto[i][j+1]==0){
aux++;
}else if(grafoLabirinto[i+1][j]==0){
aux++;
}else if(grafoLabirinto[i-1][j]==0){
aux++;
}
}
}
}
}
*/
}
This is a simple example of graph implementation represented by the list of adjacencies:
import java.util.List;
import java.util.ArrayList;
public class Grafo {
List<Vértice> vértices;
List<Aresta> arestas;
public Grafo() {
vértices = new ArrayList<Vértice>();
arestas = new ArrayList<Aresta>();
}
public Vértice addVertice(Vértice v) {
v = new Vértice(v.getId(), v.getX(), v.getY());
vértices.add(v);
return v;
}
public Aresta addAresta(Vértice origem, Vértice destino) {
Aresta e = new Aresta(origem, destino);
arestas.add(e);
return e;
}
public String arestasToString(){
String s = "";
for(Aresta a: arestas){
s += "{" + a.getDestino().getId() +" , " +a.getOrigem().getId() + "}";
}
return s;
}
public String toString() {
String r = "";
for (Vértice u : vértices) {
r+= String.format("%s (%d,%d) -> ", u.getId(), u.getX(), u.getY());
//r += u.getId() + " " + u.getX() +" -> ";
for (Aresta e : u.getArestas()) {
Vértice v = e.getDestino();
r += v.getId() + ", ";
}
r += "\n";
}
return r;
}
public void ligarArestas(){
for(Vértice v : vértices){
for(Aresta a : arestas){
if(v.getId()==a.getOrigem().getId()){
v.getArestas().add(a);
}
}
}
}
/*
public static void main(String[] args) {
Grafo g = new Grafo();
Vertice s = g.addVertice("s");
Vertice t = g.addVertice("t");
Vertice y = g.addVertice("y");
Aresta st = g.addAresta(s, t);
Aresta sy = g.addAresta(s, y);
Aresta ty = g.addAresta(t, y);
Aresta yt = g.addAresta(y, t);
System.out.println(g);
}
*/
}
My question is: how do I implement the Dijkstra class in this labyrinth context, where do I just need to go from input to output (without going through dead-ends)?