Skip navigation

Programming forum

Forum NavigationHome > Forum Index > General Chatter > Programming forum
Level 13 Human Shadow
Alignment: Chaotic good
Location: Earth Orbit, Preparing to Attack
Posted on November 30, 2007 at 6:14 pm

We used to have a programming forum around here. Any chance of resurrecting it? :)

I have a programming question that you might be able to point me toward an answer.


In the interim, I'll just post my question here in case anyone at LDA has an idea of where to point me towards. I am looking for a way to create dynamic borders between two or more players in a game based on locations owned by the player. As this is a space-based game, the borders aren't fixed to any predefined map, but rather equidistant from the nearest player's worlds. Further, the borders need to suction toward each other when near so that maps form contiguous borders. Think of the various games (Thrones and Patriots, Alpha Centauri, etc) that use borders based on where you build cities - that's what I'm trying to do.

Unfortunately I have no idea where to start my hunt for information. Simple Google searches on cartographic borders and programming have turned up GIS-type stuff, which is not what I'm looking for.

Any tips or ideas?

Thanks!

--RC

P.S. It's for an open source game - www.ospace.net - that I am an assistant developer on.

Level 13 Extraplanar Programmer
Alignment: Chaotic good
Location: Toronto
Posted on November 30, 2007 at 8:07 pm

Ah, it's too close to the end of the day, but I'll think about this over the weekend and let you know what I come up with.

Level 13 Human Shadow
Alignment: Chaotic good
Location: Earth Orbit, Preparing to Attack
Posted on November 30, 2007 at 11:33 pm

I think I got a method working - it's grid based, so easier than dynamic borders. But I'd still like other methods :)

http://www.vorklift.com/ospace/starmap_1545_17.png

Level 13 Extraplanar Programmer
Alignment: Chaotic good
Location: Toronto
Posted on December 4, 2007 at 4:48 am

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...

Tile-Based Solution
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:
[code:1:58e4fdb0e0]// Pseudo-code
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;
}
}
}[/code:1:58e4fdb0e0]
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.

Optimizing the outer loop
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&#40;y = city.location.y - city.radius; y < city.location.y + city.radius; y++&#41;
for&#40;x = city.location.x - city.radius; x < city.location.x + city.radius; c++&#41;
// Your current tile is tile&#91;x&#93;&#91;y&#93;
[/code:1:58e4fdb0e0]
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.

Optimizing the inner-loop
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.
[code:1:58e4fdb0e0]+-----+-----+-----+
| | | |
| |.... | |
| .|.....| |
| ..|.....|. |
| ...|.....|.. |
+-----+-----+-----+
| ....|.....|.. |
| ....|.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.

Polygonal Borders
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&#40;float theta = 0; theta < PI * 2; theta += PI * 2/numVertices&#41;
&#123;
x = cos&#40;theta&#41; * radius;
y = sin&#40;theta&#41; * radius;
&#125;
[/code:1:58e4fdb0e0]
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.

Finding the right radius in constant time
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&#40;float r&#41;
&#123;
float x = cos&#40;theta&#41; * r;
float y = sin&#40;theta&#41; * r;

return sqrt&#40;square&#40;x - city.position.x&#41; + square&#40;y - city.position.y&#41;&#41;;
&#125;
[/code:1:58e4fdb0e0]
Or, mathematically, that looks like this:
[code:1:58e4fdb0e0] ________________________________________________
r2&#40;r&#41; = √ &#40;cos&#40;θ&#41; · r - city.y&#41;² + &#40;sin&#40;θ&#41; · r - city.x&#41;²
[/code:1:58e4fdb0e0]
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:
[code:1:58e4fdb0e0] ________________________________________________
lim r2&#40;r&#41; = √ &#40;cos&#40;θ&#41; · r - city.y&#41;² + &#40;sin&#40;θ&#41; · r - city.x&#41;²
r->r2&#40;r&#41;
[/code:1:58e4fdb0e0]
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!

Finding the right radius in logarithmic time
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:
[code:1:58e4fdb0e0]
float acceptableError = 1.0f; // Pick a number, any number!
float radiusMax = radius;
float radiusMin = 0;

for each vertex
&#123;
for each city
&#123;
// We only consider cities that actually impede on this point
if&#40;city.influence&#40;vertex&#41; > 0&#41;
&#123;
float difference = city.influence&#40;vertex&#41; - currentCity.influence&#40;vertex&#41;;

while&#40;difference > acceptableError || difference < -acceptableError&#41;
&#123;
// Our influence is bigger than the other city's influence,
// so we can make our radius bigger.
if&#40;difference < 0&#41;
radius = radiusMin = radiusMin + &#40;radiusMax - radiusMin&#41; / 2;
// And vice-versa
else
radius = radiusMax = radiusMax - &#40;radiusMax - radiusMin&#41; / 2;

vertex = recaculateVertex&#40;radius&#41;;
difference = city.influence&#40;vertex&#41; - currentCity.influence&#40;vertex&#41;;
&#125;
&#125;
&#125;
&#125;
[/code:1:58e4fdb0e0]
My Choice
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.

Level 13 Human Shadow
Alignment: Chaotic good
Location: Earth Orbit, Preparing to Attack
Posted on December 5, 2007 at 8:17 am

Thanks Rick!

I'll read through this when I get home from work tonight.

The largest limiting factor on this game client is speed. It's written in Python, and thus as a scripting language is a lot slower than a compiled language for doing simple arithmetic.

Someone I know online is talking about rewriting the client using a compiled language (not sure which one), but he seems to always talk about this just as he's going to sleep :)

Level 13 Human Shadow
Alignment: Chaotic good
Location: Earth Orbit, Preparing to Attack
Posted on December 6, 2007 at 12:37 am

Having looked over this discussion, very useful :)

When I coded up the map I posted back on post #3, I used essentially a slightly modified optimized grid. Only I did it in reverse: I iterated through every star and grabbed it's owner. Now this is itself a fudge, because a star might have planets owned by more than one player; the game fudges by giving star ownership to you (if you are the owner) or to the owner of the last planet in the system, on a per-client basis. The server doesn't actually care.

Stored in an array with associative keys of the floor of the grid position ( x:y ) I stored an array with owner color (didn't care about the actual owner) and distance to that owner's system. I then check to see for every grid in the radius around a system if that player is closer to the grid point than another system. If so, it updates the player color and distance values in the array.

The code looks like this:

[code:1:713cc24014]
controlcolor = res.getControlColor&#40;ownerID&#41;
if controlcolor&#58;
groupCenterX = int&#40;anyX&#41;
groupCenterY = int&#40;anyY&#41;
for rX in range&#40;-CONTROLRANGE,CONTROLRANGE&#41;&#58;
for rY in range&#40;-CONTROLRANGE,CONTROLRANGE&#41;&#58;
if rX*rX+rY*rY < MAXCONTROLRANGE&#58;
ctrlid = %d&#58;%d % &#40;groupCenterX+rX,groupCenterY+rY&#41;
dist = pow&#40;anyX-&#40;groupCenterX+rX+0.5&#41;,2&#41; + pow&#40;anyY-&#40;groupCenterY+rY+0.5&#41;,2&#41;
if ctrlid in self._map&#91;self.MAP_CONTROLAREA&#93;&#58;
oldCtrl = self._map&#91;self.MAP_CONTROLAREA&#93;&#91;ctrlid&#93;
if dist > oldCtrl&#91;1&#93;&#58;
continue
self._map&#91;self.MAP_CONTROLAREA&#93;&#91;ctrlid&#93; = &#40;controlcolor,dist&#41;

[/code:1:713cc24014]

CONTROLRANGE and MAXCONTROLRANGE are constants.

It works, although I wish it had more resolution. I found that even dividing the grid in half made horrendous lag during setting up this data (about 1.5 second lag on my system). And all it added was 3 more divisions per loop and quadrupled the number of loops. Python is far from optimized in arithmetic.

------------------------------

Now for a quick overview of that equation :)


[code:1:713cc24014]
________________________________________________
lim r2&#40;r&#41; = √ &#40;cos&#40;θ&#41; · r - city.y&#41;² + &#40;sin&#40;θ&#41; · r - city.x&#41;²
r->r2&#40;r&#41;

[/code:1:713cc24014]

The simplest way is to convert it using Euler's equation and then try and solve.

[code:1:713cc24014]

lim r2&#40;r&#41; = &#40;&#40;e^iθ * r - city.y&#41;^2 + &#40;-e^iθ * i * r - city.x&#41;^2&#41;^.5
r->r2&#40;r&#41;

= &#40;&#40;e^2iθ * r^2 - 2*city.y*r*e^iθ+ city.y^2&#41; + &#40;-e^2iθ * r^2 + i*2*city.x*r*e^iθ+ city.x^2&#41;&#41;^.5

= &#40; 2 * &#40;i * city.x - city.y&#41; * r * e^iθ + city.y^2 + city.x^2&#41; ^.5
[/code:1:713cc24014]

This simplifies back into sine/cosine as:

[code:1:713cc24014]
lim r2&#40;r&#41; = &#40;-2 * r * &#40; city.x * sin&#40;θ&#41; + city.y * cos&#40;θ&#41; &#41; + city.y^2 + city.x^2&#41;^.5
r->r2&#40;r&#41;
[/code:1:713cc24014]

It is reducible more, but I am not sure that it would increase efficiency any more at this point since it would have to be turned into a series, which will most likely just increase the number of calculations. The language should already be optimized for n^0.5 calculations, so there is no need to reproduce that.

Since city.y and city.x are fixed per city, we can just store the square of their locations as part of the city instead of calculating it every time, which would greatly increase efficiency.

This type of conversion using Euler's equation is standard simplification in physics. It seems like it is a fudge, but you have to remember to always wrap it with real(...) and then it's completely accurate. The imaginary part stays imaginary, and at the end you drop it.

P.S. - hope I did my math right. I didn't exactly write it down before I wrote it :D

Level 13 Human Shadow
Alignment: Chaotic good
Location: Earth Orbit, Preparing to Attack
Posted on December 6, 2007 at 12:52 am

A couple other points I missed. I actually don't bother taking the square root. Seemed superfluous to me given that X^2 < (X+1)^2.

Also, the for x in range(...) construct is Python...which lacks a normal for loop and instead uses for as foreach - a little nutty if you ask me :)

And last, because of how python handles DICT class objects (dictionary, which is what Python calls associative arrays), I have to initialize arrays, and since I don't know the range of valid arrays, I opted to just do a string based lookup. I then split the string by the : when I render it:

[code:1:30ab04641d] def drawControlAreas&#40;self&#41;&#58;
centerX, centerY = self._mapSurf.get_rect&#40;&#41;.center
maxY = self._mapSurf.get_rect&#40;&#41;.height
currX = self.currX
currY = self.currY
scale = self.scale
for xy in self._map&#91;self.MAP_CONTROLAREA&#93;.keys&#40;&#41;&#58;
x,y = xy.split&#40;'&#58;',2&#41;
sx = int&#40;&#40;int&#40;x&#41; - currX&#41; * scale&#41; + centerX + 1
sy = maxY - &#40;int&#40;&#40;int&#40;y&#41; + 1 - currY&#41; * scale&#41; + centerY&#41; # use y+1 because we have to draw from top down rather than bottom up
if sy > centerY&#58; sy += 1 #fix a bug with the draw system
dx = scale
dy = scale
pygame.draw.rect&#40;self._mapSurf, self._map&#91;self.MAP_CONTROLAREA&#93;&#91;xy&#93;&#91;0&#93;, &#40;sx, sy, dx, dy&#41;&#41;[/code:1:30ab04641d]