Java arraylist para implementação labirinto

Lucas LC · 30 de dezembro de 2020

Olá bom dia!

Gostaria de uma ajuda.

Estou fazendo um labirinto em java, a ideia principal é que um explorador está nesse labirinto e ele pode se movimentar em 4 direções(cima,baixo,direita e esquerda), até chegar no seu destino.

Preciso implementar 4 caminhos para o meu labirinto, segue abaixo:

1. Caminho mais curto. Isto é, que passe pelo menor número possível de casas.

2. Caminho mais longo. Isto é, que passe pelo maior número possível de casas (ok, este é um
critério estranho, mas pense que o explorador possui motivos para visitar o maior número de casas
possível sem passar mais de uma vez por uma mesma casa).

3. Caminho mais valioso. Isto é, que maximiza o valor dos itens coletados.

4. Caminho mais rápido. Ou seja, aquele minimiza o tempo que se leva para chegar no
destino (note que não necessariamente equivale ao mais curto, pois depende dos itens que são coletados
no caminho, o que por sua vez afeta o tempo necessário para percorrê-lo).

Para fazer esses caminhos eu fiz um método movimentar, retornarMovimento (caso não dê as 4 direções ele retorna uma casa).

private void aumentarDirecoes() { 
        this.direcoes += 1;
    }


public void movimentar() { 

        //Parar caso não de as 4 direções.
        if(this.direcoes >= 4) return;
    
        
        Posicao retornarMovimento = retornarMovimento(); 
        
        //saber o local que ele está.
        String valor = this.game.retornarValorPosicaoLabirinto(retornarMovimento);
        
        //Caso o valor retornado seja o do próprio explorador ou a passagem esteja bloqueada não faça nada ou entrou um item. 
        if(valor.equals("X")) {
            proximoMovimento();
            aumentarDirecoes();
            //Se não de certo tente novamente.
            movimentar(); 
            
        } else { 
            
            this.posInicial = retornarMovimento; 
        }
    }

    
    private void proximoMovimento() { 
        switch(this.movimento) { 
            case CIMA:
            this.movimento = MovimentoExplorador.BAIXO; 
            break;
            case BAIXO:
            this.movimento = MovimentoExplorador.ESQUERDA; 
            break;
            case ESQUERDA:
            this.movimento = MovimentoExplorador.DIREITA; 
            break;
            case DIREITA:
            this.movimento = MovimentoExplorador.CIMA; 
            break;
        }
}

    //Em um algoritmo de tentativa e erro, sempre tem a possibilidade de retornar o movimento que não dá certo.
    public Posicao retornarMovimento() { 

        int retornoPosX = this.posInicial.getPosX();
        int retornoPosY = this.posInicial.getPosY();
        //Caso o explorador for para cima, para retornar uma posição ele precisa ser maior que 0. 
        switch(movimento) { 
            case CIMA:
                    if(retornoPosX > 0) { 
                    retornoPosX -= 1; 
                }
                    break; 

            case BAIXO: 
                    if(retornoPosX < this.game.getLines() -1){
                        retornoPosX +=1; 
                    }
                    break; 
                    
                case ESQUERDA: 
                    if(retornoPosY > 0) { 
                    retornoPosY -= 1;
                }
                    break; 
                
                case DIREITA:
                    if(retornoPosY < this.game.getColumn() -1){ 
                    retornoPosY += 1; 
                }
                    break;
        }
        return new Posicao(retornoPosX, retornoPosY); 
}

Esse método movimento ele faz apenas 1 movimento, logo na implementação do primeiro caminho para encontrar o menor número de casas eu pensei em criar uma classe que adicione as coordenadas desse movimento, mas é claro vou precisar mudar esse método movimentar para retornar as coordenadas que ele foi, então toda vez que ele fizer um movimento ele adiciona as coordenadas na outra classe e depois eu só comparo os tamanhos das listas para encontrar a menor, porém para fazer isso pensei em usar um arraylist, mas não sei como utilizar perfeitamente, alguém poderia ajudar ?

AdrianoSiqueira · 30 de dezembro de 2020

Você poderia salvar na lista apenas o histórico de coordenadas e no final pegar o tamanho dessa lista, que indicaria a quantidade de passos que foram dados. Algo mais ou menos assim:

List<Coordenada> coordenadas = new ArrayList<>();

// ...

// Para cada passo, pegue a coordenada atual e adicione na lista
Coordenada c = new Coordenada(x, y);
coordenadas.add(c)

// ...

/*
 * No final pegue a quantidade de items da lista, ela indica a quantidade de
 * passos que foram dados para encontrar a saida.
 */ 
int passos = coordenadas.size();

Lucas LC · 31 de dezembro de 2020

Boa tarde amigo.

Eu fiz a classe solução igual a sua ideia, queria saber se tá certo.

A classe Posição é instanciada no método main colocando a posição inicial e final. O getPosX() e getPosY() marca a posição atual do explorador.

CLASSE SOLUÇÃO PARA REGISTRAR O HISTÓRICO DE COORDENADAS.

21 horas atrás, AdrianoSiqueira disse:



import java.util.ArrayList;
import  java.util.Collections ;
import  java.util.PriorityQueue ;

public class Solucao{

public void adiciona(Posicao p){
//Crio uma fila de coordenadas.
ArrayList<Posicao> filaCoordenadas = new ArrayList<Posicao>();
     
p = new Coordenada(getPosX(), getPosY());
filaCoordenadas.add(p);   
}

public int tamanho(){
int tamanho = 0; 
for(Posicao p : filaCoordenadas){
tamanho++; 
}
	return tamanho;
}
}

CLASSE POSIÇÃO.

21 horas atrás, AdrianoSiqueira disse:


public class Posicao{

	//Chamando de xy.
	private int posX; 
	private int posY; 
	
	//Iniciar a posição.
	public Posicao(int PosX, int PosY) { 
		this.posX = PosX; 
		this.posY = PosY;
	}

	public int getPosX(){
		return this.posX; 
	} 

	public void setPosX(int posX){
		this.posX = posX; 
	}

	public int getPosY(){
		return this.posY; 
	} 

	public void setPosY(int posY){
		this.posY = posY; 
	} 

	public void imprimePosicoes(){
		System.out.println("X: " + this.getPosX() + "\t Y: " + this.getPosY());
	}
	
}

AdrianoSiqueira · 1 de janeiro de 2021

A classe Posicao ficou legal, mas a classe solução está errada.

Perceba que no método adiciona você está criando um ArrayList, isso significa que você vai criar uma lista nova toda vez que tentar adicionar uma posição e essa lista vai se perder, pois não está fazendo nada com ela. Crie o ArrayList fora do método, como se fosse um atributo dessa classe.

Outra coisa, você está recebendo o objeto Posicao via parâmetro, então não deveria instanciar um novo objeto, pois vai perder a informação que você recebeu.

Deveria ser algo assim:

// ...

public class Solucao {
  private ArrayList<Posicao> list = new ArrayList<>();
  
  public void adicionar(Posicao p) {
    list.add(p);
  }
  
  // ...

Lucas LC · 1 de janeiro de 2021

15 horas atrás, AdrianoSiqueira disse:

A classe Posicao ficou legal, mas a classe solução está errada.

Perceba que no método adiciona você está criando um ArrayList, isso significa que você vai criar uma lista nova toda vez que tentar adicionar uma posição e essa lista vai se perder, pois não está fazendo nada com ela. Crie o ArrayList fora do método, como se fosse um atributo dessa classe.

Outra coisa, você está recebendo o objeto Posicao via parâmetro, então não deveria instanciar um novo objeto, pois vai perder a informação que você recebeu.

Entendi, obrigado mesmo pela ajuda.

ficou assim então:

20 horas atrás, Lucas LC disse:

import java.util.ArrayList;

import java.util.Collections ;

import java.util.PriorityQueue ;

public class Solucao{

ArrayList<Posicao> filaCoordenadas = new ArrayList<Posicao>();

public void adiciona(Posicao p){

filaCoordenadas.add(p);

}

public int tamanho(){

int tamanho = 0;

for(Posicao p : filaCoordenadas){

tamanho++;

}

return tamanho;

}

15 horas atrás, AdrianoSiqueira disse:

Deveria ser algo assim:


// ...

public class Solucao {
  private ArrayList<Posicao> list = new ArrayList<>();
  
  public void adicionar(Posicao p) {
    list.add(p);
  }
  
  // ...

Assim eu consigo fazer o histórico das coordenadas que chegou até o final do caminho certo ?

Ai eu só comparo o tamanho dessas listas para ver qual é a menor ou maior.

AdrianoSiqueira · 1 de janeiro de 2021

1 hora atrás, Lucas LC disse:

Ai eu só comparo o tamanho dessas listas para ver qual é a menor ou maior.

Exato.

1 hora atrás, Lucas LC disse:

public int tamanho(){

int tamanho = 0;

for(Posicao p : filaCoordenadas){

tamanho++;

}

return tamanho;

}

Esse trecho também não está legal. Você está reinventando a roda, as listas já possuem uma maneira de pegar o tamanho.

Faça assim:

int getTamanho(){
  return filaCoordenadas.size();
}

Isso vai retornar a quantidade de itens na lista, que por sua vez é a quantidade de passos.

Lucas LC · 1 de janeiro de 2021

45 minutos atrás, AdrianoSiqueira disse:
Faça assim:
int getTamanho(){
  return filaCoordenadas.size();
}
Isso vai retornar a quantidade de itens na lista, que por sua vez é a quantidade de passos.

Ata, pensei em inicializar uma variável com 0 e meu for percorre a lista, cada vez que ela achar um objeto ela incrementa e retorna o tamanho.

AdrianoSiqueira · 1 de janeiro de 2021

Funciona, mas é desnecessário.

Lucas LC · 2 de janeiro de 2021

2 horas atrás, AdrianoSiqueira disse:

Funciona, mas é desnecessário.

Entendi, obrigado!!

Lucas LC · 2 de janeiro de 2021

Adriano boa tarde!

Será que você pode me ajudar a fazer o primeiro caminho, que é o caminho com menor casas.

Deixei todos os arquivos que eu fiz em anexo.

O primeiro caminho tentei colocar um if como caso base para parar a recursão do atributo solucao, fiz um while para ele andar no labirinto, enquanto meu explorador puder ir para cima, baixo, esquerda e direita ele continua, chamo a função movimentar() para dar um passo, programei para ele ir para cima primeiro, adiciono esse movimento na lista que você me ajudou a fazer, zero as direções para ele tentar ir para cima de novo, ai nos próximos ifs fiquei meio perdido, porque preciso ter um caminho diferente para comparar ai fiz esse atributo solucao para comparar com a melhor, por isso chamei recursivamente e depois comparo o tamanho delas e retorno o caminho melhor.

21 horas atrás, Lucas LC disse:

21 horas atrás, AdrianoSiqueira disse:

Faça assim:



public Solucao criterio1(Posicao posicaoInicial,Posicao posicaoFinal){

if(posicaoInicial.getPosX() == posicaoFinal.getPosX() && posicaoInicial.getPosY() == posicaoFinal.getPosY()) return new Solucao();
Solucao melhor = null; 

while(Fim()) { 
movimentar();
tempoExato += calculaTempo(peso);
melhor.adiciona(movimentar());
zerarDirecoes(); 

if(posicaoInicial.getPosX() != posicaoFinal.getPosX() && posicaoInicial.getPosY() != posicaoFinal.getPosY()) { 
aumentarDirecoes(); 
movimentar();
tempoExato1 += calculaTempo(peso);
solucao.adiciona(movimentar());
solucao = criterio1(posicaoInicial,posicaoFinal); 
if(solucao != null && melhor == null || solucao.tamanho() < melhor.tamanho()){
   melhor = solucao;
}else if(melhor != null) return melhor; 
}
        }
return melhor;
                }

Solucao.txt.txt Posicao.txt.txt MovimentoExplorador.txt.txt Main.txt.txt Game.txt.txt Criterios.txt.txt

AdrianoSiqueira · 2 de janeiro de 2021

Dê uma olhada nesse projeto, veja se ele te dá alguma inspiração.

Lucas LC · 2 de janeiro de 2021

1 hora atrás, AdrianoSiqueira disse:

Dê uma olhada nesse projeto, veja se ele te dá alguma inspiração.

Vou dar uma olhada sim, obrigado!

Lucas LC · 6 de janeiro de 2021

Adriano boa noite!

Consegui fazer bastante coisa já e arrumei muitas coisas no código, será que você pode me ajudar com uma dica sobre cópia de objetos ?

AdrianoSiqueira · 6 de janeiro de 2021

Procure sobre a interface Cloneable, ela é responsável por abstrair esse tipo de tarefa.

Lucas LC · 6 de janeiro de 2021

8 horas atrás, AdrianoSiqueira disse:

Procure sobre a interface Cloneable, ela é responsável por abstrair esse tipo de tarefa.

Consegui fazer meu explorador percorrer todo o labirinto e imprimir todos os caminhos possíveis, agora preciso separar entre aquele mais curto e mais longo.

Esse tabuleiro tem apenas 3 caminhos possíveis:

(x,y): (6, 2)

(x,y): (5, 2)

(x,y): (4, 2)

(x,y): (3, 2)

(x,y): (2, 2)

(x,y): (1, 2)

(x,y): (0, 2)
Tamanhos 7

Destino Encontrado!!

(x,y): (6, 2)

(x,y): (6, 1)

(x,y): (6, 0)

(x,y): (5, 0)

(x,y): (4, 0)

(x,y): (3, 0)

(x,y): (2, 0)

(x,y): (1, 0)

(x,y): (0, 0)

(x,y): (0, 1)

(x,y): (0, 2)
Tamanhos 11
Destino Encontrado!!

(x,y): (6, 2)

(x,y): (6, 3)

(x,y): (6, 4)

(x,y): (5, 4)

(x,y): (4, 4)

(x,y): (3, 4)

(x,y): (2, 4)

(x,y): (1, 4)

(x,y): (0, 4)

(x,y): (0, 3)

(x,y): (0, 2)
Tamanhos 11

Destino Encontrado!!

Toda vez que ele chega no destino ele imprime essa mensagem.

Essa é a parte do código que ele para quando encontra todos os caminhos e o switch que valida conforme o critério. A outra parte do código é movimento esquerda, baixo, direita e cima.

Em 01/01/2021 às 15:52, Lucas LC disse:

Em 01/01/2021 às 15:05, AdrianoSiqueira disse:

Faça assim:


//Se a posição XY Inicial for igual a Final = CASO BASE
if(posicaoInicial.ehigual(posicaoFinal)){
System.out.println("Destino Encontrado!!");
 solucaoAtual.imprimirCaminho();
        
//Validar com base no critério.
switch(criterio){
case 1: 
this.criterio1(solucaoAtual);
break;
case 2:
this.criterio2(solucaoAtual);				
break;
case 3:
this.criterio3(solucaoAtual);
break;
case 4:
this.criterio4(solucaoAtual);
break;
				}

Preciso validar agora com base nos críterios colocando esse objeto solucaoAtual recebendo todos os caminhos possíveis e chamar no critério1 por exemplo, ai fica assim:

public void criterio1(Solucao solucao){

if(melhor == null || solucao.tamanho() < melhor.tamanho()){

melhor = clone(solucao);

}

esse objeto melhor vale null no primeiro caso e depois faço uma cópia do objeto solucao para não modificar o endereço do objeto que tá lá naquele método que se movimenta. No entanto eu fiz um println e ele não faz mais comparações com o segundo caminho que é aquele que tem tamanho 11, será que eu preciso armazenar as cópias dos caminhos em um array ou faço uma outra lista para isso ?