Alright, I've probably completely over-thought this problem over the weekend, but I came up with a lot of stuff. Oh, and I'm going to move this to the General forum, since this isn't really about LDA support. So without further ado...
The easiest way to solve this is with a tile-based algorithm. This would work great if your game is already tile-based, but you can still use this if your game is 3D. Just hide the tiles with pretty graphics. We actually do this a lot in Hegemony, and the player is never the wiser!
As I said, the code for finding who influences each tile is pretty easy:
for each tile
float fBiggestInfluence = 0;
tile.owner = NULL;
for each city
float fInfluence = city.influence(tile.position);
if(fInfluence > fBiggestInfluence)
fBiggestInfluence = fInfluence;
tile.owner = city.owner;
The only unexplained thing here is the influence() function, which you can play with. If all your cities have the same influence -- for example, all cities affect a radius of 10 tiles -- a suitable influence() function would be:
[code:1:58e4fdb0e0]return 10 - distance(cityCentre, tileLocation);[/code:1:58e4fdb0e0]
Some games are different though. Sometimes a city will influence a larger area if it has more population, or more money, or some other variable. If this is the case, you can multiply the value from that function by your variable of choice, and it will probably work pretty well. But like I said, you can play with exactly how you handle the math in this function.
Both of those for-loops can be optimized once you have the brute-force implementation by reducing your search-space.
For the outer loop, you might spend a lot of time searching through tiles that nobody influences, so you can reduce your search-space by only searching the tiles that are surrounding your cities. Assuming you know the maximum radius of the circle around each city, you can replace the first for-loop with this:
[code:1:58e4fdb0e0]for each city
for(y = city.location.y - city.radius; y < city.location.y + city.radius; y++)
for(x = city.location.x - city.radius; x < city.location.x + city.radius; c++)
// Your current tile is tile[x][y]
But I need to come clean. In practice, that won't really save you time when you're initializing your list of tiles, because you'll be searching some tiles more than once when influence rings overlap. You might think that it would save you time if most of your tiles aren't being influenced by any cities, but in the case of initializing your tile list, you're probably going to need to initialize those un-influenced tiles to NULL on the first pass anyway.
Where that loop will really save you time is when the ownership or influence of a single city changes. Then you can drop the for each city part and just run the loop for the city which is changing, and you won't have to re-iterate through the entire tile list.
How you would optimize the inner-loop all depends on how big the influence ring of a single city can get. Let's do the easier case first, and assume that each city will affect a maximum radius of 10 tiles around themselves. In that case, you can create a second grid structure that sits over-top of your current grid, except each cell in the new grid is ten times bigger than the cells in your current grid, so if your original grid was 50,000x50,000, this new grid will be 5,000x5,000. Now, in each one of these bigger cells, keep a list of all the cities in that patch.
Got that? Now, whenever you need to search for cities which could possibly interfere with the city you're currently considering, you only need to look in the 25 patches around your current patch, because it's impossible for any city's radius to be bigger than that.
| | | |
| |.... | |
| .|.....| |
| ..|.....|. |
| ...|.....|.. |
| ....|.....|.. |
| ....|.X...|.. |
| ....|.....|.. |
| ....|.....|.. |
| ...|.....|. |
| ..|.....| |
| .|.... | |
| | | |
| | | |
| | | |
X is your city, and the dots are the tiles it influences. Each square is
five tiles across and five tiles high. Imagine two more empty rows and
columns around this diagram.
Here, our city has a 5-tile radius, and it is impossible for any other cities
to interfere with our circle unless they're in the 25 squares surrounding us.[/code:1:58e4fdb0e0]
However, if you never know what the maximum radius for a city can be, or if it can potentially cover the entire map (!) then this approach doesn't work as is. You can still use a similar approach, but you need to make another, even bigger grid where you put all the cities with radii that are too big to fit in your smaller grid. So, following through with our past example, if any city has a radius that's bigger than 10, you would put that city in a grid that's 500x500. In fact, you can do this a few times, with coarser and coarser grids.
Seasoned programmers in the house will recognize the data structure I just described: it's a quad-tree.
Now that you have this quad tree, do the same thing I told you to do for the simpler case, where you check the 25 squares around your city, but once you're done, do the same thing with the next-coarsest grid, and so on.
Note: Even in the simpler case I described, you still need to search all cities in an area five times larger than the radius of your city's influence ring. In some games, that's already bigger than the entire map! If that's the case for your game, you're going to see little-to-no performance gains by implementing this optimization. As always, programming is about making choices, and you'll need to decide if this optimization is worth all the effort.
As a curiosity, I also gave thought to how to solve this problem with polygonal borders instead of tiles, and it's significantly harder.
The first part, just drawing the circle around your city, is easy. Or at least, it's easy if you can remember high-school trigonometry, which isn't always so easy. Anyway, with the SOHCAHTOA rule, you can find a series of points in a circle around your city:
[code:1:58e4fdb0e0]for(float theta = 0; theta < PI * 2; theta += PI * 2/numVertices)
x = cos(theta) * radius;
y = sin(theta) * radius;
Now, for each vertex you find, you need to run a simple check on the vertex you picked to see if it overlaps with the radius of any other city. If it does, you're going to need to shorten this radius of this vertex until it doesn't. Unfortunately, finding out how much you have to shorten it is tough.
I attempted to figure out a way to solve this problem using fancy maths, but I'm not much of a mathematician, so I never finished this solution. If you want to read the solution I would actually end up using in code, skip to the next section.
Now, let's say the distance the vertex is from your city is r (for radius). You can find out the distance that vertex is from another city -- we'll call that distance r2 -- like so:
[code:1:58e4fdb0e0]// Assume theta and city are global variables
float r2(float r)
float x = cos(theta) * r;
float y = sin(theta) * r;
return sqrt(square(x - city.position.x) + square(y - city.position.y));
Or, mathematically, that looks like this:
r2(r) = âˆš (cos(Î¸) Â· r - city.y)Â² + (sin(Î¸) Â· r - city.x)Â²
Since we're already making this hard enough on ourselves, we'll assume that all the cities have an equal influence. If that's the case, then we want to make sure our vertex is equidistant from both cities. If other words, we want to find the value of r such that r = r2(r). I believe you would do that with a limit, like so:
lim r2(r) = âˆš (cos(Î¸) Â· r - city.y)Â² + (sin(Î¸) Â· r - city.x)Â²
Unfortunately, this is also the limit of my knowledge of mathematics. I don't know how to solve such an equation, or if it's even possible. If you're a math-wiz and you can answer this question, let me know!
Short of finding a math major to solve that limit for you, you can solve that equation iteratively using a sort of binary search until you find a value that's close enough. That would look like this:
float acceptableError = 1.0f; // Pick a number, any number!
float radiusMax = radius;
float radiusMin = 0;
for each vertex
for each city
// We only consider cities that actually impede on this point
if(city.influence(vertex) > 0)
float difference = city.influence(vertex) - currentCity.influence(vertex);
while(difference > acceptableError || difference < -acceptableError)
// Our influence is bigger than the other city's influence,
// so we can make our radius bigger.
if(difference < 0)
radius = radiusMin = radiusMin + (radiusMax - radiusMin) / 2;
// And vice-versa
radius = radiusMax = radiusMax - (radiusMax - radiusMin) / 2;
vertex = recaculateVertex(radius);
difference = city.influence(vertex) - currentCity.influence(vertex);
The polygonal approach was an interesting thought experiment, but given the choice between the two, I would probably pick the tile-base approach and just hide it with pretty graphics to make it look like a polygonal border, or even generate a purely aesthetic polygonal border from the tile-based grid with an algorithm like Marching Squares.
This might seem like a surprise, since the polygonal approach uses less memory, and potentially uses less CPU time. However, these days memory is much cheaper than CPU time, and there's a lot of extra CPU time which will be necessary in the polygon-based approach that I haven't mentioned yet.
For instance, once you've done everything I discussed above, you'll end up with a series of partial-circles, and many of those circles will belong to the same player. Before you draw this, you may want to find the polygon union of all those circles, which isn't a trivial task.
Even if you don't do that, your polygons are potentially concave hulls. Eventually you'll have to find out whether an object is inside that polygon, which isn't simple. Even if you treat that circle as a star-shaped polygon, the fastest algorithm is still logarithmic. With a grid, checking if something is in your influence is a simple -- and very fast -- table lookup!
So in the end, you're really only left with memory as the advantage of the polygonal method, and unless you're modeling a very high level of detail, or a gargantuan map, the memory you save really isn't worth it.