Pathfiding grid 16x16

SGDK only sub forum

Moderator: Stef

cloudstrifer
Interested
Posts: 23
Joined: Mon Feb 19, 2018 7:31 pm

Pathfiding grid 16x16

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;
}
}
}
}

// 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);

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
Last edited by cloudstrifer on Thu May 17, 2018 1:16 pm, edited 1 time in total.

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

Re: Pathfiding grid 16x16

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

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: 2581
Joined: Fri Aug 17, 2007 9:33 pm

Re: Pathfiding grid 16x16

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: 694
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Pathfiding grid 16x16

...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: 2760
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Pathfiding grid 16x16

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: 2581
Joined: Fri Aug 17, 2007 9:33 pm

Re: Pathfiding grid 16x16

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.

cloudstrifer
Interested
Posts: 23
Joined: Mon Feb 19, 2018 7:31 pm

Re: Pathfiding grid 16x16

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.

Who is online

Users browsing this forum: No registered users and 1 guest