[Xean]

hi,

na, unter dem header kann man vieles verstehen.... ich kann mein problem auch mit router oder "kürzesten Path sucher" bettiteln, naja.....

Ich hab schon mal hier ein Thema rein gestellt... und auch paar gute ergebnisse erziehlt (danke an pago, hat mir viel geholfen) aber ich stecke immer noch fest.

äh, ups, ich bin gesprächig..... kommt nicht oft vor

Um mein Problem auf den Punkt zu bringen:
Ich möchte eine kleine engiene für ein 2D-RPG schreiben, die den kürzesten weg zwischen dem spieler und der maus berechnet (da soll der spieler dann hinlaufen).
Ich hab auch schon paar (ich glaube) gute ideen, aber ich weiß nicht wie ich diese um setzten soll......

Es gibt eine Schwirigkeit, sonst würde ich es eigendlich selbst hinbekommen:
es gibt hindernisse, die der spieler (die engine) umgehen soll.

So, soweit zu dem thema meines problemes, jetzt zu meinen ideen:

ich hab mir gedacht, dass ich erst mal schaue, ob es zwischen dem spieler und dem ziel ein hinderniss ist. wenn net, dann kann der spieler einfach zulaufen. wenn doch, dann will ich erst mal wissen, wo das hinderniss ist.
Dazu hab ich den algorithmus von Besham gefunden. Mit diesem kann ich eine gerade spannen, und jeden pixel auf dieser gerade anschauen, und abfragen ob ich auf dem feld laufen kann oder nicht (=hinderniss).
wenn ich ein hinderniss gefunden habe. dann dachte ich, dass ich links und rechts vorbei schau, und solang um dashindernissdrum herum gehe, bis ich daszielsehe oder bis ich noch ein hinderniss sehe, wo das genze von vorne los gehen würde.

ich bekomm die umsetzung net hin. vielleicht gäbe es eine einfacherre lösung, wenn ja, bitte posten. wenn nein, vielleicht eine idee haben wie ich es am geschicktesten mache... oder am bessten (wo ich mich sehr drüber freuen würde) mir code//codeschnipsel schicken

Danke für eure hilfe.

Xean


PS:
Die map besteht aus 32x32 pixel großen, rechteckigen feldern, die einen boolean-wert haben der sagt, ob man drauf laufen kann, oder net

[Xean]

schade, hat hier niemand eine idee??

[pago]

Na ja... ich würde es immer noch mit nem A* versuchen. Der Artikel auf Wikipedia war recht gut, denke ich. Aber bei der Umsetzung kann ich dir leider nicht helfen - nicht gerade mein Fachgebiet.

[Xean]

das problem, was ich an A* sehe ist, dass dieser algorithmus sehr langsam ist, wenn ich nicht mit 3 oder 4 möglichkeiten pro knoten arbeite sondern mit 8. und noch langsamer, wenn ich nicht nur 10 sondern 500 bis 5000 knoten arbeite

[Xean]

hi,
ich hab jetzt fast eine Lösung.
zwar hat es noch paar fehler, aber vielleicht könnt ihr ja mal schauen, ob ihr
1. den Code versteht, und
2. n verbesserungs vorschlag hab

[Ben]

Mir würde das ein oder andere Kommentar gut tun .

[Xean]

... naja... also bei Util.java hab ihc schon angefangen.... aber stimmt, sind paar wenige... ich denk heute abend stell ichs nochmal rein...

[Xean]

So hier.
Ich hoffe ich soll die Path.java nicht auch noch Kommentieren...
Ich denke, dass es klar ist, was die Aufgabe dieser Klasse ist...

Und ich habe auch gemert, dass ich irgendwo micht total irre. denn man muss dem teil fast schon den weg zeigen... naja du wirst es ja sehen..

[Xean]

Util.java-Update:
irgendwie bekomme ich das teil net mehr hochgeladen....

import java.awt.Point;

/**
 *@autor Oliver Obenland (Xean)
 */

public class Util {
	private final static int ALL = 0;

	private final static int ONLY = 1;
	/**
	 * Diese Methode besucht alle Punkte die auf der kürzesten Verbindung zwischen
	 * den Startpunkt (xP|yP) und dem Endpunkt (yQ|yQ) liegen, und drägt diese in
	 * eine Liste ein. Die Liste ist eine Instanz von Path.
	 * @author Oliver Obenland
	 * 
	 * @param xP X-Koordinate vom Startpunkt
	 * @param yP Y-Koordinate vom Startpunkt
	 * @param xQ X-Koordinate vom Endpunkt
	 * @param yQ Y-Koordinate vom Endpunkt
	 * @return p Liste mit allen Punkten auf einer Gerade zwischen Start- und Endpunkt
	 */
	private static Path getPath(double xP, double yP, double xQ, double yQ,
			int type) {
		Path p = new Path();
		double x = xP;
		double y = yP;
		double D = 0;
		double HX = xQ - xP;
		double HY = yQ - yP;
		double xInc = 1;
		double yInc = 1;
		double c;
		double M;

		if (HX < 0) {
			xInc = -1;
			HX = -HX;
		}
		if (HY < 0) {
			yInc = -1;
			HY = -HY;
		}
		if (HY <= HX) {
			c = 2 * HX;
			M = 2 * HY;
			while (true) {
				if (type == ALL) {
					p.add((int) (x), (int) (y));
				} else if (type == ONLY) {
					if (p.indexOf((int) (x), (int) (y)) == -1) {
						p.add((int) (x), (int) (y));
					}
				}
				if (x == xQ) {
					break;
				}
				x += xInc;
				D += M;
				if (D > HX) {
					y += yInc;
					D -= c;
				}
			}
		} else {
			c = 2 * HY;
			M = 2 * HX;
			while (true) {
				if (type == ALL) {
					p.add((int) (x), (int) (y));
				} else if (type == ONLY) {
					if (p.indexOf((int) (x), (int) (y)) == -1) {
						p.add((int) (x), (int) (y));
					}
				}
				if (y == yQ) {
					break;
				}
				y += yInc;
				D += M;
				if (D > HY) {
					x += xInc;
					D -= c;
				}
			}
		}
		return p;
	}

	/**
	 * Diese Methode besucht alle Elemente der Instanz java.awt.Point
	 * und vergleicht diese mit den Feldern von der Map um zu Wissen, wo
	 * der erste Punkt auf der Map ist, wo der Spieler nicht durch kann,
	 * und gibt diese zurück
	 * 
	 * @author Oliver Obenland
	 * @param p
	 * @param m
	 * @return old
	 * @see Path, Map, getPath(xP,yP,xQ,yQ)
	 */
	private static Point getLastFreePoint(Path p, Map m) {
		Point old = new Point();
		while (p.hasMore()) {//Hat es noch mehr Elemente in der Liste??
			Point np = p.next();//Holt das nächste Element aus der Liste
			if (np != old && m.get(np.x, np.y) != 1) {//Schaut, ob diese Feld auf der Karte begehbar ist
				old = np;//Wenn ja, dann wird weitergesucht
			} else {
				break;//Wenn nicht, dann wird das letzte zurück gegeben
			}
		}
		return old;
	}
	
	/**
	 * Gibt die Richtung zum Ziel zurück
	 * 
	 * @param x
	 * @param y
	 * @param zx
	 * @param zy
	 * @param olddir
	 * @param n
	 * @return
	 */
	private static int getDir(int x, int y, int zx, int zy) {
		int dir = -1;
		double max = (double) Math.max(Math.abs(zx - x), Math.abs(zy - y));
		double bx = ((zx - x) / max);
		double by = ((zy - y) / max);
		if (Math.abs(by) > Math.abs(bx)) {
			if (by < 0) {
				dir = 0;
			} else {
				dir = 2;
			}
		} else {
			if (bx < 0) {
				dir = 1;
			} else {
				dir = 3;
			}
		}
		return dir;
	}
	
	/**
	 * Gibt das nächste Feld, das in der richtung @param dir liegt, zurück
	 * 
	 * @param x
	 * @param y
	 * @param dir
	 * @return
	 */
	private static Point getNextByDir(int x, int y, int dir) {
		Point re = new Point(x, y);
		switch (dir) {
		case 0:
			re = new Point(x, y - 1);
			break;
		case 1:
			re = new Point(x - 1, y);
			break;
		case 2:
			re = new Point(x, y + 1);
			break;
		case 3:
			re = new Point(x + 1, y);
			break;
		}
		return re;
	}

	/**
	 * Sucht ein Weg um alle Hindernisse.
	 * 
	 * @param x
	 * @param y
	 * @param zx
	 * @param zy
	 * @param m
	 * @return
	 */
	public static Path getPath(int x, int y, int zx, int zy, Map m) {
		Path p = new Path();
		//Schaut, ob zwischen Start- und Zielpunkt ein Hinderniss liegt.		
		Path lookFree = getPath(x, y, zx, zy, ONLY);
		Point free = getLastFreePoint(lookFree, m);
		System.out.println("Weg ist frei: " + (free == null));
		//Wenn kein Hinderniss zwischen Start und Endpunkt ist, dann braucht man nach nichts zu suchen
		if (free.x == zx && free.y == zy) {
			p.add(zx, zy);
			return p;
		}
		//Position, von der aus das nächste Feld gesucht wird
		int nx = free.x;
		int ny = free.y;
		//Das nächste Feld wird in 3 richtungen gesucht
		int[] dir = new int[3];
		System.out.println("Starte suche bei: (" + nx + "|" + ny + ")");
		//Zähler. Wenn 1.000 mal kein neues Feld gefunden wurde, dann geht es nicht weiter
		int j = 0;
		while (true) {
			//Suche die nächsten 3 Richtungen
			dir[0] = getDir(nx, ny, zx, zy);
			dir[1] = (dir[0] - 1);
			if (dir[1] <= -1) {
				dir[1] = 3;
			}
			dir[2] = (dir[0] + 1);
			if (dir[2] >= 4) {
				dir[2] = 0;
			}
			System.out.println("Dir[0]: " + dir[0] + " Dir[1]: " + dir[1]
					+ " Dir[2]: " + dir[2]);
			//Gehe auf das nächste Feld
			for (int i = 0; i < dir.length; i++) {
				Point np = getNextByDir(nx, ny, dir[i]);
				//Wenn man das Feld betreten kann und man noch nicht drauf war, dann
				if (m.get(np.x, np.y) == 0 && p.indexOf(np.x, np.y) == -1) {
					nx = np.x;
					ny = np.y;
					//wird es zu einer Liste hinzu gefügt
					p.add(nx, ny);
					//wird geschaut, ob das Ziel zu sehen ist
					lookFree = getPath(nx, ny, zx, zy, ONLY);
					free = getLastFreePoint(lookFree, m);
					System.out.println("Weg ist frei: " + (free == null));
					if (free.x == zx && free.y == zy) {//Wenn man das Ziel sieht
						p.add(zx, zy);//dann muss man nur noch hinlaufen
						return p;
					}
					System.out.println("Neuer Punkt bei: (" + nx + "|" + ny
							+ ")");
					//wird geschaut, ob man auf dem Ziel steht.
					if (nx == zx && ny == zy) {
						return p;
					}
					/*
					 * Wenn ein Feld gefunden wurde, dann braucht man keine neue
					 * Richtung. Man kann einfach wieder schauen, ob es ein neues
					 * Feld gibt
					 */
					i = 0;
					continue;
				}
			}
			if (j > 1000) {
				return p;
			}
			j++;
		}
	}
}