Detecting if a cell is within a path of cells

[thomasvandenabeele]

Hi, I’m facing a coding/math issue and was wondering if anyone could help.

I’m making a grid based puzzle game. When people trace a closed path of grid cells, all cells within this path shape need to explode. However, I can’t determine which cells are within this traced path or not.

I know the classic point-in-polygon method, but this doesn’t work with a grid-based shape (this is a simple ray intersection method which works for polygons, but not for grid cell based paths.

The path shape only makes 90 degrees angles, so no diagonals.

The attached image explains everything: how do I detect which cells are inside the closed path?

[XeduR]

Hey!

This is a cool topic. I don’t currently have the time to get more in-depth with it, but you are looking for flood fill algorithm, see:

Flood fill

Let me know if you still run into problems with this and I can help out at a later time.

[Siu]

Just for fun because I have no idea in terms of performance, but technically you can still do “point-in-polygon.”

If you are representing the grid visually, similar to that image you posted, then they exist in the Cartesian coordinate system. Thus, as each cell is selected you grab that cell’s coordinates and put them in a table.

Sort said table in order of columns and then rows, and you’ll have all the points of a polygon; you can even create it visually by passing said table to display.newPolygon() as its vertices. However, in order for this to work 0,0 must be at the center of the grid. If the grid and the polygon are both in the same display group then this should* workout fine. You can then proceed to check for point-in-polygon.

[thomasvandenabeele]

Ha. You know what? You make a very good point. I might just do that.

I was going for the grid based approach because my data structure is just that: tables representing a 2D grid of cells. But you are right, I could just use the cell coordinates.

Thanks!

[thomasvandenabeele]

Thanks XeduR, this is interesting stuff. However, it starts of from the assumption that you indicate a first point inside the enclosure. How would I go about ‘detecting’ which point(s) are inside the shape, I’m wondering?

I could do a flood fill for all areas, and see which areas hit my screen boundary (meaning: outside the drawn enclosure), but this seems computationally intensive or wasteful.

[XeduR]

Well, that depends.

Flood fill by itself isn’t a very wasteful, and depending on the size of your maps/grids, it’s likely close to instantaneous either way. If you were to “fill the outside”, then you’d know that whatever wasn’t filled is the inside region.

But, given that you yourself are creating the enclosures (or you know how they are drawn since you’ve written the algorithms), you should be able to determine a point inside the enclosure relatively easily.

[thomasvandenabeele]

Actually, given that the shapes are drawn by the user and could be very irregular, that’s not such an easy task.

I have found a solution for a grid based approach I think, using “connected component labeling” - the wiki page lists a good algorithm. Took me a while, and some graph paper, to understand, but I think this should work well.

Thanks for the help!

[thomasvandenabeele]

Well, after looking for a solution all day I arrived at detecting connecting regions, but the big problem with the grid/cell-based approach is that it’s impossible to perfectly determine which region is inside or outside the enclosure.

I’m now going to test the point-in-polygon approach, as this should fix that issue.

[thomasvandenabeele]

Here’s the solution. Feel free to ask if you need more info!