Rekursive Funktion zur Wegermittlung

[Gurke1993]

Liebe Java-Freunde,
nachdem ich mich jetzt ungelogen 3 Tage damit rumgeärgert habe, hoffe ich jetzt auf Hilfe von Euch
Zunächst eine ungefähre Beschreibung meines Problems:

Ich versuche mich zu Zeit an einer Art Advance Wars 2 (Gameboy Advance Spiel - Strategie, Rundenbasierend) für den PC. Nun mächte ich dem Spieler zeigen, welche Felder eine Einheit in diesem Zug betreten kann und vorallem möchte ich auch wissen, welche Felder dafür alle überschritten werden müssen. Entsprechend weise ich jedem der Felder eine Liste von Feldern zu, die dort hin überschritten werden müssen (beginn und ende eingeschlossen).

Dabei verwende ich folgenden Code für die Methode:

	public void showPaths(Integer type, Integer moveDistance, Integer unitId, List <Field> fieldListGot) {
		if (resistance[type] != -1) {
//WENN FELD FÜR DIE EINHEIT BEGEHBAR
		moveDistance -= resistance[type];
//Vom verbliebenen Laufweg abziehen
		if (this.getUnit() == null || (this.getUnit().getId() == unitId && this.getUnit().getHealth()<10)) {
//Wenn keine Einheit auf dem Feld oder eine Einheit gleichen Types (Unite-Funktion)
			
			if (this.fieldList.size() >= fieldListGot.size()-1 || this.fieldList.isEmpty()) {
//Wenn die alte Liste länger als der neue Weg oder es keinen alten Weg gibt
				System.out.println("Aktuelle Länge: "+this.fieldList.size());
				fieldListGot.add(this);
				this.setFieldList(fieldListGot);
				System.out.println("Liste "+getFieldX()+" "+getFieldY()+" mit Länge "+this.fieldList.size()+" ersetzt! Neuer Weg:");
				for (int i=0; i<fieldListGot.size();i++) {
					System.out.println(fieldListGot.get(i).getFieldX()+" "+fieldListGot.get(i).getFieldY());
				}
			}
		this.path.setVisible(true);
		if (moveDistance >0) {
// WENN NOCH LAUFWEG ÜBRIG
		if (this.getFieldX()>0) {
//WENN FELD LINKS EXISTIERT
			screen.fieldCollection.getField(getFieldX()-1, getFieldY()).showPaths(type, moveDistance, unitId,this.getFieldList());
//Methode auf linkem Feld aufrufen...
		}
// usw...
		if (this.getFieldX()<screen.fieldCollection.getFieldLength()-1) {
			screen.fieldCollection.getField(getFieldX()+1, getFieldY()).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		if (this.getFieldY()>0) {
			screen.fieldCollection.getField(getFieldX(), getFieldY()-1).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		if (this.getFieldY()<screen.fieldCollection.getFieldHeight()-1) {
			screen.fieldCollection.getField(getFieldX(), getFieldY()+1).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		}
			
		}
		}
	}

Allerdings ist der Output der Folgende (Im Beispiel eine Infantrieeinheit mit 3 moveDistance):

Aktuelle Länge: 0
Liste 1 0 mit Länge 2 ersetzt! Neuer Weg:
0 0
1 0
Aktuelle Länge: 0
Liste 2 0 mit Länge 3 ersetzt! Neuer Weg:
0 0
1 0
2 0
Aktuelle Länge: 0
Liste 1 1 mit Länge 4 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
Aktuelle Länge: 0
Liste 0 1 mit Länge 5 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
Aktuelle Länge: 0
Liste 2 1 mit Länge 6 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
Aktuelle Länge: 6
Liste 1 0 mit Länge 7 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
Aktuelle Länge: 0
Liste 1 2 mit Länge 8 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
Aktuelle Länge: 8
Liste 0 1 mit Länge 9 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
Aktuelle Länge: 9
Liste 1 1 mit Länge 10 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
Aktuelle Länge: 10
Liste 0 1 mit Länge 11 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
Aktuelle Länge: 11
Liste 2 1 mit Länge 12 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
2 1
Aktuelle Länge: 12
Liste 1 0 mit Länge 13 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
2 1
1 0
Aktuelle Länge: 13
Liste 1 2 mit Länge 14 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
2 1
1 0
1 2
Aktuelle Länge: 0
Liste 0 2 mit Länge 15 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
2 1
1 0
1 2
0 2
Aktuelle Länge: 15
Liste 1 2 mit Länge 16 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
2 1
1 0
1 2
0 2
1 2
Aktuelle Länge: 16
Liste 0 1 mit Länge 17 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2
0 1
1 1
0 1
2 1
1 0
1 2
0 2
1 2
0 1

Erwarten würde ich jedoch einen Output, der 1. für jedes Feldunterschiedlich ist (gleicher Weg kann nicht zu unterschiedlichen Feldern führen) und, der 2. immer kürzer als 5 Felder ist.

Könnt ihr mir helfen? Falls ihr mehr Informationen braucht fragt, mir ist klar, dass es eine recht komplexe Frage ist.

Cheers
Gurke

 

[SlaterB]

> if (this.fieldList.size() >= fieldListGot.size()-1 || this.fieldList.isEmpty()) {

> Aktuelle Länge: 6
> Liste 1 0 mit Länge 7 ersetzt! Neuer Weg:

hier liegt ein Fehler vor, der am Log klar zu erkennen ist,
wenn schon ein Pfad der Länge 6 vorhanden ist, und als Parameter auch 6 kommt, sowie noch 1 dazu für den aktuellen Schritt,
dann lieber bei 6 bleiben, nicht durch 7 ersetzen..

was zu ändern ist könnte ich sagen, aber ist so einfach und auch so wichtig darüber nachzudenken,
da lasse ich dir notfalls noch paar Minuten selber, sonst Bescheid sagen

edit:
wenn das if nicht erfüllt ist, kannst du dir eigentlich auch die restliche Rekursion sparen,
alte kürzere Wege werden sich von hier aus auch per Rekursion schon verbreitet haben,
oder sind noch dabei,
allerdings gibt es ja verschiedene Bewertungen, einmal die Anzahl Felder, und dann die moveDistance,
die vielleicht weniger 'abgenutzt' sein könnte trotz mehr Felder, willst du wirklich beide Kriterien parallel prüfen?
vielleicht die Anzahl Felder ganz ignorieren und nur die moveDistance der verschiedenen Pfade vergleichen

------

> der 2. immer kürzer als 5 Felder ist.

diese Bedingung scheint durch die moveDistance-Variable begrenzt zu sein,
leider sieht man im Log nichts davon, der Code scheint mir grob betrachet ok,

Problem könnte entweder ein irrwitzig hoher Startwert sein, jedenfalls nicht 5,
oder der Abzug mit resistance[type] ist nicht korrekt, hat vielleicht auch negative Werte

oder ich irre mich doch im Code, Log würde es jedenfalls ziemlich deutlich zeigen


------

edit:
ganz wichtig noch:
du musst die Listen wohl kopieren,
wenn du überall ein und dasselbe Objekt setzt, dann haben alle exakt dieselbe Liste,
deswegen ist im Log auch fieldList.size() immer == fieldListGot.size(), falls nicht null,
denn beide Listen sind dieselbe

und dann noch:
wenn du einen Rekursionsschritt zurückgehst, musst du das letzte eingefügtes Element aus der Parameter-Liste wieder entfernen,

mit ständig kopierter neuer Liste für die Rekursion wären beide Problem auf einmal zu schlagen

bei moveDistance besteht das Problem nicht, da dort immer ein neues Objekt zugewiesen wird,
guter Vergleich

 

[Gurke1993]

Danke für die Antwort! Hier der angepasste Code:

	public void showPaths(Integer type, Integer moveDistance, Integer unitId, List <Field> fieldListGot) {
		if (resistance[type] != -1) {
		moveDistance -= resistance[type];
		if (this.getUnit() == null || (this.getUnit().getId() == unitId && this.getUnit().getHealth()<10)) {
			
			if (this.moveDistance == null || this.moveDistance>moveDistance) {
				this.moveDistance  = moveDistance;
				System.out.println("Aktuelle Länge: "+this.fieldList.size());
				fieldListGot.add(this);
				this.setFieldList(fieldListGot);
				System.out.println("Liste "+getFieldX()+" "+getFieldY()+" mit Länge "+this.fieldList.size()+" ersetzt! Neuer Weg:");
				for (int i=0; i<fieldListGot.size();i++) {
					System.out.println(fieldListGot.get(i).getFieldX()+" "+fieldListGot.get(i).getFieldY());
				}
			
		this.path.setVisible(true);
		if (moveDistance >0) {
		if (this.getFieldX()>0) {
			screen.fieldCollection.getField(getFieldX()-1, getFieldY()).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		if (this.getFieldX()<screen.fieldCollection.getFieldLength()-1) {
			screen.fieldCollection.getField(getFieldX()+1, getFieldY()).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		if (this.getFieldY()>0) {
			screen.fieldCollection.getField(getFieldX(), getFieldY()-1).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		if (this.getFieldY()<screen.fieldCollection.getFieldHeight()-1) {
			screen.fieldCollection.getField(getFieldX(), getFieldY()+1).showPaths(type, moveDistance, unitId,this.getFieldList());
		}
		}
			}
			
		}
		}
	}

Und hier der Testoutput bei der Selben Einheit:
Aktuelle Länge: 0
Liste 1 0 mit Länge 2 ersetzt! Neuer Weg:
0 0
1 0
Aktuelle Länge: 0
Liste 2 0 mit Länge 3 ersetzt! Neuer Weg:
0 0
1 0
2 0
Aktuelle Länge: 0
Liste 1 1 mit Länge 4 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
Aktuelle Länge: 0
Liste 0 1 mit Länge 5 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
Aktuelle Länge: 0
Liste 2 1 mit Länge 6 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
Aktuelle Länge: 6
Liste 1 0 mit Länge 7 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
Aktuelle Länge: 0
Liste 1 2 mit Länge 8 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 0
1 2

Aktuelle Länge: 0
Liste 2 1 mit Länge 6 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
Aktuelle Länge: 0
Liste 1 2 mit Länge 7 ersetzt! Neuer Weg:
0 0
1 0
2 0
1 1
0 1
2 1
1 2

2 Weitere Anmerkungen: Es ist jetzt durchaus denkbar, dass die alte Länge überschrieben wird, auch wenn sie kleiner ist (längerer weg aber geringere gesamtresistenzen für die moveDistance). Aber mein Problem ist das Folgende: Infast allen Listen ist der Weg falsch! So wird von dem Feld 2:0 zu 1:1 "gesprungen". Da liegt auch mein Problem mit dem Codeteil...

 

[Gurke1993]

aaaaajaaa kannst du das mit der SELBEn liste nochmal genauer erläutern. Ich glaube genau da liegt mein Problem. Wenn ich die Funktion auf verschiedenen Feldern aufrufe müsste ich doch auch verschiede Listen haben oder?

 

[SlaterB]

eine Liste wird mit 'new' erzeugt, das machst du nur einmal ganz zu Beginn, reichst sie in der Rekursion überall durch
und speicherst sie überall ab, damit ist es überall dieselbe,
zudem wie gesagt bei Rekursionsrückschritt in derselben Liste immer noch die alten Elemente drin:

Liste x = .. // 4 Elemente
x.add(this); // 5 Elemente 
if (nach links) {
    rekursion nach links, zig Versuche // 20 Elemente
}
if (nach rechts) {
   // hier sollte es wieder die Liste mit 5 Elementen sein, sind aber 20 drin, schlecht
   rekursion nach rechts, zig Versuche
}

> Wenn ich die Funktion auf verschiedenen Feldern aufrufe müsste ich doch auch verschiede Listen haben oder?
nicht automatisch, aber immerhin das Ziel erkannt,

verwende:

                System.out.println("Aktuelle Länge: "+this.fieldList.size());
                fieldListGot = new ArrayList<Field>(fieldListGot);
                fieldListGot.add(this);
                this.setFieldList(fieldListGot);

dann hast du beide Probleme nicht mehr,
dafür zwar bisschen Arbeit, es geht auch schlauer performanter,
aber ein GHz-Prozessor will auch mal 2ms am Tag länger arbeiten

 

[Gurke1993]

Vielen Dank für die schnelle Hilfe! Zwar klappt noch nicht alles perfekt, aber das find ich jetzt alleine raus! Das dei Liste nicht automatisch als neue Liste gesetzt wird, war mir nicht bewusst.

Cheers
Gurke