Fastest way to group units that can see each other?
- by mac
In the 2D game I'm working with, the game engine is able to give me, for each unit, the list of other units that are in its view range.
I would like to know if there is an established algorithm to sort the units in groups, where each group would be defined by all those units which are "connected" to each other (even through others).
An example might help understand the question better (E=enemy, O=own unit). First the data that I would get from the game engine:
E1 can see E2, E3, O5
E2 can see E1
E3 can see E1
E4 can see O5
E5 can see O2
E6 can see E7, O9, O1
E7 can see E6
O1 can see E6
O2 can see O5, E5
O5 can see E1, E4, O2
O9 can see E6
Then I should compute the groups as follow:
G1 = E1, E2, E3, E4, E5, O2, O5
G2 = O1, O9, E6, E7
It can be safely assumed that there is a transitive property for the field of view: [if A sees B, then B sees A].
Just to clarify: I already wrote a naïve implementation that loops on each row of the game engine info, but from the look of it, it seems a problem general enough for it to have been studied in depth and have various established algorithms (maybe passing through some tree-like structure?). My problem is that I couldn't find a way to describe my problem that returned useful google hits.
Thank you in advance for your help!
