Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Ansatz zur Wegfindung

Werbeanzeige

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

21

03.04.2013, 21:05

Zitat von »Schorsch«

Als Tipp, wenn ein Algorithmus dir einen Pfad rückwärts zurück gibt, so kannst du den Algorithmus auch einfach verdreht ausführen. Damit meine ich, dass du Start und Ziel einfach vertauschst. So bekommst du den Weg direkt in richtiger Reihenfolge.
Auch ein guter Tipp, ich hätte es sonst einfach von Start zum Ziel gemacht und dann mit ner extra Funktion das Array umsortiert, so ist es aber einfacher, ich fange beim Ziel an und lasse den Weg zum Start berechnen.

Mein Code lässt sich aber nicht wirklich ausführen, ich bekomme immer eine "NullPointerExeption" in der Floodfill-Methode. Weiß jemand woran das liegen kann, logische Fehler schein der Code sonst nicht zu haben, die IDE findet zumindest nichts...

Ist es evtl. ein Problem, dass sich die Methode selbst mehrmals aufruft? Die verwendete Sprache wäre Java.

EternalPain

Frischling

Beiträge: 87

  • Private Nachricht senden

22

04.04.2013, 16:13

Zuerst würde ich prüfen ob es nicht ein ähnliches Problem wie hier gibt: Wert außerhalb des Arrays, trotz Überprüfung?

Kenne mich mit Java, der Stackgrösse und dessen Fehlermeldungen nicht aus. NullPointerExeption ist ja wohl eigentlich ein zugriff auf einen nicht definierten speicherbereich oder evl. ein fehlerhafter zugriff... prüfst Du in deiner Floodfill-Methode auch die Position vor dem Zugriff <0 >width/height?

Sollte es am Stack liegen, versuch es Probehalber mal mit einer kleineren Map Und/Oder lass Dir zählen wie oft die Funktion aufgerufen wird bis es beendet...

Wenn es am stack liegt, könnte man verschiedenes versuchen... am sinnvollsten aber wäre eine iterative Funktion...

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

23

04.04.2013, 16:34

Zitat von »MitgliedXYZ«

Mein Code lässt sich aber nicht wirklich ausführen, ich bekomme immer eine "NullPointerExeption" in der Floodfill-Methode. Weiß jemand woran das liegen kann, logische Fehler schein der Code sonst nicht zu haben
Meine Vermutung: das liegt daran das der Code Fehler hat, weil du dich nicht an die teils ausfuehrlichen Erklaerungen hier gehalten hast.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

24

04.04.2013, 17:27

Zitat von »TGGC«

Zitat von »MitgliedXYZ«

Mein Code lässt sich aber nicht wirklich ausführen, ich bekomme immer eine "NullPointerExeption" in der Floodfill-Methode. Weiß jemand woran das liegen kann, logische Fehler schein der Code sonst nicht zu haben
Meine Vermutung: das liegt daran das der Code Fehler hat, weil du dich nicht an die teils ausfuehrlichen Erklaerungen hier gehalten hast.
Ich habe mich weitgehenst an die Beschreibung gehalten, die IDE die ich benutzen muss bietet aber so gut wie keine Funktionen zum Debuggen...
Ohne das ich meine Code zeige wäre es eh schwierig gewesen, Fehler zu finden, hier also noch einmal etwas ausführlicher:

Ich rufe in der Hauptmethode die Methode Floodfill auf.
Dann lasse ich in der Hauptmethode eine Schleife ausführen, die sich so lange wiederholt, bis ein bestimmtes bool Array auf true gesetzt ist. Die Schleife ist nötig, da ich erst weitermachen kann, wenn Array2 gefüllt ist.
Die Methode Floodfill sieht bei mir nun so aus:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  public void Floodfill(int x, int y, int n)

    {
       if (Array1[x][y] == 0 && Array2[x][y] > n && x != xZiel && y != yZiel)
        {
            Array2[x][y] = n;
            if (x > 0)
            Floodfill(x-1, y, n+1);
            if (x < 19)
            Floodfill(x+1, y, n+1);
            if (y > 0)
            Floodfill(x, y-1, n+1);
            if (y < 19)
            Floodfill(x, y+1, n+1);
        }
        if (x == xZiel && y == yZiel)
        {
            Bereit = true;
        }
    }


Edit:
Wahrscheinlich ist das Problem meine Endlosschleife, die auf "Bereit == true" wartet, aber woher sollte man sonst wissen, wann denn die Methode Floodfill fertig ist, außer wenn man eine für alle Methoden zugängliche Variable benutzt?
Es wäre nicht zufällig möglich Floodfill ohne eigene Methode, sondern mit Schleifen, etc. auszuführen?
Oder könnte es ein Problem sein das beide Methoden theoretisch gleichzeitig Zugriff auf beide Arrays und die Bool Variable haben?

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »MitgliedXYZ« (04.04.2013, 18:07)

EternalPain

Frischling

Beiträge: 87

  • Private Nachricht senden

25

04.04.2013, 18:21

Alle Antworten kannst Du bereits hier im Thread nachlesen....

vielleicht hilft Dir ein Beispiel:
Meine Pathfind Routine, andere Sprache, ähnliches Prinzip:

Quellcode

 
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

Function tMaze.getPath(byval fromX as Integer, byval fromY as Integer, byval targetX as Integer, byval targetY as Integer) as Integer ptr
    Dim PathMap    as Integer ptr 
    Dim PathList   as Integer ptr
    Dim PathLength as Integer 
    Dim frompos    as Integer     = fromX+(fromY*MazeW)
    Dim targetpos  as Integer     = targetX+(targetY*MazeW)
    Dim mappos     as Integer
    Dim nearestpos as Integer
    Dim distance   as Single
    Dim distanceL  as Single      = MazeW*MazeH
    Dim fillList   as tList
    
    Dim as integer tX,tY
    
    If (frompos < 0) or (frompos > ((MazeW*MazeH)-1)) Then return 0
    
    fillList.AddEntry(frompos)
    PathMap = NEW Integer[MazeW*MazeH]
    
    While fillList.FirstEntry
        mappos = fillList.FirstEntry -> EntryValue
        fillList.DelEntry(fillList.FirstEntry)
        
        PathMap[mappos] += 1 'Set PathCost
        
        tX = mappos mod MazeW : tY = mappos \ MazeW
        
        distance = Distance2(tX,tY,targetX,targetY)
        If (distance < distanceL) Then
            distanceL  = distance 
            nearestpos = mappos
        End If
        
        If (mappos = targetpos) then exit while
        
        If (tX > 0)         andalso (MazeP[mappos-1]     < MazeWall) andalso (PathMap[mappos-1]     = 0) Then fillList.AddEntry(mappos-1)     : PathMap[mappos-1]     = PathMap[mappos]
        If (tY > 0)         andalso (MazeP[mappos-MazeW] < MazeWall) andalso (PathMap[mappos-MazeW] = 0) Then fillList.AddEntry(mappos-MazeW) : PathMap[mappos-MazeW] = PathMap[mappos]
        If (tX < (MazeW-1)) andalso (MazeP[mappos+1]     < MazeWall) andalso (PathMap[mappos+1]     = 0) Then fillList.AddEntry(mappos+1)     : PathMap[mappos+1]     = PathMap[mappos]
        If (tY < (MazeH-1)) andalso (MazeP[mappos+MazeW] < MazeWall) andalso (PathMap[mappos+MazeW] = 0) Then fillList.AddEntry(mappos+MazeW) : PathMap[mappos+MazeW] = PathMap[mappos]
    Wend
    
    fillList.DestroyList()
    
    PathLength                    = PathMap[nearestpos]
    PathList                      = New Integer[PathLength+1]
    PathList[0]                   = PathMap[nearestpos]

    Do
        mappos               = nearestpos
        PathLength           = PathMap[mappos]
        PathList[PathLength] = mappos
        If (PathLength = 1) Then Exit Do
        
        tX = mappos mod MazeW : tY = mappos \ MazeW
        
        If (tX > 0)         andalso (PathMap[mappos-1]     = PathLength-1) Then nearestpos -= 1     : continue do
        If (tY > 0)         andalso (PathMap[mappos-MazeW] = PathLength-1) Then nearestpos -= MazeW : continue do
        If (tX < (MazeW-1)) andalso (PathMap[mappos+1]     = PathLength-1) Then nearestpos += 1     : continue do
        If (tY < (MazeW-1)) andalso (PathMap[mappos+MazeW] = PathLength-1) Then nearestpos += MazeW : continue do
        exit do
    Loop
    
    Delete[] PathMap
    
    return PathList
End Function


Die Funktion gibt auch eine Liste zurück wenn Target gar nicht existiert oder erreichbar ist. Dann wird der Weg zum am nächsten erreichbaren Feld in der nähe des Ziels zurückgegeben...
Machte bei mir insofern sinn da ich per Mausklicks durch ein Labyrinth laufe, klickt man auf eine Mauer die nicht begehbar/erreiachbar ist, laeuft man so nur zum feld das am dichtesten dran ist...

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

26

04.04.2013, 20:11

Mhh, danke schon mal, aber ich komme trotzdem nicht weiter...

Meine Hauptmethode enthält nun unter anderem folgenden Code:

(Array1 speichert alle Objekte, 0 bedeutet freie Zelle, etc., Array2 speichert die Entfernungen vom Ziel.)
Array1, Array2, xZiel, yZiel und Bereit sind public und für alle Methoden zugreifbar

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

   for (int i3 = 0; i3 <= 19; i3++)
    {
        for (int i4 = 0; i4 <= 19; i4++)
        {
            if (i3 <= 19 && i4 <= 19 && i3 >= 0 && i4 >= 0)
            {
            Array2[i3][i4] = 999;//Alle Entfernungen auf einen unmöglich hohen Wert setzen
            }
        }
    }
    Bereit = false;

    Floodfill(X, Y, 0);
        do {
    } while (Bereit = false);


Danach würde die weiterverarbeitung des Array2 kommen.

Und so sieht noch mal meine Floodfill-Methode aus:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 public void Floodfill(int x, int y, int n)
    {
       if (Array1[x][y] == 0 && Array2[x][y] > n && x != xZiel && y != yZiel && n < 10)
        {
            Array2[x][y] = n;
            if (x > 0)
            Floodfill(x-1, y, n+1);
            if (x < 19)
            Floodfill(x+1, y, n+1);
            if (y > 0)
            Floodfill(x, y-1, n+1);
            if (y < 19)
            Floodfill(x, y+1, n+1);
        }
        if (x == xZiel && y == yZiel)
        {
            Bereit = true;
        }
    }


Das Problem ist doch, dass ich nicht weiß wann die Floodfill-Methode fertig ist, da sie selbst ja dauernd neue Methoden aufruft. Wie soll da meine Hauptmethode wissen, wann sie weitermachen soll? Oder liegt der Fehler noch woanders? Wenn es eine Floodfill-Variante ohne "selbstaufrufende" Methode gäbe, also nur mit Schleifen, etc. würde dieses Problem nicht entstehen, da alles nach einander verarbeitet werden könnte...

EternalPain

Frischling

Beiträge: 87

  • Private Nachricht senden

27

04.04.2013, 20:16

Wurde mehrfach erwähnt und verlinkt.... ITERATIV! Genauso wie ich es auch in meiner funktion nutze... (auch wenn ich es bei mir wegen des begrenzten Stacks so umgesetzt habe)

Das zeigt das Du hier gar nichts liest...

http://de.wikipedia.org/wiki/Floodfill

da steht alles dazu...

dafür ist in meiner Funktion eine LinkedList implementiert.
Diese speichert die noch abzusuchenden Positionen anstatt die Funktion noch einmal aufzurufen... Solange die Liste einträge enthält wird weitergesucht...
in einer Zeile darüber habe ich den 'notausgang' wenn das Ziel erreicht ist, weitere abbarbeit überspringen...

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

28

04.04.2013, 20:17

Zitat von »MitgliedXYZ«

aber woher sollte man sonst wissen, wann denn die Methode Floodfill fertig ist, außer wenn man eine für alle Methoden zugängliche Variable benutzt?
Mit einem Rueckgabewert?

Und wen du keinen Debugger hast, wie waere es ein Logfile zu schreiben?
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

29

05.04.2013, 12:40

Und für Java kann man doch Eclipse benutzen. Bei Eclipse ist doch ein brauchbarer Debugger mitgeliefert. Das solltest du dir bei deinem privaten Rechner doch installieren können um es zu testen. Auch eine rekursive Funktion muss abbrechen. Du musst überprüfen, ob dein Index ausserhalb des Arraybereichs liegt. Schon besucht Zellen werden nicht weiter expandiert. Wenn du also von deinem Startpunkt zu jedem anderen Punkt den kürzesten Weg bestimmt hast, bricht der Algorithmus von allein ab. Wenn er deinen Zielknoten zwischenzeitlich nicht gefunden hat, ist er also nicht erreichbar. Anstatt die Werte auf 999 für den Start zu setzen ist es sinnvoller "Integer.MAX_VALUE" zu benutzen. Eine iterative Version ist natürlich auch möglich. Jede rekursive Funktion lässt sich auch iterativ erstellen. Das löst dir dein Problem halt nur nicht;)
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

30

05.04.2013, 13:43

Ok, hab es nun mal mit einer I iterativen-Methode versucht, die mir das gefüllte Array mit den Entfernungswerten zurück gibt. Leider enthält jedes Feld nur den Wert 999 (ja, int.max wäre wohl besser, aber wenn ich alle Felder durchlaufen wollen würde, wären nur 400 Schritte notwendig, sogesehen würde als Startwert für jedes Kästchen schon 401 langen):

Quellcode

 
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
96
97
98
99
100
101
102
103
104
105
106

 public int[][] Floodfill(int x, int y, int n, int[][] Array1, int xZiel, int yZiel)

    {

    int[][] Array2 = new int[20][20];

    for (int a = 0; a <= 19; a++)

    {

        for (int b = 0; b <= 19; b++)

        {

            if (a <= 19 &&  b <= 19 && b>= 0 && b >= 0)

            {

            Array2[a][b] = 999;

            }

        }

    }

    
      String Wert;

      String[] WertBereich;

      int i = 0;

      int i2 = 0;

      Stack<String> stack = new Stack<String>();

      stack.push(x + "," + y + "," + n);

      while(!stack.isEmpty()) {

         Element = stack.pop();

         ElementTeile = Element.split(",");

         x = Integer.parseInt(ElementTeile[0]);

         y = Integer.parseInt(ElementTeile[1]);

         n = Integer.parseInt(ElementTeile[2]);

            if (Array1[x][y] == 0 && Array2[x][y] > n && x != xZiel && y != yZiel && n < 15)

            {

                Array2[x][y] = n;

                i = n + 1;

                if (x > 0)

                {

                i2 = x - 1;

                stack.push(i2 + "," + y + "," + i);

                }

                if (x < 19)

                {

                i2 = x + 1;

                stack.push(i2 + "," + y + "," + i);

                }

                if (y > 0)

                {

                i2 = y - 1;

                stack.push(x + "," + i2 + "," + i);

                }

                if (y < 19)

                {

                i2 = y + 1;

                stack.push(x + "," + i2 + "," + i);

                }

             } 

        }

        return Array2;

    }


Kann es an der Funktion liegen?

Werbeanzeige

Ähnliche Themen