2D Pathfinding, need help

[Mr Random]

Hi guys I've been making a simple game of pacman using c++ and SFML. Currently I have the map, Pac-pills, Pac-man, Movement and Powerpills in the game all working as intended.

I'm trying to implement my first ghost and get him fully working before worrying about the others

I really need help making my ghost chase Pacman, After some research I'd like to use Dijkstra's algorithm and nodes but I cant figure out how to implement these into pacman.

I've found several tutorials that show how to use the algorithm, finding a path between 3 or 4 nodes but i find them confusing and I dont see how they work for pathfinding.

The main things I'm having problems with is giving a node a position in my map, how to make the ghost move according to the nodes positions and how to detect which node is closest to the player.

Any help would be appreciated.

[hamsterman]

Commonly a node means a tile (provided that you use a tile based map. If you don't, describe what you use). You'd declare a node as struct Node{ int x, y, cost; Node* parent; };, possibly having a Tile* instead of x and y coordinates.
A ghost would own a list of nodes it needs to go through. It should move towards the first node in the list, and after reaching it, pop it from the list.

Should I try to explain the algorithm itself ?

[Mr Random]

Thank you, for your response.

I have a text file filled with 0's 1's and 2's where o is a black space or tile, 1 is a wall and 2 is a pac-dot.
If i changed this file to have 3's at key locations, basically every turn on the pacman map, when reading from this file I could place a node there correct?

I understand your declaration and it easily answers my question about how to give the node a co-ordinate, but i don't understand the purpose of "Node* parent" can u explain this further please.

I believe i understand how the algorithm works and how to cycle through the nodes but any advice or suggestions to implement it would be greatly appreciated.

I will play around with nodes and post again tomorrow to let you know how it goes

Thanks again for your help

[hamsterman]

You could place the nodes on corners only, but then you have your problem with figuring out which node you want to find. You could, for example, keep track of the last node Pac-man passed and go towards it . Using all tiles as potential nodes might be easier though.

"parent" is for backtracking. Once you've reached the desirable node, you need to know which nodes you went through. Though I guess this is not the only way to do it.

If you haven't, look into A* (a star). It's a slightly different version, more appropriate when nodes have positions. I have a feeling you'd find more game-oriented examples and tutorials about it.

[eraggo]

About the A* pathfinding you can get good reference from http://www.policyalmanac.org/games/aStarTutorial.htm

It is easy to understand (AFAIK)

[Mr Random]

Hi guys thanks for the replies.

I thought i understood how everything was going to work but I cant manage to even get 1 Node to work let alone the amount i need. I also don' understand how to link the nodes to each other making a path between them.

At the moment I'm reading from my map file and trying to put a node in place of a '3'

At the moment I'm trying to implement the node like this

	struct Node{ int x, y, cost; Node* parent; };
	vector<Node*> Graph;

In the header file

App::Node NodeA;
NodeA.x = WallX;
NodeA.y = WallY;
NodeA.cost = 20;
Graph.push_back(&NodeA);

Inside the function where In reading from my map file

Im still not sure what to do with Node* parent.

If anyone could help me out with an example implementation or how to use the nodes I would really appreciate it.

[hamsterman]

The link eraggo posted has an example in it.
Again, you could do it with only several nodes, but it would be easier to assume that every tile has a node (assume because you don't need to create all of them). The problem with making a graph of your own is that you then need a way to tell what nodes can be reached from another one. That would add a vector<Node*> neighbours; to your Node struct. This vector would be difficult to build, especially since it is not explicitly stated what a node's neighbours are in your map file. If you use tiles for nodes, you know that from a node (x;y) you can go to (x+1;y), (x;y+1), (x-1;y) or (x;y-1), unless some of them are walls.