I haven't done game dev in a while and I was pretty bad at it back when I did. But now I have a renewed interest in it and decided to learn C++ and play around with that and try to understand new concepts now that I've studied algorithms in university.

One concept I've been particularly eager to learn is pathfiding, and after some research and trial and error on Wikipedia and RedBlobGames, I've accomplished the task all by myself in the C++ language. The problem is that there is some quirk in my implementation that gives some pretty unnatural pathing, even if it's the most efficient. The pattern I've derived seems to have a significant bias in the up direction and I didn't get the diagonal pattern I was aiming for.

I know the problem is probably something to do with the order that I'm evaluating neighboring spaces, but I can't wrap my head around it. What's the best way to evaluate the order of neighboring spaces and determining the path?

EDIT: I'm aiming for something similar to this, but I'm struggling to come up with the graceful prose to do it

Code:
>VVVVVVVVVVVV<
>>VVVVVVVVVV<<
>>>VVVVVVVV<<<
>>>>VVVVVV<<<<
>>>>>VVVV<<<<<
>>>>>>VV<<<<<<
>>>>>>T<<<<<<<
>>>>>^^<<<<<<<
>>>>^^^^<<<<<<
>>>^^^^^^<<<<<
>>^^^^^^^^<<<<
>^^^^^^^^^^<<<


Here's the input and output of the program as it's currently written:

Code:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                            X
X                            X
X      T                     X
X                            X
X              X             X
X              X             X
X       XXXXXXXXXXXX    XXXXXX
X       XXXXXXXX             X
X              X             X
X                    P       X
X              X             X
X              X             X
X              X             X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X↓↓↓↓↓↓↓←←←←←←←←←←←←←←←←←←←←←X
X↓↓↓↓↓↓↓←←←←←←←←←←←←←←←←←←←←←X
X→→→→→→T←←←←←←←←←←←←←←←←←←←←←X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑X↑↑↑↑↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑X↑↑↑↑↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑XXXXXXXXXXXX↑↑↑↑XXXXXX
X↑↑↑↑↑↑↑XXXXXXXX↓←→→↑↑↑↑←←←←←X
X↑↑↑↑↑↑↑←←←←←←←X↓←←↑↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑←←←←←↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑X↑↑↑↑↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑X↑↑↑↑↑↑↑↑↑↑↑↑↑X
X↑↑↑↑↑↑↑↑↑↑↑↑↑↑X↑↑↑↑↑↑↑↑↑↑↑↑↑X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


And here's the source for that:


Code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>

using namespace std;

class Coord {
public:
    Coord();
    void init(int _x,int _y,int _n);
    int x,y,n;
};

Coord::Coord () {}
void Coord::init(int _x,int _y,int _n) {
    x = _x;
    y = _y;
    n = _n;
}

int main()
{
    // Creates Level
    ifstream inputFile;
    inputFile.open("level.txt");
    string input;
    vector<string> level;
    while (getline(inputFile,input)) {
        level.push_back(input);
    }
    inputFile.close();

    // Establish player and target coords
    Coord player; // not being used atm.
    Coord target;
    for (unsigned int y = 0; y < level.size(); y++) {
        for (unsigned int x = 0; x < level[y].size(); x++) {
            switch (level[y][x]) {
            case 'P' : // If char is player
                player.init(x,y,0);
                break;
            case 'T' : // If char is target
                target.init(x,y,0);
                break;
            }
        }
    }

    for (unsigned int i = 0; i < level.size(); i++) {
        printf("%s\n",level[i].c_str());
    }
    printf("\n");

    // Breadth-First
    list<Coord> frontier;
    frontier.push_back(target);
    list<Coord> cameFrom;
    cameFrom.push_back(target);
    list<Coord>::iterator it;
    for (it = frontier.begin(); it != frontier.end(); it++) {
        // Creating neighbors
        Coord current = *it;
        //printf("Evaluating neighbors of (%d,%d)\n",current.x,current.y);
        Coord temp;
        list<Coord> neighbors;
        temp.init(current.x-1,current.y,0);
        if (level[temp.y][temp.x] != 'X') { neighbors.push_back(temp); }
        temp.init(current.x,current.y-1,0);
        if (level[temp.y][temp.x] != 'X') { neighbors.push_back(temp); }
        temp.init(current.x+1,current.y,0);
        if (level[temp.y][temp.x] != 'X') { neighbors.push_back(temp); }
        temp.init(current.x,current.y+1,0);
        if (level[temp.y][temp.x] != 'X') { neighbors.push_back(temp); }
        list<Coord>::iterator i2;
        for (i2 = neighbors.begin(); i2 != neighbors.end(); i2++) {
            // If neighbor isn't in frontier, add it
            bool exists = false;
            list<Coord>::iterator i3;
            for (i3 = frontier.begin(); i3 != frontier.end(); i3++) {
                if ((*i2).x==(*i3).x && (*i2).y==(*i3).y) {
                    exists = true;
                }
            }
            if (!exists) {
                frontier.push_back(*i2);
                cameFrom.push_back(current);
            }
        }
    }

    list<Coord>::iterator i4 = cameFrom.begin();
    for (it = frontier.begin(); it != frontier.end(); it++) {
        Coord cFron = *it;
        Coord cCame = *i4;

        //printf("Comparing coords of (%d,%d) and (%d,%d) (cameFrom), ",cFron.x,cFron.y,cCame.x,cCame.y);

        if (cFron.x==cCame.x && cFron.y==cCame.y) {
            //printf("No change.\n");
        } else {
            int difX = cFron.x-cCame.x;
            int difY = cFron.y-cCame.y;
            //printf("(%d,%d) ",difX,difY);
            char temp = '?';
            // This creates a chain of arrows that eventually reaches the target
            if      (difX == -1 && difY ==  0) { temp = 26; }
            else if (difX ==  0 && difY == -1) { temp = 25; }
            else if (difX ==  1 && difY ==  0) { temp = 27; }
            else if (difX ==  0 && difY ==  1) { temp = 24; }
            level[cFron.y][cFron.x] = temp;
            //printf("Coordinate changed to '%c'.\n",temp);
        }
        i4++;
    }

    for (unsigned int i = 0; i < level.size(); i++) {
        printf("%s\n",level[i].c_str());
    }

    return 0;
}
Is this some variant of Djikstra's? Looks like it. Anyway, you should order the direction by the distance of that next tile from the target tile, and then either CW or CCW if the distances are equal. This is just a naive way though, don't take my word for it.
It is a variant of Djikstra's that's intended to be a bit simpler, otherwise I wouldn't have needed so many lists. I was going to move from this to a proper implementation of Djikstra's and eventually A* as my understanding improved

I was able to get very close to the effect I wanted with the following code, but it's still not quite symmetrical.


Code:

        if ((current.x+current.y) % 2 == 0) {
                neighbors.reverse();
        }



Code:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                            X
X                            X
X                            X
X                            X
X                            X
X                            X
X             T              X
X                            X
X                            X
X                            X
X                            X
X                            X
X                            X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X→→→→→→→↓↓↓↓↓↓↓↓↓↓↓↓←←←←←←←←←X
X→→→→→→→→↓↓↓↓↓↓↓↓↓↓←←←←←←←←←←X
X→→→→→→→→→↓↓↓↓↓↓↓↓←←←←←←←←←←←X
X→→→→→→→→→→↓↓↓↓↓↓←←←←←←←←←←←←X
X→→→→→→→→→→→↓↓↓↓←←←←←←←←←←←←←X
X→→→→→→→→→→→→↓↓←←←←←←←←←←←←←←X
X→→→→→→→→→→→→→T←←←←←←←←←←←←←←X
X→→→→→→→→→→→→↑↑↑←←←←←←←←←←←←←X
X→→→→→→→→→→→↑↑↑↑↑←←←←←←←←←←←←X
X→→→→→→→→→→↑↑↑↑↑↑↑←←←←←←←←←←←X
X→→→→→→→→→↑↑↑↑↑↑↑↑↑←←←←←←←←←←X
X→→→→→→→→↑↑↑↑↑↑↑↑↑↑↑←←←←←←←←←X
X→→→→→→→↑↑↑↑↑↑↑↑↑↑↑↑↑←←←←←←←←X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


There's still a tiny bit of bias here, I'm trying to figure it out.
The issue is that, when adding neighbors, one direction always gets added first, giving it higher priority than both of the perpendicular directions, and another always gets added last, giving it lower priority.

I think I know how to correct for the bias, but it would be rather complicated. My idea would involve processing every node added with each "step" of the fronteir in parallel, checking and potentially adding one neighbor at a time for each. The order of neighbors checked for each node would depend on the cameFrom direction, which would govern a rotation of the order in which to check neighbors by 0-3 positions.

It may also be necessray to combine the rotation with the reversal you already suggested, but my head is exploding trying to imagine all the variables combining so I can't say for sure.
I think the appropriate thing to do is to not even care about which coordinate was evaluated from which coordinate, because it's not necessary for pathfinding.

I just need to determine how far away each coordinate is from the source point "T". I always intended to do this with the n variable in that class.

however an object moves will just be handled by the object when it has two or more agreeable paths of which to choose from. It could be random, or maybe there's object specific behavior, I don't know.

Determining how characters move from this algorithm is probably a mistake and not worth implementing.
So I worked on things a little more and I came up with my own flavor for the A* pathfinding algorithm I can use for an ascii-type game that given a map that contains the player and target coordinates, will provide a list of the optimal moves for the shortest path between those two points (if there is more than one, it shows all of them, some other mechanism would be used to pick the appropriate one).

It works and it runs pretty fast, even for larger or more complicated maps, and it has some support for tile traversal with a higher cost. I'm wondering if there was any way to make the code reasonable smaller and/or more efficient. I'm not too great at C++ yet, so it'd be nice to kind of see other people's styles reflected in the same sort of code I wrote.

If there's any really obvious inefficiencies, it'd be good to know.


Code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <queue>

using namespace std;

const int NDIR = 4; // number of possible directions to go at any position

// if NDIR = 4
const int xDir[NDIR] = {1, 0, -1, 0};
const int yDir[NDIR] = {0, 1, 0, -1};

// if NDIR = 8
//const int xDir[NDIR] = {1, 1, 0, -1, -1, -1, 0, 1};
//const int yDir[NDIR] = {0, 1, 1, 1, 0, -1, -1, -1};

struct Coord {
    int x;
    int y;
    int n;
    int h;
    int a;
};

class CompareCoord {
public:
    bool operator()(Coord& t1, Coord& t2)
    {
       if (t1.a < t2.a) return false;
       return true;
    }
};

int heuristic(Coord a, Coord b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int areMatch(Coord a, Coord b) {
    if (a.x == b.x && a.y == b.y && a.n == b.n && a.h == b.h && a.a == b.a) return true;
    return false;
}

int main()
{
    // Creates Level
    ifstream inputFile;
    inputFile.open("level.txt");
    string input;
    vector<string> level;
    while (getline(inputFile,input)) {
        level.push_back(input);
    }
    inputFile.close();

    Coord player;
    Coord target;
    for (int y = 0; y < (int)level.size(); y++) {
        for (int x = 0; x < (int)level[y].size(); x++) {
            switch (level[y][x]) {
            case 'P' : // If char is player
                player = {x,y,0,0,0};
                break;
            case 'T' : // If char is target
                target = {x,y,0,0,0};
                break;
            }
        }
    }
    target.h = heuristic(player,target);
    target.a = target.n + target.h;

    list<Coord> frontier;
    frontier.push_back(target);
    priority_queue<Coord, vector<Coord>, CompareCoord> pq;
    priority_queue<Coord, vector<Coord>, CompareCoord> pq_temp;
    pq.push(target);

    list<Coord> bestMoves;

    while (! pq.empty()) {
        Coord current = pq.top();
        if (level[current.y][current.x] == 'P') {
            break;
        }
        list<Coord> neighbors;
        Coord temp;

        for(int i = 0; i < NDIR; i++) {
            if ((current.x+current.y)%2 == 0) temp = {current.x+xDir[i],current.y+yDir[i],current.n+1,0};
            if ((current.x+current.y)%2 == 1) temp = {current.x+yDir[i],current.y+xDir[i],current.n+1,0};
            temp.h = heuristic(temp,player);
            temp.a = temp.n + temp.h;
            neighbors.push_back(temp);
        }

        list<Coord>::iterator iT;
        for (iT = neighbors.begin(); iT != neighbors.end(); iT++) {
            char charAt = level[(*iT).y][(*iT).x];
            switch (charAt) {
            case 'W' :
                (*iT).n++;
                (*iT).a = (*iT).n + (*iT).h;
            case 'P' :
            case ' ' :
                bool exists = false;
                list<Coord>::iterator iF;
                for (iF = frontier.begin(); iF != frontier.end(); iF++) {
                    if (heuristic(*iT,*iF)==0) {
                        exists = true;
                        if ((*iT).n<(*iF).n) {
                            iF = frontier.erase(iF);
                            exists = false;
                        }
                    }
                }
                if (!exists) {
                    frontier.push_back(*iT);
                    pq.push(*iT);
                    if ((*iT).h == 1) {
                        bestMoves.push_back(*iT);
                    }
                }
                break;

            }
        }
        if (areMatch(pq.top(),current)) {
            pq.pop();
        }

//    list<Coord>::iterator iF;
//    for (iF = frontier.begin(); iF != frontier.end(); iF++) {
//        Coord cFron = *iF;
//        //printf("Coord (%d,%d,%d,%d)\n",cFron.x,cFron.y,cFron.n,cFron.h);
//        char temp = (cFron.h % 10) + 48;
//        if (level[cFron.y][cFron.x] == ' ' || level[cFron.y][cFron.x] == 'W') {
//            level[cFron.y][cFron.x] = temp;
//        }
//    }
//    system("cls");
//    for (unsigned int i = 0; i < level.size(); i++) {
//        printf("%s\n",level[i].c_str());
//    }
//    system("pause");
    }

    list<Coord>::iterator iF;
//    for (iF = frontier.begin(); iF != frontier.end(); iF++) {
//        Coord cFron = *iF;
//        //printf("Coord (%d,%d,%d,%d)\n",cFron.x,cFron.y,cFron.n,cFron.h);
//        char temp = (cFron.h % 10) + 48;
//        if (level[cFron.y][cFron.x] == ' ' || level[cFron.y][cFron.x] == 'W') {
//            level[cFron.y][cFron.x] = temp;
//        }
//    }
//    system("cls");
//    for (unsigned int i = 0; i < level.size(); i++) {
//        printf("%s\n",level[i].c_str());
//    }

    for (iF = bestMoves.begin(); iF != bestMoves.end(); iF++) {
        Coord cFron = *iF;
        printf("Best Move Coord (%d,%d,%d,%d,%d)\n",cFron.x,cFron.y,cFron.n,cFron.h,cFron.a);
    }


    return 0;
}
Your use of lists may make the algorithm somewhat expensive. Otherwise it looks all right.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement