OK, the main purpose of my project has been implementing Reinforcement Learning in Pacman. I have spent all my time and energy, trying to get that right. But now I have to implement pathfinding in order to compare the two techniques'' performances. I do in general understand, the principles of pathfinding, the graphs, nodes, links etc, and how they are structured. I have already used blind-search (just moving towards pacman without considering the costs) but its not enough. I was thinking of using Breadth-First search. The problem is I have no idea how to implement it in my code. I guess I have to treat each intersection as a node, and the path between intersections as a link. And I know I have to calculate the cost of paths. But the question is HOW to implement it in my code? Can you PLEASE give me some guidance. Any help would be greatly appreciated. I am using a 2D integer array for my maze, and I am programming it in Java. Also if you think that breadth-first might not be suitable, please let me know.

If this helps I have C++ code on my site for Breadth-first, Depth-First, Dijkstra and A* implementations. It is in console mode, but this week i have also been writing a Pacman game which uses these algorithms for the ghosts.

CurrentProjects

[edited by - Defcom on April 24, 2003 5:06:35 AM]

quote: Original post by pars
I was thinking of using Breadth-First search. The problem is I have no idea how to implement it in my code. I guess I have to treat each intersection as a node, and the path between intersections as a link.

It''s easier to begin with treating every possible square as a node, and every direction of movement from each square as a link. This is a little wasteful in tunnel-like mazes such as Pacman, but will be easier to develop.

BFS is pretty simple, usually revolving around a queue of nodes in a simple implementation. You start with the original node, find all the adjacent nodes, and put them on the back of the queue. Store the examined node in a different list. Then you get the next node off the front of the queue and repeat this process. The only other real detail is avoiding going in circles, by checking that you never add 2 nodes with the same position to the queue. Each node should generally contain a position (eg. x/y values or an index into your array) and a reference/pointer to the node that came before it. When you find the destination, these references to previous nodes will constitute your path.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]