Wegfindung gesucht ich bin ratlos

bountyboy

Hallo,
ich suche dringend eine einfache und kurze Möglichkeit in c++ um in einem feld den optimalen Weg vom Start bis zum Ziel zu finden.

Aufgabe ist es in einem per Zufall mit 0 und 1 belegten Feld[10][10] einen Weg zu ermitteln, wobei alle mit 0 belegten Einträge passierbar sind und alle anderen nicht.

Wie könnte ich das ohne grossen Aufwand schnell hinbekommen? Wenn jemand ein kleines Bsp. als Source hätte, wäre es nett, wenn er es mir posten könnte, danke.

H.L.T.O

such mal nach A*

bountyboy

nix verstehen könntest Du mir etwas mehr an Hinweisen geben? Danke

Blue-Tiger

ein sehr bekannter Wegfindungsalgorithmus ist A* (auch bekannt als "A Stern"), such einfach in Google danach. Ich glaub das wollte H.L.T.O dir sagen

Fischi

Für ein 10x10 Gitter und der Bemerkung "ohne größeren Aufwand" halte ich A* vielleicht für etwas übertrieben.

Man könnte das in etwa so machen, wenn es nur darum geht überhaupt einen Weg zu finden.

array karte_versperrt[10][10]
array markierung[10][10]
ziel(x,y)

suche_pfad(x,y)
{
if (x<0 || x>=10 || y<0 || y>=10)
    return KEIN_WEG;
if (karte_versperrt[x,y])
    return KEIN_WEG;
if (markierung[x,y])
    return KEIN_WEG;

markierung[x,y] = 1;

if ( (x,y) = (ziel) )
    return WEG_GEFUNDEN;

if ( suche_pfad[x+1,y] == WEG_GEFUNDEN ||
    suche_pfad[x  ,y+1] == WEG_GEFUNDEN ||
    suche_pfad[x-1,y] == WEG_GEFUNDEN ||
    suche_pfad[x  ,y-1]= = WEG_GEFUNDEN )
    {
    ausgabe(x,y);
    return WEG_GEFUNDEN;
    }
}

main()
{
lösche(markierung)
erstelle(karte_versperrt)
setzte (ziel)
suche_pfad(startposition)
}

[EDIT]
Für die suche nach dem kürzesten Weg, müsstest du geringe Modifikationen vornehmen, also nicht nur speichern ob Feld bereits besucht, sondern mit
welchen Aufwand man zu dem Feld kommt.
[/EDIT]

Viele Grüße
Fischi

bountyboy

also ich kann bei Google suchen wie ich will, ich finde den Alg. nicht und gleich gar nicht mit Bsp.

Wenn Ihr wisst, wo ich dazu etwas finden kann, dann wäre es schön, mir den Link zu posten

otze

*hust* das hört sich für mich sehr nach dem wettbewerb informatik an, aufgabe3 um genau zu sein, du musst die aufgabe rekursiv lösen

Blue-Tiger

komisch dass du nix findest

http://www.google.com/search?hl=en&lr=&ie=UTF-8&client=firefox-a&q="A+*"+Pathfinding&btnG=Search

TGGC

bountyboy schrieb:

also ich kann bei Google suchen wie ich will, ich finde den Alg. nicht und gleich gar nicht mit Bsp.

Je dümmer desto Obi?

Bye, TGGC Deine Unterstützung wird gebraucht!

life

struct Way
{
  std::list<D3DXVECTOR2*> wayPoints; //liste von allen punkten des weges
  int wayValue; //der wert des weges (je länger der weg, desto höher der wert)
}

Way* findShortestPath(int x, int y, int tiefe)
{
   if(x == zielX && y == zielY || tiefe >= maxTiefe)
   {
     Way* currentWay = new Way();
     currentWay->wayValue = 1;
     D3DXVECTOR2* currentPos = new D3DXVECTOR2(x,y);
     currentWay->wayPoints.push_back(currentPos);
     return currentWay;
   }
   else
   {
     Way* leftWay = NULL;
     if(x-1 >= 0 && myArray[x-1][y] == 0)
        leftWay = findShortestPath(x-1,y,tiefe+1); 
     Way* topWay = NULL;
     if(y+1 < 10 && myArray[x][y+1] == 0)
        topWay = findShortestPath(x,y+1,tiefe+1); 
     Way* rightWay = NULL;
     if(x+1 < 10 && myArray[x+1][y] == 0)
        rightWay = findShortestPath(x+1,y,tiefe+1); 
     Way* bottomWay = NULL;
     if(y-1 >= 0 && myArray[x][y-1] == 0)
        bottomWay = findShortestPath(x,y-1,tiefe+1); 

     if(leftWay != NULL && (topWay == NULL || leftWay->wayValue <= topWay->wayValue) && (rightWay == NULL || leftWay->wayValue <= rightWay->wayValue) && (bottomWay == NULL || leftWay->wayValue <= bottomWay->wayValue))
     {
       //der linke Weg ist der kürzeste von den 4 also den nehmen
       leftWay->wayPoints.push_back(new D3DXVECTOR2(x,y));
       leftWay->wayValue += 1;
       delete topWay;
       delete rightWay;
       delete bottomWay;
       return leftWay;
     }

    //andere Wege entsprechend 
   }  

}

btw. sollteste das noch getreu dem motto: "Wenn du weißt, dass der Weg schlecht ist, prüfe nicht, wie schlecht er ist." optimieren

Crabbe

otze schrieb:

*hust* das hört sich für mich sehr nach dem wettbewerb informatik an, aufgabe3 um genau zu sein, du musst die aufgabe rekursiv lösen

Genau der Gedanke kam mir auch als ich den Thread gelesen habe. Also vergiss es und denk selber nach. Das ist doch der Sinn der Sache.

Gruß Crabbe