Iterate over the adjacent elements in a matix container

Discussion in 'C++' started by Alexander, Sep 26, 2011.

  1. Alexander

    Alexander Guest

    Hello everyone!

    I need a way to perform an action in adjacent positions in a matrix (grid) container.

    Example 1:
    In a Minesweeper game, if a square is empty and there are no mines around it, all the empty squares around it should be opened, and all the empty squares around them, and ... well, you get the point.

    Example 2:
    In a painting program, when a 'fill' tool is used, when a pixel is clicked, all the adjacent squares, and their, adjacent squares, and... with the same color get colored in another way.

    Could you tell me about a possibly simple, possibly efficient (emphasis on simplicity though) for implementing stuff like that?

    If I haven't made myself clear enough, or you have any questions, please ask!

    Thank you!

    P.S. 1:
    Sorry for posting to this group, this is not a c++ specific question, but I did not find a more suitable group, and I usually program in C++ (though recently I'm falling in love with Python for the quick-and-dirty jobs)

    P.S. 2:
    In case you think I'm a student asking help for his homework, I would be perfectly happy with general answers, like just the name of an algorithm. Anyway that's not the case. (I am a student, but in high-school, programming is a hobby for me).
    Alexander, Sep 26, 2011
    #1
    1. Advertising

  2. On 9/26/2011 3:44 PM, Alexander wrote:
    > I need a way to perform an action in adjacent positions in a matrix
    > (grid) container. [..]
    >
    > P.S. 1: Sorry for posting to this group, this is not a c++ specific
    > question, but I did not find a more suitable group, and I usually
    > program in C++ (though recently I'm falling in love with Python for
    > the quick-and-dirty jobs)


    Try comp.programming.

    >[..]


    V
    --
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 26, 2011
    #2
    1. Advertising

  3. Alexander

    puppi Guest

    On Sep 26, 4:44 pm, Alexander <> wrote:
    > Hello everyone!
    >
    > I need a way to perform an action in adjacent positions in a matrix (grid) container.
    >
    > Example 1:
    > In a Minesweeper game, if a square is empty and there are no mines aroundit, all the empty squares around it should be opened, and all the empty squares around them, and ... well, you get the point.
    >
    > Example 2:
    > In a painting program, when a 'fill' tool is used, when a pixel is clicked, all the adjacent squares, and their, adjacent squares, and... with the same color get colored in another way.
    >
    > Could you tell me about a possibly simple, possibly efficient (emphasis on simplicity though) for implementing stuff like that?
    >
    > If I haven't made myself clear enough, or you have any questions, please ask!
    >
    > Thank you!
    >
    > P.S. 1:
    > Sorry for posting to this group, this is not a c++ specific question, butI did not find a more suitable group, and I usually program in C++ (thoughrecently I'm falling in love with Python for the quick-and-dirty jobs)
    >
    > P.S. 2:
    > In case you think I'm a student asking help for his homework, I would be perfectly happy with general answers, like just the name of an algorithm. Anyway that's not the case. (I am a student, but in high-school, programmingis a hobby for me).


    Try a stack. Or, if you really favor bits of simplicity over
    efficiency, try recursion.
    puppi, Sep 26, 2011
    #3
  4. Paul <> wrote:
    > You could create two temp bool arrays of the same size.
    > One array indicates the checked squares as a 1 value, set the equivalent
    > index for the original square clicked on.
    > Start a loop which tests each of the four squares adjacent to *the
    > square*( starting with the square the user clicked as *the square*).
    > Test each adjacent index for equality(see note) , update the other bool
    > array to indicate which indices tested true.
    > Test one bool array against the other for an xor result.
    > If a true xor result is found then loop again[1] using the index that tested
    > true(xor test) as *the square*, if not end.
    > [1]Update the array that stores the tested squares to include the previous
    > *square* before relooping.


    As usual, you have no idea what you are talking about.

    What he wants is a depth-first search, which is relatively simple recursive
    algorithm:

    1) Make a function that takes the initial point to be marked as parameter.

    2) Mark that point.

    3) Call this function recursively with each point adjacent to that one
    which is empty (ie. to be included in the search) and not marked already.

    The algorithm will naturally terminate when all the connected empty points
    have been marked.
    Juha Nieminen, Sep 27, 2011
    #4
  5. Alexander

    Krice Guest

    On 26 syys, 22:44, Alexander <> wrote:
    > Example 2:
    > In a painting program, when a 'fill' tool is used, when a pixel is
    > clicked, all the adjacent squares, and their, adjacent squares, and..
    > with the same color get colored in another way.


    If you do some homework with google you'll find out that the routine
    is called flood fill. The easiest way to implement it is scan over
    the entire area with a seed number set to the point of origin:
    surrounding to-be-filled spaces get new seed number and those points
    are then processed in the next scan etc. until no more free spaces.
    Then you have a seed map which is the shape of the area.
    Krice, Sep 27, 2011
    #5
  6. On 9/27/11 3:12 AM, Juha Nieminen wrote:
    > Paul<> wrote:
    >> You could create two temp bool arrays of the same size.
    >> One array indicates the checked squares as a 1 value, set the equivalent
    >> index for the original square clicked on.
    >> Start a loop which tests each of the four squares adjacent to *the
    >> square*( starting with the square the user clicked as *the square*).
    >> Test each adjacent index for equality(see note) , update the other bool
    >> array to indicate which indices tested true.
    >> Test one bool array against the other for an xor result.
    >> If a true xor result is found then loop again[1] using the index that tested
    >> true(xor test) as *the square*, if not end.
    >> [1]Update the array that stores the tested squares to include the previous
    >> *square* before relooping.

    >
    > As usual, you have no idea what you are talking about.
    >
    > What he wants is a depth-first search, which is relatively simple recursive
    > algorithm:
    >
    > 1) Make a function that takes the initial point to be marked as parameter.
    >
    > 2) Mark that point.
    >
    > 3) Call this function recursively with each point adjacent to that one
    > which is empty (ie. to be included in the search) and not marked already.
    >
    > The algorithm will naturally terminate when all the connected empty points
    > have been marked.


    One problem with a depth-first search done this way is you will need a
    recursion depth equal to the maximum number of nodes that may need to be
    marked. A breadth first search, using a stack like structure to store
    the list of nodes to visit, may require less levels stored, and if using
    tail recursion optimization, doesn't actually need to use recursion.

    Pauls method is basically this except stores the locations to check in a
    bit map, and scans the bit map to find the next location, which is
    really neither breadth first or depth first. His method always uses 2
    bits per cell in the universe, and a lot of program looping to scan. A
    breadth first search needs to store a coordinate (maybe a 16 bit value
    for up to a 256x256 pattern), and typically needs a lot less of them. It
    also doesn't need to search to find the next point, so has a significant
    time savings for a possible small space cost.
    Richard Damon, Sep 27, 2011
    #6
  7. Richard Damon <> wrote:
    > One problem with a depth-first search done this way is you will need a
    > recursion depth equal to the maximum number of nodes that may need to be
    > marked. A breadth first search, using a stack like structure to store
    > the list of nodes to visit, may require less levels stored, and if using
    > tail recursion optimization, doesn't actually need to use recursion.


    Well, the original poster emphasized simplicity, and the depth-first
    search is definitely a very simple solution.

    A minor optimization can be done to the solution I suggested: The function
    also marks all the adjacent points (before making the recursive calls).
    This may in some cases somewhat reduce the recursion depth (and overall
    amount of work) performed compared to the pure depth-first search, and
    isn't significantly more complicated to implement.
    Juha Nieminen, Sep 27, 2011
    #7
  8. Alexander

    Alexander Guest

    Krice, thank you very much! The name of the algorithm I need helps very much i finding info.

    Paul, sorry, but I'll need about a week to fully understand your idea.

    Thanks everyone!
    Alexander, Sep 29, 2011
    #8
  9. Alexander <> wrote:
    > Paul, sorry, but I'll need about a week to fully understand your idea.


    Just curious, but I'm wondering if/why you consider the depth-first
    search solution unfit.
    Juha Nieminen, Sep 30, 2011
    #9
  10. Richard Damon <> wrote:
    > One problem with a depth-first search done this way is you will need a
    > recursion depth equal to the maximum number of nodes that may need to be
    > marked. A breadth first search, using a stack like structure to store
    > the list of nodes to visit, may require less levels stored, and if using
    > tail recursion optimization, doesn't actually need to use recursion.


    Btw, I didn't notice this at first, but now I see that you seem to be
    suggesting that it's much preferable to avoid recursion, even if it means
    using a more complicated (to implement) solution. Why?

    Note that by using a stack you are not really saving any memory. You
    will still be storing O(n) amount of data (where n is the number of nodes
    that have to be marked). In fact, depending a bit on the situation, the
    breadth-first search may end up storing more data than the depth-first
    search (although it's true that in some cases it may be the other way
    around).

    Anyways, your concern seems to not be the amount of data needed to
    perform the task, but the recursion. Why? What exactly is the problem?
    Juha Nieminen, Sep 30, 2011
    #10
  11. Alexander

    Nobody Guest

    On Fri, 30 Sep 2011 06:24:12 +0000, Juha Nieminen wrote:

    >> One problem with a depth-first search done this way is you will need a
    >> recursion depth equal to the maximum number of nodes that may need to be
    >> marked. A breadth first search, using a stack like structure to store
    >> the list of nodes to visit, may require less levels stored, and if using
    >> tail recursion optimization, doesn't actually need to use recursion.

    >
    > Btw, I didn't notice this at first, but now I see that you seem to be
    > suggesting that it's much preferable to avoid recursion, even if it means
    > using a more complicated (to implement) solution. Why?


    One advantage of an explicit stack is that you're more likely to be able
    to allocate a large heap block than a large stack. On Unix, any memory
    allocated for the stack (RLIMIT_STACK) cannot be used for anything else,
    which tends to result in it being somewhat smaller than the largest
    possible heap block.

    Also, you can detect malloc() failure (NULL return) more easily than a
    stack overflow (SIGSEGV, which can only be caught if you have allocated an
    alternate signal stack).

    Finally, the amount of memory for each recursion level is likely to be
    less when using a manual stack. Each frame on the program stack will
    typically contain saved program counter, stack pointer and frame pointer
    registers, as well as space for any temporary storage. This is all in
    addition to space which is inherently required by the algorithm.
    Nobody, Sep 30, 2011
    #11
  12. On 9/30/11 2:24 AM, Juha Nieminen wrote:
    > Richard Damon<> wrote:
    >> One problem with a depth-first search done this way is you will need a
    >> recursion depth equal to the maximum number of nodes that may need to be
    >> marked. A breadth first search, using a stack like structure to store
    >> the list of nodes to visit, may require less levels stored, and if using
    >> tail recursion optimization, doesn't actually need to use recursion.

    >
    > Btw, I didn't notice this at first, but now I see that you seem to be
    > suggesting that it's much preferable to avoid recursion, even if it means
    > using a more complicated (to implement) solution. Why?
    >
    > Note that by using a stack you are not really saving any memory. You
    > will still be storing O(n) amount of data (where n is the number of nodes
    > that have to be marked). In fact, depending a bit on the situation, the
    > breadth-first search may end up storing more data than the depth-first
    > search (although it's true that in some cases it may be the other way
    > around).
    >
    > Anyways, your concern seems to not be the amount of data needed to
    > perform the task, but the recursion. Why? What exactly is the problem?



    Note that there are a couple of issues here. One is that a level of
    recursion cost a lot more memory space than saving a few locations to
    iterate in a program controlled resource than a recursive call. Remember
    that a level of recursion is going to create new copies of every
    automatic variable used in the function, as opposed to just what is
    needed to keep track locations to be filled.

    A second issue is that recursion grows the program stack space, and
    there is no way (portably) of checking for program stack overflow, while
    you can check for running out of memory in the heap or program defined
    memory structure. (Not every program runs on machines with gigabytes of
    RAM).

    Also, in typical worse case type configurations, a depth first path is
    going to trace down to a significantly higher depth than a breadth first
    search, as after you run out to what would seem to be a maximum distance
    away, the depth first search will turn around and come back and
    eventually hit most of the open cells in a deep path, it may
    occasionally trap it self, but after it backs out a few steps, it will
    find the deeper path. For a 200x200 flood file, I would expect it to get
    at least 30,000 levels deep. On the other hand, a breadth first search
    will tend to generate an expanding ring only a couple of cells thick,
    needing maybe 1600 locations recorded at a given time for the same area.
    The key here is that breadth first limits itself to first looking near
    where it has done work, and finishes cells, so we don't need to revisit
    them. Depth first can't tell that a later path will get to a cell at a
    shorted depth. This is a common issue with traversing highly connected
    paths.

    There is nothing inherently wrong with recursion, but it isn't always
    the right tool, and often is a somewhat heavy handed one. An important
    thing when using recursion is to make sure that it does terminate, and
    in a reasonable number of levels. Removing recursion and replacing it
    with iteration is a common optimization. (For an extreme case compare
    recursive and iterative version of factorial or Fibonacci calculations).
    Richard Damon, Sep 30, 2011
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Gogo
    Replies:
    1
    Views:
    2,097
    Sudsy
    Sep 4, 2003
  2. Michael Goerz

    freeing a matix

    Michael Goerz, Dec 1, 2006, in forum: C Programming
    Replies:
    10
    Views:
    622
    Barry Schwarz
    Dec 4, 2006
  3. Replies:
    4
    Views:
    797
    Daniel T.
    Feb 16, 2006
  4. Knute Johnson
    Replies:
    16
    Views:
    740
    Roedy Green
    Aug 31, 2007
  5. Hicham Mouline
    Replies:
    1
    Views:
    390
    Kai-Uwe Bux
    Apr 11, 2010
Loading...

Share This Page