[JavaScript] Calcola il percorso più breve tra due punti su una griglia

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:

In particolare voglio mettere in evidenza il metodo addVicino(nodo)

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:

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:

E naturalmente con un po’ di CSS:

E infine la pagina HTML per mettere il tutto insieme.

Vediamo infine un esempio funzionante del codice.

Rispondi

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.