Navigazione Mappa

[Neptune]

Salve a tutti,
creo un topic differente da quello sulla 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 più grafo, in realtà l'algoritmo di navigazione avrà a disposizione di:

- 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 ,
Neptune

[valia]

veramente questo te lo avevo suggerito (anche se per via indiretta devo dire).
L'idea è tenere non tutti i nodi, ma solo i vicini, quindi hai un algoritmo, possibilmente efficiente, che dato un nodo x restituisca i vicini. Supponevo già evitassi di tenerti tutto in memoria, vabbé.

Beh per tenerti il percorso, hai proprio una mappa di in cui via via metti quelli che passi (ti basta solo il loro id), ricordando in questo caso che risalirci significa ripartire il percorso.

Adesso lascio libero sfogo alla mia fantasia (ehehe) e vediamo al visita. Sei al nodo X, devi vedere i nodi vicini (e li hai nella tua lista di adiacenza) e selezionare quelli che

1. potrebbero portarti nella direzione desiderata
2. almeno uno dei nodi adiacenti ti porta nella direzione desiderata (con priorità bassa rispetto al caso precedente).

Il punto è come fai a capire se prendere un nodo o no? Devi creare un intorno che consideri buono (es. un raggio di 1 km intorno alla latitudine desiderata, se il nodo casca li stai a cavallo). se non ne trovi allarga il raggio di ricerca, se ne trovi muoviti in quel senso (verso il più preciso).

Dovresti in questo modo ottenere qualcosa (tagli i nodi della direzione opposta ad esempio).
Hai ricerche continue, ma non cerchi in tutto il mondo, cerchi in sottoinsiemi che desumi piccoli del mondo.
Se poi hai strutturato bene la ogni nodo (e i suoi adiacenti) qualcoas dovresti ottenere (spero)
Non so se come idea ti è di aiuto, l'ho buttata li

[Neptune]

Originariamente inviato da valia
veramente questo te lo avevo suggerito (anche se per via indiretta devo dire).
L'idea è tenere non tutti i nodi, ma solo i vicini, quindi hai un algoritmo, possibilmente efficiente, che dato un nodo x restituisca i vicini. Supponevo già evitassi di tenerti tutto in memoria, vabbé.

Beh per tenerti il percorso, hai proprio una mappa di in cui via via metti quelli che passi (ti basta solo il loro id), ricordando in questo caso che risalirci significa ripartire il percorso.

Adesso lascio libero sfogo alla mia fantasia (ehehe) e vediamo al visita. Sei al nodo X, devi vedere i nodi vicini (e li hai nella tua lista di adiacenza) e selezionare quelli che

1. potrebbero portarti nella direzione desiderata
2. almeno uno dei nodi adiacenti ti porta nella direzione desiderata (con priorità bassa rispetto al caso precedente).

Il punto è come fai a capire se prendere un nodo o no? Devi creare un intorno che consideri buono (es. un raggio di 1 km intorno alla latitudine desiderata, se il nodo casca li stai a cavallo). se non ne trovi allarga il raggio di ricerca, se ne trovi muoviti in quel senso (verso il più preciso).

Dovresti in questo modo ottenere qualcosa (tagli i nodi della direzione opposta ad esempio).
Hai ricerche continue, ma non cerchi in tutto il mondo, cerchi in sottoinsiemi che desumi piccoli del mondo.
Se poi hai strutturato bene la ogni nodo (e i suoi adiacenti) qualcoas dovresti ottenere (spero)
Non so se come idea ti è di aiuto, l'ho buttata li

Me nel mio algoritmo lavorando per vicini, ed avendo una funzione di costo che me li ordina come più probabili (in base a direzione e distanza) non vado in tutto il mondo, mi sposto sempre nella direzione di quel nodo. Se incontro un ostacolo è li che magari l'algoritmo un po' soffre perché deve capire come spostarsi ma supponendo di calcolare bene il costo dovrebbe sempre tentare di spostarsi in un nodo più vicino possibile e non in tutto il mondo.

Quello che mi sfugge è come dirgli se in questo percorso lmax (che decedenti con l'aggiunta di ogni nodo) è uguale a 0 allora torna indietro e considera gli altri. Sarà che mi è venuto un gran mal di testa a furia di sbatterci la testa oggi.

[valia]

e ti chiedo adesso, tu conosci il punto A (partenza) e il punto B (arrivo)? Corretto? bene, a grandi linee la direzione la conosci se fai un primo calcolo che so a risoluzione 50. Sai a grandi linee i punti verso cui ti muovi. Se la risoluzione è quella finisci, se in pratica è che so 80, parti dal path di alto livello (restringi il campo di azione) e vai via via a dettagliare ad un livello sottostante...ti sembra plausibile?
mi viene in mente googlemaps che parte a metà risoluzione di default

[Andrea1979]

domanda, da un punto a puoi andare a qualsiasi altro punto "vicino"?

Perché buttando qualche punto su un foglio, scegliendone 2:
- A = partenza
- B = arrivo


la cosa che mi viene in mente è - graficamente:
- "Rettifico" il percorso da A a B (ovvero li unisco con un segmento - o con l'ortodromia, ovvero l'arco di circonferenza massima per quei due punti)
- calcolo la distanza di tutti i punti, rispetto alla "rettificata".
- "ottimizzo" scegliendo solo quei punti la cui distanza dalla rettificata è minore o uguale a...
- su questi punti calcolo il percorso minimo.

[valia]

Originariamente inviato da Andrea1979
domanda, da un punto a puoi andare a qualsiasi altro punto "vicino"?

Perché buttando qualche punto su un foglio, scegliendone 2:
- A = partenza
- B = arrivo


la cosa che mi viene in mente è - graficamente:
- "Rettifico" il percorso da A a B (ovvero li unisco con un segmento - o con l'ortodromia, ovvero l'arco di circonferenza massima per quei due punti)
- calcolo la distanza di tutti i punti, rispetto alla "rettificata".
- "ottimizzo" scegliendo solo quei punti la cui distanza dalla rettificata è minore o uguale a...
- su questi punti calcolo il percorso minimo.

devo imparare a scrivere così, proprio questo che volevo fare però partendo da un percorso calcolato ad alto livello (che è rapido da calcolare)

[Pastore12]

Originariamente inviato da Andrea1979
domanda, da un punto a puoi andare a qualsiasi altro punto "vicino"?

Perché buttando qualche punto su un foglio, scegliendone 2:
- A = partenza
- B = arrivo


la cosa che mi viene in mente è - graficamente:
- "Rettifico" il percorso da A a B (ovvero li unisco con un segmento - o con l'ortodromia, ovvero l'arco di circonferenza massima per quei due punti)
- calcolo la distanza di tutti i punti, rispetto alla "rettificata".
- "ottimizzo" scegliendo solo quei punti la cui distanza dalla rettificata è minore o uguale a...
- su questi punti calcolo il percorso minimo.

Penso che occorra almeno un raffinamento, se la "rettificata" taglia una penisola (non so, A è nel Tirreno e B nell'Adriatico) l'ottimizzazione potrebbe non essere significativa oppure potrebbe tagliare fuori punti preziosi.

Partire da un percorso "calcolato ad alto livello", come dice valia, dovrebbe evitare questo problema.

[Neptune]

L'idea del tirare la linea potrebbe essere effettivamente utile per le rotte in alto mare, perché effettivamente una rotta lineare è sicuramente la più consigliabile. Anche se in realtà devo valutare nel costo anche le zone ad alto traffico.

Rimane comunque il problema di aggirare degli ostacoli. Cioè come fargli definire la rotta in caso deve passare in uno stretto o circumnavigare un isola.

Ad esempio a voler utilizzare qualcosa tipo visita in profondità dei grafi del tipo:

navigazione(partenza, rotta, lamx)
  se lmax > 0
     per ogni nodo adiacente a partenza partendo da quello con il costo minimo
         se il nodo è navigabile allora
             rotta = rotta + partenza;
             decrementa lmax
              navigazione(adiacente, rotta, lmax)

Incorrerei nei seguenti problemi:

- Se lmax in un percorso arriva a zero che faccio?
- Anche trovando un modo per ritornare indietro, come faccio poi ad imporgli di non rifare la stessa identica rotta?


Il mio codice attuale, e non funzionante, è attualmente questo qua: (giusto per farvi un idea).

	public ArrayList<Vertex> calcolo_rotta_ricorsiva(double lmax_attuale,ArrayList<Vertex> rotta)
	{
		ArrayList<Vertex> lista_nodi=null;
		int i;
		double lmax_i;
		if(lmax_attuale > 0 && flag==false)
		{
			i=0;
			lista_nodi=vicini_ordinati(rotta.get(rotta.size()-1),rotta);
			lmax_i = lmax_attuale - 1;
			System.out.println("lmax: "+lmax_i);
			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;
						
				}
				else 
				{
					if(lmax_i!=0)
						rotta.add(lista_nodi.get(i));
					rotta = calcolo_rotta_ricorsiva(lmax_i, rotta);
				}
				i++;
			}
			return rotta;
		}
		else if(flag == false)
		{
			if(!rotta.isEmpty())
				rotta.remove(rotta.size()-1);
				lmax_attuale++;
			System.out.println("rotta dopo rimozione: " + rotta);
		}
		return rotta;
	}

[valia]

hai presente come funziona google maps? se tu chiedi un percorso da A a B ti fissa un percorso a zoom che so 40 (quindi molto in alto). Fallo pure tu. Se vai a creare il percorso da A a B devi dettagliare quello, ma tu sai che hai un percorso da A a B, non so se mi hai seguito.
Se parti dalla linea retta, signfiica che sei in mare, ma già sai che sei in mare o devi calcolarlo? Se non ci fosse il limite della mappa sarebbe la soluzione ideale.

Poi se tu sai che un percorso esiste, hai una direzione (ovviamente), muoviti verso quella e non dovresti arrivare ad assurdi.
Se disgraziatamente non arrivi ad un intorno che so di 1 km, allarga un po (non troppo), entro un certo intervallo dovresti farcela.
Poi il valore di lmax non dovrebbe essere fisso, ma funzione dello zoom (più ad alto livello sei più "largo" è questo intervallo.

[Neptune]

Mi aiutae a capire cosa ce che non va in questo codice?

	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");
			}
		}
		if(flag == false)
		{
			for(int j=i; j>1; j--)
			{
				rotta.remove(rotta.size()-1);
				System.out.println("\n\n\nRIMOZIONE!\n\n\n");
			}
		}
		
		//rotta = new ArrayList<Vertex>();
		//rotta.add(nodo_partenza);

		return rotta;
	}

Mi da come output:

La rotta calcolata e: 
[ID:1 - 0.0%, ID:6 - 0.0%, ID:7 - 0.0%, ID:8 - 0.0%, ID:13 - 0.0%, ID:12 - 0.0%, ID:11 - 0.0%, ID:16 - 0.0%, ID:18 - 0.0%, ID:18 - 0.0%, ID:17 - 0.0%, ID:16 - 0.0%, ID:12 - 0.0%, ID:11 - 0.0%, ID:17 - 0.0%, ID:18 - 0.0%, ID:12 - 0.0%, ID:11 - 0.0%, ID:16 - 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%]

Quando invece dovrebbe essere:
1->2->3->4->5->10->15->20

La funzione "vicini_ordinati" praticamente mi da tutti i vicini di un nodo in ordine di costo inoltre se un vicino l'ho già visitato mi memorizzo in una lista "lmax" a cui l'ho visitato, ora solo se ci sono arrivato da un percorso più breve dovrebbe restituirmelo per evitare appunto che cicli sempre con gli stessi nodi.

Il problema credo che sia il fatto che se arrivo alla fine di un ramo (essendo una visita in profondità un po' modificata) e decide di tornare indietro dovrebbe rimuovermi tutti i nodi che ho fatto nel cammino, invece non lo fa. Probabilmente mi sto imputtanando con la ritorsione e necessito veramente di qualche consiglio per uscirne