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:
Here's the input and output of the program as it's currently written:
Code:
And here's the source for that:
Code:
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
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXAnd 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;
}
