[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.