• Hey! Guest! The 37th GMC Jam will take place between May 28th, 12:00 UTC and June 1st, 12:00 UTC. Why not join in! Click here to find out more!

Is instance surrounded?

Queequeg

Member
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.
 

NightFrost

Member
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

Member
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.
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.

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.
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.
 

Queequeg

Member
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.
 
Top