im currently trying to code Pacman in C++. Im doing it in RAD Studio 10.2 (Embarcadero IDE) because we have to use it. I implemented a C++-Source-Code for the Ghost-Pathfinding from the Internet. But it never finds a path.
First things first - this is my the source code (that matters for the problem):
static int map[ROWS][COLUMNS] = { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 2, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 2, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 0, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 7, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 7, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 3, 1, 1, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 3, 3, 3, 3, 3, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 3, 12, 3, 13, 3, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 3, 3, 14, 3, 3, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 2, 0, 0, 0, 5, 0, 0, 0, 2, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 3, 1, 0, 1, 3, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 2, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 2, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
const int n = 60; // horizontal size of the map
const int m = 60; // vertical size size of the map
static int closed_nodes_map[n][m]; // map of closed (tried-out) nodes
static int open_nodes_map[n][m]; // map of open (not-yet-tried) nodes
static int dir_map[n][m]; // map of directions
const int dir = 4; // number of possible directions to go at any position
static int dx[dir] = { 1, 0, -1, 0 };
static int dy[dir] = { 0, 1, 0, -1 };
int Gx, Gy, Px, Py;
using namespace std;
void TForm1::GhostMove(Ghost *ghost) {
Gx = ((ghost->X)-((ghost->X)%32))/32;
Gy = ((ghost->Y)-((ghost->Y)%32))/32;
Px = ((player->X)-((player->X)%32))/32;
Py = ((player->Y)-((player->Y)%32))/32;
Label1->Caption = Py;
string st = pathFind(Gx, Gy, Px, Py);
UnicodeString str = st.c_str();
}
string pathFind(const int &xStart, const int &yStart,
const int &xFinish, const int &yFinish) {
static priority_queue<node> pq[2]; // list of open (not-yet-tried) nodes
static int pqi; // pq index
static node* n0;
static node* m0;
static int i, j, x, y, xdx, ydy;
static char c;
pqi = 0;
// reset the node maps
for (y = 0; y<m; y++)
{
for (x = 0; x<n; x++)
{
closed_nodes_map[x][y] = 0;
open_nodes_map[x][y] = 0;
}
}
// create the start node and push into list of open nodes
n0 = new node(xStart, yStart, 0, 0);
n0->updatePriority(xFinish, yFinish);
pq[pqi].push(*n0);
open_nodes_map[x][y] = n0->getPriority(); // mark it on the open nodes map
// A* search
while (!pq[pqi].empty())
{
// get the current node w/ the highest priority
// from the list of open nodes
n0 = new node(pq[pqi].top().getxPos(), pq[pqi].top().getyPos(),
pq[pqi].top().getLevel(), pq[pqi].top().getPriority());
x = n0->getxPos(); y = n0->getyPos();
pq[pqi].pop(); // remove the node from the open list
open_nodes_map[x][y] = 0;
// mark it on the closed nodes map
closed_nodes_map[x][y] = 1;
// quit searching when the goal state is reached
//if((*n0).estimate(xFinish, yFinish) == 0)
if (x == xFinish && y == yFinish)
{
// generate the path from finish to start
// by following the directions
string path = "";
while (!(x == xStart && y == yStart))
{
j = dir_map[x][y];
c = '0' + (j + dir / 2) % dir;
path = c + path;
x += dx[j];
y += dy[j];
}
// garbage collection
delete n0;
// empty the leftover nodes
while (!pq[pqi].empty()) pq[pqi].pop();
return path;
}
// generate moves (child nodes) in all possible directions
for (i = 0; i<dir; i++)
{
xdx = x + dx[i]; ydy = y + dy[i];
if (!(xdx<0 || xdx>n - 1 || ydy<0 || ydy>m - 1 || map[xdx][ydy] == 1
|| closed_nodes_map[xdx][ydy] == 1))
{
// generate a child node
m0 = new node(xdx, ydy, n0->getLevel(),
n0->getPriority());
m0->nextLevel(i);
m0->updatePriority(xFinish, yFinish);
// if it is not in the open list then add into that
if (open_nodes_map[xdx][ydy] == 0)
{
open_nodes_map[xdx][ydy] = m0->getPriority();
pq[pqi].push(*m0);
// mark its parent node direction
dir_map[xdx][ydy] = (i + dir / 2) % dir;
}
else if (open_nodes_map[xdx][ydy]>m0->getPriority())
{
// update the priority info
open_nodes_map[xdx][ydy] = m0->getPriority();
// update the parent direction info
dir_map[xdx][ydy] = (i + dir / 2) % dir;
// replace the node
// by emptying one pq to the other one
// except the node to be replaced will be ignored
// and the new node will be pushed in instead
while (!(pq[pqi].top().getxPos() == xdx &&
pq[pqi].top().getyPos() == ydy))
{
pq[1 - pqi].push(pq[pqi].top());
pq[pqi].pop();
}
pq[pqi].pop(); // remove the wanted node
// empty the larger size pq to the smaller one
if (pq[pqi].size()>pq[1 - pqi].size()) pqi = 1 - pqi;
while (!pq[pqi].empty())
{
pq[1 - pqi].push(pq[pqi].top());
pq[pqi].pop();
}
pqi = 1 - pqi;
pq[pqi].push(*m0); // add the better node instead
}
else delete m0; // garbage collection
}
}
delete n0; // garbage collection
}
return ""; // no route found
}
So as you can see it first creates a map - this looks like this: (Each Tile is 32*32)
Then for the GhostMoving it tries to find the shortest path to the Player. But if click the Button for Testing the result/my teststring/testlabel is "" which means no path got found.
I dont really unterstand this because like in the extern algorithm code from the internet my Obstacles(Walls) are 1 in the map array.
So I dont really see through all this - is it maybe because of the Tilesize?
Thanks for your help