Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 commutative 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!

share|improve this question
1  
I think this question is general enough that it could get better answers in stackoverflow, or maybe even math (set theory?). It isn't game development specific is my point. –  Tor Valamo Nov 13 '11 at 0:51
1  
@Tor - Probably true, but the fact that we know it's for a game might allow people to craft answers that are more specific to the problem. –  OverMachoGrande Nov 13 '11 at 1:24
    
I think you could do some clever stuff with a spin on spatial hashing and a visibility map - I just need to think about it. –  Jonathan Dickinson Nov 14 '11 at 13:06

4 Answers 4

up vote 6 down vote accepted

If your "can see" relation is symmetric, so that "A can see B" implies "B can see A", then the groups you want to compute are the connected components of the graph defined by the "can see" relation. As others have noted, there are simple algorithms for computing these, such as:

while ungrouped units remain:
    let u = arbitrary ungrouped unit
    let g = new group
    let s = temporary stack
    assign u to g
    push u onto s
    while s is not empty:
        let v = topmost unit in s
        remove v from s
        for each unit w that v can see:
            if w is ungrouped:
                assign w to g
                push w onto s
            end if
        end for
    end while
 end while

(A queue or any other collection that efficiently implements the operations "add new element" and "remove and return some element" can be used in place of the stack s above.)

If your "can see" relation is not symmetric, you need to decide whether you want your groups to be the strongly or the weakly connected components. For weakly connected components, the algorithm above will work as is, except that the line for each unit w that v can see should be replaced with for each unit w that can see v, or that v can see. For strongly connected components, you can use one of the algorithms (Kosaraju's, Tarjan's or Gabow's) mentioned on the linked Wikipedia page.

For non-symmetric relations, you may also want to compute the transitive closure of the relation, or of its strongly connected components. For this, you can use the Floyd–Warshall algorithm; see this answer on SO for (a bit) more information.


Ps. As the Wikipedia article I linked to above notes, it may be more efficient to dynamically update the groups as the visibility relation changes. I'm not familiar with the advanced(?) algorithms mentioned on Wikipedia, but it shouldn't be hard to cobble together something that at least beats recomputing the groups from scratch every time.

One half of this is easy: if two units in different groups acquire a line of sight between them, merge the groups. Dealing with units losing sight of each other is a bit more tricky; one simple but perhaps not optimal solution is to rerun the grouping algorithm for the units in the affected group whenever that happens. There are some optimizations you can make to that, if the visibility changes occur one pair of units at a time:

  • If a unit could only see one other unit, and loses sight of it, just remove it from its previous group and assign it to a new group.
  • Otherwise, you could start at one of the affected units and run an A* search on the visibility graph (using e.g. straight-line distance as the heuristic) for the other unit. If you find it, the group didn't break up; if you don't, the set of units the search visited forms the new group.
  • You could try to guess which of the two units is more likely to belong to the smaller half of the group, if it does split, and start the search from that unit. One possibility would be to always start from the unit that can directly see fewer other units.
share|improve this answer

What you have is a connectivity graph. And generally, the best way to group the connected nodes (ie: characters) together is with a graph search algorithm. Depth-first, breadth-first, whichever. All you're doing is building a list of which nodes are reachable from all others. So long as your graph is undirected (if A is visible to B, then B is visible to A), this works fine.

There may be some algorithms to improve this for specific cases. For example, if sometimes characters don't move (and terrain doesn't move too, so immobile characters remain visible) then you can choose not to test them again to update their connectivity graphs.

But in general, you're going to have to retest visibility every frame. Odds are, that's going to be slower than the graph traversal to find the visibility groups.

share|improve this answer
3  
Just to add the technical term: what you're trying to find is the connected components of the graph, and the standard algorithm is: (1) put all the nodes in a list, (2) pick a node, (3) find all connected nodes using BFS/DFS, (4) remove all the nodes you found from the list, (5) repeat until no more nodes left. –  Nathan Reed Nov 13 '11 at 2:36

Seems like a standard graph connectivity problem. There may well be some sort of algorithm for this, and it might look like the following:

remaining units = all units
for each unit in remaining units:
    current group = create a new group
    add this unit to current group
    for each unit visible to this unit:
        if unit is in a group already:
            merge current group into that existing group
            set current group as that existing group
        else:
            remove that unit from remaining units
            add that unit to current group

I expect it is possible to implement this via a tree, like hierarchical clustering, but I doubt that would work out quicker - trees tend to be O(log N) whereas most of the checks I give above can be implemented as O(1).

share|improve this answer
    
Out of interest, the hierarchical clustering approach is a bit like this: For every unit, create a group. Then, for every pair of units that can see each other, if they're in different groups, merge the groups into one, and discard the other. –  Kylotan Nov 13 '11 at 2:09
    
This is what I referred to as naïve implementation in my OP. Good to know that it might not be as bad as I thought then! :) –  mac Nov 13 '11 at 9:42
    
The way you do it as a tree is to use a union set with path compression. That's not very naïve, and in fact is optimal. –  Peter Taylor Nov 13 '11 at 22:21

I agree with all others who responded in terms of this being a graph connectivity problem, however let me point out that what you need here is the Delaunay Triangulation graph generated from all your relevant units. What this does is ensures that only units closest to one another will be connected in the graph that you generate. You will find it very challenging to do this any other way, because graph crossings (non-planarity) will cause units too far from one another to be incorrectly connected within the graph.

The above only applies if you are using a continuous space (as in most free-movement FPSes); however if you already have an underlying grid (a planar graph) on which your units move, then you can just use that to evaluate connectivity instead.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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