Solved

Depth-first search 2d array

Posted on 2004-03-29
7
2,747 Views
Last Modified: 2013-12-26
Hello

I’m programming in c++

I have a 2d array of ints
Int map[10][10];

Each element has value of 1 or 0
1 is passable
0 is not passable

I have 2 locations on the array
(2, 2) and (5, 5)

I want to make sure that the two positions are reachable by each other.
Please provide some sample code


i will give more points if you can show me how to do the same thing with a
A* search
Breadth-first search

Thank you
0
Comment
Question by:funvill
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
7 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10711174
Hi funvill,

Is this your homework assignment ?

Sunnycoder
0
 
LVL 2

Author Comment

by:funvill
ID: 10711212
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10711309
Ok ... here we go

step 1 : you need an entry point into the maze ... let us assume that it is 0,0

step 2 : now imagine that you have a tree of possible moves ... your initial position will be at the root of this tree ...
All possible positions after the next move would the children of a given node in the tree

e.g. take a simplistic matrix  
 E  1  0
 0  1  1
 1  1  0

E denotes the entry point .... now your root is 0,0
Assuming that diagonal moves are disallowed, you can only go to 0,1 in this case ... so your tree would look like
                              0,0
                               |
                               |
                              0,1
from 0,1 you can go to 1,1 only ... all other moves are disallowed ... so your search tree becomes
                              0,0
                               |
                               |
                              0,1
                               |
                               |
                              1,1

from here you have two options to follow ... either you can go to 1,2 or 2,1 .. thus your search tree becomes

                              0,0
                               |
                               |
                              0,1
                               |
                               |
                              1,1
                             /    \
                            /      \
                           1,2     2,1
and so on so forth ... In such a tree you need to find if there is a particular node present along any path ... If it is present, then it is reachable ... To find the node, you need to search the tree

You can use either DFS or BFS or A* to search the tree ... http://www.ics.uci.edu/~eppstein/161/960215.html gives a good explanation of BFS and DFS ...


Note that the search space I constructed above was a bit simple ... I did not take into account the nodes which have already been seen/processed ... To apply this kind of thing to your problem you need to keep a track of nodes already processed (the difference between DFS for a tree and DFS for a graph)

I think this should be good enough to get you started ....

Sunnycoder
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Author Comment

by:funvill
ID: 10711457
I know the theory behind all of these search patterns that’s not what I asked for.

I was just looking for a simple solution so I wouldn’t have to think so much (not having much spare time any more)

But if I don’t get a suitable answer by the weekend I guess I will just use a boost lib
http://www.boost.org/libs/graph/doc/breadth_first_search.html

Thank you for your time
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10711518
0
 
LVL 2

Author Comment

by:funvill
ID: 10720891
still not what i asked for :(
i spent 30min that i didn't have today and answered my own question


#include <queue>

#define MAP_SIZE_X      5
#define MAP_SIZE_Y      5

#define GOAL_X      3
#define GOAL_Y      4

#define START_X      0
#define START_Y      4

class cell
{
public:

      bool m_passable; ;
      bool m_marked;
};


class Coordinate
{
public:
    int x;
    int y;
    float heuristic;
};

const int DIRTABLE[4][2] = { {  0, -1 },    // N
                             {  1,  0 },    // E
                             {  0,  1 },    // S
                                          { -1,  0 }};    // W


int main()
{

      cell map[MAP_SIZE_X][MAP_SIZE_Y];
      int ax, ay;
      int x, y;

      int moves  = 0;
      bool found = false ;

      /// Make a map
      // =================

      /******
      X012345
      0000000
      1011100
      2010100
      3011100
      4@00X00
      5000000
      ******/
      // 0 = Passable
      // 1 = Not passable
      // @ = Current location
      // X = Goal

      /// set all to true
      // =================
      for (x = 0 ; x < MAP_SIZE_X; x++)
      {
            for (y = 0 ; y < MAP_SIZE_Y; y++)
            {
                  map[x][y].m_passable = true;
                  map[x][y].m_marked   = false ;
            }
      }

      map[1][1].m_passable = false;
      map[1][2].m_passable = false;
      map[1][3].m_passable = false;
      map[2][1].m_passable = false;
      map[2][3].m_passable = false;
      map[3][1].m_passable = false;
      map[3][2].m_passable = false;
      map[3][3].m_passable = false;      


      
      std::queue<Coordinate> Q;
      
      // Add the start to the que
      Coordinate pos;

      pos.x = START_X;
      pos.y = START_Y;
      pos.heuristic = 0.0f;

      Q.push(pos);


      /// Print the map
      // ===============
      for (x = 0 ; x < MAP_SIZE_X; x++)
      {
            for (y = 0 ; y < MAP_SIZE_Y; y++)
            {
                  if ( map[x][y].m_marked )
                  {
                        printf("[X]");
                  }
                  else
                  {
                        printf("[0]");
                  }
            }
            printf("\n");
      }
      


      // start the main loop
    while( Q.size() != 0 )
    {
            printf("=== Start of loop === \n");

            // pull the first cell off the queue and process it.
        pos.x = Q.front().x;
        pos.y = Q.front().y;
            Q.pop();
       
            printf("X=[%d] Y=[%d]\n",pos.x , pos.y);

            // check to see if its allready checked
            if ( map[pos.x][pos.y].m_marked == false )
            {
                  // status
                  printf("X=[%d] Y=[%d] New node\n",pos.x , pos.y);
                  // mark the cell as it is pulled off the queue.
                  map[pos.x][pos.y].m_marked = true ;

                  // we are at our gole then quit
                  if (pos.x == GOAL_X && pos.y == GOAL_Y)
                  {
                        printf("X=[%d] Y=[%d] We are at our goal\n",pos.x , pos.y);
                        found = true ;
                        break;
                  }


                  // loop through each direction.
            for( int dir = 0; dir < 4; dir++ )
            {
                // retrieve the coordinates of the current adjacent cell
                ax = pos.x + DIRTABLE[dir][0];
                ay = pos.y + DIRTABLE[dir][1];

                // check to see if the adjacent cell is a valid index,
                // passable
                if( ax >= 0                  && ay >= 0 && 
                              ax < MAP_SIZE_X && ay < MAP_SIZE_Y)
                        {
                              if ( map[ax][ay].m_passable == true )
                              {
                                    printf("\tChecking X=[%d] Y=[%d]\n", ax , ay);
                                    // add the new ones to the que
                                    pos.x = ax ;
                                    pos.y = ay ;
                                    Q.push(pos);

                                    /// Print the map
                                    // ===============
                                    for (x = 0 ; x < MAP_SIZE_X; x++)
                                    {
                                          for (y = 0 ; y < MAP_SIZE_Y; y++)
                                          {
                                                if ( ax == x && ay == y )
                                                {
                                                      printf("[@]");
                                                }
                                                else if ( map[x][y].m_marked )
                                                {
                                                      printf("[X]");
                                                }
                                                else
                                                {
                                                      printf("[0]");
                                                }
                                          }
                                          printf("\n");
                                    }

                                    moves++;

                              }
                              else
                              {
                                    printf("\tNot passable X=[%d] Y=[%d]\n", ax , ay);
                              }
                        }
                        else
                        {
                              printf("\tOut of bounds X=[%d] Y=[%d]\n", ax , ay);
                        }
                  }
            }
            else
            {
                  // we have allready been here
                  printf("X=[%d] Y=[%d] is allready marked\n",pos.x , pos.y);

            }

    }

      printf("\n\n==============================\n");
      
      if ( found )
      {
            printf("Found in %d moves\n", moves);
      }
      else
      {
            printf("Did not find out goal\n");
      }
      printf("End of program\n");

      return 0;
}
0
 
LVL 5

Accepted Solution

by:
Netminder earned 0 total points
ID: 10721750
User resolved; points (50) refunded and question closed.

Netminder
Site Admin
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an antispam), the admini…

733 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question