1,105,594 Community Members

Need help with pathfinding... URGENT!!!

robertstan79
Newbie Poster
1 post since Jul 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
Unverified Member
 
0
 

Hi, I am writing a program that uses post-order breadth first tree-traversal to give me a path navigating from one point in my house to another. Here is a map of my house: http://postimage.org/image/3vq80wdkx/. Here is the tree that I need to traverse and list all the possibilites of: http://postimage.org/image/nlbv9dp03/. For example, the possibilites are:
AB
ABC
ABCD
ABCDE
ABCF
ABCFI
ABCFIG
ABCFIH

How do I implement this in C++?

Member Avatar
deceptikon
Eternally Awesome
4,690 posts since Jan 2012
Reputation Points: 1,341 [?]
Q&As Helped to Solve: 688 [?]
Skill Endorsements: 104 [?]
Administrator
Featured
 
0
 

How are you storing the graph? That kind of matters in the implementation. ;) Another critical factor would be whether there's a cycle in the graph or not. It's simpler if you don't have to consider revisiting a node.

In fact, if there are no cycles then you can probably store the graph as a tree and call it good with a simple preorder traversal:

#include <iostream>
#include <vector>

using namespace std;

struct node
{
    char value;
    vector<node*> link;
};

void PreOrder(node* root)
{
    cout << root->value << ' ';

    for (vector<node*>::size_type i = 0; i < root->link.size(); ++i)
    {
        PreOrder(root->link[i]);
    }
}

int main(void)
{
    node tree[9];

    // Initialize to the stated graph
    tree[0].value = 'A'; tree[0].link.push_back(&tree[1]);
    tree[1].value = 'B'; tree[1].link.push_back(&tree[2]);
    tree[2].value = 'C'; tree[2].link.push_back(&tree[3]); tree[2].link.push_back(&tree[4]);
    tree[3].value = 'D'; tree[3].link.push_back(&tree[5]);
    tree[4].value = 'F'; tree[4].link.push_back(&tree[6]); tree[4].link.push_back(&tree[7]);
    tree[5].value = 'E';
    tree[6].value = 'I';
    tree[7].value = 'G'; tree[7].link.push_back(&tree[8]);
    tree[8].value = 'H';

    // Do a straight inorder traversal to display
    PreOrder(tree);

    return 0;
}

The only trick from there would be saving the current path at each node, which constitutes most of the effort of this solution after making the connection between your graph and a multi-way tree where a preorder traversal accomplishes the goal of pathfinding.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article