Algorithm to find a frontline between enemy and friendly bases?

Question

Please look at this picture first:

As you can see, blue and red both have a line showing the frontline bases.

Let's assume two players start playing against eachother.

One placing a base at the far left, the other at the far right.

The players continue by expanding and gaining territory.

After a while, the two sides will meet and battle will start.

Question is, in a randomly ordered list of base positions how would one find the two lines that are drawn in the picture?

Answer 1

You could get the distance between enemy bases, where the distance is shorter is the frontline.

Example:

 0 1 2 3 4 5 6
0 aa A   B bbb
1 aA      B bb
2 A        B b
3 aA       B b
4 aaaA      Bb
5 aaaA       B
6 aaaA       B

If you substract the X positions of the enemy bases in the same row, the ones with the less distance between them are the front lines, B.x - A.x will give you a smaller number that b.x - a.x. Then you can check which ones were the ones that gave you the smaller distance for each row.

Unless I'm getting your question wrong.

Answer 2

area

• many games do not draw territory border by polylines
• instead they draw a disc with constant radius (or dependent on base strength) at every base position
• if the radius is set big enough then these discs/circles will overlap
• and create seamless area of single color representing controlled territory
• it is easy but inaccurate

perimeter polyline

1. first cluster all bases and create lists of bases close together

   • this can be done by grouping bases with distance <= treshold

2. process each group

3. find the outer most bases of group

   • something like perimeter points
   • this may help with it
   • also it contains inverse problem of yours which can solve the whole thing more here

4. now find the perimeter closed loop of area

   • the algorithm for that is also in the link above
   • when done then use this list of points as BEZIER cubics poly-curve control points
   • if borderline too close to the bases then enlarge the points
   • first compute avg point ap of group
   • then any point p is computed p=((p-ap)*scale)+ap
   • it is not exact but for your purposes it is enough
   • if you want something better then
   • p=p-ap
   • l=|p|
   • p=ap+(p*(l+dl)/l)
   • where dl is the step at which your border is enlarged
   • and if you want the accurate thing then you have to compute polygon enlargement
   • which is not easy task

5. handle edge cases

   • for singular base groups draw circle around
   • this approach has problem in close proximity of bases
   • one solution is not to count bases too close to any enemy base

per pixel borders

• you can process the map image by pixels

• something like this: (beware this is not tested)

  1. per each pixel

  2. compute the min distance to any player bases

     • remember two closest distances of different players
     • distance0 is closest
     • distance1 is second closest (but base owns another player)

  3. select territory ownership

     • the player which has closest base own this
     • if the distance0 > treshold then this area is uncontrolled
     • in that case stop processing this pixel
     • if ((distance0 >= d-w)&&(distance0 <= d+w)&&(distance1>d+w+s)) then set pixel color to border polyline color
     • d is border line distance from base
     • w is half-size of borderline thickness
     • s is min distance between close front lines

  4. edge case

     • previous step ignore border points that are closer to bases (close enemy bases)
     • to add them just add
     • if ((distance0<d)&&(|distance0-distance1|<=s+w)&&(|distance0-distance1|>=s-w)) then set pixel color to player ownership
     • also this will fail if any two opposing bases are closer then s-w

[Notes]

• I think the best way is the per pixel
• it is most close to the solution you want
• the render can be a bit slower but you need to change it only if any base is conquered