A* funktioniert, aber zu langsam

[Opi3]

Hallo,
für ein Spiel brauche ich irgendein Algo fürs Pathfinding.
Ich habe mich führ A* entschieden und ihn umgesetzt.:rtfm:

Leider, lässt er, in Hinsicht auf die Geschwindigkeit stark zu wünschen übrig:

	public List<Point> search() {

		if (start == null || ziel == null) {
			return null;
		}

		clearNodes();
		ArrayList<Knoten> openList = new ArrayList<Knoten>();

		openList.add(start);
		start.G = 1;
		start.setH(ziel);
		start.setF();
		start.last = null;
		Boolean zielGefunden = false;
		while (!zielGefunden) {
			if (openList.isEmpty()) {
				return null;
			}
			Collections.sort(openList);
			Knoten base = openList.get(0);
			openList.remove(base);
			base.flag = Knoten.IS_CLOSED_LIST;
			if (checkKnoten(base.x - 1, base.y, base, openList)) {
				zielGefunden = true;
			}
			if (checkKnoten(base.x + 1, base.y, base, openList)) {
				zielGefunden = true;
			}
			if (checkKnoten(base.x, base.y - 1, base, openList)) {
				zielGefunden = true;
			}
			if (checkKnoten(base.x, base.y + 1, base, openList)) {
				zielGefunden = true;
			}

		}
		ArrayList<Point> path = new ArrayList<Point>();
		Knoten base = ziel;
		path.add(ziel.point);
		while (true) {
			base = base.last;
			if (base == null) {
				break;
			}
			path.add(base.point);
		}
		return path;
	}

	private boolean checkKnoten(int _x, int _y, Knoten base,
			ArrayList<Knoten> openList) {
		if ((_x >= 0 && _x < x) && (_y >= 0 && _y < y)) {
			Knoten k = knoten[_x][_y];

			int g = base.G + 1;
			int h = k.getH(ziel);

			if (k.flag != Knoten.IS_CLOSED_LIST) {
				k.G = g;
				k.H = h;
				k.setF();
				k.last = base;
				openList.add(k);
			} else if (g < k.G) {
				k.G = g;
				k.H = h;
				k.setF();
				k.last = base;
				openList.add(k);
				k.flag = Knoten.IS_OPEN_LIST;
			}
			return k == ziel;
		}
		return false;

	}

	private void clearNodes() {
		for (int _x = 0; _x < x; _x++) {
			for (int _y = 0; _y < y; _y++) {
				Knoten k = knoten[_x][_y];
				k.G = -1;
				k.H = -1;
				k.F = -1;
				k.flag = Knoten.NO_List;
				k.last = null;
			}
		}

Kann mir eventuell jemand Tipps geben,
wie ich ihn Optimieren kann?

Opi3

 

[schalentier]

Wie gross ist dein Graph?

 

[Opi3]

~50*150

(Und ich muss mehrere Minuten warten!!!)
(Der Graph ist doch die 'Map' oder bin ich auf dem falschen Dampfer?)

Opi3

 

[Fu3L]

   Boolean zielGefunden = false;

Hier im Forum fällts leicht auf: Musst aufpassen mit der Groß- und Kleinschreibung.. Hab hier schon Beispiele gesehen, wo global deklarierte Booleans zu "unerklärbaren" NullPointerExceptions geführt haben. (boolean würde vom Compiler ja automatisch mit false gefüllt)

Hat zwar herzlich wenig mit der Geschwindigkeit des Algorithmus zu tun, aber der ist bei größeren Graphen schnell überfordert (s. Schalentiers Post)

Edit: ich war auch schonmal schneller^^

 

[Beni]

Versuch mal eine PriorityQueue zu verwenden, statt für jeden Knoten die gesammten "openList" neu zu sortieren.

 

[schalentier]

Ja, mit Graph mein ich die Groesse der Map.

50*150 = 7500, was noch nich besonders gross ist. Mir ist zunaechst mal das Collection.sort() aufgefallen, das is in jedem Falle unnoetig und moeglicherweise die Ursache fuer die schlechte Performance. Wobei bei einem so kleinen Graph das eigentlich kaum eine Rolle spielen sollte... aber genau wirst du das nur mit einem Profiler (z.B. YourKit, da gibts auch ne zeitlich beschraenkte Demo) herausbekommen.

Das Sortieren ist unnoetig, weil du immer nur das kleinste Element brauchst. Besser ist ein Heap, denn der ist immer sortiert (weil neue Elemente gleich korrekt einsortiert werden). Eventuell ist ein TreeSet, anstatt der ArrayList schon ausreichend (fuer die openList; da kannste dir auch das Collection.sort() sparen).

Ansonsten nimm den Profiler und finde die teuren Operationen.

edit: rechnen muesste man koennen...

 

[Opi3]

Wahnsinn, früher hat's ~40 Sekunden gedauert in einer 50*50 'Map',
jetzt dauerst's in einer 500*500 ~632.0 Ms.
Das nennt sich optimieren!!!:toll::applaus:

Vielen dank.
Wenn noch jemandem etwas auffährt...

	public List<Point> search() {
		if (start == null || ziel == null) {
			return null;
		}

		clearNodes();
		PriorityQueue<Knoten> openList = new PriorityQueue<Knoten>();

		openList.add(start);
		start.G = 1;
		start.setH(ziel);
		start.setF();
		start.last = null;
		Boolean zielGefunden = false;
		while (!zielGefunden) {
			if (openList.isEmpty()) {
				return null;
			}
			Knoten base = openList.element();
			openList.remove(base);
			base.flag = Knoten.IS_CLOSED_LIST;
			if (checkKnoten(base.x - 1, base.y, base, openList)) {
				zielGefunden = true;
			}
			if (checkKnoten(base.x + 1, base.y, base, openList)) {
				zielGefunden = true;
			}
			if (checkKnoten(base.x, base.y - 1, base, openList)) {
				zielGefunden = true;
			}
			if (checkKnoten(base.x, base.y + 1, base, openList)) {
				zielGefunden = true;
			}

		}
		ArrayList<Point> path = new ArrayList<Point>();
		Knoten base = ziel;
		path.add(ziel.point);
		while (true) {
			base = base.last;
			if (base == null) {
				break;
			}
			path.add(base.point);
		}
		
		return path;
	}

 

[Beni]

Mir fällt nur auf, dass man das hier...

            Knoten base = openList.element();
            openList.remove(base);

... auch so schreiben könnte:

Knoten base = openList.poll();

Ich bezweifle aber, dass das noch gross was ändert.

 

[Marco13]

Hmm... aufpassen: Wenn mich nicht alles täuscht, muss da ja irgendwo die Entfernungvon Konten aktualisiert werden, die schon in der Queue sind. Diese Knoten werden durch eine Änderung dann NICHT an eine neue Position in der Queue verschoben. Wenn sich eine Eigenschaft des Knotens ändert, die für seine Position in der Queue relevant ist, muss man (in diesem Fall) den Knoten aus der Queue entfernen und nach der Änderung neu einfügen. (Eine Möglichkeit, die Queue, nur ein "update" machen zu lassen, gibt es AFAIK nicht)

 

[schalentier]

Hmm... aufpassen: Wenn mich nicht alles täuscht, muss da ja irgendwo die Entfernungvon Konten aktualisiert werden, die schon in der Queue sind.

Richtig, das hab ich voellig vergessen. Ich hab mal meine uralte BinaryHeap Implementierung angehangen, vielleicht hilft dir das was. Die kann auch einen geaenderten Eintrag im Heap neu sortieren (update). Bei Interesse kann ich auch den AStar Algo posten - aber vorsicht, der Code is gruselig :-D

 

[Opi3]

@Marco13
Gut, das hat den Bug gelöst, der z.b. entsteht wenn man das Ziel auf (0/0) und den Start auf(49/49)(ganz unten rechts im eck) setzt. (<- den habe ich gestern noch gute 3 Stunden gesucht. (Dann ist meine 'Liebe Frau Mama' ins zimmer gekommen, war ganz fassungslos, dass ich noch nicht schlafe, hat mir das Netbook weggenommen...))


Anleitung: Rechtsklick auf Kasten, Art auswählen.
(Hier noch mit Bug)

Opi3,

Edit: @schalentier tut mir Leid, dich habe ich völlig überlesen.
Ich werde mir die klassen mal angucken. vielen Dank