class Mappa {
/*
COSTRUTTORE: Di predefinito partiamo con 10 x 10 come dimensione della mappa e con un numero di ostacoli da definire (poi metteremo anche quello a 10)
*/
constructor(n = 10,ostacoli) {
this.nodi = [];
this.n = n;
this.inizio = null;
this.fine = null;
this.setOstacoli(ostacoli);
this.costruisciMappa();
this.costruisciOstacoli();
}
/*
COSTRUIAMO LA MAPPA: Noi sappiamo che la mappa è una griglia quadrata limitata, dove gli spostamenti possibili sono solo in verticale e orizzontale, non è possibile spostarsi in diagonale.
NB: I nodi li mettiamo in una lista di nodi unidimensionale, rispetto alla mappa bidimensionale
*/
costruisciMappa() {
this.nodi = [];
for(var r = 0; r < this.n; r++ ) {
for(var c = 0; c < this.n; c++ ) {
// qui convertiamo le coordinate in una sola dimensione
var posCorr = r * this.n + c;
// aggiungiamo il nodo
this.nodi.push((new Cella()).setCoor(r,c));
if( c > 0 ) {
// colleghiamo subito il nodo con quelli appena precedenti
this.nodi[posCorr].addVicino(this.nodi[posCorr-1]);
}
if( r > 0 ) {
// colleghiamo subito il nodo con quelli soprastanti
this.nodi[posCorr].addVicino(this.nodi[posCorr-this.n]);
}
}
}
}
// impostiamo il numero di ostacoli
setOstacoli(ostacoli) {
this.ostacoli = ostacoli;
}
// creiamo gli ostacoli con una funzione casuale
costruisciOstacoli() {
var o = 0;
while(o < this.ostacoli) {
// troviamo una posizione casuale all'interno della lista dei nodi
var pos = Math.round((this.n*this.n-1)*Math.random());
// nel caso in cui la cella sia vuota
if( this.nodi[pos].tipo == CellaTipo.Vuota ) {
// impostiamo l'ostacolo
this.nodi[pos].tipo = CellaTipo.Ostacolo;
o++;
}
}
}
hasPartenza() {
return this.inizio != null;
}
hasFine() {
return this.fine != null;
}
getNodo(r,c) {
var pos = r * this.n + c;
return this.nodi[pos];
}
// impostiamo la partenza
setPartenza(r,c) {
if( this.inizio != null ) return false;
var pos = r * this.n + c;
if( this.nodi[pos].tipo == CellaTipo.Vuota ) {
this.nodi[pos].tipo = CellaTipo.Partenza;
this.inizio = pos;
return true;
}
return false;
}
// impostiamo la fine
setFine(r,c) {
if( this.fine != null ) return false;
var pos = r * this.n + c;
if( this.nodi[pos].tipo == CellaTipo.Vuota ) {
this.nodi[pos].tipo = CellaTipo.Fine;
this.fine = pos;
return true;
}
return false;
}
// calcoliamo il percorso, facendo anche un po' di statistiche
calcolaPercorso() {
if( this.inizio != null && this.fine != null ) {
this.percorsi = [];
this.shortest = [];
this.maxlen = null;
this.scartati_lung = 0;
this.scartati_vici = 0;
this.tstart = new Date();
this.calcolo(this.nodi[this.inizio],[]);
this.tend = new Date();
console.log("Tempo di calcolo: "+Math.round((this.tend-this.tstart))+"ms, Scartati troppo lunghi: "+this.scartati_lung+", Scartati per vicini: "+this.scartati_vici);
}
return null;
}
// controlliamo che il percorso non curvi inutilmente, in base al numero di vicini prossimi ad ogni nodo
nMaxVicini(nodo,percorso) {
var vicini = 0;
for(var i = 0; i < percorso.length; i++ ) {
if(nodo.vicini.includes(percorso[i])) vicini++;
}
return vicini;
}
/*
CALCOLO: qui calcoliamo il percorso a partire da un nodo dato in poi, spostandoci su ogni vicino del nodo, finché non troviamo il nodo finale
*/
calcolo(nodo,percorso) {
// se la lunghezza del percorso attuale supera il percorso dalla lunghezza minima trovato, allora interrompiamo la funzione ricorsiva
if( this.maxlen != null && percorso.length >= this.maxlen )
{
this.scartati_lung++;
return;
}
// se il nodo non è già contenuto nel percorso, aggiungiamolo
if( !percorso.includes(nodo) ) {
// se il numero di vicini è maggiore di 2 interrompiamo il calcolo
if( this.nMaxVicini(nodo,percorso) > 2 ) {
this.scartati_vici++;
return;
}
percorso.push(nodo);
// proseguiamo su ogni vicino del nodo
for(var i = 0; i < nodo.vicini.length; i++ ) {
if( nodo.vicini[i].tipo == CellaTipo.Fine ) {
// abbiamo trovato un percorso
percorso.push(nodo.vicini[i]);
var len = percorso.length;
if( len < this.maxlen || this.maxlen == null ) {
this.maxlen = len;
this.shortest = percorso.slice();
}
this.percorsi.push(percorso.slice());
}
if( nodo.vicini[i].tipo == CellaTipo.Vuota ) {
this.calcolo(nodo.vicini[i],percorso.slice());
}
}
}
}
}
