Solved

Depth-first search 2d array

Posted on 2004-03-29
7
2,535 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
  • 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

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…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
This Micro Tutorial will give you a basic overview how to record your screen with Microsoft Expression Encoder. This program is still free and open for the public to download. This will be demonstrated using Microsoft Expression Encoder 4.
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …

867 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now