Sorry if I don't write this properly, this is my first post here. I am working in Unity 2018.2.xx I have an issue where the current solution for checking whether a squad formation is broken. For ease of explanation, it's easier to visualise in 2D space from a top-down perspective. currently, there is the Squad is tracked by its own class and is an empty game object. the units in the squad have their own unit class and pass data to the Squad controller when needed. i.e on the death of a unit, it tells the squad manager to remove itself from the squad

the Squad formation is tracked in a 2D array and for testing purposes, the squad was formed in a 3*3 square as I tried to display below

o o o
o o o
o o o

what I need, is a way to detect when the squad is split into two, by the player killing/ removing units from the middle. i.e the squad on the left still has one unit in the middle, and when the unit in the middle column, the unit "breaks" and the remaining survivors scatter.

o o o    o x o
o x o    o x o
o x o    o x o

Currently, I am checking each column and making sure it isn't the start or end. Then, checking the row to see if there are still units in that column. if not, it runs the splitting functions.

so my question is, is there a better way to do this without going too complex with the approach

  • \$\begingroup\$ Sounds fine to me if all you can have is vertical splits, but what about horizontal, diagonal or even arbitrary splits? A general solution would be performing flood fills to detect separated groups. \$\endgroup\$ – Quentin Nov 19 '18 at 10:34
  • \$\begingroup\$ @Quentin thank you. yeah, it was only vertical splits. You can only approach them front on. Can you explain what a flood fill is and how it would detect separated groups? I am not sure if I know what that means \$\endgroup\$ – faulknerj Nov 19 '18 at 10:48
  • \$\begingroup\$ Flood fill is a well-documented algorithm used for example in drawing programs for the paint bucket. You fill in a group from an arbitrary unit, then any unit not filled belongs in some other group and there is thus a split. Repeat until all units are filled. \$\endgroup\$ – Quentin Nov 19 '18 at 10:56
  • \$\begingroup\$ @Quentin awesome, I'll definitely give it a read. It sounds a little too advanced for what I need, but I will have to play around with it in future projects. \$\endgroup\$ – faulknerj Nov 20 '18 at 2:23

Perform a flood fill starting on an arbitrary unit and see if it covers all living units. When it does, the formation is still coherent.

The flood fill algorithm works like this:

  1. Every unit can have one of three states: "dead", "visited" or "unvisited". At the beginning, all units have the state "dead" or "unvisited". I would recommend to create a local 2-dimensional array to represent these states.
  2. Pick any "unvisited" unit as your starting point.
  3. Mark the current unit as "visited"
  4. For each neighbor-unit of the current unit check if it is "unvisited" and when it is, recursively call the algorithm from step 3 with that neighbor as the current unit.

When all the recursive call-chains return, then any units which are still "unvisited" do not have an unbroken connection to the unit you started with. As a side-effect, you also found a first connected sub-group. If you are interested in knowing all connected sub-groups, keep performing the above algorithm on the remaining units until they are all "visited" (some sub-groups might consist of only one unit).

  • \$\begingroup\$ Ahh, thank you. @Quentin also mentioned flood filling and will be investigating it as a viable solution to my problem. \$\endgroup\$ – faulknerj Nov 20 '18 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.