3. Kürzester Weg

Kürzester Weg

  • M

    hier gibts zb ein paar informative sachen dazu:
    http://www-cs-students.stanford.edu/~amitp/gameprog.html

    0
  • B

    Ja aber wie mach ich sowas. Und dann noch möglichst auf kurzem Weg?!?!

    0
  • M

    das ist nicht so einfach wie du dir das wahrscheinlich vorstellst, dafür gibts keine "schnelle" erklärung würd ich mal so sagen...

    0
  • R

    muss es unbedingt der perfekteste weg sein? **g**

    ansontens reicht oft ne stumpfmethode, bei solchen dingen wie nicht U-formigen hindernissen.

    rapso->greets();

    0
  • D

    Mit der »Stumpfmethode« schlechthin, Backtracking, kommt man durch jedes Labyrinth.

    [»Perfekt« kann man nicht sinnvoll steigern, es sei den, Du bist in der Werbebranche tätig.]

    0
  • B

    Backtracking habe ich schon gemacht.
    Ist sehr interessant, finde ich.
    Nur ist es nicht besonders "resourcensparent" den ganzen Ozean abzufahren um von Amerika nach Afrika zu fahren...

    Ich benötige einfach eine Methode um den kürzesten Weg zu bestimmen. Das mit dem Pathfinding ist ebenfalls verdammt interessant, nur finde ich KEINE Tutorial auf deutsch/englisch mit verständlichem C - Code dabei.

    Danke
    cu para
    😃

    0
  • P

    Hi!
    http://www.google.de/search?hl=de&ie=UTF-8&oe=UTF-8&q=heuristische+Suche+Wege+C%2B%2B&meta=

    cu

    P84

    0
  • B

    Also ich habs jetzt (teilweise) gelößt.
    Was für ein Algorithmus das jetzt genau ist weiss ich nicht, und er ist mit Sicherheit kein Faz optimiert.

    Also ich erklär mal schnell:

    Man hat ein Feld, zB 5x5 Felder, mit 2 Punkten, A und B, und Hinternissen X.
    Leere Felder sind mit einem - gekennzeichnet

    - - - - -
- - X - - 
A - X - B 
- - X - - 
- - - - -

    Jetzt soll man von A schnellsmöglichst nach B kommen, also auf dem kürzesten Weg.
    Mein Prog setzt einen Knoten auf A und setzt dann Wegkosten. Ist das ganze Feld zugepflastert, bis dahin bin ich jetzt gekommen mit der Programmierei, dann sieht es so aus:

    2 3 4 5 6
1 2 0 6 7 
A 1 0 7 B 
1 2 0 6 7 
2 3 4 5 6

    (Dort wo vorher eine Wand war steht jetzt eine 0)

    So und der Witz daran ist jetzt, dass man nur vom Ziel, das ist der Buchstabe B zurückgehen muss. Auf B wäre ja die 8, die hab ich halt weggelassen zwecks Übersicht. Also fangen wir bei 8 an. Durchsuchen das komplette Feld und suchen eine "Wegkostenzahl" die 8-1 beträgt. Also irgentwas wo halt ne 7 steht. Welche 7 wir nehemn ist völlig egal. Jetzt gehts weiter: Man sucht sich die nächstkleine Zahl, nämlich die 6. Das ganze macht man solange, bis es die A, da wäre die "Wegkostenzahl" = 0, erreicht hat.

    Die Koordinaten, die man dabei findet, kennzeichnet man in der oberen Karte irgentwie, dann müsste es so aussehen:

    - * * * -
- * X * - 
A * X * B 
- - X - - 
- - - - -

    Dann hat man den kürzesten Weg!!

    Also das was mein Programm bisher kann ist nicht besonderes, wie gesagt mir fehlt noch der Teil mit dem markieren. Ich bekomme bis jetzt nur die Ausgabe der Wegkosten.

    Das sieht zum Beispiel so aus:

    021 020 019 018 017 016 015 014 013 012 013 012 013 014 015 016 017 018 019 020
020 019 018 017 016 015 014 013 012 011 000 011 012 013 014 015 016 017 018 019
019 018 017 016 015 014 013 012 011 010 009 010 011 012 013 014 015 016 017 018
018 017 016 015 014 013 012 011 010 009 008 009 010 011 012 013 014 015 016 017
017 016 015 014 013 012 011 010 009 008 007 008 009 010 011 012 013 014 015 016
016 015 014 013 012 011 010 009 008 007 006 007 008 009 010 011 012 013 014 015
015 014 013 012 011 010 009 008 007 006 005 006 007 008 009 010 011 012 013 014
014 013 012 011 010 009 008 007 006 005 004 005 006 007 008 009 010 011 012 013
013 012 011 010 009 008 007 006 005 004 003 004 005 006 007 008 009 010 011 012
012 011 010 009 008 007 006 005 004 003 002 003 004 005 006 007 008 009 010 011
011 010 009 008 007 006 005 004 003 002 001 002 003 004 005 006 007 008 009 010
012 011 010 009 008 007 006 005 004 003 002 003 004 005 006 007 008 009 010 011
013 012 011 010 009 008 007 006 005 004 003 004 005 006 007 008 009 010 011 012
014 013 012 011 010 009 008 007 006 005 004 005 006 007 008 009 010 011 012 013
015 014 013 012 011 010 009 008 007 006 005 006 007 008 009 010 011 012 013 014
016 015 014 013 012 011 010 009 008 007 006 007 008 009 010 011 012 013 014 015
017 016 015 014 013 012 011 010 009 008 007 008 009 010 011 012 013 014 015 016
018 017 016 015 014 013 012 011 010 009 000 009 010 011 012 013 014 015 016 017
019 018 017 016 015 014 013 012 011 010 000 010 011 012 013 014 015 016 017 018
020 019 018 017 016 015 014 013 012 011 012 011 012 013 014 015 016 017 018 019

    Hierbei war der Startknoten genau in der Mitte und das Feld betrug 20x20.

    Also ich hoffe ich habe das Prinzip von Pathfinding wenigstens einwenig verstanden. Sollte es nicht so sein, dann sagt es bitte. Ich wollte mit diesem Post einfach nur zeigen wie es auch möglich ist.

    Falls es jemanden interessiert, hier ist der Quelltext vom Programm, falls es halt jemand ausprobiern will.

    PS: Der Code ist 100% noch nicht optimiert, fehlerfrei, schnell, etc...

    CODE:
    settings.h

    // defines
#define             CX          20
#define             CY          20
#define             MAXTODO     CX*CY
#define             MAXWALL     5

    pathfinding.h

    // todo struct
typedef struct _todo{
    int x;
    int y;
    int c;
}TODO;

// knot struct
typedef struct _knot{
    bool    bSet;
    int     iCosts;
}KNOT;

// functions
void ClearToDo();
int GetFreeToDoID();
void AddToToDoList(int x, int y, int costs);
int HandleToDos();
void PrintToDoList();
void PrintCosts();
void MarkWay(int xposB, int yposB);

    main.cpp

    // includes
#include <stdio.h>
#include <stdlib.h>

#include "settings.h"
#include "pathfinding.h"

// public
char                cField[CX][CY] = {0};
static int          iKnots=0;   

// function to print out field
void PrintField()
{   
    // clrscreen
    //system("cls");

    // each 
    for(int y=0; y<CY; y++){
        for(int x=0; x<CX; x++)
            printf("%c", cField[x][y]);

        printf("\n");
    }

}

// function to fill field
void CreateField()
{
    // each 
    for(int x=0; x<CX; x++){
        for(int y=0; y<CY; y++)
            cField[x][y] = ' ';
    }

    // set start & target
    cField[CX-1][CY/2] = 'T';
    cField[   0][CY/2] = 'S';

    // walls
    cField[CX/2][1] = '*';
    cField[CX/2][CY-3] = '*';
    cField[CX/2][CY-2] = '*';
}

int main()
{
    // set up
    CreateField();
    ClearToDo();

    // add start knot to to-do list
    AddToToDoList(CX/2,CY/2,1);

    // handle all to-do's
    do{
        //getchar();
        //PrintField();
        //PrintToDoList();
        PrintCosts();

    }while(HandleToDos()==1);

    // fin
    printf("Fertig!\nSuche Weg...\n");
    PrintCosts();

    // quit
    getchar();
    return 0;
}

    pathfinding.cpp

    // includes
#include <stdio.h>
#include "settings.h"
#include "pathfinding.h"

void PrintField();

// private
static KNOT knot[CX][CY] = {0};
TODO    lstToDo[MAXTODO];
extern char             cField[CX][CY];

// function to check if knot set
bool bIsOK(int x, int y)
{
    // still set?
    if(knot[x][y].bSet)
        return false;

    // is there a wall?
    if(cField[x][y]=='*')
        return false;

    // all right
    return true;
}

// function to print out cost-field
void PrintCosts()
{   
    for(int y2=0; y2<CY; y2++){
        for(int x2=0; x2<CX; x2++)
            printf("%.3d ", knot[x2][y2].iCosts );

        //printf("\n");
    }
}

// function to clear to do list
void ClearToDo()
{
    // clear knots
    for(int k1=0; k1<CX; k1++){
        for(int k2=0; k2<CY; k2++)
            knot[k1][k2].bSet = false;
    }

    // clear it
    for(int t=0; t<MAXTODO; t++){
        lstToDo[t].x = -1;
        lstToDo[t].y = -1;
    }
}

// function to get a free to-do list id
int GetFreeToDoID()
{
    // search
    for(int t=0; t<MAXTODO; t++){
        if(lstToDo[t].x == -1 && lstToDo[t].y == -1)
            return t;
    }

    // nothing found
    return -1;
}

// function to add a knot to to-do list
void AddToToDoList(int x, int y, int costs)
{
    // check if entry still exists
    // in to-do list
    for(int t=0; t<MAXTODO; t++){
        if(lstToDo[t].x == x && lstToDo[t].y==y)
            return;
    }

    // get free id
    int id = GetFreeToDoID();

    // clear it
    lstToDo[id].x = x;
    lstToDo[id].y = y;
    lstToDo[id].c = costs;
}

// function to clear one point
void DeleteFromToDo(int x, int y)
{
    // clear it
    for(int t=0; t<MAXTODO; t++){
        if(lstToDo[t].x==x && lstToDo[t].y==y){
            lstToDo[t].x = -1;
            lstToDo[t].y = -1;
            lstToDo[t].c = 0;
        }
    }
}

// function to create knots
int CreateKnot(int x, int y, int costs)
{
    // set costs, etc
    knot[x][y].bSet = true;
    knot[x][y].iCosts = costs;

    // next knots
    if(x-1>=0 && bIsOK(x-1, y))AddToToDoList(x-1, y, costs+1);
    if(x+1<CX && bIsOK(x+1, y))AddToToDoList(x+1, y, costs+1);
    if(y-1>=0 && bIsOK(x, y-1))AddToToDoList(x, y-1, costs+1);
    if(y+1<CY && bIsOK(x, y+1))AddToToDoList(x, y+1, costs+1);

    // delete itself drom list
    DeleteFromToDo(x, y);

    return 1;
}

// function to mark the
// shortest was
void MarkWay(int xposB, int yposB)
{
    // private

    // we have to walk backwars
    // to the start

    // get cost of posB
    int cost = knot[0][0].iCosts;
    cField[xposB][yposB] = 'x';

    printf("cost = %d", cost);

    /*while(cost2!=1){
        PrintCosts();
        PrintField();
        getchar();
    }*/

}

// function to print out
// the to-do list
void PrintToDoList()
{
    printf("->> To-Do List\n");
    for(int t=0; t<MAXTODO; t++){
        if(lstToDo[t].x!=-1 && lstToDo[t].y!=-1){
            printf("\tK(%d / %d), %d\n", lstToDo[t].x, lstToDo[t].y, lstToDo[t].c);
        }
    }
}

// function to handle the points
// in to-do list
int HandleToDos()
{
    // private
    TODO buf[MAXTODO];

    int c1=0, c2=0;
    int t;

    // get count of lstToDos
    for(t=0; t<MAXTODO; t++){
        if(lstToDo[t].x!=-1 && lstToDo[t].y!=-1)
            c1++;
    }

    // lstToDos exists?
    if(c1>0){

        // all lstToDos
        for(t=0; t<MAXTODO; t++){
            // does knote exist?
            if(lstToDo[t].x!=-1 && lstToDo[t].y!=-1){
                buf[c2].x = lstToDo[t].x;
                buf[c2].y = lstToDo[t].y;
                buf[c2].c = lstToDo[t].c;

                c2++;
            }
        }

        // add all found knotes
        for(t=0; t<c1; t++)
            CreateKnot(buf[t].x, buf[t].y, buf[t].c);

        // success
        return 1;
    }

    // fin
    return 0;
}

    Viel Spass

    cu para
    😃

    0
  • A

    Du hast gesagt das man sich diagonal bewegen kann.
    Sieht der kürzete Weg dann nicht so aus?

    - - * - -
- * X * - 
A - X - B
- - X - - 
- - - - -

    Die Weg Kosten sehen dann so aus

    2 2 2 3 4
1 1 0 3 4
A 1 0 4 B
1 1 0 3 4
2 2 2 3 4

    Um damit auf den kürzten Weg zu kommen muss man den Punkt wählen dessen Nummer am niedrigsten ist

    [ Dieser Beitrag wurde am 14.03.2003 um 13:35 Uhr von Andorxor editiert. ]

    0
  • ?

    Ja man kann sich diagonal bewegen.
    Aber in meinem Beispiel und in meinem Programm, kann man sch bisher noch nicht diagonal bewegen.

    cu para
    😃

    PS: @Marc++us: Wäre es evtl. möglich mir ein Passwort zuzusenden mit dem ich wieder rein komm. Da schien was schief geloffen zu sein. Hab nach eMail Änderung n neues bekommen und konnte es irgentwie nicht ändern und hab dann das alte schon wieder verlegt, sorry!
    Also wäre da was zu machen?? Bittte!

    cu para
    😃

    0
Anmelden zum Antworten