A* Algorithmus Ergänzung |
Tommy1234
Foren As
Dabei seit: 12.07.2015
Beiträge: 93
|
|
Habe jetzt das TreeSet implementiert und versucht die erweiterte for-Schleife durch einen Iterator und eine while-Schleife zu ersetzen. Hat zwar funktioniert, aber je größer die Distanz zwischen startPunkt und endPunkt, desto langsamer wurde die Pfadsuche und man konnte dann auch eine Verzögerung während der Zuweisung erkennen.
Frage: HashSet -----> HashMap
TreeSet ------> TreeMap
Bei TreeMap<Field,Double> in der Methode addNeighbours hat mir der Compiler gemeldet, dass er Field nicht casten kann zu Comparable.
Gruß Tommy
|
|
28.03.2016 20:02 |
|
|
|
Zitat: |
hat mir der Compiler gemeldet, dass er Field nicht casten kann zu Comparable. |
Du musst ja auch auf mich hören
Zitat: |
Du musst dann natürlich compareTo überschreiben. |
Das schließt ein implements Comparable ein.
Wie auch immer, bei mir wackelt der Weg nicht mehr.
Eigentlich sollte ich jetzt sämtliche Zeilenumbrüche rauslöschen
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
|
package infoboard;
import java.util.HashMap;
public class Field implements Comparable<Field> {
public int x; //so habe ich dir das nicht gegeben. Bei mir war das private
public int y;
private HashMap<Field, Double> neighbors = new HashMap<Field, Double>();
private double f;
private double g;
public boolean blocked;
private Field predecessor;
public Field(int x, int y, boolean blocked) {
this.x = x;
this.y = y;
this.blocked = blocked;
}
public void addNeighbor(Field neighbor) {
double delta = Math.sqrt(((this.x - neighbor.x) * (this.x - neighbor.x)) + ((this.y - neighbor.y) * (this.y - neighbor.y)));
if (!neighbor.blocked && this != neighbor) {
neighbors.put(neighbor, delta);
}
}
public HashMap<Field, Double> getNeighbors() {
return neighbors;
}
public double getF() {
return f;
}
public void setF(double f) {
this.f = f;
}
public double getG() {
return g;
}
public void setG(double g) {
this.g = g;
}
public Field getPredecessor() {
return predecessor;
}
public void setPredecessor(Field predecessor) {
this.predecessor = predecessor;
}
public double calch(Field target) {
double dx = Math.abs(this.x - target.x);
double dy = Math.abs(this.y - target.y);
return (Math.sqrt(2) - 1) * Math.min(dx, dy) + Math.max(dx, dy);
}
@Override
public String toString() {
return x + "/" + y;
}
@Override
public int compareTo(Field o) {
return 4 * (int) Math.signum(this.f - o.f) + 2 * (int) Math.signum(this.x - o.x) + (int) Math.signum(this.y - o.y);
}
} |
|
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
|
package infoboard;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;
public class AStar {
public static ArrayList<Field> AStaralgorithm(int xFrom, int yFrom, int xTo, int yTo, boolean[][] grid, int width, int height) {
Field[][] fields = new Field[width][height];
for (int x = 0; x < width; x += 1) {
for (int y = 0; y < height; y += 1) {
fields[x][y] = new Field(x, y, grid[x][y]);
}
}
for (int x = 0; x < width; x += 1) {
for (int y = 0; y < height; y += 1) {
for (int dx = -1; dx <= 1; dx += 1) {
for (int dy = -1; dy <= 1; dy += 1) {
if (x + dx < 0 || x + dx >= width || y + dy < 0 || y + dy >= height) {
continue;
}
if (!fields[x + dx][y].blocked || !fields[x][y + dy].blocked)
fields[x][y].addNeighbor(fields[x + dx][y + dy]);
}
}
}
}
TreeSet<Field> openList = new TreeSet<Field>();
Set<Field> closedList = new HashSet<Field>();
openList.add(fields[xFrom][yFrom]);
Field target = fields[xTo][yTo];
while (!openList.isEmpty()) {
Field current = openList.first();
openList.remove(current);
if (current == target) {
ArrayList<Field> result = new ArrayList<Field>();
Field tmp = target;
while (tmp != null) {
result.add(0, tmp);
tmp = tmp.getPredecessor();
}
return result;
}
closedList.add(current);
expandNode(current, target, openList, closedList);
}
return null;
}
public static void expandNode(Field current, Field target, Set<Field> openList, Set<Field> closedList) {
HashMap<Field, Double> successors = current.getNeighbors();
Iterator<Entry<Field, Double>> it = successors.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Field, Double> pair = it.next();
Field successor = pair.getKey();
if (closedList.contains(successor)) {
continue;
}
double tentative_g = current.getG() + pair.getValue();
if (openList.contains(successor) && tentative_g >= successor.getG()) {
continue;
}
successor.setPredecessor(current);
successor.setG(tentative_g);
double f = tentative_g + successor.calch(target);
openList.remove(successor);
successor.setF(f);
openList.add(successor);
}
}
} |
|
__________________ Syntax Highlighting fürs Board (Link)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 29.03.2016 09:39.
|
|
29.03.2016 09:37 |
|
|
Tommy1234
Foren As
Dabei seit: 12.07.2015
Beiträge: 93
|
|
Zitat: |
Eigentlich sollte ich jetzt sämtliche Zeilenumbrüche rauslöschen |
HaHa
Ok, habs soweit verstanden.
Ich werde mich die nächste Woche nicht mehr melden, denn ich werde mich intensiv mit Deinem Code und Sets, Maps und Queues auseinandersetzen. Ich hatte dieses Kapitel in der Insel blos überflogen und für unnötig befunden... .
Jetzt sehe ich, dass mir diese Grundlagen erstens fehlen und zweitens das Leben durchaus vereinfachen können.
Die Anwendung des Algorithmus auf großen Maps ist denke ich für mich machbar.
Für den weiteren Verlauf meines Projekts, werde ich nun weiterkommen.
Vielen, vielen Dank nochmal für Deine Geduld und Deine Mühe, Du hast mir sehr geholfen und ich hab wieder was gelernt.
Gruß Tommy
|
|
29.03.2016 16:21 |
|
|
Tommy1234
Foren As
Dabei seit: 12.07.2015
Beiträge: 93
|
|
Weitere Ergänzungen zu A-Stern |
|
Hallo mal wieder,
hatte viel um die Ohren und komme erst jetzt wieder zum programmieren.
Ich habe mich in Sets, Listen und Maps eingelesen und ein wenig herumexperimentiert mit dem Ergebnis, dass eulerscheZahl die beste Lösung mit dem TreeSet bereits verwendet hat.
Außerdem experimentiere ich mit dem A* viel und komme doch an einigen Stellen nicht weiter.
Gleich zu meinen Fragen:
Also, wenn ich zwar die Größe eines booleanGrids definiert habe aber keine Blockade eingebaut habe,dann müsste doch, wenn startx bzw. starty 0,0
ist und zielx bzw ziely einfach die geklickte aktuelle Mausposition darstellt, der gemalte Pfad einfach eine Linie vom Start zum Ziel darstellen. Tuts aber nicht, WIESO?
Die zweite Frage betrifft folgendes:
Ich habe ein isometrisches Feld erstellt mit isometrischen Texturen die auch korrekt angezeigt werden. Was ist jetzt, wenn ich den A* auf ein isometrisches Spielfeld anwenden möchte bezüglich des boolean grids und des tatsächlichen isometrischen Spielfeldes?
Ich stelle mir das in etwa so vor, dass der Spieler (ein isometrisch dargestelltes Rechteck) über das isometrische Spielfeld laufen und der A* dabei Hindernisse erkennt und der Spieler darum herumlaufen kann. Also im Prinzip nichts anderes als ein orthogonales Spielfeld mit rechteckigen Kacheln nur eben isometrisch.
Schließlich noch etwas, was ich bereits gefragt habe:
Die Laufzeit leidet stark bei dieser Implementierung ( nicht falsch verstehen bin ja dankbar für die investierte Zeit von eulersche Zahl ), d.h., dass beim Starten der Applikation ca. 3 Sekunden vergehen bis der Spieler angezeigt wird und pro Klick vergehen ca. 1,5 Sekunden. Das ganze läuft natürlich besser wenn man statt 1x1, 32x32 hernimmt und so schnell wie bei letzterem sollte der A* auch bei 1x1 gehen. Ist das überhaupt möglich und was kann man noch verbessern??? (Ich hab das noch nicht ganz verstanden, deshalb frage ich)
Mir ist klar, dass sehr viele Punkte berechnet werden müssen, aber wenn man an professionelle Spiele denkt, funktioniert es ja auch.
Ok, ziemlich viel.
Wäre aber dennoch für einen geduldigen Menschen dankbar, der mir etwas dazu sagen kann.
Gruß Tommy
|
|
29.09.2016 19:27 |
|
|
Tommy1234
Foren As
Dabei seit: 12.07.2015
Beiträge: 93
|
|
Mir gibt noch etwas zu bedenken, nämlich die Nachbarknoten. (also bei addNeighbours)
In Deinem Code berechnest Du alle Nachbarknoten von allen möglichen Knoten auf einmal und das pro Frame. Ich denke, dass genau das die Laufzeitprobleme verursacht. Ich dachte aber, dass man nur die Nachbarknoten des gerade zu untersuchenden Knotens berechnen muss zur Laufzeit. Kann mich aber auch irren.
Gruß Tommy
|
|
30.09.2016 08:09 |
|
|
|