Implementazione di A * Pathfinding in Java

1. Introduzione

Gli algoritmi di pathfinding sono tecniche per la navigazione delle mappe , che ci consentono di trovare un percorso tra due punti diversi. Diversi algoritmi hanno diversi pro e contro, spesso in termini di efficienza dell'algoritmo e dell'efficienza del percorso che genera.

2. Che cos'è un algoritmo di individuazione del percorso?

Un Pathfinding Algorithm è una tecnica per convertire un grafico, costituito da nodi e bordi, in un percorso attraverso il grafico . Questo grafico può essere qualsiasi cosa che debba essere attraversata. Per questo articolo, tenteremo di attraversare una parte del sistema della metropolitana di Londra:

("London Underground Overground DLR Crossrail map" di sameboat è concesso in licenza con CC BY-SA 4.0)

Questo ha molti componenti interessanti:

  • Possiamo o meno avere un percorso diretto tra i nostri punti di partenza e di arrivo. Ad esempio, possiamo andare direttamente da "Earl's Court" a "Monument", ma non ad "Angel".
  • Ogni singolo passaggio ha un costo particolare. Nel nostro caso, questa è la distanza tra le stazioni.
  • Ogni fermata è collegata solo a un piccolo sottoinsieme delle altre fermate. Ad esempio, "Regent's Park" è direttamente collegato solo a "Baker Street" e "Oxford Circus".

Tutti gli algoritmi di pathfinding prendono come input una raccolta di tutti i nodi - nel nostro caso le stazioni - e le connessioni tra loro, e anche i punti di inizio e fine desiderati. L'output è tipicamente l'insieme di nodi che ci porterà dall'inizio alla fine, nell'ordine in cui dobbiamo andare .

3. Che cos'è A *?

A * è uno specifico algoritmo di pathfinding , pubblicato per la prima volta nel 1968 da Peter Hart, Nils Nilsson e Bertram Raphael. È generalmente considerato il miglior algoritmo da utilizzare quando non è possibile pre-calcolare le rotte e non ci sono vincoli sull'utilizzo della memoria .

Sia la complessità della memoria che quella delle prestazioni possono essere O (b ^ d) nel peggiore dei casi, quindi mentre risolverà sempre il percorso più efficiente, non è sempre il modo più efficiente per farlo.

Un * è in realtà una variazione dell'algoritmo di Dijkstra, dove sono fornite informazioni aggiuntive per aiutare a selezionare il nodo successivo da utilizzare. Non è necessario che queste informazioni aggiuntive siano perfette: se disponiamo già di informazioni perfette, la ricerca del percorso è inutile. Ma meglio è, migliore sarà il risultato finale.

4. Come funziona A *?

L'algoritmo A * funziona selezionando in modo iterativo qual è il percorso migliore fino ad ora e tentando di vedere qual è il miglior passo successivo.

Quando lavoriamo con questo algoritmo, abbiamo diversi dati di cui dobbiamo tenere traccia. L '"insieme aperto" è tutti i nodi che stiamo attualmente considerando. Non si tratta di tutti i nodi del sistema, ma di tutti i nodi da cui potremmo eseguire il passaggio successivo.

Terremo anche traccia del miglior punteggio corrente, del punteggio totale stimato e del miglior nodo precedente corrente per ogni nodo nel sistema.

Come parte di questo, dobbiamo essere in grado di calcolare due punteggi diversi. Uno è il punteggio da ottenere da un nodo all'altro. Il secondo è un'euristica per fornire una stima del costo da qualsiasi nodo alla destinazione. Questa stima non deve essere accurata, ma una maggiore accuratezza produrrà risultati migliori. L'unico requisito è che entrambi i punteggi siano coerenti tra loro, ovvero che siano nelle stesse unità.

All'inizio, il nostro set aperto è costituito dal nostro nodo iniziale e non abbiamo alcuna informazione su nessun altro nodo.

Ad ogni iterazione, faremo:

  • Seleziona il nodo dal nostro set aperto che ha il punteggio totale stimato più basso
  • Rimuovi questo nodo dall'insieme aperto
  • Aggiungi al set aperto tutti i nodi che possiamo raggiungere da esso

Quando lo facciamo, elaboriamo anche il nuovo punteggio da questo nodo a ogni nuovo per vedere se si tratta di un miglioramento rispetto a quello che abbiamo ottenuto finora, e se lo è, allora aggiorniamo ciò che sappiamo su quel nodo.

Questo quindi si ripete fino a quando il nodo nel nostro set aperto che ha il punteggio totale stimato più basso è la nostra destinazione, a quel punto abbiamo il nostro percorso.

4.1. Esempio lavorato

Ad esempio, partiamo da "Marylebone" e cerchiamo di trovare la strada per "Bond Street".

All'inizio, il nostro set aperto consiste solo di "Marylebone" . Ciò significa che questo è implicitamente il nodo per cui abbiamo ottenuto il miglior "punteggio totale stimato".

Le nostre prossime tappe possono essere "Edgware Road", con un costo di 0,4403 km, o "Baker Street", con un costo di 0,4153 km. Tuttavia, "Edgware Road" è nella direzione sbagliata, quindi la nostra euristica da qui alla destinazione fornisce un punteggio di 1,4284 km, mentre "Baker Street" ha un punteggio euristico di 1,0753 km.

Ciò significa che dopo questa iterazione il nostro set aperto è composto da due voci: "Edgware Road", con un punteggio totale stimato di 1,8687 km, e "Baker Street", con un punteggio totale stimato di 1,4906 km.

La nostra seconda iterazione inizierà quindi da "Baker Street", poiché questo ha il punteggio totale stimato più basso. Da qui, le nostre prossime tappe possono essere "Marylebone", "St. John's Wood "," Great Portland Street ", Regent's Park" o "Bond Street".

Non lavoreremo su tutto questo, ma prendiamo "Marylebone" come un esempio interessante. Il costo per arrivarci è di nuovo 0,4153 km, ma questo significa che il costo totale ora è 0,8306 km. Inoltre, l'euristica da qui alla destinazione dà un punteggio di 1,323 km.

Ciò significa che il punteggio totale stimato sarebbe 2,1536 km, che è peggiore del punteggio precedente per questo nodo. Questo ha senso perché abbiamo dovuto fare del lavoro extra per non arrivare da nessuna parte in questo caso. Ciò significa che non lo considereremo un percorso percorribile. In quanto tali, i dettagli per "Marylebone" non vengono aggiornati e non vengono aggiunti nuovamente al set aperto.

5. Implementazione Java

Ora che abbiamo discusso di come funziona, implementiamolo effettivamente. Costruiremo una soluzione generica e poi implementeremo il codice necessario affinché funzioni per la metropolitana di Londra. Possiamo quindi usarlo per altri scenari implementando solo quelle parti specifiche.

5.1. Rappresentare il grafico

In primo luogo, dobbiamo essere in grado di rappresentare il nostro grafico che desideriamo attraversare. Si compone di due classi: i singoli nodi e quindi il grafico nel suo insieme.

Rappresenteremo i nostri singoli nodi con un'interfaccia chiamata GraphNode :

public interface GraphNode { String getId(); }

Ciascuno dei nostri nodi deve avere un ID. Qualsiasi altra cosa è specifica per questo particolare grafico e non è necessaria per la soluzione generale. Queste classi sono semplici Java Beans senza logica speciale.

Our overall graph is then represented by a class simply called Graph:

public class Graph { private final Set nodes; private final Map
    
      connections; public T getNode(String id) { return nodes.stream() .filter(node -> node.getId().equals(id)) .findFirst() .orElseThrow(() -> new IllegalArgumentException("No node found with ID")); } public Set getConnections(T node) { return connections.get(node.getId()).stream() .map(this::getNode) .collect(Collectors.toSet()); } }
    

This stores all of the nodes in our graph and has knowledge of which nodes connect to which. We can then get any node by ID, or all of the nodes connected to a given node.

At this point, we're capable of representing any form of graph we wish, with any number of edges between any number of nodes.

5.2. Steps on Our Route

The next thing we need is our mechanism for finding routes through the graph.

The first part of this is some way to generate a score between any two nodes. We'll the Scorer interface for both the score to the next node and the estimate to the destination:

public interface Scorer { double computeCost(T from, T to); }

Given a start and an end node, we then get a score for traveling between them.

We also need a wrapper around our nodes that carries some extra information. Instead of being a GraphNode, this is a RouteNode – because it's a node in our computed route instead of one in the entire graph:

class RouteNode implements Comparable { private final T current; private T previous; private double routeScore; private double estimatedScore; RouteNode(T current) { this(current, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode(T current, T previous, double routeScore, double estimatedScore) { this.current = current; this.previous = previous; this.routeScore = routeScore; this.estimatedScore = estimatedScore; } }

As with GraphNode, these are simple Java Beans used to store the current state of each node for the current route computation. We've given this a simple constructor for the common case, when we're first visiting a node and have no additional information about it yet.

These also need to be Comparable though, so that we can order them by the estimated score as part of the algorithm. This means the addition of a compareTo() method to fulfill the requirements of the Comparable interface:

@Override public int compareTo(RouteNode other) { if (this.estimatedScore > other.estimatedScore) { return 1; } else if (this.estimatedScore < other.estimatedScore) { return -1; } else { return 0; } }

5.3. Finding Our Route

Now we're in a position to actually generate our routes across our graph. This will be a class called RouteFinder:

public class RouteFinder { private final Graph graph; private final Scorer nextNodeScorer; private final Scorer targetScorer; public List findRoute(T from, T to) { throw new IllegalStateException("No route found"); } }

We have the graph that we are finding the routes across, and our two scorers – one for the exact score for the next node, and one for the estimated score to our destination. We've also got a method that will take a start and end node and compute the best route between the two.

This method is to be our A* algorithm. All the rest of our code goes inside this method.

We start with some basic setup – our “open set” of nodes that we can consider as the next step, and a map of every node that we've visited so far and what we know about it:

Queue openSet = new PriorityQueue(); Map
    
      allNodes = new HashMap(); RouteNode start = new RouteNode(from, null, 0d, targetScorer.computeCost(from, to)); openSet.add(start); allNodes.put(from, start);
    

Our open set initially has a single node – our start point. There is no previous node for this, there's a score of 0 to get there, and we've got an estimate of how far it is from our destination.

The use of a PriorityQueue for the open set means that we automatically get the best entry off of it, based on our compareTo() method from earlier.

Now we iterate until either we run out of nodes to look at, or the best available node is our destination:

while (!openSet.isEmpty()) { RouteNode next = openSet.poll(); if (next.getCurrent().equals(to)) { List route = new ArrayList(); RouteNode current = next; do { route.add(0, current.getCurrent()); current = allNodes.get(current.getPrevious()); } while (current != null); return route; } // ...

When we've found our destination, we can build our route by repeatedly looking at the previous node until we reach our starting point.

Next, if we haven't reached our destination, we can work out what to do next:

 graph.getConnections(next.getCurrent()).forEach(connection -> { RouteNode nextNode = allNodes.getOrDefault(connection, new RouteNode(connection)); allNodes.put(connection, nextNode);   double newScore = next.getRouteScore() + nextNodeScorer.computeCost(next.getCurrent(), connection); if (newScore < nextNode.getRouteScore()) { nextNode.setPrevious(next.getCurrent()); nextNode.setRouteScore(newScore); nextNode.setEstimatedScore(newScore + targetScorer.computeCost(connection, to)); openSet.add(nextNode); } }); throw new IllegalStateException("No route found"); }

Here, we're iterating over the connected nodes from our graph. For each of these, we get the RouteNode that we have for it – creating a new one if needed.

We then compute the new score for this node and see if it's cheaper than what we had so far. If it is then we update it to match this new route and add it to the open set for consideration next time around.

This is the entire algorithm. We keep repeating this until we either reach our goal or fail to get there.

5.4. Specific Details for the London Underground

What we have so far is a generic A* pathfinder, but it's lacking the specifics we need for our exact use case. This means we need a concrete implementation of both GraphNode and Scorer.

Our nodes are stations on the underground, and we'll model them with the Station class:

public class Station implements GraphNode { private final String id; private final String name; private final double latitude; private final double longitude; }

The name is useful for seeing the output, and the latitude and longitude are for our scoring.

In this scenario, we only need a single implementation of Scorer. We're going to use the Haversine formula for this, to compute the straight-line distance between two pairs of latitude/longitude:

public class HaversineScorer implements Scorer { @Override public double computeCost(Station from, Station to) { double R = 6372.8; // Earth's Radius, in kilometers double dLat = Math.toRadians(to.getLatitude() - from.getLatitude()); double dLon = Math.toRadians(to.getLongitude() - from.getLongitude()); double lat1 = Math.toRadians(from.getLatitude()); double lat2 = Math.toRadians(to.getLatitude()); double a = Math.pow(Math.sin(dLat / 2),2) + Math.pow(Math.sin(dLon / 2),2) * Math.cos(lat1) * Math.cos(lat2); double c = 2 * Math.asin(Math.sqrt(a)); return R * c; } }

We now have almost everything necessary to calculate paths between any two pairs of stations. The only thing missing is the graph of connections between them. This is available in GitHub.

Let's use it for mapping out a route. We'll generate one from Earl's Court up to Angel. This has a number of different options for travel, on a minimum of two tube lines:

public void findRoute() { List route = routeFinder.findRoute(underground.getNode("74"), underground.getNode("7")); System.out.println(route.stream().map(Station::getName).collect(Collectors.toList())); }

This generates a route of Earl's Court -> South Kensington -> Green Park -> Euston -> Angel.

The obvious route that many people would have taken would likely be Earl's Count -> Monument -> Angel, because that's got fewer changes. Instead, this has taken a significantly more direct route even though it meant more changes.

6. Conclusion

In questo articolo, abbiamo visto cos'è l'algoritmo A *, come funziona e come implementarlo nei nostri progetti. Perché non prenderlo ed estenderlo per i tuoi usi?

Forse provare ad estenderlo per tenere conto degli interscambi tra le linee della metropolitana e vedere come questo influisce sui percorsi selezionati?

E ancora, il codice completo dell'articolo è disponibile su GitHub.