[PGI-Bis]

Forse non ti serve. Dall'altro post mi sembra di capire che tu abbia una mappa divisa in quadranti. Se è così allora il passaggio da un nodo ad un altro ha lo stesso costo quindi la scansione in ampiezza ti darebbe lo stesso risultato dell'A*. In ogni caso l'A* è una scansione in ampiezza mitigata dalla distanza variabile quindi fai presto a passare all'altro.

Nota che sia l'A* che il breadth first ti danno il percorso di lunghezza minima, con la differenza che l'A* ti permette di specificare il significato di "lunghezza".

Per un'implementazione del breadth-first ti serve una classe Nodo con un campo "precedente".

class Nodo {
    Nodo precedente;
}

Il campo precedente lo usi per ricostruire il percorso una volta che, attraverso la scansione, scopri di essere arrivato a destinazione.

Servono poi tutti i nodi adiacenti ad un Nodo. Serve cioè che da qualche parte ci sia un metodo:

List<Nodo> getNodiAdiacentiA(Nodo n) {...}

In base a cosa determini chi siano gli adiacenti di un Nodo n dipende dalla tua mappa. Nei giochi la mappa è statica, cioè i Nodo sono:

class Nodo {
    Nodo precedente;
    List<Nodo> adiacenti = ...
}

Ma in realtà è irrilevante che un Nodo sappia chi sono i suoi vicini, possono tranquillamente essere determinati esternamente - purchè siano costanti.

Per poter identificare le adiacenze di un Nodo con ogni probabilità tu avrai bisogno di inserire in Nodo qualche altra informazione, ad esempio le sue coordinate, quindi il tuo Nodo potrebbe essere:

class Nodo {
    Nodo precedente;
    Vertex coordinate;

    Nodo(Vertex coordinate) {
        this.coordinate = coordinate;
    }
}

A conti fatti il tuo Nodo altro non sarebbe che una decorazione di Vertex fatta perchè Vertex abbia il campo precedente. Potresti anche non usare Nodo e affidarti ad una HashMap per gestire l'associazione Vertex-Vertex precedente.

Comunque, una volta che hai il Nodo e il metodo esterno List<Nodo> getNodiAdiacenti(Nodo), la scansione è banale e procede un po' come l'onda formata da un sasso gettato in uno stagno: parti da un punto e procedi guardando intorno a quel punto, poi intorno alle adiacenze di quel punto, alle adiacenze delle adiacenze... e così via finchè l'onda non becca la destinazione.

Usi una lista per i nodi da visitare e una lista per i nodi già visitati. La seconda ti serve per evitare i cicli che si verificherebbero nel caso in cui due nodi avessero un adiacenza comune:

Nodo trova(Nodo partenza, Nodo arrivo) {
   List<Nodo> visitati = new LinkedList<Nodo>();
   List<Nodo> daVisitare = new LinkedList<Nodo>();
   visitati.add(partenza);

   while(!visitati.isEmpty()) {
      Nodo nodo = visitati.removeFirst();
      if(nodo == arrivo) {
         return nodo;
      } else {
         visitati.add(nodo);
         List<Nodo> adiacenti = getNodiAdiacentiA(nodo);
         for(Nodo a : adiacenti) {
            if(!visitati.contains(a) && !daVisitare.contains(a)) {
               //cioè è la prima volta che "vedo" a
               a.precedente = nodo;
               daVisitare.add(a);
            }
         }
      }
   }
   return null;
}

Se il risultato di trovaPercorso è diverso da null allora il Nodo restituito (la destinazione) ha come precedente il "passo" che viene prima di lui nel percorso. Il precedente avrà come precedente il passo... che l'ha preceduto e così via.

Puoi ricostruire il percorso come lista di nodi semplicemente aggiungendo ad una pila il precedente del precedente finchè questo esiste.

List<Nodo> creaPercorso(Nodo n) {
    List<Nodo> percorso = new LinkedList<Nodo>();
    while(n.precedente != null) {
        percorso.push(n);
        n = n.precedente;
    }
    return percorso;
}

Non ho provato il codice quindi è "pseudo". Fai riferimento al capitolo di quel libro per averlo esatto.

L'A* è praticamente uguale solo che la condizione di inserimento nella lista dei nodi da visitare dipende anche dalla distanza.