Well, Incursion has finally seen some progress on the map generator, so I thought I'd share with you all some of the ridiculous stuff I had to go through to get it to work. As some may know, Incursion's map generator creates territories of random shapes, clustered together; sometimes they're all connected, but other times there are isolated continents that don't connect to anything. Therefore I needed a way to add water routes to connect these lands.

This way lies madness.

I started out with a couple of simple goals:

• Connect all continents together, then connect territories that are too many "hops" apart.
  
• For each connection, find the shortest possible route between targets.
  
• Water routes should be as straight as possible.
  
• Water routes may go over the edge of the map and emerge on the other side.
  
  Now, the dashed line icons I used for water routes don't have any bends in them more than 45 degrees; that is, there are no sharp corners. However the lines can only run in the 8 cardinal directions.
  The first thing I did was to fill the map (a list within a datum) with a special water datum. This water datum kept a list of territories and the distance to each. Water would be created along the coastlines and "spread out" from there; distances were measured by taking all adjacent water datums and using the minimum distance +1 (or else, adjusting them to use its own distance +1 if it was higher). Eventually this made it possible to, from any water square on the map, find the number of water squares needed to get to a given territory. Unfortunately, this was completely wrong. The paths from territory to territory, you see, could wander about or even move at right angles. I often found situations where the "best" pivot point for a connecting path was like this:
  

t    t
tt ttt
t P tt

(You see, the P should have been in the square directly north, but it's still 1 unit from the nearest t in either direction.

So, back to the drawing board. My new rules:

• Connect all continents together, then connect territories that are too many "hops" apart.
  
• For each connection, find the shortest possible route between targets.
  
• A line can't bend more than once, and may only bend 45 degrees if at all.
  
• The lines from the pivot point to both endpoints must be 135 or 180 degrees apart (i.e., the line can't bend more than 45 degrees.
• 
  So, the spreading-out of the water was wrong. Not only was it wrong, but it was inefficient and took forever to run. What I really needed was something to do straight lines. I realized that along any given straight line there could only be one territory at the end, and it could only be so far away.
  
  So now, for each coastline section of a territory, I'd call a RadiateWater proc to send out straight lines through the water, stopping when they hit another territory. The water could then be marked with a bit flag to see if the line pointed to either "side" of the two groups I was trying to connect; water with both flags set indicates a potential pivot for a path. The water was given a dist[] list and a dirto[] list, where dist[territory] = the shortest distance thereto, and dirto[territory] = the directions along which you could reach that territory quickest.
  
  Well, things worked a lot better now, only I found a few problems:
  
  
• Routes going off the map diagonally (except corners) are hard to follow.
  
• Some of the routes were in stupid places and looked ambiguous by coming too close to another territory.
  

t\   t  t |  t  11 /
tt\ttt  tt|ttt  21/
t  \tt  t | tt  22

(Left-hand case: A diagonal route would often brush a corner. This was especially weird when it would attach to a T-intersection between territories as pictured on the right. In the middle, you see that the path runs parallel to two coastlines; one is bad enough.)

• Routes could cross each other.
  
• Routes could cross the edge of the map more than once, which was really confusing to follow.
  
  So, more modifications were needed. Last thing's first:
  
  
• A route may not cross the edge of the map twice. From the "center" point, check to see if either end crosses; if both do, the route is invalid.
  
  Well, natually this didn't work. Turns out that even one side of the route could cross the map edge twice, if it was a diagonal line, while the other one could just go straight home. So I had to modify this a bit:
  
  
• When radiating water from a territory, if the map edge is about to be crossed a second time, stop there.
  
  Okay, so far so good. Now what about the stupid-direction problem? Well, I had to give the water datum a baddirs var, which used the same direction flags. This was set according to the following rules:
  
  
• If there is a horizontal boundary or map edge to the north or south, include west and east among the invalid directions.
  
• If there is a vertical boundary or map edge to the east or west, include north and south among the invalid directions.
  
• If on a map edge, all diagonals off the edge are invalid unless they go off the exact corner of the map.
  
• If a corner (not part of a T or intersection) "faces" a diagonal, the horizontal and vertical directions toward that corner are invalid.
  

   /
 B/
ttB
tt

(Closeup of P and t; the southwest diagonal faces a corner, so west and south would run parallel to t and therefore would be invalid.)

• If a corner (OR part of a T or intersection) faces tangent to a diagonal, the diagonal is invalid in both directions.
  

\     11
 \    11
tt\   22\
tt \  22 \

(Two cases of this: A diagonal sideswipes the coastline of t, and another diagonal is a little bit ambiguous because it sort of touches 2 but really connects to 1.)

Okay, now for the crossing problem. When a route is added, we could just set baddirs to 255 (all directions) for every piece of water in the path, so lines would never radiate out through another path... right? Wrong! Diagonals could still cross each other that way. The only fool-proof way of doing this is to set baddirs=255 for all the surrounding water datums as well.

Whew! That's all, right? Well no, but that's where it stands right now. (I haven't even mentioned the headache of the shortcut algorithm, which tries to decide which of several far-separated territories are on "side A" and which are on side "B". I found out this can be a real problem if the two sides aren't distinct, if there is in fact a side "C", "D", and so on.)

Now there are a few more problems that have yet to be addressed. You see, when a water datum is chosen as the pivot point for a line (even if it doesn't bend, that is), it's chosen at random from a list of other water datums that have valid routes going the same distance. Then, a route is chosen at random from there. This sounds just fine, except that sometimes bent lines are selected when straight ones would be more appropriate.

As of right now, the algorithm only offers a slight advantage to straight routes: The longer ones get counted extra times, because there are more places along the route that count as a pivot. However, I want to choose straight routes to the exclusion of all else if they're available. This means getting into the guts of the BestWater() proc that chooses the pivot, to make sure it's aware of which routes are actually available, and whether any straight routes are to be found.

Have I confused you all yet? Good!

If anyone can suggest other ways for me to handle this, especially to increase efficiency, I'm all ears. But this post wasn't to seek advice so much as to share a harrowing tale of a programmer's nightmare.

Lummox JR