Question

Printing off the Path in an Adjacency Matrix (Pacman)

Asked by: Arcyani

Hello everyone.

I have an example of a Pacman game, we are doing path finding and we are looking at BFS (Breadth first search)

I need to be able to write down all the paths that the BFS search explores when searching for a path to the "goal". It suggests that It would be quicker to edit the pathPlanBFS function so that the program writes out the paths for you.

There are many loops within loops and I am not sure what entity I should be printing off or where to put the cout.

And can someone explain this line to me as well

if(adjacencyMatrix[currentIndex][otherIndex])

What is the if statement actually asking, if either is true or false?

- Thanks

list<int> Level::planPathBFS(short currentX, short currentY, short goalX, short goalY, short debugMode)
{
        /*
        Each node in the graph has an index.
        For and given x and y position this can be found b calling index(x,y) e.g.
        goalIndex = index(goalX, goalY); 
        This function returns a path, a linked list of nodes, give a route through the map e.g.
        <555, 554, 553, 552, 551> 
        This path is contructed using a breadth first approach.
        The initial node is added to possible path list.
        This possible papth list is added to a second list, the list of possible paths.
        So after initialisation this list of possible paths only has one element,
        a list containing the current nodes index:
        <<555>> 
        This list is then expanded as follows:
                For each element in the list:
                        Take the tail of the list as the current node
                        Check for connections from this node to other nodes (using the adjacency matrix)
                        If there is a connection
                                Add a new path to the list consisting of the current path + the (other) new node
                                Check if this new is the goal node, if so return the current path
                        End 
        Should look something like this:
        Start node is 555
        Goal node is 552 
        <<555>>
        <<555,554>,<555,556>>
        <<555,554,553>,<555,554,555>,<555,556,555>,<555,556,557>>
        <<555,554,553,552>,... goal found to return path: <555,554,553,552>
                                 
        */
        list<int> path; // Final path to be constructed
        list<list<int>> pathTree; // BFS tree
        list<list<int>> pathTreeTmp; // BFS tree - used in working
        list<int> ppath;// Partial path used in BSF tree construction 
        list<list<int>>::iterator ptIter; // Iterator used for looping through the list of partial paths 
        int goalIndex; // Index of the goal node
        int currentIndex; // Index of the current node
        int otherIndex; // Index of a second node
        bool goalFound = false; // Has the goal been found? 
        goalIndex = index(goalX, goalY); // Set the goal index
        currentIndex = index(currentX, currentY); // Set the index of the current node 
        ppath.push_front(currentIndex); // Add the current index to a partial path
        pathTree.push_front(ppath); // Add that partial path to the list of partial paths 
        while (!goalFound) // Until we find the goal node
        {
                // Loop through the partial paths
                for(ptIter=pathTree.begin();ptIter != pathTree.end(); ++ptIter)
                {
                        ppath = *ptIter; // Take the next partial path
                        currentIndex = ppath.back(); // Find the index of the current node, the last node in the curretn partial path 
                        // Look in the adjacency matrix for connections to other nodes
                        for(otherIndex = 0; otherIndex < nNodes; otherIndex++)
                        {
                                // Check for a connection
                                if(adjacencyMatrix[currentIndex][otherIndex])
                                {
                                        // If so make a new partial path which is equal to the current path
                                        list<int> ppathTmp = ppath;
                                        // Add the index of the new node to the end of the path
                                        ppathTmp.push_back(otherIndex);
                                        // Add this new partial path to the list of partial paths
                                        pathTreeTmp.push_back(ppathTmp);
                                        // If the new node is the goal node
                                        if(otherIndex == goalIndex)
                                        {
                                                goalFound = true; // Set goal found to true
                                                cout << pathTreetmp ;
                                                path = ppathTmp;  // Set the path which will be return to the current partial path
                                        }
                                }
                        }
                } 
                pathTree = pathTreeTmp; // Set the list of paths to the new list
                pathTreeTmp.erase(pathTreeTmp.begin(),pathTreeTmp.end()); // Delete everything in the new list so it's ready to be filled again
        } 
 
 
        return path; // Return the path - starts with th current node ends in the goal node
}

                                  
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:

Select allOpen in new window

This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.

Subscribe now for full access to Experts Exchange and get

Instant Access to this Solution

  • Plus...
  • 30 Day FREE access, no risk, no obligation
  • Collaborate with the world's top tech experts
  • Unlimited access to our exclusive solution database
  • Never be left without tech help again

Subscribe Now

Asked On
2009-11-01 at 22:30:34ID24862908
Tags

Path Finding C++ Adjacency Matrix

Topics

C++ Programming Language

,

Game Programming

,

Programming Languages

Participating Experts
3
Points
420
Comments
7

Trusted by hundreds of thousands everyday for fast, accurate and reliable tech support.

  • "The time we save is the biggest benefit of Experts Exchange to Warner Bros. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange." Mike Kapnisakis, Warner Bros.
  • "Our team likes having a resource that is more secure than just using Google and most experts using this service really know their stuff. It's nice to look here first versus using Google." Dayna Sellner, Lockheed Martin
  • "Anytime that I've been stumped with a problem, 9 out of 10 times Experts Exchange has either the accepted solution or an open discussion of the potential solution to the problem." Kenny Red, eBay Inc.

See what Experts Exchange can do for you.

Got a question?

We've got the answer.

Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.

Screenshot of Experts Exchange Knowledgebase

Need individual assistance?

Our experts are ready to help.

If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.

Screenshot of Experts Exchange Knowledgebase

Want to learn from the best?

Read articles from industry experts.

Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.

Screenshot of an Article

Working on a long term project?

Store your work and research.

Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.

Screenshot of Experts Exchange Knowledgebase

Access the answers to your technology questions today.

Subscribe Now

30-day free trial. Register in 60 seconds.

What Makes Experts Exchange Unique?

Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.

Trusted by the world's most respected brands.

image of each brand's logo

Faithfully serving IT professionals since 1996.

Experts Exchange Logo

Try it out and discover for yourself.

Subscribe Now

30-day free trial. Register in 60 seconds.

Related Solutions

  1. AI for card games
    I'm trying to write a card game in c++. The game is pitch (hi-lo-jack). I'd like some sort of kick start to the ai portion of the program. Like how to represent the cards and how to tell the computer what to throw. Thanks, Karl
  2. adjacency matrix or 2-d array
    Hi all, if writing in pas, would 2d array or adjacency matrix be better or easier. i am preparing to write a program on subjects, objects and directed edges (like a b-tree) with checking for cycle. and also is there any way we could write program to show the tree rather th...
  3. BF 1942 CTD
    Anyone ever heard of this problem, a pretty common problem where BF 1942 crashes to desktop when the map is loading in multiplayer after you connected to a server, spontaneously occurs. Does anyone have a fix for this? I have... 2.2 ghz AMD 1 GB RAM 128 mb geforce 4 ti 4200 ...
  4. Graphs, Adjacency Table/List Examples?
    I'm trying to learn more about graph implementation using Adjacency tables/matrix, adjacency list, and linked lists. I have been searching but can't really find a SIMPLE example. I'm basically wanting to see how something is inserted into graph (vertices/edges) and printing...
  5. Writing a program to perform DFS and BFS
    I am to write a program to perform Depth First Search and Breadth First Search operations on a graph. I must implemtnt ADT Graph in either array-based or adjacent lists and other ADTs like stack and queue. The main function must construct the graph first and then perform DF...

Free Tech Articles

  1. WARNING: 5 Reasons why you should NEVER fix a computer for free.
    It is in our nature to love the puzzle. We are obsessed. The lot of us. We love puzzles. We love the challenge. We thrive on finding the answer. We hate disarray. It bothers us deep in our soul. W...
  2. SCCM OSD Basic troubleshooting
    SCCM 2007 OSD is a fantastic way to deploy operating systems, however, like most things SCCM issues can sometimes be difficult to resolve due to the sheer volume of logs to sift through and the dispe...
  3. Migrate Small Business Server 2003 to Exchange 2010 and Windows 2008 R2
    This guide is intended to provide step by step instructions on how to migrate from Small Business Server 2003 to Windows 2008 R2 with Exchange 2010. For this migration to work you will need the fo...
  4. Create a Win7 Gadget
    This article shows you how to create a simple "Gadget" -- a sort of mini-application supported by Windows 7 and Vista. Gadgets can be dropped anywhere on the desktop to provide instant information, ...
  5. Outlook continually prompting for username and password
    There have been a lot of questions recently regarding Outlook prompting for a username and password whilst using Exchange 2007. There are a few reasons why this would happen and I will try to cover t...
  6. Backup Exchange 2010 Information Store using Windows Backup
    There seems to be quite a lot of confusion around the ability to backup Exchange 2010 using the built in Windows Backup feature. This stems from the omission of this feature prior to Exchange 2007 s...

Cloud Class Webinars

  1. Avoiding Bugs in Microsoft Access
    Alison Balter takes and in-depth look at avoiding bugs in Access. In this webinar you will learn about using the immediate window to debug your applications, invoking the debugger, using breakpoints to troubleshoot, stepping through code, setting the next statement to execute, ...
  2. Top 10 Best New Features in Visio 2010
    Scott Helmers gives live demonstrations of the top 10 new features in Visio 2010. This webinar will teach you how to create compelling diagrams by adding shapes to the page with a single click, linking the shapes in a diagram to data in Excel (or SQL Server, or SharePoint), ...
  3. IT Consultant Business Secrets Revealed
    Michael Munger, Experts Exchange tech pro and IT consultant, pulls back the curtain on his very successful businesses and answers question on every IT consultant and business owner should know about. He shares secrets on what he did to solve the 5 most common problems in IT, ...
  4. Disaster Recovery and Business Continuity
    Quest CTO, Mike Billon, gives an overview of the steps involved in building a dunamic disaster recovery plan. Through case studies and an examination of software/hardware tooles for monitoring and testing, you'll gain a better understandin of where you are, where you want ...
  5. Organize Your Visio Diagrams with Containers and Lists
    Scott Helmers uses cross functional flowcharts, wireframe diagrams, data graphic legends and seating charts to teach you: how to ustilize all three new structured diagram components in Visio 2010, the best practices for organizeing shapes in previous version of Visio, how to organize ...
  6. How to Us Objects, Properties, Events and Methods in Microsoft Access
    Alison Dalter gives an in-depbth look at objects, properties, events and methods in Microsoft Access. In this webinar you will learn about using the object browser, referring to objects, working with properties and methods, working with object variables, understanding the ...

Join the Community

Give a Little. Get a Lot.

Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.

Join the Community

Answers

 

by: Let_Me_BePosted on 2009-11-02 at 02:27:48ID: 25718262

What do you mean all paths? All paths that lead to goal? Then simply instead of setting goalFound=true, output the path.

adjacencyMatrix is obviously an adjacency matrix marking what nodes are adjacent (you can move from one to another).

 

by: ArcyaniPosted on 2009-11-02 at 04:00:07ID: 25718635

Output what entity?

 

by: itsmeandnobodyelsePosted on 2009-11-02 at 08:47:40ID: 25721019

>>>> can someone explain this line to me as well
>>>> if(adjacencyMatrix[currentIndex][otherIndex])

The if condition is true if the adjacencyMatrix at cell (currentIndex, otherIndex) is not 0.

 

by: itsmeandnobodyelsePosted on 2009-11-02 at 08:49:49ID: 25721037

>>>>  and we are looking at BFS (Breadth first search)

Can you explain wht that means?

 

by: ArcyaniPosted on 2009-11-02 at 10:11:18ID: 25721881

BFS is used in AI in computer games.

let's say I'm in a room and the computer player is in another room, the program checks for all the possible routes until it can reach the room I am currently in.

Its a tree that starts at 1 and from 1 it splits into a number of different branches, the program goes left hand side first and checks all the rooms until it reaches the leaf goal.

 

by: trinitrotoluenePosted on 2009-11-02 at 18:18:41ID: 25725611

arcyani:

pretty intuitive and straightforward for an AI algo.

just look at the below two lines. Your requirement is to print all the possible explored paths. So ppathTmp stores the possible indexes added to the current path. So print this list out everytime. You will see each index which gets added to the path list.

Next there could be several other paths, this is why you have a pathTree. Print this list out too.




list<int>::iterator i;
list<int>::iterator j; 

ppathTmp.push_back(otherIndex);
//prints out the path with current index which got added to the path
for(i= ppathTmp.begin(); i != ppathTmp.end(); ++i) cout << *i << " "; 
// Add this new partial path to the list of partial paths
pathTreeTmp.push_back(ppathTmp);
//add similar code to print out all paths in all path lists in the path tree
  
                                              
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Select allOpen in new window

 

by: ArcyaniPosted on 2009-11-03 at 09:28:14ID: 31648730

Thanks for the help guys!

20120131-EE-VQP-002

3 Ways to Join

30-Day Free Trial

The Experts

98% positive feedback on 31,087 answers since March 2000. angeliii is a Microsoft Most Valuable Professional for his work with MS SQL Server & Develoment.

He has also proven his knowledge of Visual Basic Programming, PHP Scripting and Oracle Databases.

The Experts

97% positive feedback on 10,752 answers since July 2000. lrmoore has more than 18 years experience in the networking industry.

The six-time Mircosoft MVPs specialties include firewalls, virtual private networking, and network management.

Testimonials

"...and excellent source for support... Kind of like having your very own IT dept." Electriciansnet

Testimonials

"I was apprehensive at signing up at first. However... it has already made my life as an IT administrator much easier." JaCrews

Testimonials

"WOW! You guys have great, active, and knowledgeable people on here." moore50

Business Clients

Business Clients

In the Press

"If you’ve got a question... Experts Exchange can supply an answer.”

In the Press

"...an invaluable aid for both IT professionals and those who require tech support."

In the Press

"where IT professionals provide quick answers on just about any topic"

Business Account Plans

Loading Advertisement...