ENCLOSURE DETECTION
So you want to make enclosures in your game?
Since this was a big problem I needed to solve early on in my Yokai Sanctuary development I thought I’d share the knowledge I gleaned with other devs looking to do this same thing! My solution included three main algorithms, so I’ll break down each one in a section.
These solutions make the following assumption you should take into account when writing your placement logic
A fence can only be touching 0, 1, or 2 other fences
Your game uses a grid system to keep track of placement of fences
I’m developing this game in Unity, so my answers are tailored towards Unity and C#, but this is mostly an abstract explanation and won’t have actual code in it, so you can apply these concepts to whatever framework you’re working in.
Fence Groups and Loops
The first step is to determine when you’ve made a loop aka an enclosure, and to do that we need to keep track of our fences.
Where are my fences? When have I made an enclosure?
Video showing example of fence placement adjusting Fence Group Ids.
The first problem you have to solve is keeping track of your fence positions. I do this by keeping a dictionary of positions and fence ids. When your player puts down a fence, keep track of where your fence is. Easy!
Maintain a list of “Fence Group Ids” (FGI) which are unique ids that represent a “group” or clump of connected fences. Each fence should keep track of its FGI. A full loop of fences will all share the same FGI.
When you place your fence, you need to figure out what other fences its touching. This will look different depending on how your game grid is set up. I made this complicated for myself because I made my fences directional as well as being on the grid, so I had to account for which direction a fence was facing as well as its grid coordinate. Once you know which other fences it’s touching, you need to get the Fence Group Id of the touching fences. Depending on the results you do the following:
Not touching any other fences -> assign your fence a new unused FGI
Touching one fence -> assign your fence the same FGI as the once fence
Touching two fences (with different Fence Group Ids ) -> assign your fence the same FGI as one of the fences and change the FGI of the other fence (recursively so the whole group is changed)
Touching two fences (with the same Fence Group Ids) -> Congratulations! You’ve found a loop, and therefore a valid enclosure!
Enclosure Orientation
The blue line represents the raycast going from point a (red sphere) to point b (white sphere). It hits two fences of the same FGI and therefore point a is outside the enclosure.
So great, we have a loop! But we still don’t know which side of the loop is “in” and which side is “out”. So the next step will help us determine that using a Ray Casting Algorithm. This will work for enclosures that are any weird shapes, not just rectangles.
Which side is the inside?
First you’ll need to have some way of orienting a “point a side” and “point b side” of your fence. My example here shows a “red sphere” and a “white sphere” and placing them on either side of the fence. It doesn’t actually matter which is which. You hide these from the player, obviously.
Once you have determined you have a loop (from the previous section), you need to perform a Ray Cast Algorithm in the following manner: draw a raycast from point a to point b, so in this example it’s starting from the red sphere on the bottom right of the image and going towards the white sphere into infinity.
Count the number of raycast hits of type fence, and of the same Fence Group Id as the original fence that started this whole check (otherwise its another enclosure and shouldn’t count). Depending on the hits:
Even number of hits -> your starting point a was outside the enclosure
Odd number of hits -> your starting point a was inside the enclosure
With that information you know that the grid position of point a or b is inside your enclosure and you can move on.
Flood Fill
The last step is to keep track of all the grid squares that now make up your enclosure. If your enclosures are always rectangular this is probably overkill, but if you have a strange wobbly enclosure you might want to use a Flood Fill Algorithm to determine what squares are inside. Disclaimer, many people have described this algorithm better than I will and I would recommend just looking up someone else’s explanation of this one!
Which squares are part of my enclosure?
Video showing the result of the flood fill.
Using the location of the inside (from the previous section), start the flood fill algorithm. Keep track of a list of grid positions inside your enclosure. Add your starting square to this list. Keep track of a list of positions already checked so you don’t check them twice.
Make a recursive function “getFloodFillPositions(position p)” that takes grid position p. Check if position p has it’s reached a fence and if you’ve already visited it return nothing. If your fences are directional and not just position based you’ll have to account for the direction you’re moving your flood fill here.
You’ve hit a fence-> return your list of positions
You’ve haven’t hit a fence-> add to your list the results of getFloodFillPositions(n) where n is every direction touching position p. Add to your list position p.
Congratulations, you’ve got an enclosure!
If your game can remove fences, you’ll need to divide your fence groups into two groups when you delete a fence.
I hope you’ve found this helpful~
-Harvey Jules
