# Hindernisse umfahren



## Alex04 (1. Okt 2008)

Hallo,
ich stoße auf ein kleines Problem und weiß nicht genau wie ich es lösen kann.
Und zwar habe ich eine 2D Karte mit statischen Objekten (bewegen sich nicht) und "moveable" Objekten, welche sich, wie der Name schon sagt, bewegen. Diese bewegbaren Objekte nenn ich im folgenden einfach NPCs.

So diese NPCs starten an einer beliebigen koordinate, suchen sich ein Ziel, fahren dort hin, verweilen kurz und suchen sich ein neues Ziel usw. .

Nun gut, natürlich sieht es blöd aus, wenn diese NPCs über die statischen Objekte hinwegfahren, denn wer kann schon zB über Wasser fahren?! Ich hätte gerne dass:

-der NPC wenn er an ein statisches Objekt kommt dieses umfährt oder wenn das zu kompliziert ist
-sich ein neues Ziel sucht und normal weiter macht.

Hier ein bisschen Code:

Die MovableObject Klasse:


```
public class MovableObject extends Rectangle2D.Double {
	protected GamePanel parent;
	private int speed;
	protected int zielX;
	protected int zielY;
	protected Image objectImage;
	
	public MovableObject(int x, int y, int speed, Image objectImage, GamePanel parent) {
		super(x, y, objectImage.getWidth(null), objectImage.getHeight(null));
		//Speed muss größer 0 sein, mit 0kmh kann man nicht fahren
		if(speed == 0) {
			speed = 1;
		}
		this.parent = parent;
		this.zielX = x;
		this.zielY = y;
		this.objectImage = objectImage;
		this.speed = speed;
	}
	
	public Image getImage() {
		return objectImage;
	}
	
	public void moveTo(long delta) {
		//Wenn die aktuelle koordinate nicht mit dem Ziel übereinstimmt
		//müssen wir das Objekt bewegen
		if(zielX != x || zielY != y) {
			
			//Ist die X Koordinate + speed größer als Ziel_X dann setzen wir X eins nach unten
			if(x > zielX && x - speed > zielX)
				x = x - (speed*(delta/1e8));
			
			//Andernfalls setzen wir x weiter nach oben
			else if(x < zielX && x + speed < zielX)
				x = x + (speed*(delta/1e8));
			
			//Wenn beides nicht zutriff können wir sicher sein, dass mit dem nächsten Move
			//Unser X Ziel erreicht wird
			else {
				x = zielX;
			}
			
			//Y Koordinate genau analog zur X Koordinate
			if(y < zielY && y + speed < zielY) {
				y += (speed*(delta/1e8));
			}
			else if(y > zielY && y - speed > zielY) {
				y -= (speed*(delta/1e8));
			}
			else {
				y = zielY;
			}
		}
		
	}
//USW: CODE m M n nicht relevant
```

Sowie die davon abgeleitete NPC klasse:


```
public class Npc extends MovableObject {
	//Hat ein NPC das Ziel ereicht, wie viele Runden soll er stehen bleiben
	private int maxStandingRounds = 59;
	private int stayRounds = 0;
	
	public Npc(int x, int y, int speed, Image objectImage, GamePanel parent) {
		super(x, y, speed, objectImage, parent);
	}
	
		public void hasToMove(long delta) {
		
		//Hier handelt es sich um einen NPC welcher Automatisch durch die Welt
		//läuft. D.h. hat er sein Ziel einmal erreicht, sucht er sich ein neues Ziel
		if(zielX != x || zielY != y) {
			moveTo(delta);
		}
		//Ziel erreicht -> neues Ziel innerhalb des Elternfensters
		else {
			stayRounds++;
			//Wenn er solange wie vorgegeben an der Position verweilt hat,
			//dann soll er zu nächsten Ziel
			if(stayRounds == maxStandingRounds) {
				int newX = (int) (Math.random() * (parent.getWidth() - this.objectImage.getWidth(null)));
				int newY = (int) (Math.random() * (parent.getHeight() - this.objectImage.getHeight(null)));
				super.setZiel(newX, newY);
				stayRounds = 0;
			}
		}
	}

}
```

Die NPCs werden in einer LinkedList<Npc> in der Klasse GamePanel gespeichert und folgendermaßen bewegt und gezeichnet:



```
public void paintComponent(Graphics g) {
		super.paintComponent(g);
		g.drawImage(bgImage, 0, 0, null);
		g.setColor(Color.red);
		g.drawString("FPS: " + fps, 10, 10);
		//g.drawImage(tree.getImage(), tree.getKoordinate().x, tree.getKoordinate().y, null);
		if(markedNpc != null)
			g.drawOval((int) treeMove.getX(), (int) treeMove.getY(), (int) treeMove.getWidth(), (int) treeMove.getHeight());
		for(Npc n : computerOpponents) {
			n.drawObject(g);
		}
		tree.drawObject(g);
	}
while(alive) {
			//Als erstes berechnen wir den aktuellen FPS Wert
			computeDelta();
			for(Npc n : computerOpponents) {
				n.hasToMove(delta);
			}
//usw...
```


----------



## Illuminatus0301 (1. Okt 2008)

such einfach mal ein tutorial für "Path finding" 

Spontan fällt mir Link1 und Link2 ein, sind zwar beide für Delphi ,aber die Grundüberlegungen sind ja gleich


----------



## 0x7F800000 (1. Okt 2008)

1) so wie ich das mitbekommen hab, haben sich die entwickler von WoW um solche kleinigkeiten wie fliegende Oger nicht sonderlich viele gedanken gemacht^^

2) ohne komplizierte pathfinding algos reicht in einfacheren Fällen zunächst auch folgendes:
kein Hindernis? laufen. 
kein Hindernis? laufen.
kein Hindernis? laufen.
Hindernis? um das Hindernis herum mit der "rechten" bzw "linken" hand-regel laufen (einfach an dem Rand festhalten und entlanglaufen) wenn das Hindernis nicht mehr den gradlinigen weg versperrt, dann weiter den Weg entlanglaufen.
kein Hindernis? laufen...

ist so ziemlich das simpelste und naheliegendste, was man mit einem GPS, jedoch ohne jegliche kentnisse über das gelände machen könnte. Bei ausschließlich Konvexen Hindernissen sieht das nicht mal allzu dumm aus...


----------



## Landei (1. Okt 2008)

Google mal nach "A*" oder "A Star". Das ist der gebräuchlichste Algorithmus um einen Weg zu finden, und dafür sollte es eigentlich Tonnen an Implementierungen geben. Vorteil dabei ist, dass die NPCs nicht an Ecken hängenbleiben o. ä.


----------

