A* (A-star) Algorithmus Optimierung
Ich bin ein student und ich und mein team haben, um eine simulation des Schülers Verhalten in einem campus (wie "Freunde") gehen, etc. Für die Suche nach Pfad, der Schüler hat zu gehen, ich verwendete A* - Algorithmus (wie ich fand heraus, dass seine einer der am schnellsten Pfad zu finden-algorithmen). Leider ist unsere simulation läuft nicht flüssig (es dauert wie 1-2 Sek. zwischen aufeinander folgenden Iterationen). Ich wollte zu optimieren, den Algorithmus, aber ich habe keine Ahnung was ich mehr tun kann. Können Sie mir helfen, die Jungs und teilen Sie mit mir Informationen, wenn die Möglichkeit zur Optimierung meiner A* - Algorithmus? Hier geht code:
public LinkedList<Field> getPath(Field start, Field exit) {
LinkedList<Field> foundPath = new LinkedList<Field>();
LinkedList<Field> opensList= new LinkedList<Field>();
LinkedList<Field> closedList= new LinkedList<Field>();
Hashtable<Field, Integer> gscore = new Hashtable<Field, Integer>();
Hashtable<Field, Field> cameFrom = new Hashtable<Field, Field>();
Field x = new Field();
gscore.put(start, 0);
opensList.add(start);
while(!opensList.isEmpty()){
int min = -1;
//searching for minimal F score
for(Field f : opensList){
if(min==-1){
min = gscore.get(f)+getH(f,exit);
x = f;
}else{
int currf = gscore.get(f)+getH(f,exit);
if(min > currf){
min = currf;
x = f;
}
}
}
if(x == exit){
//path reconstruction
Field curr = exit;
while(curr != start){
foundPath.addFirst(curr);
curr = cameFrom.get(curr);
}
return foundPath;
}
opensList.remove(x);
closedList.add(x);
for(Field y : x.getNeighbourhood()){
if(!(y.getType()==FieldTypes.PAVEMENT ||y.getType() == FieldTypes.GRASS) || closedList.contains(y) || !(y.getStudent()==null))
{
continue;
}
int tentGScore = gscore.get(x) + getDist(x,y);
boolean distIsBetter = false;
if(!opensList.contains(y)){
opensList.add(y);
distIsBetter = true;
}else if(tentGScore < gscore.get(y)){
distIsBetter = true;
}
if(distIsBetter){
cameFrom.put(y, x);
gscore.put(y, tentGScore);
}
}
}
return foundPath;
}
private int getH(Field start, Field end){
int x;
int y;
x = start.getX()-end.getX();
y = start.getY() - end.getY();
if(x<0){
x = x* (-1);
}
if(y<0){
y = y * (-1);
}
return x+y;
}
private int getDist(Field start, Field end){
int ret = 0;
if(end.getType() == FieldTypes.PAVEMENT){
ret = 8;
}else if(start.getX() == end.getX() || start.getY() == end.getY()){
ret = 10;
}else{
ret = 14;
}
return ret;
}
//EDIT
Dies ist, was ich von jProfiler:
So getH ist ein bottlneck ja? Vielleicht erinnern H-score von-Feld wäre eine gute Idee?
Sollten Sie erwägen, die Verwendung UnitTest zu verifiy alles funktioniert, vor der Optimierung. Ich denke, dein code hat >1 Fehler, in getDist(..) ->
start.getX() == end.getY()
sollte es sein start.getY()
?Ich werde versuchen, einen profiler verwenden, aber ich muss lernen, wie es zu benutzen, aber ich werde resoults als ich einige bekommen, danke für die Idee :).
Ja, du hast Recht, mein Fehler. Ich war testalgorithmus und es war mir gut resoults, aber jetzt sehe ich, ich habe zu prüfen, ob alles wieder ok ist, danke 🙂
java-performance.info/java-collections-overview diese Seite kann Ihnen helfen, zu wählen, effektiver Sammlungen, aber wie die anderen traurig, die Sie finden, müssen Sie den Engpass ersten
InformationsquelleAutor Bartosz Wyględacz | 2014-01-16
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einer verknüpften Liste ist nicht eine gute Datenstruktur für die open set. Sie haben, um den Knoten mit dem kleinsten F aus, können Sie entweder die Suche durch die Liste in O(n) oder legen Sie Sie in position sortiert in O(n), so oder so ist es O(n). Mit einem heap es ist nur O(log n). Aktualisierung des G-score bleiben würde O(n) (da müssen Sie den Knoten finden, der erste), es sei denn, Sie hat auch Hinzugefügt, eine Hash-Tabelle von Knoten in Indizes der heap.
Verlinkte Liste ist auch nicht eine gute Datenstruktur für die geschlossene Gruppe, wo Sie Sie brauchen, schnell "Enthält", die O(n) in einer verknüpften Liste. Sollten Sie ein HashSet.
Ich empfehle die Verwendung min-priority-queue für die Daten-Struktur. Es hilft mir, es zu beschleunigen Algorithmus zu 6X.
InformationsquelleAutor harold
Optimieren Sie das problem durch die Verwendung eines anderen Algorithmus, der folgenden Seite veranschaulicht und vergleicht viele verschiedene aglorihms und Heuristiken:
http://qiao.github.io/PathFinding.js/visual/
InformationsquelleAutor Chriss
Aus Ihrer Umsetzung es scheint, dass Sie mit naive A* - Algorithmus. Verwenden Sie folgenden Weg:-
Ich nicht denke, es ist eine Notwendigkeit für Rückverfolgung, weil hier Ein* berücksichtigt alle Möglichkeiten zur gleichen Zeit, wenn Sie eine Sackgasse erreichen Sie können immer einen anderen offenen Knoten in der Warteschlange.
Aber die anderen Knoten? Wie weit in die Tiefe tun brauchen, um sich in die Warteschlange für das finden eines geeigneten Knoten?
Sie brauchen nur zu Holen Sie sich die nächst beste Knoten aus der queue und weiter. Es ist kein backtracking erforderlich. Hier ist die wiki-Seite mit einem pseudo-code, wo Sie sehen können, es gibt kein backtracking verwendet -en.wikipedia.org/wiki/A*_search_algorithm
InformationsquelleAutor Vikram Bhat
Mehr RAM zuweisen
Es ist eine gute Idee dabei ist, jedem Schüler, der in ThreadPool
InformationsquelleAutor Igor S.
a) Wie bereits erwähnt, sollten Sie verwenden einen heap in Eine* - entweder eine grundlegende Binär-heap oder einen pairing-heap, die sollte theoretisch schneller.
b) In größeren maps kommt es immer wieder vor, dass Sie einige Zeit brauchen, für die der Algorithmus ausgeführt wird (D. H., wenn Sie einen Pfad, es wird einfach einige Zeit dauern). Was getan werden kann, ist die Nutzung von einigen lokalen navigation-Algorithmus (z.B. "führen Sie direkt zum Ziel"), während der Pfad berechnet.
c) Wenn Sie eine angemessene Menge von Orten (z.B. in ein navmesh) und einige Zeit, am Anfang des Codes, warum nicht verwenden Floyd-Warshall-Algorithmus? Mit, dass, können Sie die Informationen, wohin Sie gehen als Nächstes in O(1).
InformationsquelleAutor JakubT
Baute ich eine neue pathfinding-Algorithmus. rief Schnell* oder Fastaer, Es ist ein BFS wie A*, aber ist schneller und effizienter als Eine*, die Genauigkeit ist zu 90% Ein*. bitte Lesen Sie diesen link zur info und demo.
https://drbendanilloportfolio.wordpress.com/2015/08/14/fastaer-pathfinder/
Es hat eine schnelle gierig line tracer, um Weg gerader.
Die demo-Datei hat es in sich. Überprüfen Sie den Task-manager, wenn Sie die demo für performance-Metriken. So weit nach Gebäude dieser die die profiler-Ergebnisse dieses hat eine maximale überlebenden generation von 4 und geringer bis null-GC-Zeit.
InformationsquelleAutor D.R.Bendanillo