Solved

Depth-first search 2d array

Posted on 2004-03-29
7
2,502 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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

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 …
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.
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
This video gives you a great overview about bandwidth monitoring with SNMP and WMI with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're looking for how to monitor bandwidth using netflow or packet s…

746 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

8 Experts available now in Live!

Get 1:1 Help Now