# Silverlight-based "area of influence" algorithm

I am in the process of developing a tool for a game called MechWarrior: Online which defines a map of an area of space called the Inner Sphere. Essentially, this map is a set of points (planets) on a Cartesian plane. Each planet can be owned by a different faction, typically represented on the map by a colour. I can colour the various planet points as different colours, but ideally what I'd like to do is show an area of influence (circle) for each faction by using something like a `GeometryGroup` to help with the simplification of the geometry object that using 2,240 points' circles will produce before rendering it to a Silverlight Canvas.

However, I'm not even sure that this is a good idea or the right way to approach this problem from an algorithmic standpoint, specifically because where there are overlaps of influence at the faction "borders", how do I deal with the overlaps to effectively show a reduced area of influence for both factions in the resulting geometry?

Edit for clarity:

Thank you for the responses so far - colour interpolation was not what I meant, tho it is similar in principle.

The image above shows two faction planets (one red point, one blue point) and their areas of influence (one red circle, one blue circle). In the top image, it shows the areas of influence (territory) and their overlap. The bottom image shows how I would like to resolve the overlap.

This is the simplest example I can think of and it may be that expanding this out over multiple planets would work to get the result I am looking for, but it could become computationally expensive as if you have n planets in one faction and n planets in another, you could end up with a Big O notation value of n squared at the minimum for two factions due to the required number of comparisons for checking intersection and there are actually 10 factions each with a minimum of two neighbours, so it's more than n squared anyway.

I am not sure of what effect doing a 1 to n faction iteration while doing a search for planets in influence diameter range (i.e. intersection range) would have on that n squared value however, as it's impossible to predict deterministically how many planets will be in range to each other planet. I am assuming that it's unlikely to be very many.

• What you are doing sounds like a Voronoi diagram, except space that's too far from any seed point doesn't end up being part of a cell.
– Hey
Dec 29, 2014 at 4:02
• Are pixel shaders an option for you? What you want is conceptually close to the color-blending, except that you simply want the "stronger" color to be the only one to show up - no blending, per se. This sounds like a case where you could pass in a bitmap simply containing faction "strengths" via colors and then color appropriately with the pixel shader, possibly with a layer per faction. This is definitely dependent on the number of factions though - how many factions are possible? Dec 29, 2014 at 7:23
• @Hey: Very close but the cell size needs to be constrained and cells would need to support multiple points. @J Trana: In Silverlight it is an option through XNA apparently but I've not done low-level 3D gfx (including shaders) for about 10 years now. Dec 29, 2014 at 8:37
• @toadflakz I think just the size needs to be constrained, cells don't really need to support multiple points. Something like this: jsfiddle.net/37x7t52b (just a simple brute-force algorithm, iterating over each pixel and finding the nearest seed).
– Hey
Dec 29, 2014 at 18:59

### Translucent circles approach:

One approach would be to use translucent overlays to show area of influence. You should be able to map the faction's influence strength to the intensity of the color representing the faction.

From there, simply allow the overlapping colors to combine and the resulting color demonstrates that there is a reduced level of influence in the area shared by the two factions.

If the geometric shapes you're using won't allow you to blend the colors of overlapping shapes, then you'll need to detect the cases where there is overlap and run a calculation to determine what the blended color should be.

### Colored edges approach:

Another approach would be to determine where the circles of influence intersect with other circles, and then create a polygon based upon the intersection points and the remainders of the circles. This approach aligns with what you drew in your question - you would have circles with the edges colored, but the centers transparent.

Given that any particular circle could be trimmed multiple times, you would probably want to start with a circle to represent the influence, but treat it as a polygon when calculating successive rounds of overlap. The point here is to carry the existing shape forward and not make assumptions about the initial shape. That way you avoid recalculating influence conflict from a previously completed round.

In other words, Planet ABC may have to have the circle of influence trimmed three times due to competing, nearby Factions. Planet ABC's influence starts as a circle mapped onto a polygon, becomes a true polygon after the first trim, and remains a polygon for the next two trimmings.

### Responsiveness optimizations

Hidden within your question are concerns regarding the overall performance or responsiveness of generating this mapping. There are some things you could consider to decrease the number of calculations necessary.

The first consideration would be to reduce the number of planets for consideration. So you would remove any planet that's far enough away from any other planet so that the circle of influence wouldn't possibly be affected.

Another consideration would be to build a directed acyclic graph (DAG) for the planets. Use the DAG to determine the neighbors to a given planet. Similar to the first optimization, there's no point in checking for overlap when the planets are too far apart.

Said another way, you don't check Faction A's planets against all of Faction B's planets. You only check A's planets against B's when they are neighbors.

A final way to optimize the responsiveness of the algorithm is to determine the markers that affects the circle of influence and only update those planets where the markers have changed. This requires more overhead on your part because you have to track the state of the game. But there's no point in calculating something that hasn't changed from the previous round of calculations.

• Excellent update, thank you. Your Colored Edges approach with the Responsiveness Optimisations is what I was looking for. That DAG is what I had in mind to reduce the calculations required. The app is able to show any state of the game based on a set of data at the time (provided by the game maker's public JSON API) which basically is the set of planets and the faction currently assigned which is why I need as optmised an algorithm as possible. XAML is limited in terms of what it can detect/do graphically so a polygon approach would be easiestdue to good polygon support. Dec 29, 2014 at 8:30