A * zu Move


NudelMaus

Grünschnabel
Halli Hallo,

Ich habe ein Problem, und zwar weiss ich leider nicht wie man es schafft einen Spieler einen Pfad entlang gehen zu lassen :(
Der A* Algorithmus gibt mir ja den Pfad in Coordinaten der Kacheln zurück, wie schafft man es das ganze dann so umzuwandeln damit der Spieler auch den Pfad folgt,

Der naive versuch es in einer for schleife durchlaufen zu lassen hat leider nicht das gewünschte ergebnis gebracht.

std::vector<std::pair<int, int>> coordinate; // Vector mit den Koordinaten des zurückgegebenen Pfades (z.B 0 , 0 | 0 , 1)

for (unsigned int i = 0; i < coordinate.size(); i++) {
player.setPosition(coordinate.first * TileSize, coordinate.second * TileSize);
}
Da springt mir der Player sofort auf die Ziel Kachel.

Villeicht kann mir jemand einen Tipp geben, das würde mich sehr freuen
Mfg
 

Technipion

Erfahrenes Mitglied
Zuerst mal: Bitte poste deinen Code in Code-Tags (dafür auf Einfügen -> Code klicken). So bekommt man ja Augenkrebs.

Auch dürfte der Code, soweit ich das entziffern kann, gar nicht compilieren. Du hast einen std::vector<...> coordinate und versuchst auf coordinate.first und coordinate.second zuzugreifen, diese Felder existieren aber gar nicht! Hast du vergessen einen Index anzugeben? coordinate[i].first

Gruß Technipion
 

Jennesta

Erfahrenes Mitglied
Ohne den Rest des Codes und die Zusammenhänge zu kennen, wird es etwas schwierig die genauen Gründe herauszufinden.

Wenn deine Funktion setPosition aber lediglich die neue Position setzt, nichts zeichnet und keinen Delay hat, dann wird die Schleife vermutlich in sehr großer Geschwindigkeit durchiteriert und du kannst aufgrundd er Geschwindigkeit nur die Endposition sehen.

Aber wie gesagt, das ist nur eine Vermutung.
 

NudelMaus

Grünschnabel
Vielen Dank für die schnelle Antworten ..

Erst einmal tut es mir leid @Technipion, ich bin neu im Forum und wusste das nicht mit dem Code einfügen .. Und jap ich habe den Index vergessen also hier noch einmal richtig ..

C++:
std::vector<std::pair<int, int>> coordinate // Speichert den zurück gegebenen Pfad z.B 0,0 0,1
    
    for (unsigned int i = 0; i < coordinate.size(); i++){
        player.setPosition(coordinate[i].fist * tilesize, coordinate[i].second * tilesize);
    }
Und ja @Jennesta das habe ich mir auch gedacht aber leider weiss ich nicht wie ich es schaffe ein delay zu machen. Villeicht hat jemand eine idee oder einen Tipp.

Und leider kann ich meinen A* code noch nicht posten da ich mitten im Umzug bin und mein Internet erst diese Woche kommen soll, darum bin ich gezwungen alles hier mit dem Handy zu posten :(

Trotzdem bin ich sehr dankbar für jeden vorschlag :)

Mfg
 

Technipion

Erfahrenes Mitglied
Und ja @Jennesta das habe ich mir auch gedacht aber leider weiss ich nicht wie ich es schaffe ein delay zu machen. Villeicht hat jemand eine idee oder einen Tipp.

Und leider kann ich meinen A* code noch nicht posten da ich mitten im Umzug bin und mein Internet erst diese Woche kommen soll,
Ja, das ist jetzt doof. Weil ohne den Rest des Codes zu kennen, können wir ja nicht wissen wie man in deinem Programm einen delay einbaut. Und wenn du einfach ein
std::this_thread::sleep_for (std::chrono::milliseconds(16)); in die for-Schleife packst wird vermutlich das ganze Programm aufgehängt :(

Also ich befürchte hier geht's erst weiter wenn wir den Rest des Codes haben.

Gruß Technipion

PS: Du kannst es ja mal mit Tethering versuchen?
 

NudelMaus

Grünschnabel
Oki, vielen Dank für die Antwort, ich werde mich schnellst möglich wieder melden wenn mein Internet da ist...

Aber vielen vielen Dank für die Antworten
Mit freundlichen Grüßen
 

NudelMaus

Grünschnabel
Oki da es noch länge dauern wird bis dieser nette Technicker mal kommt, habe ich im Internt einen ahnlichen code gefunden..

Villeicht könnt ihr mir damit helfen :)

C++:
brightness_4
// A C++ Program to implement A* Search Algorithm
#include<bits/stdc++.h>
using namespace std;
 
#define ROW 9
#define COL 10
 
// Creating a shortcut for int, int pair type
typedef pair<int, int> Pair;
 
// Creating a shortcut for pair<int, pair<int, int>> type
typedef pair<double, pair<int, int>> pPair;
 
// A structure to hold the neccesary parameters
struct cell
{
    // Row and Column index of its parent
    // Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
    int parent_i, parent_j;
    // f = g + h
    double f, g, h;
};
 
// A Utility Function to check whether given cell (row, col)
// is a valid cell or not.
bool isValid(int row, int col)
{
    // Returns true if row number and column number
    // is in range
    return (row >= 0) && (row < ROW) &&
           (col >= 0) && (col < COL);
}
 
// A Utility Function to check whether the given cell is
// blocked or not
bool isUnBlocked(int grid[][COL], int row, int col)
{
    // Returns true if the cell is not blocked else false
    if (grid[row][col] == 1)
        return (true);
    else
        return (false);
}
 
// A Utility Function to check whether destination cell has
// been reached or not
bool isDestination(int row, int col, Pair dest)
{
    if (row == dest.first && col == dest.second)
        return (true);
    else
        return (false);
}
 
// A Utility Function to calculate the 'h' heuristics.
double calculateHValue(int row, int col, Pair dest)
{
    // Return using the distance formula
    return ((double)sqrt ((row-dest.first)*(row-dest.first)
                          + (col-dest.second)*(col-dest.second)));
}
 
// A Utility Function to trace the path from the source
// to destination
void tracePath(cell cellDetails[][COL], Pair dest)
{
    printf ("\nThe Path is ");
    int row = dest.first;
    int col = dest.second;
 
    stack<Pair> Path;
 
    while (!(cellDetails[row][col].parent_i == row
             && cellDetails[row][col].parent_j == col ))
    {
        Path.push (make_pair (row, col));
        int temp_row = cellDetails[row][col].parent_i;
        int temp_col = cellDetails[row][col].parent_j;
        row = temp_row;
        col = temp_col;
    }
 
    Path.push (make_pair (row, col));
    while (!Path.empty())
    {
        pair<int,int> p = Path.top();
        Path.pop();
        printf("-> (%d,%d) ",p.first,p.second);
    }
 
    return;
}
 
// A Function to find the shortest path between
// a given source cell to a destination cell according
// to A* Search Algorithm
void aStarSearch(int grid[][COL], Pair src, Pair dest)
{
    // If the source is out of range
    if (isValid (src.first, src.second) == false)
    {
        printf ("Source is invalid\n");
        return;
    }
 
    // If the destination is out of range
    if (isValid (dest.first, dest.second) == false)
    {
        printf ("Destination is invalid\n");
        return;
    }
 
    // Either the source or the destination is blocked
    if (isUnBlocked(grid, src.first, src.second) == false ||
            isUnBlocked(grid, dest.first, dest.second) == false)
    {
        printf ("Source or the destination is blocked\n");
        return;
    }
 
    // If the destination cell is the same as source cell
    if (isDestination(src.first, src.second, dest) == true)
    {
        printf ("We are already at the destination\n");
        return;
    }
 
    // Create a closed list and initialise it to false which means
    // that no cell has been included yet
    // This closed list is implemented as a boolean 2D array
    bool closedList[ROW][COL];
    memset(closedList, false, sizeof (closedList));
 
    // Declare a 2D array of structure to hold the details
    //of that cell
    cell cellDetails[ROW][COL];
 
    int i, j;
 
    for (i=0; i<ROW; i++)
    {
        for (j=0; j<COL; j++)
        {
            cellDetails[i][j].f = FLT_MAX;
            cellDetails[i][j].g = FLT_MAX;
            cellDetails[i][j].h = FLT_MAX;
            cellDetails[i][j].parent_i = -1;
            cellDetails[i][j].parent_j = -1;
        }
    }
 
    // Initialising the parameters of the starting node
    i = src.first, j = src.second;
    cellDetails[i][j].f = 0.0;
    cellDetails[i][j].g = 0.0;
    cellDetails[i][j].h = 0.0;
    cellDetails[i][j].parent_i = i;
    cellDetails[i][j].parent_j = j;
 
    /*
     Create an open list having information as-
     <f, <i, j>>
     where f = g + h,
     and i, j are the row and column index of that cell
     Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
     This open list is implenented as a set of pair of pair.*/
    set<pPair> openList;
 
    // Put the starting cell on the open list and set its
    // 'f' as 0
    openList.insert(make_pair (0.0, make_pair (i, j)));
 
    // We set this boolean value as false as initially
    // the destination is not reached.
    bool foundDest = false;
 
    while (!openList.empty())
    {
        pPair p = *openList.begin();
 
        // Remove this vertex from the open list
        openList.erase(openList.begin());
 
        // Add this vertex to the closed list
        i = p.second.first;
        j = p.second.second;
        closedList[i][j] = true;
      
       /*
        Generating all the 8 successor of this cell
 
            N.W   N   N.E
              \   |   /
               \  |  /
            W----Cell----E
                 / | \
               /   |  \
            S.W    S   S.E
 
        Cell-->Popped Cell (i, j)
        N -->  North       (i-1, j)
        S -->  South       (i+1, j)
        E -->  East        (i, j+1)
        W -->  West           (i, j-1)
        N.E--> North-East  (i-1, j+1)
        N.W--> North-West  (i-1, j-1)
        S.E--> South-East  (i+1, j+1)
        S.W--> South-West  (i+1, j-1)*/
 
        // To store the 'g', 'h' and 'f' of the 8 successors
        double gNew, hNew, fNew;
 
        //----------- 1st Successor (North) ------------
 
        // Only process this cell if this is a valid one
        if (isValid(i-1, j) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i-1, j, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i-1][j].parent_i = i;
                cellDetails[i-1][j].parent_j = j;
                printf ("The destination cell is found\n");
                tracePath (cellDetails, dest);
                foundDest = true;
                return;
            }
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i-1][j] == false &&
                     isUnBlocked(grid, i-1, j) == true)
            {
                gNew = cellDetails[i][j].g + 1.0;
                hNew = calculateHValue (i-1, j, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i-1][j].f == FLT_MAX ||
                        cellDetails[i-1][j].f > fNew)
                {
                    openList.insert( make_pair(fNew,
                                               make_pair(i-1, j)));
 
                    // Update the details of this cell
                    cellDetails[i-1][j].f = fNew;
                    cellDetails[i-1][j].g = gNew;
                    cellDetails[i-1][j].h = hNew;
                    cellDetails[i-1][j].parent_i = i;
                    cellDetails[i-1][j].parent_j = j;
                }
            }
        }
 
        //----------- 2nd Successor (South) ------------
 
        // Only process this cell if this is a valid one
        if (isValid(i+1, j) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i+1, j, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i+1][j].parent_i = i;
                cellDetails[i+1][j].parent_j = j;
                printf("The destination cell is found\n");
                tracePath(cellDetails, dest);
                foundDest = true;
                return;
            }
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i+1][j] == false &&
                     isUnBlocked(grid, i+1, j) == true)
            {
                gNew = cellDetails[i][j].g + 1.0;
                hNew = calculateHValue(i+1, j, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i+1][j].f == FLT_MAX ||
                        cellDetails[i+1][j].f > fNew)
                {
                    openList.insert( make_pair (fNew, make_pair (i+1, j)));
                    // Update the details of this cell
                    cellDetails[i+1][j].f = fNew;
                    cellDetails[i+1][j].g = gNew;
                    cellDetails[i+1][j].h = hNew;
                    cellDetails[i+1][j].parent_i = i;
                    cellDetails[i+1][j].parent_j = j;
                }
            }
        }
 
        //----------- 3rd Successor (East) ------------
 
        // Only process this cell if this is a valid one
        if (isValid (i, j+1) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i, j+1, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i][j+1].parent_i = i;
                cellDetails[i][j+1].parent_j = j;
                printf("The destination cell is found\n");
                tracePath(cellDetails, dest);
                foundDest = true;
                return;
            }
 
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i][j+1] == false &&
                     isUnBlocked (grid, i, j+1) == true)
            {
                gNew = cellDetails[i][j].g + 1.0;
                hNew = calculateHValue (i, j+1, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i][j+1].f == FLT_MAX ||
                        cellDetails[i][j+1].f > fNew)
                {
                    openList.insert( make_pair(fNew,
                                        make_pair (i, j+1)));
 
                    // Update the details of this cell
                    cellDetails[i][j+1].f = fNew;
                    cellDetails[i][j+1].g = gNew;
                    cellDetails[i][j+1].h = hNew;
                    cellDetails[i][j+1].parent_i = i;
                    cellDetails[i][j+1].parent_j = j;
                }
            }
        }
 
        //----------- 4th Successor (West) ------------
 
        // Only process this cell if this is a valid one
        if (isValid(i, j-1) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i, j-1, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i][j-1].parent_i = i;
                cellDetails[i][j-1].parent_j = j;
                printf("The destination cell is found\n");
                tracePath(cellDetails, dest);
                foundDest = true;
                return;
            }
 
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i][j-1] == false &&
                     isUnBlocked(grid, i, j-1) == true)
            {
                gNew = cellDetails[i][j].g + 1.0;
                hNew = calculateHValue(i, j-1, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i][j-1].f == FLT_MAX ||
                        cellDetails[i][j-1].f > fNew)
                {
                    openList.insert( make_pair (fNew,
                                          make_pair (i, j-1)));
 
                    // Update the details of this cell
                    cellDetails[i][j-1].f = fNew;
                    cellDetails[i][j-1].g = gNew;
                    cellDetails[i][j-1].h = hNew;
                    cellDetails[i][j-1].parent_i = i;
                    cellDetails[i][j-1].parent_j = j;
                }
            }
        }
 
        //----------- 5th Successor (North-East) ------------
 
        // Only process this cell if this is a valid one
        if (isValid(i-1, j+1) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i-1, j+1, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i-1][j+1].parent_i = i;
                cellDetails[i-1][j+1].parent_j = j;
                printf ("The destination cell is found\n");
                tracePath (cellDetails, dest);
                foundDest = true;
                return;
            }
 
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i-1][j+1] == false &&
                     isUnBlocked(grid, i-1, j+1) == true)
            {
                gNew = cellDetails[i][j].g + 1.414;
                hNew = calculateHValue(i-1, j+1, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i-1][j+1].f == FLT_MAX ||
                        cellDetails[i-1][j+1].f > fNew)
                {
                    openList.insert( make_pair (fNew, 
                                    make_pair(i-1, j+1)));
 
                    // Update the details of this cell
                    cellDetails[i-1][j+1].f = fNew;
                    cellDetails[i-1][j+1].g = gNew;
                    cellDetails[i-1][j+1].h = hNew;
                    cellDetails[i-1][j+1].parent_i = i;
                    cellDetails[i-1][j+1].parent_j = j;
                }
            }
        }
 
        //----------- 6th Successor (North-West) ------------
 
        // Only process this cell if this is a valid one
        if (isValid (i-1, j-1) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination (i-1, j-1, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i-1][j-1].parent_i = i;
                cellDetails[i-1][j-1].parent_j = j;
                printf ("The destination cell is found\n");
                tracePath (cellDetails, dest);
                foundDest = true;
                return;
            }
 
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i-1][j-1] == false &&
                     isUnBlocked(grid, i-1, j-1) == true)
            {
                gNew = cellDetails[i][j].g + 1.414;
                hNew = calculateHValue(i-1, j-1, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i-1][j-1].f == FLT_MAX ||
                        cellDetails[i-1][j-1].f > fNew)
                {
                    openList.insert( make_pair (fNew, make_pair (i-1, j-1)));
                    // Update the details of this cell
                    cellDetails[i-1][j-1].f = fNew;
                    cellDetails[i-1][j-1].g = gNew;
                    cellDetails[i-1][j-1].h = hNew;
                    cellDetails[i-1][j-1].parent_i = i;
                    cellDetails[i-1][j-1].parent_j = j;
                }
            }
        }
 
        //----------- 7th Successor (South-East) ------------
 
        // Only process this cell if this is a valid one
        if (isValid(i+1, j+1) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i+1, j+1, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i+1][j+1].parent_i = i;
                cellDetails[i+1][j+1].parent_j = j;
                printf ("The destination cell is found\n");
                tracePath (cellDetails, dest);
                foundDest = true;
                return;
            }
 
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i+1][j+1] == false &&
                     isUnBlocked(grid, i+1, j+1) == true)
            {
                gNew = cellDetails[i][j].g + 1.414;
                hNew = calculateHValue(i+1, j+1, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i+1][j+1].f == FLT_MAX ||
                        cellDetails[i+1][j+1].f > fNew)
                {
                    openList.insert(make_pair(fNew, 
                                        make_pair (i+1, j+1)));
 
                    // Update the details of this cell
                    cellDetails[i+1][j+1].f = fNew;
                    cellDetails[i+1][j+1].g = gNew;
                    cellDetails[i+1][j+1].h = hNew;
                    cellDetails[i+1][j+1].parent_i = i;
                    cellDetails[i+1][j+1].parent_j = j;
                }
            }
        }
 
        //----------- 8th Successor (South-West) ------------
 
        // Only process this cell if this is a valid one
        if (isValid (i+1, j-1) == true)
        {
            // If the destination cell is the same as the
            // current successor
            if (isDestination(i+1, j-1, dest) == true)
            {
                // Set the Parent of the destination cell
                cellDetails[i+1][j-1].parent_i = i;
                cellDetails[i+1][j-1].parent_j = j;
                printf("The destination cell is found\n");
                tracePath(cellDetails, dest);
                foundDest = true;
                return;
            }
 
            // If the successor is already on the closed
            // list or if it is blocked, then ignore it.
            // Else do the following
            else if (closedList[i+1][j-1] == false &&
                     isUnBlocked(grid, i+1, j-1) == true)
            {
                gNew = cellDetails[i][j].g + 1.414;
                hNew = calculateHValue(i+1, j-1, dest);
                fNew = gNew + hNew;
 
                // If it isn’t on the open list, add it to
                // the open list. Make the current square
                // the parent of this square. Record the
                // f, g, and h costs of the square cell
                //                OR
                // If it is on the open list already, check
                // to see if this path to that square is better,
                // using 'f' cost as the measure.
                if (cellDetails[i+1][j-1].f == FLT_MAX ||
                        cellDetails[i+1][j-1].f > fNew)
                {
                    openList.insert(make_pair(fNew, 
                                        make_pair(i+1, j-1)));
 
                    // Update the details of this cell
                    cellDetails[i+1][j-1].f = fNew;
                    cellDetails[i+1][j-1].g = gNew;
                    cellDetails[i+1][j-1].h = hNew;
                    cellDetails[i+1][j-1].parent_i = i;
                    cellDetails[i+1][j-1].parent_j = j;
                }
            }
        }
    }
 
    // When the destination cell is not found and the open
    // list is empty, then we conclude that we failed to
    // reach the destiantion cell. This may happen when the
    // there is no way to destination cell (due to blockages)
    if (foundDest == false)
        printf("Failed to find the Destination Cell\n");
 
    return;
}
 
 
// Driver program to test above function
int main()
{
    /* Description of the Grid-
     1--> The cell is not blocked
     0--> The cell is blocked    */
    int grid[ROW][COL] =
    {
        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
        { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
        { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
        { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
        { 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 }
    };
 
    // Source is the left-most bottom-most corner
    Pair src = make_pair(8, 0);
 
    // Destination is the left-most top-most corner
    Pair dest = make_pair(0, 0);
 
    aStarSearch(grid, src, dest);
 
    return(0);
}

Also wie schaffe ich es das mein spieler den Pfad folgen kann..

100000000 Dank
Mfg
 

Jennesta

Erfahrenes Mitglied
Hallo.

Nun, der Code des A* Algorithmus ist mir bekannt, den hätte ich gegebenenfalls auch selbst suchen können.
Was viel wichtiger ist, ist der Code den du selbst geschrieben hast.

Du hast etwas von einem Spieler gesagt. Wie sieht die Klasse aus, wie bewegt sich ein Spieler und wie wird das dargestellt. Zeichnest du auf ein Fenster oder gibst du Koordinaten in der Konsole aus?

Ich weiß gerade nicht was du dir für eine Lösung erhoffst.

Viele Grüße
 

NudelMaus

Grünschnabel
Ok ich versuche es jetzt so genau wie möglich zu Beschreiben :)
Mein Ziel war es den A Star algorithmus zu verstehen und anzuwenden, Das kann ich jetzt abhacken. Das nächste ist das gelernte anzuwenden in Form von einem Spieler der dem Pfad auch folgen kann, und genau daran verzweifel ich seit nun mehr als einer Woche..

Mein grösstes Problem ist, wie ich es schaffe den Player anhand der Koordinaten zu bewegen..

Noch kurz angemerkt sei, Ich verwende SFML.

Ok mein erster gedanke war die Koordinaten in einem Vector zu speichern.

C++:
std::vector<std::pair<int, int>> coordinate;

void tracePath(cell cellDetail[][COL], Pair dest) {
    int row = dest.first;
    int col = dest.second;

    std::stack<Pair> Path;

    while (!(cellDetail[row][col].parent_i == row && cellDetail[row][col].parent_j == col))
    {
        Path.push(std::make_pair(row, col));
        int temp_row = cellDetail[row][col].parent_i;
        int temp_col = cellDetail[row][col].parent_j;
        row = temp_row;
        col = temp_col;
    }

    Path.push(std::make_pair(row, col));
    while (!Path.empty())
    {
        std::pair<int, int> p = Path.top();
        Path.pop();
        coordinate.push_back(p);
    }
}
Da es ja nur zum Testen ist habe ich eine einfache und schnelle Player Klasse geschrieben

C++:
class Player
{
public:
    Player() {
        mShape.setPosition(sf::Vector2f(0.f, 0.f));
        mShape.setSize(sf::Vector2f(32.f, 32.f));
        mShape.setFillColor(sf::Color::Green);
    }

    sf::Vector2f getPosition() {
        return mShape.getPosition();
    }

    void move(sf::Vector2f movement) {
        mShape.move(movement.x, movement.y);
    }

    void setPosition(sf::Vector2f newPos) {
        mShape.setPosition(newPos);
    }

    void Render(sf::RenderWindow &window) {
        window.draw(mShape);
    }

private:
    sf::RectangleShape mShape;
};
Und in der ProcessEvent schleife dann per Mausklick den start und end Knoten setzten

C++:
int main()
{
    sf::RenderWindow window(sf::VideoMode(800, 600), "Test", sf::Style::Default);

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            switch (event.type)
            {
            case sf::Event::Closed:
                window.close();
                break;
            case sf::Event::MouseButtonPressed:
                switch (event.key.code)
                {
                case sf::Mouse::Button::Left:
                    sf::Vector2f selectedNode(sf::Mouse::getPosition(window).x / 32, sf::Mouse::getPosition(window).y / 32);
                    Pair start = std::make_pair(player.getPosition().x / 32, player.getPosition().y / 32);
                    Pair end = std::make_pair(selectedNode.x, selectedNode.y);

                    aStar(start, end);

                    // Und hier mein naiver versuch
                    for (unsigned int i = 0; i < coordinate.size(), i++) {
                        mPlayer.setPosition(coordinate[i].first * 32, coordinate[i].second * 32);
                        // und später dann mit sf::sleep(sf::seconds(1));
                        // und das selbe in der tracePath Funktion mit sleep versucht sie zu verlangsamen
                    }
                    break;
                default:
                    break;
                }
            }
        }
        // Update //
        
        // Draw
        window.clear();
        player.Render(window);
        window.display();
    }
    return 0;
}
Ok danach habe ich versucht die schleifen zu verlangsamen mit sf::Sleep(sf::second(1));

Das lustige ist das mir der Pfad in der Konsole schrittweise angezeigt wird aber mein "Player" wartet bis die schleife zu ende ist und springt dann an die Ziel Position..

Ok ich hoffe das sind genug details damit ihr mein Problem kennt und villeicht noch einen Tipp habt für mich..

Ps: Sollten irgentwelche Fehler im Code sein, bitte ich um entschuldigung, aber ist alles mit Handy geschrieben, und man vergisst wie bequem eigentlich so eine IDE ist.. Hihi

Ich Bedanke mich im voraus..

Mfg
 

Technipion

Erfahrenes Mitglied
Noch kurz angemerkt sei, Ich verwende SFML.
Ahhhhh, genau die Info haben wir gebraucht.

Übrigens: Du kriegst von mir auch einen Daumen nach oben, weil du dieses Mal vorbildlich gleich den ganzen Code mitgepostet hast (y)

Zurück zum Problem: In deiner Hauptschleife (while (window.isOpen())) hast du schon fast die Lösung des Ganzen. Zunächst liest du dort evtl. Events aus (also Input/Output, auf den dein Programm reagieren sollte). Soweit so üblich. Dann kommt ein Kommentar // Update //. Und genau dorthin gehört eigentlich der Code, der alle deine In-Game-Objekte updated. Wenn du also einen Player mPlayer; hast, dann gehört dort eigentlich ein mPlayer.update(double elapsed); hin.

Aber wir sollten uns Schritt für Schritt dort hinarbeiten. In einem ersten Schritt könntest du die for-Schleife von Post #1 hier verwursteln:
C++:
int main()
{
    sf::RenderWindow window(sf::VideoMode(800, 600), "Test", sf::Style::Default);
    
    std::vector<std::pair<int, int> > coordinates;
    // benutze hier deinen A* um coordinates zu berechnen
    
    size_t coordinates_index = 0; // wir starten die Bewegung bei Koordinate 0

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            switch (event.type)
            {
            case sf::Event::Closed:
                window.close();
                break;
            case sf::Event::MouseButtonPressed:
                switch (event.key.code)
                {
                case sf::Mouse::Button::Left:
                    sf::Vector2f selectedNode(sf::Mouse::getPosition(window).x / 32, sf::Mouse::getPosition(window).y / 32);
                    Pair start = std::make_pair(player.getPosition().x / 32, player.getPosition().y / 32);
                    Pair end = std::make_pair(selectedNode.x, selectedNode.y);

                    aStar(start, end);

                    // Und hier mein naiver versuch
                    for (unsigned int i = 0; i < coordinate.size(), i++) {
                        mPlayer.setPosition(coordinate[i].first * 32, coordinate[i].second * 32);
                        // und später dann mit sf::sleep(sf::seconds(1));
                        // und das selbe in der tracePath Funktion mit sleep versucht sie zu verlangsamen
                    }
                    break;
                default:
                    break;
                }
            }
        }
        // Update //
        
        /* MOVE mPlayer                      */
        coordinates_index += 1; // gehe zur nächsten Position
        
        if (coordinates_index >= coordinates.size()) {
            // falls wir am Ende des Pfades angekommen sind
            // springe auf Anfang zurück
            coordinates_index = 0;
        }
        
        // und setze Position:
        mPlayer.setPosition(coordinates[coordinates_index].first * 32,
                            coordinates[coordinates_index].second * 32);
        /* END of MOVE mPlayer               */
        
        // Draw
        window.clear();
        player.Render(window); // müsste das nicht mPlayer sein?
        window.display();
    }
    return 0;
}
Du kannst es ja mal testen und uns berichten.

Gruß Technipion
 

NudelMaus

Grünschnabel
Halli Hallo,

Ich habe es jetzt so umgesetzt und Hurra der Player bewegt sich, yeahh :)

Aber jetzt kommen zwei neue Probleme :(

Das erste ist das der player nun in endlosschleife den Pfad geht, und nicht am Ziel stoppt.
Und das zweite ist, da ich jetzt die koordinaten im Initialisierungsteil berechne, kann ich sie nicht mehr ändern, mein ziel war es ja per mausklick das ziel zu bestimmen, und nicht zu Anfang :(

Und wenn ich jetzt versuche die Koodinaten erst nach mausklick zu berechnen, stürz natürlich das Programm ab, da ja coordinaten_index in setPosition auf einen leeren Index greift ..

Kann man die zwei Probleme irgentwie noch lösen.

Trotz all dem vielen vielen dank ich bin mega Happy das der player sich endlich schrittweise Bewegt :)
 

Technipion

Erfahrenes Mitglied
Ich habe es jetzt so umgesetzt und Hurra der Player bewegt sich, yeahh :)
Sehr schön!

Kann man die zwei Probleme irgentwie noch lösen.
Ja das geht. Allerdings bewegst du dich jetzt immer mehr in Richtung Pfadanimationen, und das ist ein komplexes Thema für sich. Leider habe ich gerade viel zu tun, und deshalb keine Zeit das jetzt ausführlich zu erklären. Ich habe deshalb hier ein Beispiel aufgesetzt, das hoffentlich alles veranschaulicht:
C++:
#include <SFML/Graphics.hpp>   // for sf::*
#include <vector>              // for std::vector

// EXAMPLE from https://www.sfml-dev.org/documentation/2.5.1/
// modified to needs


int main()
{
    sf::RenderWindow window(sf::VideoMode(800, 600), "SFML window");

    sf::Texture texture;
    // source: https://upload.wikimedia.org/wikipedia/commons/d/df/Sprite01.gif
    if (!texture.loadFromFile("Sprite01.gif"))
        return EXIT_FAILURE;

    sf::Sprite sprite(texture);
    sprite.setOrigin(50, 50);

    sf::Font font;
    // source: https://www.fontspace.com/freesans-font-f13276
    if (!font.loadFromFile("FreeSans-LrmZ.ttf"))
        return EXIT_FAILURE;

    sf::Text text("Klick mich", font, 50);
    text.setOrigin(100, 35);
    text.setPosition(400, 300);

    std::vector<std::pair<float, float> > path;
    float path_time = 0.0f;
    bool following_path = false;

    std::vector<sf::CircleShape> path_points;
    for (const auto &p : path) {
        sf::CircleShape circle(4.0f);
        circle.setFillColor(sf::Color::Green);
        circle.setPosition(p.first, p.second);

        path_points.push_back(circle);
    }

    sf::Clock clock;

    while (window.isOpen())
    {
        sf::Time elapsed = clock.restart();

        sf::Event event;
        while (window.pollEvent(event))
        {
            switch (event.type)
            {
                case sf::Event::Closed:
                    window.close();
                    break;

                case sf::Event::MouseButtonPressed:
                    switch (event.key.code)
                    {
                        case sf::Mouse::Button::Left:
                        {
                            float x = sf::Mouse::getPosition(window).x;
                            float y = sf::Mouse::getPosition(window).y;

                            path.push_back(std::make_pair(x, y));

                            sf::CircleShape circle(4.0f);
                            circle.setFillColor(sf::Color::Green);
                            circle.setPosition(x, y);

                            path_points.push_back(circle);

                            following_path = true;
                            path_time = 0.0f;
                            break;
                        }
                        default:
                            break;
                    }
                case sf::Event::KeyPressed:
                    if (event.key.code == sf::Keyboard::Space) {
                        path.clear();
                        path_points.clear();

                        following_path = false;
                        path_time = 0.0f;
                    }
                    break;
            }
        }

        // rotate text:
        text.rotate(180.0f * elapsed.asSeconds()); // 180° per second

        // follow path:
        if (following_path == true) {
            path_time += 0.5f * elapsed.asSeconds(); // slow down to 50%

            if (path_time > path.size()) {
                path_time = 0.0f;
                following_path = false;
            }

            size_t path_from = (size_t)path_time % path.size();
            size_t path_to = (path_from + 1) % path.size();
            float interpol = path_time - (float)path_from;

            float x = ((1.0f - interpol) * path[path_from].first +
                       interpol          * path[path_to].first);

            float y = ((1.0f - interpol) * path[path_from].second +
                       interpol          * path[path_to].second);

            sprite.setPosition(x, y);
        }

        window.clear();
        window.draw(sprite);
        window.draw(text);

        for (const auto &c : path_points) {
            window.draw(c);
        }

        window.display();
    }
    return EXIT_SUCCESS;
}
So, deine Aufgabe ist jetzt:
  • Führe den Code mal aus und teste, dass alles funktioniert
  • Lies den Code mehrmals durch und versuche ihn nachzuvollziehen
  • Falls etwas unklar ist versuch ruhig Google zu bemühen, das müssen Programmierer drauf haben
  • Für alles was nicht rein technisch ist (also Verständnisfragen, Vorschläge, oder andere Überlegungen) kannst du gerne wieder hier im Forum nachfragen
Wenn du das getan hast können wir an den Feinschliff gehen :)

Gruß Technipion