[Useful and fast] basic pathfinding

Fraza · Post by **Fraza** » Sun Apr 03, 2005 4:19 am

Basic 'tilemap' pathifindng.

One thing Irrlicht is capable of is isometric game creation. I am absolutely sure some people will want to make such games, also, if you used a 2D tilemap in a 3D game, this would be useful.

The basic idea is as follows.

Here is our map (i will put it in a code box for the font):

Code: Select all

* = wall

  = blank

 0123456789
0**********
1*        *
2*        *
3*        *
4*        *
5*        *
6*        *
7*        *
8*        *
9**********

next we add an object (e.g. a tank) and a finishing point for the tank to get to

Code: Select all

* = wall
  = blank
t = tank
d = destination

 0123456789
0**********
1*        *
2* d      *
3*        *
4*        *
5*        *
6*        *
7*      t *
8*        *
9**********

To get the moves from point t to point d we simply have a 2 dimensional array of numbers, 0 to 9 by 0 to 9, as on the map. On the map, a wall is represented by a -1, an empty square is represented as 0 and d is represented as 1. We know the Co ordinates of t so we shan't bother to represent t (for reasons that will become apparent later).

the grid in number form looks like

Code: Select all

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  1  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

now, we write a function that returns a boolean that will execute the next move. The next move is executed as follows:

initialising, a boolean is set saying no moves have been done

1. The grid is scanned, if a number matches the current move number (whcich is incremented every move) the program then 'examines' this square.
2. It looks at the adjacent squares and checks their values
3. if the squares value is equal to 0 or greater than the next moves number, the program reassigns this grid value as the next moves number. A boolean is set saying a move has been done.

finalising. Once the array is fully scanned and changed the boolean is returned.

the result of doing this is as follows:

move 1:

Code: Select all

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  0  2  0  0  0  0  0  0 -1
-1  2  1  2  0  0  0  0  0 -1
-1  0  2  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

move 2:

Code: Select all

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  3  2  3  0  0  0  0  0 -1
-1  2  1  2  3  0  0  0  0 -1
-1  3  2  3  0  0  0  0  0 -1
-1  0  3  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

move 3:

Code: Select all

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  3  2  3  4  0  0  0  0 -1
-1  2  1  2  3  4  0  0  0 -1
-1  3  2  3  4  0  0  0  0 -1
-1  4  3  4  0  0  0  0  0 -1
-1  0  4  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

and so on. We stop updating this map when the procedure returns false.

the function would be written thus when implemented:

Code: Select all

    int iMoves = 1;
    while(ourFunction(iMoves))
        iMoves++;

Then what we can do is go from point 7, 7 (the point of the tank) and utilise these numbers

If the number in the grid at point 7, 7 were 0, the program would know the move were impossible.

If not the procedure does the following:

initialising. a boolean is set to false to indicate the target isn't reached.

1. Checks all 4 adjacenet squares and finds which has the lowest value and is greater or equal to 1
2. it moves to this square (sets its new coordanites to this square also for the next move!), if this square is equal to one, it returns true

note: if 2 squares are of equal value it can choose to use either square, you may wish to have an order like top first, then left, then bottom, then right. It doesn't realy matter.

this procedure is implemented in almost th exact same way:

Code: Select all

    int iX = 7, iY = 7;
    while(OurSecondFunction()){}//unfortunately there is no simple incrementing that can be done here so we input a blank statement in empty braces

That concludes basic pathfinding on a tile map!

If I feel sufficiently bored at a later date I may make a basic text screen demo for you and post the source (it would be written in DevCpp).

Well, I hopw the idea is clear and easy to understand and is of help to someone!

If I've made any mistakes please point them out immidietly!

This is intended as a starting point for someone who wishes to create their own Pathfinding for their game and make it as efficient as possible but doesn't know where to start. I know there are much better versions than this on the internet, but I recognise some people (like myself) want to do as much as they can by themselves, by giving out such basic information someone can excersize their own programming and logic to create their own much enhanced pathfinding.

Fraza · Post by **Fraza** » Sun Apr 03, 2005 7:40 am

I made a basic console app to demonstrate the technique. I compiled it in DevCpp, but if you have Visual C++ please tell me if it compiles in that also.

Code: Select all

#include <iostream.h>
#include <stdlib.h>

//Globals
//Constants
const int MAP_WIDTH = 10;
const int MAP_HEIGHT = 10;
//Variables
bool bStepByStep = false;
char cMap[MAP_WIDTH][MAP_HEIGHT];
int iMapPath[MAP_WIDTH][MAP_HEIGHT];
int iCurrentX, iCurrentY, iMovesTaken;

//Function prototypes
void FindPath(int iBeginX, int iBeginY, int iEndX, int iEndY);
void PrintMap();
void PrintNumericMap();
bool FindNumericPath(int iMove);
bool UsePath();


int main()
{
    bool bRunning = true;
    for(int iCountX = 0; iCountX < MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY < MAP_HEIGHT; iCountY++)
            if((iCountX == 0) || (iCountX == MAP_WIDTH - 1) || (iCountY == 0) || (iCountY == MAP_HEIGHT - 1))
                cMap[iCountX][iCountY] = '*';
            else
                cMap[iCountX][iCountY] = ' ';
    while(bRunning)
    {
        char cInput;
        cout << "Basic path finding, by James Fraser" << endl << "a) Find path" << endl << "b) Toggle step by step mode" << endl << "c) Print map" << endl << "d) Add wall" << endl << "e) Add blank space" << endl << "f) Show key" << endl << "other) quit" << endl;
        cin >> cInput;
        cout << endl;
        switch(cInput)
        {
            case 'a':
            {
                int iBeginX, iBeginY, iEndX, iEndY;
                cout << "Enter begin X : ";
                cin >> iBeginX;
                cout << "Enter begin Y : ";
                cin >> iBeginY;
                cout << "Enter end X : ";
                cin >> iEndX;
                cout << "Enter end Y : ";
                cin >> iEndY;
                cout << endl;
                FindPath(iBeginX, iBeginY, iEndX, iEndY);
            }
            break;
            case 'b': bStepByStep = !bStepByStep; break;
            case 'c':
            {
                PrintMap();
                system("PAUSE");
                cout << endl << endl;
            }
            break;
            case 'd':
            {
                int iWallX, iWallY;
                cout << "Enter wall X : ";
                cin >> iWallX;
                cout << "Enter wall Y : ";
                cin >> iWallY;
                cMap[iWallX][iWallY] = '*';
                PrintMap();
                system("PAUSE");
                cout << endl << endl;                
            }
            break;
            case 'e':
            {
                int iBlankX, iBlankY;
                cout << "Enter blank space X : ";
                cin >> iBlankX;
                cout << "Enter blank space Y : ";
                cin >> iBlankY;
                cMap[iBlankX][iBlankY] = ' ';
                PrintMap();
                system("PAUSE");
                cout << endl << endl;                
            }
            break;
            case 'f':
            {
                cout << "0 = Path" << endl << "* = Wall" << endl << "  = Blank" << endl << "B = Beginning point" << endl << "E = End point" << endl << endl;
                system("PAUSE");
            }
            break;
            default:  bRunning = false; break;
        }
    }
    return EXIT_SUCCESS;
}

void FindPath(int iBeginX, int iBeginY, int iEndX, int iEndY)
{
    for(int iCountX = 0; iCountX < MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY < MAP_HEIGHT; iCountY++)
            switch(cMap[iCountX][iCountY])
            {
                case'*': iMapPath[iCountX][iCountY] = -1; break;
                default: iMapPath[iCountX][iCountY] =  0; break;
            }
    iMapPath[iEndX][iEndY] = 1;
    if(bStepByStep)
    {
        PrintNumericMap();
        system("PAUSE");
    }
    int iMoves = 1;
    while(FindNumericPath(iMoves))
        if(bStepByStep)
        {
            PrintNumericMap();
            iMoves++;
            system("PAUSE");
        }
        else
            iMoves++;
    iCurrentX = iBeginX;
    iCurrentY = iBeginY;
    iMovesTaken = 0;
    while(UsePath())
        iMovesTaken++;
    cMap[iBeginX][iBeginY] = 'B';
    cMap[iEndX][iEndY] = 'E';
    PrintMap();
    cout << "Moves taken : " << iMovesTaken << endl;
    system("PAUSE");
    for(int iCountX = 0; iCountX < MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY < MAP_HEIGHT; iCountY++)
            if(cMap[iCountX][iCountY] != '*')
                cMap[iCountX][iCountY] = ' ';
    cout << endl << endl;
}

void PrintMap()
{
    for(int iCountY = 0; iCountY < MAP_HEIGHT; iCountY++)
    {
        for(int iCountX = 0; iCountX < MAP_WIDTH; iCountX++)
            cout << cMap[iCountX][iCountY];
        cout << endl;
    }
}

void PrintNumericMap()
{
    for(int iCountY = 0; iCountY < MAP_HEIGHT; iCountY++)
    {
        for(int iCountX = 0; iCountX < MAP_WIDTH; iCountX++)
            if((iMapPath[iCountX][iCountY] >= 10) || (iMapPath[iCountX][iCountY] < 0))
                cout << iMapPath[iCountX][iCountY] << " ";
            else
                cout << " " << iMapPath[iCountX][iCountY] << " ";            
        cout << endl;
    }
}

bool FindNumericPath(int iMove)
{
    bool bMadeMove = false;
    for(int iCountX = 0; iCountX < MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY < MAP_HEIGHT; iCountY++)
            if(iMapPath[iCountX][iCountY] == iMove)
            {
                if(iCountX >= 1)
                    if((iMapPath[iCountX - 1][iCountY] == 0) || (iMapPath[iCountX - 1][iCountY] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX - 1][iCountY] = iMove + 1;
                    }
                if(iCountY >= 1)
                    if((iMapPath[iCountX][iCountY - 1] == 0) || (iMapPath[iCountX][iCountY - 1] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX][iCountY - 1] = iMove + 1;
                    }
                if(iCountX < MAP_WIDTH - 1)
                    if((iMapPath[iCountX + 1][iCountY] == 0) || (iMapPath[iCountX + 1][iCountY] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX + 1][iCountY] = iMove + 1;
                    }
                if(iCountY < MAP_HEIGHT - 1)
                    if((iMapPath[iCountX][iCountY + 1] == 0) || (iMapPath[iCountX][iCountY + 1] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX][iCountY + 1] = iMove + 1;
                    }
            }
    return bMadeMove;
}

bool UsePath()
{
    int iMoveX, iMoveY, iBest = 999;//iBest has arbitrary high value
    bool bNotSolved = true;
    if(iMapPath[iCurrentX][iCurrentY] <= 1)
        bNotSolved = false;
    else
    {
        if(iCurrentX >= 1)
            if((iMapPath[iCurrentX - 1][iCurrentY] > 0) && (iMapPath[iCurrentX - 1][iCurrentY] < iMapPath[iCurrentX][iCurrentY]))
            {
                iMoveX = -1;
                iMoveY = 0;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX - 1][iCurrentY];
            }
        if(iCurrentY >= 1)
            if((iMapPath[iCurrentX][iCurrentY - 1] > 0) && (iMapPath[iCurrentX][iCurrentY - 1] < iMapPath[iCurrentX][iCurrentY]) && (iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY - 1] < iBest))
            {
                iMoveX = 0;
                iMoveY = -1;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY - 1];
            }
        if(iCurrentX < MAP_WIDTH - 1)
            if((iMapPath[iCurrentX + 1][iCurrentY] > 0) && (iMapPath[iCurrentX + 1][iCurrentY] < iMapPath[iCurrentX][iCurrentY]) && (iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX + 1][iCurrentY] < iBest))
            {
                iMoveX = 1;
                iMoveY = 0;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX + 1][iCurrentY];
            }
        if(iCurrentY < MAP_HEIGHT - 1)
            if((iMapPath[iCurrentX][iCurrentY + 1] > 0) && (iMapPath[iCurrentX][iCurrentY + 1] < iMapPath[iCurrentX][iCurrentY]) && (iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY + 1] < iBest))
            {
                iMoveX = 0;
                iMoveY = 1;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY + 1];
            }
        iCurrentX += iMoveX;
        iCurrentY += iMoveY;
        cMap[iCurrentX][iCurrentY] = '0';
    }
    return bNotSolved;
}

Just paste in the code and compile, have a play around and tell me if there are any errors please, and enjoy!

Edit: Here's a quick screenshot with a maze I put in.

Guest · Post by **Guest** » Sun Apr 03, 2005 10:22 am

Looks a bit like Dijkstra's to me, Dijkstra's also searches in a circular way. With an heap it can reach speeds of O(|E|log|V|) (E=edge V=vertex) while it seems like your path algorithm still has a speed of O(|V|2) (I may be wrong though). If you need speed on large maps you might look into A* (a 'smart' variant on Dijkstra's).

Guest · Post by **Guest** » Sun Apr 03, 2005 10:28 am

Found a neat and simple article explaining A* in detail (with pictues

):
http://www.policyalmanac.org/games/aStarTutorial.htm

Fraza · Post by **Fraza** » Sun Apr 03, 2005 10:30 am

I preffer to do things myself, unfortunately I have no 3D graphics based education so for now I am gong to use Irrlicht... But this path finder can solve a 100 x 100 empty map at the moment, which is large enough for now!

I will try and make it more efficient at some point in the future.

Chris · Post by **Chris** » Sun Apr 03, 2005 11:17 am

Needed a little modification to get it to work in VS6, due to iCountX being redefined.

This is what I changed it to:

Code: Select all

#include <iostream.h>
#include <stdlib.h>

//Globals
//Constants
const int MAP_WIDTH = 9;
const int MAP_HEIGHT = 9;
//Variables
bool bStepByStep = false;
char cMap[MAP_WIDTH][MAP_HEIGHT];
int iMapPath[MAP_WIDTH][MAP_HEIGHT];
int iCurrentX, iCurrentY, iMovesTaken;
int iCountX;

//Function prototypes
void FindPath(int iBeginX, int iBeginY, int iEndX, int iEndY);
void PrintMap();
void PrintNumericMap();
bool FindNumericPath(int iMove);
bool UsePath();


int main()
{
    bool bRunning = true;
    for(int iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
            if((iCountX == 0) || (iCountX == MAP_WIDTH) || (iCountY == 0) || (iCountY == MAP_HEIGHT))
                cMap[iCountX][iCountY] = '*';
            else
                cMap[iCountX][iCountY] = ' ';
    while(bRunning)
    {
        char cInput;
        cout << "Basic path finding, by James Fraser" << endl << "a) Find path" << endl << "b) Toggle step by step mode" << endl << "c) Print map" << endl << "d) Add wall" << endl << "e) Add blank space" << endl << "f) Show key" << endl << "other) quit" << endl;
        cin >> cInput;
        cout << endl;
        switch(cInput)
        {
            case 'a':
            {
                int iBeginX, iBeginY, iEndX, iEndY;
                cout << "Enter begin X : ";
                cin >> iBeginX;
                cout << "Enter begin Y : ";
                cin >> iBeginY;
                cout << "Enter end X : ";
                cin >> iEndX;
                cout << "Enter end Y : ";
                cin >> iEndY;
                cout << endl;
                FindPath(iBeginX, iBeginY, iEndX, iEndY);
            }
            break;
            case 'b': bStepByStep = !bStepByStep; break;
            case 'c':
            {
                PrintMap();
                system("PAUSE");
                cout << endl << endl;
            }
            break;
            case 'd':
            {
                int iWallX, iWallY;
                cout << "Enter wall X : ";
                cin >> iWallX;
                cout << "Enter wall Y : ";
                cin >> iWallY;
                cMap[iWallX][iWallY] = '*';
                PrintMap();
                system("PAUSE");
                cout << endl << endl;               
            }
            break;
            case 'e':
            {
                int iBlankX, iBlankY;
                cout << "Enter blank space X : ";
                cin >> iBlankX;
                cout << "Enter blank space Y : ";
                cin >> iBlankY;
                cMap[iBlankX][iBlankY] = ' ';
                PrintMap();
                system("PAUSE");
                cout << endl << endl;               
            }
            break;
            case 'f':
            {
                cout << "0 = Path" << endl << "* = Wall" << endl << "  = Blank" << endl << "B = Beginning point" << endl << "E = End point" << endl << endl;
                system("PAUSE");
            }
            break;
            default:  bRunning = false; break;
        }
    }
    return EXIT_SUCCESS;
}

void FindPath(int iBeginX, int iBeginY, int iEndX, int iEndY)
{
    for(int iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
            switch(cMap[iCountX][iCountY])
            {
                case'*': iMapPath[iCountX][iCountY] = -1; break;
                default: iMapPath[iCountX][iCountY] =  0; break;
            }
    iMapPath[iEndX][iEndY] = 1;
    if(bStepByStep)
    {
        PrintNumericMap();
        system("PAUSE");
    }
    int iMoves = 1;
    while(FindNumericPath(iMoves))
        if(bStepByStep)
        {
            PrintNumericMap();
            iMoves++;
            system("PAUSE");
        }
        else
            iMoves++;
    iCurrentX = iBeginX;
    iCurrentY = iBeginY;
    iMovesTaken = 0;
    while(UsePath())
        iMovesTaken++;
    cMap[iBeginX][iBeginY] = 'B';
    cMap[iEndX][iEndY] = 'E';
    PrintMap();
    cout << "Moves taken : " << iMovesTaken << endl;
    system("PAUSE");
    for(iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
            if(cMap[iCountX][iCountY] != '*')
                cMap[iCountX][iCountY] = ' ';
    cout << endl << endl;
}

void PrintMap()
{
    for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
    {
        for(iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
            cout << cMap[iCountX][iCountY];
        cout << endl;
    }
}

void PrintNumericMap()
{
    for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
    {
        for(iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
            if((iMapPath[iCountX][iCountY] >= 10) || (iMapPath[iCountX][iCountY] < 0))
                cout << iMapPath[iCountX][iCountY] << " ";
            else
                cout << " " << iMapPath[iCountX][iCountY] << " ";           
        cout << endl;
    }
}

bool FindNumericPath(int iMove)
{
    bool bMadeMove = false;
    for(iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
        for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
            if(iMapPath[iCountX][iCountY] == iMove)
            {
                if(iCountX >= 1)
                    if((iMapPath[iCountX - 1][iCountY] == 0) || (iMapPath[iCountX - 1][iCountY] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX - 1][iCountY] = iMove + 1;
                    }
                if(iCountY >= 1)
                    if((iMapPath[iCountX][iCountY - 1] == 0) || (iMapPath[iCountX][iCountY - 1] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX][iCountY - 1] = iMove + 1;
                    }
                if(iCountX <= MAP_WIDTH - 1)
                    if((iMapPath[iCountX + 1][iCountY] == 0) || (iMapPath[iCountX + 1][iCountY] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX + 1][iCountY] = iMove + 1;
                    }
                if(iCountY <= MAP_HEIGHT - 1)
                    if((iMapPath[iCountX][iCountY + 1] == 0) || (iMapPath[iCountX][iCountY + 1] > iMove + 1))
                    {
                        bMadeMove = true;
                        iMapPath[iCountX][iCountY + 1] = iMove + 1;
                    }
            }
    return bMadeMove;
}

bool UsePath()
{
    int iMoveX, iMoveY, iBest = 999;//iBest has arbitrary high value
    bool bNotSolved = true;
    if(iMapPath[iCurrentX][iCurrentY] <= 1)
        bNotSolved = false;
    else
    {
        if(iCurrentX >= 1)
            if((iMapPath[iCurrentX - 1][iCurrentY] > 0) && (iMapPath[iCurrentX - 1][iCurrentY] < iMapPath[iCurrentX][iCurrentY]))
            {
                iMoveX = -1;
                iMoveY = 0;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX - 1][iCurrentY];
            }
        if(iCurrentY >= 1)
            if((iMapPath[iCurrentX][iCurrentY - 1] > 0) && (iMapPath[iCurrentX][iCurrentY - 1] < iMapPath[iCurrentX][iCurrentY]) && (iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY - 1] < iBest))
            {
                iMoveX = 0;
                iMoveY = -1;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY - 1];
            }
        if(iCurrentX <= MAP_WIDTH - 1)
            if((iMapPath[iCurrentX + 1][iCurrentY] > 0) && (iMapPath[iCurrentX + 1][iCurrentY] < iMapPath[iCurrentX][iCurrentY]) && (iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX + 1][iCurrentY] < iBest))
            {
                iMoveX = 1;
                iMoveY = 0;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX + 1][iCurrentY];
            }
        if(iCurrentY <= MAP_HEIGHT - 1)
            if((iMapPath[iCurrentX][iCurrentY + 1] > 0) && (iMapPath[iCurrentX][iCurrentY + 1] < iMapPath[iCurrentX][iCurrentY]) && (iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY + 1] < iBest))
            {
                iMoveX = 0;
                iMoveY = 1;
                iBest = iMapPath[iCurrentX][iCurrentY] - iMapPath[iCurrentX][iCurrentY + 1];
            }
        iCurrentX += iMoveX;
        iCurrentY += iMoveY;
        cMap[iCurrentX][iCurrentY] = '0';
    }
    return bNotSolved;
}

Although you probably could have managed that yourself.

Fraza · Post by **Fraza** » Sun Apr 03, 2005 11:38 am

Hmmm... I really don't understand why iCountX ought to be a global variable, and why is this not the case for iCountY?

Also, in for loops, aren't you defining iCountX as a simple local variable to that loop and you also have it defined as a global variable. Why doesn't that cause problems?

Electron · Post by **Electron** » Sun Apr 03, 2005 12:58 pm

If anyone needs an A* pathfinder, look on the link in my sig, then go to Downloads page.

jox · Post by **jox** » Sun Apr 03, 2005 7:11 pm

There you are raping arrays again...

defining:

char cMap[MAP_WIDTH][MAP_HEIGHT];

and doing:

for(int iCountX = 0; iCountX <= MAP_WIDTH; iCountX++)
for(int iCountY = 0; iCountY <= MAP_HEIGHT; iCountY++)
cMap[iCountX][iCountY] = '*';

is bad! Believe me. (use "iCountX < MAP_WIDTH", not "iCountX <= MAP_WIDTH")

Youre gonna be in big trouble some day. Because what happens is: some other innocent variable(s) will get overwritten. And this can lead to very hard to track bugs in more complex programms.

What compiler do you use? Do me a favor and compile this program in Release mode. Then run it and watch it nicely crash (tested in MSVC .NET).

Fraza · Post by **Fraza** » Sun Apr 03, 2005 10:47 pm

OK... I gave it a quick test and entered cMap[MAP_WIDTH + 1][MAP_HEIGHT + 1] = ' ';. And I got no error read out of array bounds or memory accessing errors.

I'm new at C++ and figured you would get these errrors, I still love Delphi and good old RELIABLE Turbo Pascal.

Editted the source code above as well.

ZDimitor · Post by **ZDimitor** » Mon Apr 11, 2005 7:06 am

2Fraza:

Wake up Neo! Wake up!

Armen138 · Post by **Armen138** » Mon Apr 11, 2005 6:05 pm

im using a*, works great...