A* Algorithmus Ergänzung

21.03.2016, 13:59

Auf diesen Beitrag antworten »

Tommy1234

A* Algorithmus Ergänzung

Hallo nochmal,

das Beispiel im Thema vorher hab ich nachvollziehen können und habe sogleich eine grafische Umsetzung erzielen können.

Bisher kann ich auf einer großen Map mit Kollisionspunkten, den kürzesten Weg immer erfolgreich finden,ABER sobald ich die Map (ich meine nur ein rechteckiges Gitter mit kollisionspunken) mit 1x1 großen Knoten erstelle, dann läuft die Wegfindungberechnung sehr sehr langsam. Daraufhin hab ich mir überlegt die Map nur einmal im Konstruktor zu laden, aber der Weg muss ja immer zur Laufzeit neuberechnet werden, also das funktioniert irgendwie nicht.
Wie kann ich bei 1x1 großen Knoten und Mapbreite von z.B. 200 und Höhe von 320, eine bessere Performance erzielen, oder ist das normal, das es so langsam geht?

Meine andere Frage betrifft letztendlich doch die Umsetzung der Bewegung einer Spielfigur ( hier nur ein Rechteck) entlang des Pfades.
Ich dachte das wäre einfach, aber da hab ich mich wohl sehr getäuscht, denn es gelingt mir einfach nicht die Spielfigur nach den Pfadkoordinaten zu Bewegen. Ich war 2 Nächte dran gesessen und hab mir den Kopf zerbrochen, komme aber nicht drauf wie das geht.

Bitte um nochmalige Hilfe, wenns keine Umstände macht,

Gruß Tommy

21.03.2016, 16:30

Auf diesen Beitrag antworten »

eulerscheZahl

Mal ein paar Vorschläge:
In meinem Code ist openList schlecht implementiert (Suche mit linearer Laufzeit, sollte erst mal nur funktionieren und verständlich für dich sein). Halte die Liste die ganze Zeit über sortiert, dann sollte es merklich schneller werden.

Wenn du den Weg nur einmal berechnen musst, könntest du es mit Floyd probieren. Damit kannst du die Berechnung in den Konstruktor verschieben. Aber Laufzeit O(n^3) könnte schon kritisch werden.

Du könntest auch Wege zwischen bestimmten Punkten vorberechnen und dann nur noch schauen, wie du vom Startknoten zu einem dieser Punkte kommst und wie du dann wieder wegkommst (wie beim Navi, das einen auf die Autobahn lotsen will).

Ein Rechteck zu bewegen, kann doch nicht so schwer sein. Wo hängt es genau?

21.03.2016, 19:38

Auf diesen Beitrag antworten »

Tommy1234

OpenList hab ich mittlerweile als ProrityQueue, also mit Warteschlnge implementiert. Geht jetzt auch schneller.

Also ein Rechteck bewegen mach ich indem ich die x bzw y Koordinate erhöhe
oder vermindere.

x += speed;
y += speed;

Das ist ja klar.

Ich hab nun vor, wenn das überhaupt möglich ist den x bzw. y Wert genau an den Pfad anzupassen so das sich das Rechteck schließlich entsprechend bewegt.

In meiner ersten sehr primitiven A* Implementation ist mir das gelungen, indem ich einfach den x bzw y- Wert des Wegpunktes den Rechteckkoordinaten angepasst habe, also so

x = Knotenx;
y = Knoteny;

So müsste es eigentlich sein und das hatte auch funktioniert, allerdings musste ich das für jeden x bzw y Wert einzeln zuweisen und das ist sehr viel Schreibarbeit, wenn der Weg länger wird.

Bei dem von Dir angefertigten Code findet A* zwar den kürzesten Weg, aber wenn ich dann wie oben die Koordinaten zuweise springt das Rechteck nach kurzer Verzögerung sofort zum Zielpunkt.
Ich möchte aber eine flüssige Bewegung erreichen.

Die Koordinaten werden ja von A* stets richtig berechnet. Und genau das bereitet mir Kopfzerberechen.

Grad beim schreiben ist mir die Idee gekommen die einzelnen x bzw y Werte des Pfades dynamisch in einem Array zu speichern und dann die Werte anzupassen per Schleife. Aber grad nur so ne Idee....

Ich hoffe du weisst jetzt was ich erreichen möchte?!!!

21.03.2016, 19:41

Auf diesen Beitrag antworten »

eulerscheZahl

Hast du in der Bewegung ein Warten (sleep oder ähnliches)?
Nicht dass du erst langsam den Weg ausrechnest und dann ganz schnell einen Punkt nach dem anderen zuweist.

Anzeige

22.03.2016, 10:22

Auf diesen Beitrag antworten »

Tommy1234

Ich habe nur eine Spielschleife mit einem Thread, den ich alle 48ms schlafen lege.

Also:

run(){

while(true){
update();
repaint();

Thread.sleep(48);
}
}

Mehr nicht.

Ist das falsch? Habe das nämlich immer so gemacht.

25.03.2016, 17:50

Auf diesen Beitrag antworten »

Tommy1234

Hallo nochmal,

es hatte nicht mit irgendnem Warten oder sleep zu tun, sondern der Grund warum der Spieler immer sofort zum Ziel gesprungen ist liegt daran, dass der Pfad vom Ziel ausgehend zum Startpunkt berechnet wird. Das heisst, dass man die Werte in der Pfadliste einfach nur umzudrehen braucht, also anstatt von hinten nach vorne, von vorne nach hinten. Zunge raus

Zunge raus

Erst dann kann man eine Bewegung erzielen.

Ich denke das bekomme ich hin also die Liste "umzudrehen".

Danke trotzdem.

PS: Habe mich nun intensiver mit Spielschleifen beschäftigt und nun endlich mal eine einigermaßen vernünftige Spielschleife hinbekommen mit UPS und FPS Werten bei 60.

25.03.2016, 21:45

Auf diesen Beitrag antworten »

Tommy1234

Ok,

du hattest Recht, der Weg wird erst langsam ausgerechnet und anschließend wird ganz schnell der Weg ausgerechnet. Aber ich habe weder sleep noch irgendein warten implementiert. Leider hab ich keinen blassen Schimmer woran das liegen könnte. Ich nutze repaint(), aber daran allein kann das nicht liegen vermute ich.

Bei Bedarf poste ich hier die Klasse, die das Fenster mit dem Label erzeugt und die Map auf dem Bildschirm ausgibt.

Wäre toll nochmal was zu hören.

Gruß Tommy

26.03.2016, 08:06

Auf diesen Beitrag antworten »

eulerscheZahl

Ich wollte dich schon für die letzte Frage um den Code bitten - muss es dann irgendwie vergessen haben.
Lade bitte mal so viel hoch, dass ich es kompilieren kann (werde es zeitlich aber wohl erst morgen schaffen).

26.03.2016, 12:10

Auf diesen Beitrag antworten »

Tommy1234

Hallo hier mal der gesamte Code. Die Mapdaten musst du in eine txt.Datei kopieren und in eclipse importieren in eine folder.

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:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:

package main;
import java.awt.Color;
import java.awt.Graphics; 
import java.util.ArrayList;
import javax.swing.JFrame; 
import javax.swing.JLabel;

public class Main extends JFrame{
  	
        private static final long serialVersionUID = 1L; 
	
        static int width = 300; 
	static int height = 300; 
	static int startx; 
	static int starty; 
	static int zielx; 
	static int ziely; 
	static int playerx; 
	static int playery; 
	static boolean[][] grid; 
	 	
        public static void main(String[] args) {
 		 		
        Display display = new Display(); 
	Main m = new Main();     

        m.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 	           
        m.setSize(810,670); 
        m.setLocationRelativeTo(null); 
        m.add(display);
        m.setVisible(true); 		 		

        while(true){ 

	       long lastTime = System.nanoTime();
 	       final double ns = 1000000000.0/60.0; 
	       double delta = 0; 
	       long timer = System.currentTimeMillis(); 	
	       int frames = 0; 
	       int updates = 0; 			 			 

              while(true){ 
                   long now = System.nanoTime(); 
                   delta += (now - lastTime) / ns; 
                   lastTime = now; 
                   while(delta >= 1){ 
                        display.update();
                        delta--; 
                        updates++; 					
                        display.repaint(); 				    
                        frames++;				 				    

                        if((System.currentTimeMillis() - timer) >1000){
 				         


             timer+=1000; 					 					m.setTitle("A-Stern v1.0" + "|" + updates + "ups," + frames + "fps"); 					 					
updates = 0; 					
frames = 0; 				} 			} 		} 	} 	 	
public static class Display extends JLabel{ 
 	private static final long serialVersionUID = 1L; 		 		    

        Level level = new Level(); 
        public Display(){ 
             addMouseListener(new Mouse()); 	
             setFocusable(true); 
	} 
        public void update(){ 
		zielx = Mouse.mousex;
		ziely = Mouse.mousey; 
	grid = new boolean[width][height]; 			 			for(int y = 0;y<height;y++){ 				
for(int x = 0;x<width;x++){ 
	if(Level.levelMap[x/10][y/10]==1){ 						grid[x][y] = true; 					} 				} 			} 			 			 			 		} 		 		
protected void paintComponent(Graphics g){ 			super.paintComponents(g); 
	for(int x = 0;x<30;x++){ 
	for(int y = 0;y<30;y++){ 					  

           g.drawRect(x*10,y*10,10,10); 
	}
	} 			 			 

        level.drawTiles(g); 
	ArrayList<Field> path = 

AStar.AStaralgorithm(startx,starty,zielx,ziely,grid,width,height); 			 			if(path != null){ 
			 

            for(Fieldf:path){ 					 					g.fillRect(f.x,f.y,1,1); 					
System.out.println(f); 	
			} 	
		} 			 			
                g.setColor(Color.BLUE); 
		g.fillRect(playerx,playery,10,10); 
		} 
		 	} } package main;  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;  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; 						} 						fields[x][y].addNeighbor(fields[x+dx][y+dy]); 					} 				} 			} 		} 		 		Set<Field> openList = new HashSet<Field>(); 		Set<Field> closedList = new HashSet<Field>(); 		 		openList.add(fields[xFrom][yFrom]); 		Field target = fields[xTo][yTo]; 		 		while(!openList.isEmpty()){ 			Field current = null; 			for(Field f : openList){ 				if(current ==null || current.getF()>f.getF()){ 					current = f; 				} 			} 			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); 			successor.setF(f); 			openList.add(successor); 		} 	}  } package main;  import java.util.HashMap;  public class Field {  	public int x; 	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; 	} } package main;  import java.awt.Graphics; import java.awt.image.BufferedImage; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException;  import javax.imageio.ImageIO;  public class Level {  	public static int[][] levelMap; 	public int tilesw; 	public int tilesh; 	public int RASTER = 10; 	public int[] level; 	 	public BufferedImage tiles; 	public int tileNr; 	 	public Level() { 		 		try { 			tiles = ImageIO.read(new File("gui//spritesheet.png")); 		} catch (IOException e) {e.printStackTrace();} 		 		generateMap(1,"gui//map.txt"); 		 	} 	 	public void generateMap(int level_nr,String filename){ 		         if(level_nr == 1){             tilesw=30;             tilesh=30;         }                  String stringMap = "";          try {         	BufferedReader reader = new BufferedReader(new FileReader(filename));         	String line = null; 		           	while ((line = reader.readLine()) != null) {         		stringMap += line; 			}         	reader.close();         } catch (IOException e) {e.printStackTrace();}          if(stringMap != ""){ 			 	        String[] stringarray = stringMap.split(","); 	        level = new int[stringarray.length]; 	         	        for(int i = 0;i<stringarray.length;i++){ 	        	level[i] = Integer.parseInt(stringarray[i]); 	        } 			 	        int nr = 0; 			 			levelMap = new int[tilesw][tilesh]; 			 			for(int y=0;y<tilesh;y++){ 	            for(int x=0;x<tilesw;x++){ 	            	levelMap[x][y]= level[nr]; 		            nr++; 	            } 			}        }             }  	 	public void drawTiles(Graphics g){ 		 		for(int x = 0; x<tilesw*RASTER; x+=RASTER){		 			for(int y = 0; y<tilesh*RASTER; y+=RASTER){ 				tileNr = levelMap[x/RASTER][y/RASTER]; 				if(tileNr==1){ 					g.fillRect(x,y,RASTER,RASTER); 				} 			} 		}	 	} } package main;  import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent;  public class Mouse extends MouseAdapter{  	public static int mousex,mousey; 	  	@Override 	public void mouseClicked(MouseEvent e) { 		 		mousex = e.getX(); 		mousey = e.getY(); 	}  }  //mapdata 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0, 0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0, 0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0, 0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0, 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0, 0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0, 0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0, 0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,0,0, 0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0, 0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Ich hoffe das hilft. Bei mir ist der Code kompilierbar.

Sorry für die Formatierung.(5min Arbeit großes Grinsen

großes Grinsen

)

26.03.2016, 18:54

Auf diesen Beitrag antworten »

eulerscheZahl

Na ein Glück, dass eclipse automatische Codeformatierung hat...
Du hättest es aber auch einfach in eclipse archivieren und das .zip hochladen können. Naja, schaue ich mir morgen an.

27.03.2016, 14:09

Auf diesen Beitrag antworten »

eulerscheZahl

Wenn es dir um die Verzögerung zwischen Klicken und Einzeichnen des Wegs geht: das Event wird wohl einfach nicht schneller ausgeführt. Mache eine Kontrollausgabe - du wirst sehen, es vergehen ein paar Millisekunden.

Ansonsten: wenn du die Wegsuche in einem größeren Programm einbauen willst, berechne den Weg nur einmal und speichere den Pfad ab. Das geht schneller, als ihn für jedes Frame neu zu berechnen.

27.03.2016, 16:06

Auf diesen Beitrag antworten »

Tommy1234

Ok Danke,

aber das löst mein Bewegungsproblem noch nicht.

Hm. Ich denke ich mach es so, dass ich wie du sagst den Weg in einem int Array speichere und anschließend die Positionen pro frame einzeln zuweise. Allerdings vermute ich, dass es dann wieder zu schnell oder viel zu langsam geht.

Also so z.B.:

for(int x = 0;x<intx.length;x++){

intx[x] = playerx;

}

Noch eine Frage:

Mit einem Timer den Spieler bewegen (wegen der einzelnen Positionen) ist Schwachsin oder?

27.03.2016, 16:11

Auf diesen Beitrag antworten »

eulerscheZahl

Bei jedem "Tick", also Neuzeichnen würde ich auch den Spieler bewegen. Dazu solltest du die benötigte Zeit für das Zeichnen mit einfließen lassen, damit man sich auf jedem Rechner gleich schnell bewegen kann.

code:
1: 2: 3:	for(int x = 0;x<intx.length;x++) { intx[x] = playerx; }

ist keine gute Idee: das ist abgekoppelt vom Zeichnen und warten. Außerdem würde ich Punkte speichern, keine x Koordinaten.

28.03.2016, 09:51

Auf diesen Beitrag antworten »

Tommy1234

Also,

ich hab die Bewegung jetzt endlich.

Allerdings hab ich noch ein Problem. Der Algorithmus den Du geschrieben hast berechnet zwar den Pfad sehr gut, doch zur Laufzeit ändert sich der Pfad, d.h.
er wird pro Frame neu berechnet. Ich hab schon die Wurzel 2 raus, aber das ändert nix. Wie kann ich denn den Pfad konstant halten?

Dann hab ich noch eine Frage:

Dein Algorithmus berechnet auch die diagonalen Nachbarn, doch mein Spieler kann ja nicht um Ecken gehen, wenn du weisst was ich meine?

Ich möchte erreichen, dass der Spieler bei Kollision nur horizontal und vertikal laufen kann, um ein Hindernis zu umgehen und ansonsten auch diagonal. Wie erreiche ich das?

Hab schon einiges probiert doch nichts fruchtet.

Gruß Tommy

28.03.2016, 10:07

Auf diesen Beitrag antworten »

eulerscheZahl

OpenList hast du als Set implementiert. Das Problem ist, dass ein HashSet keine feste Reihenfolge sicherstellt.
Du könntest die Ordnung sicherstellen, indem du z.B. TreeSet statt HashSet nimmst - das sichert die richtige Reihenfolge. Du musst dann natürlich compareTo überschreiben.
Netter Nebeneffekt:

ich hatte schon geschrieben, dass das schlecht ist

code:
1: 2: 3: 4: 5: 6:	Field current = null; for (Field f : openList) { if (current == null \|\| current.getF() > f.getF()) { current = f; } }

Beim TreeSet musst du nicht nach dem kleinsten Wert suchen, da bereits sortiert ist. Das verbessert die Laufzeit.

Die einfachste Möglichkeit, das Diagonallaufen zu verhindern, wäre die Nachbarschaftsbeziehung zu modifizieren:

code:
1: 2:	if (!fields[x + dx][y].blocked \|\| !fields[x][y + dy].blocked) //Die Bedingung ist neu :) fields[x][y].addNeighbor(fields[x + dx][y + dy]);

28.03.2016, 20:02

Auf diesen Beitrag antworten »

Tommy1234

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

29.03.2016, 09:37

Auf diesen Beitrag antworten »

eulerscheZahl

Zitat:

hat mir der Compiler gemeldet, dass er Field nicht casten kann zu Comparable.

Du musst ja auch auf mich hören smile

smile

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 Teufel

Teufel

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);
		}
	}
}

29.03.2016, 16:21

Auf diesen Beitrag antworten »

Tommy1234

Zitat:

Eigentlich sollte ich jetzt sämtliche Zeilenumbrüche rauslöschen

HaHa

Freude

Freude

Freude

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.09.2016, 19:27

Auf diesen Beitrag antworten »

Tommy1234

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

30.09.2016, 08:09

Auf diesen Beitrag antworten »

Tommy1234

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

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »