Is instance surrounded?

Discussion in 'Programming' started by Queequeg, May 15, 2019.

  1. Queequeg

    Queequeg Member

    Joined:
    Aug 14, 2016
    Posts:
    3
    Hi there,
    Picture a classic snake game where you're allowed to cross your own path. The snake only makes 90 degree turns on say, a 32x32 grid. I want to know when the segments of this snake have completely surrounded another instance or instances. The snake could get pretty long and cross its own path more than once.
    Is there a best practice way to approach this problem? Not even looking for code specifics, just the main idea.
    Thanks.
     
  2. FrostyCat

    FrostyCat Member

    Joined:
    Jun 26, 2016
    Posts:
    4,175
    Implement a flood-fill algorithm and start the fill from the instance to check. If the fill can reach the border of the grid, then it isn't surrounded.
     
    Queequeg likes this.
  3. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,803
    OP: you don't specify "surrounded" well enough. How are empty grid cells handled? Do empty cells between the snake and the surrounded entity mean the entity is not completely surrounded, or do you just need to roughly surround it (empty cells not counting)? If former, you need to detect both empty cells and grid edge in the flood fill, if latter you just check if you can reach the grid edge.
     
    Queequeg likes this.
  4. Queequeg

    Queequeg Member

    Joined:
    Aug 14, 2016
    Posts:
    3
    Absolutely, that might be the easiest way. There may be a lot of these instances and I was wondering if there might be a simpler way than chugging through that algorithm for every instance. I think I may end up doing that, thanks.

    You would just need to roughly surround it, empty cells are disregarded, to clarify. I guess I will just try the flood fill approach and see how it works.Thanks for the responses.
     
  5. Queequeg

    Queequeg Member

    Joined:
    Aug 14, 2016
    Posts:
    3
    OK. I think the flood fill is the best way to go. I wasted some time mucking around with rectangle collisions and wasn't getting anywhere.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice