Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Per title, what algorithms are available for defining borders for states (or other entities) based on certain nodes in the world (eg. cities or armies) with varying weights?

For example, there are three non-equidistant city-states and a bunch of military vehicles of varying strength nearby representing each city-states' military power. I would like to be able to draw a border that accounts for the fact city-state A has a huge great army on their outskirts, projecting their power outward.

Ideally the optimal algorithm would be able to calculate a series of connected lines with a high level of precision for multiple states and a large number of nodes (let's say three dozen, for the sake of argument). Speed isn't too much of a factor, since the results would be cached and I'd need to apply a function to 'curve' it anyway.

share|improve this question
+1 and favorite! Keep us posted on your solution :) – Mikael Högström Aug 16 '12 at 15:41
If you work on some kind of a grid.. "childhood" memories remind me of the smell of this monster: . You could seed fronts from clusters of units, march the fronts based on a weight function and then get a discrete version of the borders. Ideally, the fronts will intersect and merge if the clusters are packed and have a sufficiently high weight associated to them. Or you could take an energy-based approach and apply a rubber band that contracts wrapping around your units (with buffer radii for the weights). – teodron Aug 16 '12 at 17:01
up vote 4 down vote accepted

One solution that springs to mind is creating a Voronoi diagram. This will, in the original form, only take into account distance (although you can use different norms like manhattan or euclidean) which is not exactly what you want. I think though that you could tweak the algorithm to use some other heuristic like the one you mention, taking into account armies, economics or other factors.

share|improve this answer
Looks like there are many variants of the Voronoi diagram, including weighted ones: Had a look at a couple of papers and I'm sure there's one or two things that will work. Cheers! – Rushyo Aug 17 '12 at 8:24

Your Answer


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.