Efficiently determining the bounds of a set

I'm writing an AI for an RTS game, using the API the game offers. One thing I want to do is determine a set of line segments bounding the enemy nation, However, the game only offers a function which tells me the teamID of a single 2D point of territory.

Queries to the g开发者_运维技巧ame AI are incredibly expensive to execute, so I need to keep the number of queries to an absolute minimum, even if this means occasionally getting a slightly worse quality answer. It's also better to overestimate the area of the enemy territory than underestimate it.

How can I efficiently determine a set of bounding lines, around a non convex area of space, using the minimum number of queries?

Nb: Bonus points for answer written in Lua, but Pseudo-code is fine too.

You may be looking for the convex hull around a set of points, see: http://en.wikipedia.org/wiki/Convex_hull

It's an O(n log n) problem -- not too bad computationally. For some pseudocode, see: http://en.wikipedia.org/wiki/Graham_scan

EDIT: with your clarified question, I understand that the regions are not necessarily convex, so the convex hull will give you a broader region than you're looking for. However, it may be starting point (since the ultimate, non-convex region you're looking for is inside the hull) that you can refine.

MORE EDIT: if you really only have a function to query a single point, then your problem is the same as vectorizing a bitmap image. Each point is a "pixel", and the enemy region is the (approximate) vectorization of the "pixels".

I assume you can find a point in the space that is in the territory. Call that Z. (Since you have several cities, you could pick an average city location as being sort of central.)

Given the starting point Z, what I'd consider doing is generating a set of rays outward from that point, each ray having a lower and upper bound on size, and the set growing in number to get detail. I've sketched a scheme below. Nothing about it tested; feel free to suggest improvements.

Each ray is represented by an angle Theta, and has an origin Z. Rather than one length, each ray has two associated lengths, Inside and Outside, which we're going to try to converge. The initial value of Inside is set to 0 and outside set to a value larger than the radius any possible territory ("Horizon"); we'll shrink Outside till it is inside the territory, and grow Inside until it is not quite outside the territory, using binary search (log2 N in the diameter of your game space). We also going to increase the number of rays as the end points spread out to acquire territory boundary detail. The final result is supposed to be a set of rays that establish a bound around the territory whose endpoints are no more than "spacing" apart.

You can start with just one ray (theta=North(0), Inside=0, Outside=Horizon). Lets call the set of rays R. We assume the set of rays R is sorted by theta, and if we have a ray r from R, that next(r) is the next ray in the sorted set, with next(r) for the last ray in R being the first ray in the set. Since you know city locations, you might seed the set with rays having cities as Inside points. It should work either way.

An additional parameter "threshold" gives you the degree of precision of your answer.

R = empty
add_to_R(0,0,Horizon)
repeat until done
    done = true
     for each ray r in R
      guess = average(Inside(r),Outside(r))
      if guess>threshold
         then done = false
      if interritory(Z+(Theta(r),guess))
        then Inside(r)=guess
        else Outside(r)=guess
     for each ray r in R
       if (distance(Inside(r),Inside(next(r)))> spacing
          then add_to_R(average(Theta(r),Theta(next(r)),
                        min(Inside(r),Inside(next(r)),
                        max(Outside(r),Outside(next(r))
end

The running cost should be log 2 in your maximum territory diameter, with a multiplier having to do with the circumference of the territory divided by the ray end-point spacing chosen.

This scheme isn't perfect; it will fail in the presence of peninsulas of the territory that a ray happens to cross by not sampling within the peninsula. If peninsulas are arbitrarily thin, it would take arbitrarily many samples to discover them. You can perhaps choose a peninsula minimum width, and then adjust the algorithm to step outward when it finally finds a converged ray, in peninsula widths to make sure it hasn't goofed.

I suggest you approach it using Monte Carlo methods

http://en.wikipedia.org/wiki/Monte_Carlo_method

Starting with a set of known points should may be able to improve additional "random" guesses based on knowledge of your targets and the results of your initial points (being the set of starting cities)

I might consider trying something akin to equi-potential lines between known points, weighted by the presumed size of the points. Islands which are incorrectly assumed to be attached early on will greatly affect these guesses though.... needs more thought.

EDIT:

So I spoke with a friend who does map analysis for locating spans of specific vegetation from sat/aerial images... somewhat related to this problem because she tries to automate locating patches before reviewing the maps herself.

She says the typical approach is to apply a grid pattern which subdivides your total area and shrinks within itself when it finds specific patterns. So you would sample a regular grid (designing this grid could include some knowledge of sizes you're looking for), if you get a hit, sample more in that area... if you don't, offset your grid and re-sample.

The optimization of this approach is in human knowledge of your search pattern. For example, you specify the number of subdivisions in your search grid based on a common expectation of size/shape.