[Java-Pseudocodice] Navigazione Mappa

[guylmaster]

Salve a tutti,
creo un topic differente da quello sull'esaurimento della memoria perché mi sono accorto che l'algoritmo di navigazione esauriva la memoria perché effettivamente faceva dei giri assurdi (e a volte calcolava pure rotte che non erano possibili). Ora sto un po' impazzendo per capire come buttar già almeno uno pseudocodice di come questo algoritmo deve funzionare.

Dunque in realtà non ho un grafo, ma avrò:

- una cella di partenza ed un cella di destinazione;
- Una funzione che dato un nodo ti da una lista di nodi vicini. Da notare che non abbiamo più un grafo, quindi niente archi, e non abbiamo nemmeno tutti i nodi sulla mappa abbiamo solo questa funzione che ti crea di volta in volta solo i nodi vicini (se li calcolassimo tutti addio memoria);
- Una funzione di costo per ordinare i nodi vicini e prendere di volta in volta il meno costoso;

L'algoritmo almeno per ora è da rappresentare in maniera simile ad una visita di un grafo in profondità, con una variante: Inizio a crearmi un percorso in profondità, se vedo che la lunghezza del percorso che mi sono studiato supera una lunghezza massima (lmax) termino su quel ramo e ricominicio da un'altro.

Quindi in pratica all'algoritmo di navigazione ricorsivo gli passo:

(Vertex partenza, double lmax_attuale,ArrayList<Vertex> rotta)

Dove ho un Vertex Destinazione che è globale (in quanto la destinazione è sempre quella), la partenza ovviamente cambia di volta in volta perché passiamo da un nodo al suo vicini, e rotta penso che bisogna passarglielo perché in qualche modo quando ci accorgiamo che un cammino è finito dobbiamo "reinizializzarlo" al passo precedente.

Voi cosa consigliate di fare? Io prorpio su quel "reinizializzarlo al cammino precedente" mi sto perdendo. Se rotta è una lista di nodi come faccio a sapere quali erano i nodi del cammino precedente?

Insomma se avete qualche idea di pseudocodice ve ne sarei grato ,
guylmaster.

[PGI-Bis]

Per come sono fatti i nodi una ricerca in ampiezza (che è esattamente l'opposto della ricerca in profondità). Se puoi stimare la distanza tra un nodo qualsiasi ed il punto di arrivo puoi usare un A*. Gli algoritmi li trovi cercando "breadth-first" e "A star", sono due modi comuni di realizzare la ricerca di percorsi nei videogiochi. Ad esempio se vuoi il codice in java lo trovi nel download del capitolo 12 di questo libro sui videogames:

http://www.brackeen.com/javagamebook/#download

[guylmaster]

Originariamente inviato da PGI-Bis

Per come sono fatti i nodi una ricerca in ampiezza (che è esattamente l'opposto della ricerca in profondità). Se puoi stimare la distanza tra un nodo qualsiasi ed il punto di arrivo puoi usare un A*. Gli algoritmi li trovi cercando "breadth-first" e "A star", sono due modi comuni di realizzare la ricerca di percorsi nei videogiochi. Ad esempio se vuoi il codice in java lo trovi nel download del capitolo 12 di questo libro sui videogames:

http://www.brackeen.com/javagamebook/#download

Dove posso trovare uno pseudocodice capibile di questo A* ? perché ho cercato su wikipedia ma lo pseudocodice che fornisce non mi è del tutto chiaro

[PGI-Bis]

Forse non ti serve. Dall'altro post mi sembra di capire che tu abbia una mappa divisa in quadranti. Se è così allora il passaggio da un nodo ad un altro ha lo stesso costo quindi la scansione in ampiezza ti darebbe lo stesso risultato dell'A*. In ogni caso l'A* è una scansione in ampiezza mitigata dalla distanza variabile quindi fai presto a passare all'altro.

Nota che sia l'A* che il breadth first ti danno il percorso di lunghezza minima, con la differenza che l'A* ti permette di specificare il significato di "lunghezza".

Per un'implementazione del breadth-first ti serve una classe Nodo con un campo "precedente".

class Nodo {
    Nodo precedente;
}

Il campo precedente lo usi per ricostruire il percorso una volta che, attraverso la scansione, scopri di essere arrivato a destinazione.

Servono poi tutti i nodi adiacenti ad un Nodo. Serve cioè che da qualche parte ci sia un metodo:

List<Nodo> getNodiAdiacentiA(Nodo n) {...}

In base a cosa determini chi siano gli adiacenti di un Nodo n dipende dalla tua mappa. Nei giochi la mappa è statica, cioè i Nodo sono:

class Nodo {
    Nodo precedente;
    List<Nodo> adiacenti = ...
}

Ma in realtà è irrilevante che un Nodo sappia chi sono i suoi vicini, possono tranquillamente essere determinati esternamente - purchè siano costanti.

Per poter identificare le adiacenze di un Nodo con ogni probabilità tu avrai bisogno di inserire in Nodo qualche altra informazione, ad esempio le sue coordinate, quindi il tuo Nodo potrebbe essere:

class Nodo {
    Nodo precedente;
    Vertex coordinate;

    Nodo(Vertex coordinate) {
        this.coordinate = coordinate;
    }
}

A conti fatti il tuo Nodo altro non sarebbe che una decorazione di Vertex fatta perchè Vertex abbia il campo precedente. Potresti anche non usare Nodo e affidarti ad una HashMap per gestire l'associazione Vertex-Vertex precedente.

Comunque, una volta che hai il Nodo e il metodo esterno List<Nodo> getNodiAdiacenti(Nodo), la scansione è banale e procede un po' come l'onda formata da un sasso gettato in uno stagno: parti da un punto e procedi guardando intorno a quel punto, poi intorno alle adiacenze di quel punto, alle adiacenze delle adiacenze... e così via finchè l'onda non becca la destinazione.

Usi una lista per i nodi da visitare e una lista per i nodi già visitati. La seconda ti serve per evitare i cicli che si verificherebbero nel caso in cui due nodi avessero un adiacenza comune:

Nodo trova(Nodo partenza, Nodo arrivo) {
   List<Nodo> visitati = new LinkedList<Nodo>();
   List<Nodo> daVisitare = new LinkedList<Nodo>();
   visitati.add(partenza);

   while(!visitati.isEmpty()) {
      Nodo nodo = visitati.removeFirst();
      if(nodo == arrivo) {
         return nodo;
      } else {
         visitati.add(nodo);
         List<Nodo> adiacenti = getNodiAdiacentiA(nodo);
         for(Nodo a : adiacenti) {
            if(!visitati.contains(a) && !daVisitare.contains(a)) {
               //cioè è la prima volta che "vedo" a
               a.precedente = nodo;
               daVisitare.add(a);
            }
         }
      }
   }
   return null;
}

Se il risultato di trovaPercorso è diverso da null allora il Nodo restituito (la destinazione) ha come precedente il "passo" che viene prima di lui nel percorso. Il precedente avrà come precedente il passo... che l'ha preceduto e così via.

Puoi ricostruire il percorso come lista di nodi semplicemente aggiungendo ad una pila il precedente del precedente finchè questo esiste.

List<Nodo> creaPercorso(Nodo n) {
    List<Nodo> percorso = new LinkedList<Nodo>();
    while(n.precedente != null) {
        percorso.push(n);
        n = n.precedente;
    }
    return percorso;
}

Non ho provato il codice quindi è "pseudo". Fai riferimento al capitolo di quel libro per averlo esatto.

L'A* è praticamente uguale solo che la condizione di inserimento nella lista dei nodi da visitare dipende anche dalla distanza.

[mmx[ngg]]

Semplice curiosità...ti avevo parlato di Voronoi perchè mi sembra che sia esattamente quello che ti serve. Cito da wikipedia :

Si può sfruttare la struttura di un diagramma di Voronoi per scoprire il punto di S più vicino ad un punto dato x senza calcolare ad ogni richiesta la distanza di x da ogni elemento di S. Una tale ricerca può avere applicazioni geografiche in sistemi informativi geografici (ad esempio "trova l'ospedale più vicino ad una data abitazione")

E' un sistema semplice che ti permette di segmentare un piano in più parti, di avere l'esatta distanza di un nodo dagli altri, di avere una struttura pulita e veloce (non indifferente visto che usi Java che non è un fulmine) e ti evita un sacco di rogne su memoria, tempi ecc. ecc...cioè...stai provando a riscoprire l'acqua calda, non è più faticoso ?

Perchè non vuoi utilizzarlo ? Lo eviti perchè è complicato o c'è un motivo differente ?

[guylmaster]

Originariamente inviato da mmx[ngg]

Semplice curiosità...ti avevo parlato di Voronoi perchè mi sembra che sia esattamente quello che ti serve. Cito da wikipedia :



E' un sistema semplice che ti permette di segmentare un piano in più parti, di avere l'esatta distanza di un nodo dagli altri, di avere una struttura pulita e veloce (non indifferente visto che usi Java che non è un fulmine) e ti evita un sacco di rogne su memoria, tempi ecc. ecc...cioè...stai provando a riscoprire l'acqua calda, non è più faticoso ?

Perchè non vuoi utilizzarlo ? Lo eviti perchè è complicato o c'è un motivo differente ?

Non so come applicarlo, mi sto davvero dannando la vita. Se hai da buttar giù uno pseudocodice sarei la persona più felice del mondo.

Attualmente ho provato a provare questo codice:

public ArrayList<Vertex> vicini_ordinati(Vertex partenza, double lmax){
		
		
		int id=partenza.get_ID();
		Vertex nodo;
		ArrayList<Integer> nodi_vicini=Funzioni_matematiche.get_nodi_vicini(id,mx.get_n_righe_matrice_partizionata() , mx.get_n_colonne_matrice_partizionata());
		//calcolo dei costi per i nodi vicini ad un determinato nodo
		ArrayList<Vertex> lista_nodi=new ArrayList<Vertex>();
		//System.out.println(id + " : " + nodi_vicini);
		int i=0;
		while (i<nodi_vicini.size()) 
		{
			//nodo= (Vertex) (mv.get_hasmap()).get(nodi_vicini.get(i));
			 //nodo.avvalora();
			nodo=new Vertex(mx.ritorna_partizione(nodi_vicini.get(i),lista_partizioni),mr);
			 double c=costo(1,1,1,nodo,nodo_destinazione, nodo_partenza);
			 nodo.set_costo(c);
			 //System.out.println(nodo.getpercentuale_non_navigabilita());
			 
			 
			 if(nodo.getpercentuale_non_navigabilita() == (float) 0 && !contiene_nodo(nodo, lmax))
			{
				 lista_nodi.add(nodo);
			}
			 i++;
			 //System.out.println("WHILE");
		}
		
		return lista_nodi;
	}
	
	public boolean contiene_nodo(Vertex nodo, double lmax){
		boolean flag=false;
		 if(lista_visitati.containsKey(nodo.get_ID()))
		 {
			 if (lista_visitati.get(nodo.get_ID()).lmax > lmax)
			 {
				flag = true; 
			 }
		 }
	 return flag;	 
	}
	double lmax_attuale = 20;
	public ArrayList<Vertex> calcolo_rotta_ricorsiva(double lmax_attuale,ArrayList<Vertex> rotta)
	{
		ArrayList<Vertex> lista_nodi=null;
		Integer i = new Integer(0);
		double lmax_i=0;
		System.out.println(rotta);
		if(lmax_attuale > 0 && flag==false)
		{
			lista_nodi=vicini_ordinati(rotta.get(rotta.size()-1),lmax_attuale);
			if(lista_nodi.isEmpty())
			{
				rotta.remove(rotta.size()-1);
				System.out.println("\n\n\nVICOLO CECO!\n\n\n");
				return rotta;
			}
			System.out.println("ID: " + rotta.get(rotta.size()-1).get_ID() + " Vicini: " + lista_nodi + " lmax: "+ lmax_attuale);
			lmax_i = lmax_attuale - 1;
			while(i<lista_nodi.size() && flag == false)
			{
				
				if(lista_nodi.get(i).appartiene(t.get_destinazione()))
				{
						flag = true;
						rotta.add(lista_nodi.get(i));
						rotta_calcolata = rotta;
						return rotta_calcolata;
						
				}
				else 
				{
					//if(lmax_i!=0)
						rotta.add(lista_nodi.get(i));
						lista_visitati.put(lista_nodi.get(i).get_ID(),new Visitati(lista_nodi.get(i), lmax_i));
					//System.out.println(rotta);
					    calcolo_rotta_ricorsiva(lmax_i, rotta);
				}
				i++;
				//System.out.println(rotta);
				//System.out.println("WHILE2");
				//System.out.println("WHILE i: " + i);
			}
		}
		if(flag == false)
		{
			//System.out.println("FOR i: " + i);
			for(int j=i; j>=1 && rotta.size() >1; j--)
			{
				if(!rotta.isEmpty())
					rotta.remove(rotta.size()-1);
				//System.out.println("\n\n\nRIMOZIONE!\n\n\n");
			}
			System.out.println("Rotta appena svuotata: " + rotta);
			
		}
		
		//rotta = new ArrayList<Vertex>();
		//rotta.add(nodo_partenza);

		return rotta;
	}

Ho però dei problemi a ripulire la rotta per quando abbandono un ramo (o per vicolo cieco o per aver superato lmax) e decido di tornare un passo indietro.

Infatti mi ritorna:
[ID:1 - 0.0%, ID:3 - 0.0%, ID:4 - 0.0%, ID:5 - 0.0%, ID:10 - 0.0%, ID:15 - 0.0%, ID:20 - 0.0%]

E si salta il nodo 7 di mezzo, o 6 - 7 a seconda di che cappero di percorso decide di fare. Questo perché probabilmente con quel ciclo for di remove cancello troppo

[mmx[ngg]]

Io ho capito per sommi capi che devi fare ma o mi son perso un pezzo o non l'hai detto...te da che dati parti ? Nel senso, le tue entità da che dati sono composte ? Una singola coordinata che ne indica il punto sulla mappa (più semplice), un'insieme di coordinate che ne delimitano un'area (inzia a farsi dura) o cosa ? Inoltre, di quante entità parliamo ? 10, 100 o milioni ? Perchè al ridursi del loro numero si può semplificare di molto gli algoritmi da implementare tenendo presente che Voronoi è un sistema e non un algoritmo specifico. Quest'ultimo varia in base ai dati di partenza e al risultato che si vuole ottenere.

Inizia a chiarire da che tipo di dati parti, la dimensione dell'insieme ed elenca tutte le funzionalità che vuoi ottenere.

[guylmaster]

Originariamente inviato da mmx[ngg]

Io ho capito per sommi capi che devi fare ma o mi son perso un pezzo o non l'hai detto...te da che dati parti ? Nel senso, le tue entità da che dati sono composte ? Una singola coordinata che ne indica il punto sulla mappa (più semplice), un'insieme di coordinate che ne delimitano un'area (inzia a farsi dura) o cosa ? Inoltre, di quante entità parliamo ? 10, 100 o milioni ? Perchè al ridursi del loro numero si può semplificare di molto gli algoritmi da implementare tenendo presente che Voronoi è un sistema e non un algoritmo specifico. Quest'ultimo varia in base ai dati di partenza e al risultato che si vuole ottenere.

Inizia a chiarire da che tipo di dati parti, la dimensione dell'insieme ed elenca tutte le funzionalità che vuoi ottenere.

I dati sono dei Vertex, che contengono un range di latitudini (minima e massima) ed un range di longitudini (minima e massima). Nel caso di precisione 1 i massimi ed i minimi coincido ed abbiamo una rappresentazione puntuale.

Quando dobbiamo calcolare le distanze rappresentiamo la cella con un centroide, ed abbiamo una funzione sia che ci dice la direzione di un punto verso un'altro (quindi verso la destinazione) che la distanza.

Il numero di dati dipende dalla mappa e dalla distanza tra partenza e destinazione nonché dalla precisione. Non ti so dire così un numero. E' comunque elevato.

La mappa non la memorizzo nemmeno tutta assieme ma lavoro in questa maniera:

Leggo tutte le longitudini della mappa e le memorizzo in un vettore, leggo tutte le latitudini e le memorizzo in un'altro vettore. Mi divido la mappa in quadranti la cui grandezza dipende dalla precisione e poi individuo i quadranti che contengono partenza e destinazione. Ovviamente so come passare da latitudine e longitudine ad id del quadrante (sono numerati per righe con un intero crescente che parte da uno).

Ho anche una funzione che mi restituisce gli adiacenti di un quadrante (ordinandoli anche rispetto a dei costi specifici di cui devo tener conto ovvero distanza della cella dalla destinazione, traffico ma anche di quanto differisce dalla rotta "lineare") e quindi mi avvalora le celle solo quando effettivamente sono adiacenti ad un punto della rotta. Così facendo insomma evito di avvalorarmi tutta la mappa ma mi avvaloro solo i dintorni dei punti in cui passo.

Nel mio algoritmo, sapendo che so prendermi gli adiacenti pur non avendo in realtà un grafo come struttura, quello che volevo realizzare (anzi che devo realizzare, è la traccia) è una visita in profondità.

Il problema è che non riesco a "guidare" questa visita in profondità in maniera da crearmi un percorso decente. Ovvero o inizia a girarmi intondo sempre sugli stessi nodi oppure metto dei paletti troppo rigidi e me ne salta qualcuno. Essendo poi tutto fatto mediante ritorsione diventa anche abbastanza impegnativo andare avanti a debug.

Ad esempio l'errore che sto riscontrando adesso è del tipo:
Sto sul nodo 11, prendo gli adiacenti del nodo 11 che sono 16 e 17, quindi proseguo su 16 e ho come adiacente 17. Arrivo su 17 da 16 e mi rendo conto che è un vicolo cieco o qualcosa di problematico, torno indietro sul ciclo degli adiacenti di 11 e mi ritrovo nel ciclo 17 e ci ritorno dinuovo. Insomma mi sto perdendo nella ritorsione.

[mmx[ngg]]

Ok ho afferato quasi tutto, quasi perchè non ho ancora capito se la mappa in origine contiene coordinate o delimitazioni...sicuramente alla fine arrivi a trattare i dati per delimitazioni ed è qua che ti complichi la vita da morire. In sostanza l'impressione che si ha è che la struttura di base che hai utilizzato non è adatta allo scopo se non tramite giri strani. Certo, io conosco poco o nulla del tutto quindi potrei benissimo sbagliarmi.

Mi sono soffermato poco o nulla sull'algoritmo che hai postato però ho letto che sospendi la ricorsione e riparti da un altro nodo. L'errore forse è proprio qui. Tramite ricorsione sai esattamente i nodi trattati e quali ancora da trattare (Per ogni punto della rotta) quindi se l'interrompi e poi incappi in qualche vicolo cieco l'algoritmo non funziona più perchè ritratti nodi già utilizzati. La ricorsione la devi far andare fino in fondo o, se non puoi per limiti di memoria, devi organizzare i dati in maniera diversa ed eliminarla.

La sotto mappa che ti crei è riferita esclusivamente al punto di destinazione ? Se si puoi evitare ricorsione, sorting ecc. ecc. Crei l'insieme salvandoti (per ogni cella) alcune informazioni fondamentali per il calcolo della rotta, quindi :

- La distanza tra la cella trattata e quella di destinazione
- Un flag che ti indica se l'hai già trattata
- Altre eventuali informazioni che assegnano un peso in fase di calcolo della rotta tipo il traffico

A questo punto ti crei un vettore che contiene in ogni elemento l'ID delle celle attraversate per la rotta dove il primo elemento è la partenza. Da li in poi applichi le seguenti logiche sull'ultimo elemento nel vettore :

1 - Ricerchi le celle confinanti (qui dovevi utilizzare Voronoi ma a questo punto utilizza l'algoritmo del precedente post).
2 - Prendi quella con il peso (distanza, traffico ecc. ecc.) più significativo che non sia ancora trattata (sono 8 quindi un ciclo va bene). Se ne trovi una passi al punto 3 altrimenti vai al 4.
3 - L'aggiungi al vettore rotta, ne incrementi il numero e setti la cella come trattata e riparti dal punto 1.
4 - Se non hai più celle da trattare e non sei a destinazione significa che sei in un vicolo cieco quindi decrementi il vettore rotta e ritorni alla cella precedenente. Riparti dal punto 1.

Alla fine il vettore rotta deve contenere i vari segmenti della rotta (cioè un'elenco delle celle attraversate) presi in base al loro peso. Non è un algoritmo velocissimo su larga scala (se becchi un vicolo cieco verso la fine è un casino) ma per come hai trattato i dati, per i vari limiti di memoria ecc. ecc. non vedo di meglio.

[banryu79]

Notare che personalizzando la funzione/metodo che restituisce gli adiacenti di un nodo, la soluzione proposta da PGI-Bis fa quello che ti serve in versione iterativa (nel metodo "trova", "visitati" funge da stack) invece che ricorsiva.

[guylmaster]

Credo di aver risolto, ma non canto vittoria finchè non faccio test più accurati (magari ad orari in cui sono meno stanco ), utilizzando un albero n-ario (una mia rappresentazione semplificatissima).

Praticamente tutti i percorsi che trovo li metto in un albero n-ario sotto forma di padre-figlio. Quando arrivo a destinazione con una lunghezza del percorso che gli passo come parametro semplicemente risalgo dal nodo foglia al nodo radice, stampo tutto al contrario e ho la rotta

Devo però cercare di migliorare il costo da assegnare ai vari nodi perché noto che spesso il computer tende a non fare spostamenti in diagonale ma spotamenti ad L allungando inutilmente i percorsi.