Pathfiding grid 16x16

SGDK only sub forum

Moderator: Stef

Post Reply
cloudstrifer
Very interested
Posts: 118
Joined: Mon Feb 19, 2018 7:31 pm

Pathfiding grid 16x16

Post by cloudstrifer » Wed May 16, 2018 9:31 pm

Hi, my demo use a pathfinding algorithm "converted" from C++ to C (https://www.geeksforgeeks.org/a-search-algorithm/).
I don't know how to optimize it to MD, it takes 0.5 sec to create the path (20 x 14 grid).

I have to generate a partial path or improve speed.

I need a timeout parameter, the code was modified to don't let pass by blocked diagonals.

Please, help to make this code better.

Thank you!

Code: Select all



#include <genesis.h>

#include "res\gfx.h"
#include "res\sprite.h"
#include "res\sound.h"


#define ROW 9
#define COL 10

fix32 FLT_MAX = 65000;
int lineText = 4;


// Creating a shortcut for int, int pair type
typedef struct {
	s16 first;
	s16 second;
}Pair;

// Creating a shortcut for int, int pair type
typedef struct {
	fix32 first;
	Pair second;
}PairList;

// Creating a shortcut for pair<int, pair<int, int>> type
//typedef pair<double, pair<int, int>> pPair;

// A structure to hold the neccesary parameters
typedef struct
{
    // 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;
}cell;

// A Utility Function to check whether given cell (row, col)
// is a valid cell or not.
int 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
int 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
int 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 ((fix16)fix16Sqrt ((row-dest.first)*(row-dest.first) + (col-dest.second)*(col-dest.second)));
	//return 1;
}

Pair make_pair(int row, int col){
	Pair newPair;
	newPair.first = row;
	newPair.second = col;
	return newPair;
}

void printf(char str[30]){
	VDP_drawText(str, 25, lineText);
	lineText ++;
}

// A Utility Function to trace the path from the source
// to destination
void tracePath(cell cellDetails[][COL], Pair dest)
{
    printf ("The Path is ");
    fix16 row = dest.first;
    fix16 col = dest.second;

    Pair Path[600];
    fix16 posArr = 0;

    while (!(cellDetails[row][col].parent_i == row
             && cellDetails[row][col].parent_j == col ))
    {
        Path[posArr] = 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;
        posArr ++;
    }

    Path[posArr] = make_pair(row, col);

    char first[6];
	char second[6];
	char str[20];

    while (posArr >=0)
    {

    	strclr(str);
        Pair p = Path[posArr];
        intToStr(p.first, first, 2);
        intToStr(p.second, second, 2);
        strcat(str, "R");
        strcat(str, first);
        strcat(str, "C");
        strcat(str, second);
        printf(str);
        posArr --;
    }


    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");
        return;
    }

    // If the destination is out of range
    if (isValid (dest.first, dest.second) == FALSE)
    {
        printf ("Destination is invalid");
        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");
        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");
        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
    fix16 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.*/
    PairList openList[600];

    // Put the starting cell on the open list and set its
    // 'f' as 0

    int intAux = 0;

    openList[intAux].first = 0.0;
    openList[intAux].second = make_pair (i, j);

    //openList.insert(make_pair (0, make_pair (i, j)));


    // We set this boolean value as false as initially
    // the destination is not reached.
    int foundDest = FALSE;
    int lowPos = 0;

    //while (!openList.empty()) TODO
    while (openList[lowPos].first != 65535)
    {
    	PairList p = openList[lowPos];
    	openList[lowPos].first = 65535;
    	lowPos ++;

        // Remove this vertex from the open list
        //openList.erase(openList.begin()); //TODO

        // Add this vertex to the open 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
        fix16 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");
                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)
                {
                    intAux ++;
                    openList[intAux].first = fNew;
                    openList[intAux].second = 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");
                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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");
                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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");
                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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");
                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 && (isUnBlocked(grid, i-1, j) == TRUE) && (isUnBlocked(grid, i, 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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");
                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 && (isUnBlocked(grid, i-1, j) == TRUE) && (isUnBlocked(grid, i, 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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");
                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 && (isUnBlocked(grid, i, j+1) == TRUE) && (isUnBlocked(grid, i+1, j) == 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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");
                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 && (isUnBlocked(grid, i+1, j) == TRUE) && (isUnBlocked(grid, i, 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)
                {
                    intAux ++;
					openList[intAux].first = fNew;
					openList[intAux].second = 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");

    return;
}


static void updateCamera(fix32 x, fix32 y);

// sprites structure (pointer of Sprite)
Sprite* arrPlayers[1];
Sprite* arrObjects[11];
Sprite* arrItens[7];
Sprite* arrEnemies[2];
Sprite* icon_p1;
Sprite* icon_p2;


fix32 camposx;
fix32 camposy;

static void updateCamera(fix32 x, fix32 y)
{
    if ((x != camposx) || (y != camposy))
    {
        camposx = x;
        camposy = y;
        VDP_setHorizontalScroll(PLAN_A, fix32ToInt(-camposx));
        VDP_setHorizontalScroll(PLAN_B, fix32ToInt(-camposx) >> 3);
        VDP_setVerticalScroll(PLAN_A, fix32ToInt(camposy));
        VDP_setVerticalScroll(PLAN_B, fix32ToInt(camposy) >> 3);
    }
}

int main()
{
    u16 palette[64];

    camposx = -1;
    camposy = -1;

    // disable interrupt when accessing VDP
    SYS_disableInts();
    // initialization
    VDP_setScreenWidth320();

    // init sprites engine
    SPR_init(16, 256, 256);

    // set all palette to black
    VDP_setPaletteColors(0, (u16*) palette_black, 64);

    // VDP process done, we can re enable interrupts
    SYS_enableInts();

    // init scrolling
    updateCamera(FIX32(0), FIX32(0));

    arrPlayers[0] = SPR_addSprite(&char01_sprite, 160, 160, TILE_ATTR(PAL1, TRUE, FALSE, FALSE));
    arrPlayers[1] = SPR_addSprite(&char01_sprite, 190, 160, TILE_ATTR(PAL1, TRUE, FALSE, FALSE));

    arrEnemies[0] = SPR_addSprite(&enemy01_sprite, 160, 64, TILE_ATTR(PAL3, TRUE, FALSE, FALSE));
    arrEnemies[1] = SPR_addSprite(&enemy01_sprite, 190, 64, TILE_ATTR(PAL3, TRUE, FALSE, FALSE));

    icon_p1 = SPR_addSprite(&icon01_sprite, 6, 10, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    icon_p2 = SPR_addSprite(&icon01_sprite, 200, 10, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));

    arrItens[0] = SPR_addSprite(&item01_sprite, 16, 64, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrItens[1] = SPR_addSprite(&item02_sprite, 16, 80, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrItens[2] = SPR_addSprite(&item03_sprite, 32, 80, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrItens[3] = SPR_addSprite(&item04_sprite, 48, 80, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrItens[4] = SPR_addSprite(&item02_sprite, 64, 128, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrItens[5] = SPR_addSprite(&item03_sprite, 80, 128, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrItens[6] = SPR_addSprite(&item04_sprite, 96, 128, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));

    arrObjects[0] = SPR_addSprite(&object01_sprite, 16, 160, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrObjects[1] = SPR_addSprite(&object02_sprite, 16, 176, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrObjects[2] = SPR_addSprite(&object03_sprite, 32, 96, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrObjects[3] = SPR_addSprite(&object03_sprite, 48, 160, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrObjects[4] = SPR_addSprite(&object01_sprite, 48, 176, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
    arrObjects[5] = SPR_addSprite(&object02_sprite, 64, 64, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
	arrObjects[6] = SPR_addSprite(&object01_sprite, 80, 80, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
	arrObjects[7] = SPR_addSprite(&object03_sprite, 96, 96, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
	arrObjects[8] = SPR_addSprite(&object02_sprite, 112, 112, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
	arrObjects[9] = SPR_addSprite(&object03_sprite, 128, 128, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));
	arrObjects[10] = SPR_addSprite(&object03_sprite, 144, 144, TILE_ATTR(PAL2, FALSE, FALSE, FALSE));

    SPR_update();

    // prepare palettes
    memcpy(&palette[0], char01_sprite.palette->data, 16 * 2);
    memcpy(&palette[16], char01_sprite.palette->data, 16 * 2);
    memcpy(&palette[32], item01_sprite.palette->data, 16 * 2);
    memcpy(&palette[48], enemy01_sprite.palette->data, 16 * 2);



    /* 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, 1, 1, 1, 1, 0, 0, 0, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 }
	};

	// Source is the left-most bottom-most corner
	                //ROW  //COL
	Pair src = make_pair(8, 9);

	// Destination is the left-most top-most corner
	Pair dest = make_pair(0, 0);

	aStarSearch(grid, src, dest);



    // fade in
    VDP_fadeIn(0, (4 * 16) - 1, palette, 20, FALSE);

    while(TRUE)
    {
        //if (!reseted)
        // update sprites
        SPR_update();
        VDP_waitVSync();
    }

    return 0;
}



Attachments
sprite_pathfinding.rar
(190.43 KiB) Downloaded 177 times
Last edited by cloudstrifer on Thu May 17, 2018 1:16 pm, edited 1 time in total.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Pathfiding grid 16x16

Post by Sik » Wed May 16, 2018 11:43 pm

20×14 is pretty close to Star Chaser's grid (20×12) so I may as well put its pathfinding code here (though the borders are always filled meaning worst case is searching 18×10=180 tiles, you may need to adjust the stack to account for that... I should replace the numbers with constants >_>)

Code: Select all

;****************************************************************************
; Pathfind
; Updates the pathfind results with the token be at the specified position.
;----------------------------------------------------------------------------
; input d0.w ... X coordinate of token
; input d1.w ... Y coordinate of token
;----------------------------------------------------------------------------
; breaks: all
;****************************************************************************

Pathfind:
    lea     (PathfindMap), a0           ; Where to store the pathfind results
    move.l  (StageAddr), a1             ; Where collision data is stored
    
    move.w  #20*12-1, d7                ; Initialize pathfind map
@InitMap:
    moveq   #0, d6
    cmp.b   #TILE_W, (a1)+
    shs.b   d6
    move.b  d6, (a0)+
    dbf     d7, @InitMap
    
    lea     -20*12(a0), a0              ; Get back the proper map address
    lea     -20*12*2(sp), a1            ; Make room for the FIFO queue
    
    add.b   d1, d1                      ; Calculate offset of the target
    add.b   d1, d1
    add.b   d1, d0
    add.b   d1, d1
    add.b   d1, d1
    add.b   d1, d0
    
    moveq   #0, d2                      ; Save this for later (needed for a
    move.b  d0, d2                        ; quick hack regarding the algo)
    
    move.b  d0, (a1)                    ; Push target into the FIFO
    move.b  #0, 1(a1)                   ; Starting distance is 0
    lea     2(a1), a2                   ; Set where the FIFO ends
    
    moveq   #0, d0                      ; Reset upper bits
    moveq   #0, d1                      ; Target is at distance 0
@Loop:
    move.b  (a1)+, d0                   ; Get tile to check
    move.b  (a1)+, d1                   ; Get current distance
    addq.b  #1, d1                      ; Increment distance
    
    lea     -1(a0,d0.w), a3             ; Check if the tile to the left of us
    tst.b   (a3)                          ; is free, and add it to the path
    bne.s   @DontGoLeft                   ; if so
    move.b  d1, (a3)
    move.b  d0, d7                      ; Tell algorithm to check this tile
    subq.b  #1, d7                        ; later (for longer paths)
    move.b  d7, (a2)+
    move.b  d1, (a2)+
@DontGoLeft:
    
    lea     1(a0,d0.w), a3              ; Check if the tile to the right of
    tst.b   (a3)                          ; us is free, and add it to the
    bne.s   @DontGoRight                  ; path if so
    move.b  d1, (a3)
    move.b  d0, d7                      ; Tell algorithm to check this tile
    addq.b  #1, d7                        ; later (for longer paths)
    move.b  d7, (a2)+
    move.b  d1, (a2)+
@DontGoRight:
    
    lea     -20(a0,d0.w), a3            ; Check if the tile above is free,
    tst.b   (a3)                          ; and add it to the path if so
    bne.s   @DontGoUp
    move.b  d1, (a3)
    move.b  d0, d7                      ; Tell algorithm to check this tile
    sub.b   #20, d7                       ; later (for longer paths)
    move.b  d7, (a2)+
    move.b  d1, (a2)+
@DontGoUp:
    
    lea     20(a0,d0.w), a3             ; Check if the tile below is free,
    tst.b   (a3)                          ; and add it to the path if so
    bne.s   @DontGoDown
    move.b  d1, (a3)
    move.b  d0, d7                      ; Tell algorithm to check this tile
    add.b   #20, d7                       ; later (for longer paths)
    move.b  d7, (a2)+
    move.b  d1, (a2)+
@DontGoDown:
    
    cmp.l   a1, a2                      ; More tiles to check?
    bne.s   @Loop
    
    move.b  #0, (a0,d2.w)               ; HACK: reset the target distance x_x
    rts                                 ; End of subroutine
That still takes up about 1/3 of a frame, and it reuses the results for all AI players (this works as long as everybody has the same target, check this article). If optimized asm takes up that much I wouldn't be that hopeful about a C implementation.

If you absolutely need to take this path (no pun intended) then consider stuff like spreading the search across multiple frames (you probably don't want pathfinding to be perfect anyway, delayed reactions are a good way to achieve that - also avoids some bugs where the AI can get stuck switching back and forth in some edge cases).

Also depending on the case you may want to consider alternatives like this one:
http://www.gamasutra.com/blogs/MilanBab ... ffects.php
Sik is pronounced as "seek", not as "sick".

Chilly Willy
Very interested
Posts: 2984
Joined: Fri Aug 17, 2007 9:33 pm

Re: Pathfiding grid 16x16

Post by Chilly Willy » Thu May 17, 2018 12:00 am

One big piece of advice: don't use DOUBLE-PRECISION FLOATING POINT in anything you do on the MD! Don't use float at all! That's crazy on a plain 68000. You simply can't get any speed at all.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Pathfiding grid 16x16

Post by Sik » Thu May 17, 2018 12:16 am

...I completely overlooked that because I didn't look at the C code (since as I said even optimized asm eats up a significant chunk of CPU time).

Yeah, avoid that double at all costs. Heck:

Code: Select all

// A Utility Function to calculate the 'h' heuristics.
double calculateHValue(int row, int col, Pair dest)
{
    // Return using the distance formula
    return ((fix16)fix16Sqrt ((row-dest.first)*(row-dest.first) + (col-dest.second)*(col-dest.second)));
	//return 1;
}
It even looks like you always meant to use fix16 all along considering how you're casting the return value.

By the way, how are you using that value? Because if it's just to compare values, then just use their Manhattan distance (basically: abs(x2-x1) + abs(y2-y1)). It's less accurate, but it'll do the job.

Actually, even that may be useless: horizontally and vertically adjacent tiles are always 1 tile apart, and diagonally adjacent tiles are always around 1.414 (sqrt(2)) tiles away, so you don't even need to do any complex calculations there.
Sik is pronounced as "seek", not as "sick".

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Pathfiding grid 16x16

Post by Stef » Thu May 17, 2018 12:27 pm

Also doing path finding is something you can break up on several frames, depending your game it may be ok if you update it each second (so that let you 60 frames to compute it).

Chilly Willy
Very interested
Posts: 2984
Joined: Fri Aug 17, 2007 9:33 pm

Re: Pathfiding grid 16x16

Post by Chilly Willy » Thu May 17, 2018 1:25 pm

Sik wrote:
Thu May 17, 2018 12:16 am
By the way, how are you using that value? Because if it's just to compare values, then just use their Manhattan distance (basically: abs(x2-x1) + abs(y2-y1)). It's less accurate, but it'll do the job.
Yeah - taxicab geometry is the way to go on old consoles. 8)

cloudstrifer
Very interested
Posts: 118
Joined: Mon Feb 19, 2018 7:31 pm

Re: Pathfiding grid 16x16

Post by cloudstrifer » Thu May 17, 2018 3:15 pm

I will try to use your code Sik.

Chilly Willy, thank you for advices.
Stef, the SGDK is so good, thank you.

Thank you for your big help.

Post Reply