Vediamo oggi come creare in JavaScript una griglia sulla quale posizionare due punti e trovare il percorso più breve evitando degli ostacoli.
A titolo di curiosità ho svolto un esercizio simile (ma senza l’uso di Nodi) in Python: [python] Esercizio su funzioni ricorsive e calcolo del percorso minore possibile
Il risultato che vogliamo ottenere sarà simile a questo (avere la possibilità di impostare una dimensione e il numero di ostacoli). Versione semplice:
Versione un po’ più complicata:
Questo esercizio è consultabile anche al seguente link.
Procediamo con ordine e andiamo anzitutto a creare una classe per gestire le singole celle e quelle ad esse collegate. Vogliamo creare un sistema collegato a nodi, che rappresenti la connessione tra tutte le celle. Definiamo perciò una classe nel modo seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
const CellaTipo = { Vuota: 0, Ostacolo: 1, Partenza: 2, Fine: 3, Percorso: 4 } class Cella { constructor(tipo = CellaTipo.Vuota) { this.tipo = tipo; this.vicini = []; this.coor = {r:null,c:null}; } addVicino(nodo) { if(!this.vicini.includes(nodo)) this.vicini.push(nodo); if(!nodo.vicini.includes(this)) nodo.vicini.push(this); } setCoor(r,c) { this.coor.r = r; this.coor.c = c; return this; } } |
In particolare voglio mettere in evidenza il metodo addVicino(nodo)
|
1 2 3 4 5 6 |
addVicino(nodo) { if(!this.vicini.includes(nodo)) this.vicini.push(nodo); if(!nodo.vicini.includes(this)) nodo.vicini.push(this); } |
Vogliamo che ogni nodo sia interconnesso con il proprio vicino, quindi se abbiamo due nodi A e B allora A avrà nei vicini B e B avrà nei vicini A.
Costruiamo adesso la classe che creerà la mappa. Nel codice ho inserito i commenti ai vari metodi:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 |
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()); } } } } } |
In particolare vorrei soffermarmi sul controllo dei vicini con il metodo nMaxVicini(nodo,percorso)
Durante la ricerca del percorso voglio evitare tutti quei percorsi che si annodano a serpentina, perché tanto non sarebbero mai il percorso migliore. Se un percorso è così annodato, significa che esiste un nodo che ha almeno 3 vicini, durante la costruzione almeno 2 (ricordiamoci che il nodo successivo non è stato ancora aggiunto). Quindi ogni nodo, durante la costruzione, non deve avere più di un vicino.
Completiamo il tutto con la creazione della griglia vera e propria:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
var mappa = null; function avvioMappa(d, o) { mappa = new Mappa(d, o); $('#griglia').html(""); $('#griglia').css("width",(d*52)+"px"); $('#griglia').css("height",(d*52)+"px"); for(var r = 0; r < d; r++ ) { for(var c = 0; c < d; c++ ) { var cont = mappa.getNodo(r,c).tipo == CellaTipo.Ostacolo ? "X" : " "; $('#griglia').append('<div class="cella'+(cont=="X"?" ostacolo":"")+'" data-row="'+r+'" data-col="'+c+'">'+cont+'</div>'); } } $('.cella').unbind(); $('.cella').click(function() { var r = parseInt($(this).attr("data-row")); var c = parseInt($(this).attr("data-col")); if( !mappa.hasPartenza() ) { if( !mappa.setPartenza(r,c) ) alert("casella non valida"); else $(this).html("A").css("color","red"); } else { if( !mappa.setFine(r,c) ) alert("casella non valida"); else $(this).html("B").css("color","green"); } }); $('#trova').unbind(); $('#trova').click(function(){ if( mappa.hasFine() ) { mappa.calcolaPercorso(); if( mappa.shortest.length > 0 ) { for(var i = 0; i < mappa.shortest.length; i++ ) { var r = mappa.shortest[i].coor.r; var c = mappa.shortest[i].coor.c; if( mappa.shortest[i].tipo == CellaTipo.Vuota ) $('.cella[data-row='+r+'][data-col='+c+']').html("•").css("color","blue"); } } else { alert("Impossibile trovare percorso!"); } } else { alert("Imposta percorso!"); } }); } $(document).ready(function(){ $('#mostra').click(function(){ var dim = parseInt($('#dimensione').val()); var ost = parseInt($('#ostacoli').val()); if( dim > 1 && ost >= 0 && ost <= dim * dim ) { avvioMappa(dim, ost); } else { alert("Valori non validi!"); } }); }); |
E naturalmente con un po’ di CSS:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#griglia { width: 520px; height: 520px; display: flex; flex-wrap: wrap; margin-top: 12px; } .cella { width: 50px; height: 50px; line-height: 50px; border: 1px solid #333; text-align: center; font-family: Verdana; font-size: 32px; cursor: pointer; } .ostacolo { background-color: #f00; } |
E infine la pagina HTML per mettere il tutto insieme.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
<html> <head> <title>Calcolo del percorso</title> <link href="percorso.css" rel="stylesheet"> </head> <body> <input type="text" id="dimensione" value="10" placeholder="dimensione"> <input type="text" id="ostacoli" value="10" placeholder="n. ostacoli"> <button type="button" id="mostra">Mostra griglia</button> <button type="button" id="trova">Trova percorso</button> <div id="griglia"></div> </body> <script src="jquery-3.6.1.min.js"></script> <script src="percorso.js"></script> <script src="main.js"></script> </html> |
Vediamo infine un esempio funzionante del codice.