Map editing for AI path-finding problems.

[nikolai1962]

AI path-finding Guidelines

The AI is massively handicapped by path-finding problems between regions. Their armies are often immobile through not being able to find the target they have been given.

Some quick examples:
1) The southern starting scottish army doesn't move at all.
2) The english AI will move two seperate stacks towards caernavon and will usually stall two tiles away.

*Revolts/rebel activity can change this occasionally.

There are dozens of other examples.

These problems only seem to effect those AI stacks that are moving to attack an enemy settlement and *seem* to only occur between adjacent regions i.e a stack can move through multiple regions prefectly well and only stalls at the last hurdle.

This kind of thing is happening all over the map between particular pairs of regions, sometimes in both directions, sometimes unidirectional. In areas where there are a lot of adjacent regions it is less noticeable because if one faction is stuck attacking a region from one direction then another faction will sooner or later attack it from another direction. The problem still exists however and means part of a faction's total army is being wasted. In all cases where an AI army is stuck this way they get unstuck when the target city is taken

~~~

Since RTW i've been trying to figure out what precisely leads the AI to get problems with their path-finding but haven't been able to figure it out. However there are some recurring elements that have led me to certain guidelines which help a bit.

Some game elements i *think* are related to the problem.

1. Roads only form along orthogonal paths i.e where there is an up/down or left/right path between two tiles.

2. Roads aim to take the fastest route between the settlement to the border of the adjacent region, not neccesarily the fastest path between settlements. This can be effected by the lack of an orthogonal route and also by the game averaging out two nearby roads.

3. If you move your own armies the arrow takes the shortest route between the start position of your army and the point you click. It is hard to be sure how an AI army chooses its path, either the fastest route or the fastest route to the adjacent border, maybe both under different circumstances.

~~~

Some recurring themes I've noticed trying to unstick stalled AI armies.

1. Pathing through a mutually adjacent region.

If an army in region A is targeted to attack region B and the route it takes passes over a region C that is adjacent to both A and B.

Some definite exceptions to this.

a) If the border between the start region A and the target region B is all impassable they seem to have no problem navigating through mutually adjacent region C.

b) If the path involves another region D that isn't mutually adjacent to the start and target regions they seem fine too. An example of this on the vanilla MTW2 map is jedda->damascus which goes jedda->gaza->jerusalem->damascus. The path goes through Gaza first which is not mutually adjacent to jedda and damascus. This is an example of the AI taking the fastest route and not the fastest route to a common border.

c) A contra-example to the general theory is Yerevan->Trebizond. The fastest route is through the mutually adjacent Tblisi but the AI takes the longer route to the trebizond border instead. This is an example of the AI taking the fastest route to a common border and not the fastest route overall.

Though c) seems to contradict the theory i've seen many places where a stuck army can be made to move if the map is changed so the fastest route doesn't pass through a mutually adjacent region. There is obviously something i'm missing but there is some element of truth in it in some circumstances. It is not 100% consistent however and i think the inconsistency may be something to do with whether the AI army path-finds the fastest route to it's target across regions or the fastest route to the border of its target and then from the border to the settlement.


2. Non-convex regions.

This CA post:

A few other caveats about regions:
- they should be 'convex' (one landmass, no inaccessible areas)*- they should have only one settlement and only one port

This implies to me either that there should be no moveable tiles that are completely unreachable, or that each region shouldn't have walkable tiles that can't be reached from that region e.g tiles that are across a river with no ford. I think it is the latter as I've seen AI path-finding problems being cured by fixing examples of non-convex regions.

I had hoped this non-convexity of regions on the map would prove to be a major part of the general path-finding problem with a global messing-up effect on the path-finding algorithm but unfortunately it seems more localized and inconsistent. It may just be a variation of 1) as a region split in this way will effectively be two sub-regions with an increased possibility of calculated paths crossing into mutually adjacent regions.

edit: I misunderstood what was meant by "convex". Actually means this

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

making all the regions like this cures almost all pathing problems.

3. Non-orthogonal paths.

Imagine four square regions joining at a point.

aabb
ccdd

where a, b, c, d are fertile tiles at the corners of the four regions. An AI army moving from region C to B has only a diagonal path. If the game only path-finds using orthogonal connections then it would actually go either right then up, or up then right to get to the diagonal path to the target region. This would fall foul of the mutually adjacent *rule* and the army would stall. Which an AI army will invariably do in that situation.

I *think* this is only a potential problem on the border.

It can occur more frequently than you might think for example.

aammm
bbccc

where a, b, c are fertile tiles of regions a, b and c and m is mountains. An AI army going from a to c or vice versa may get this diagonal problem if it was the fastest path. Or maybe only if it is the *only* path.

Basically this is another subset of the problem 1). The diagonal path means that if the path-finding is only calculated using orthogonal connections then it clips into the mutually adjacent region B even though the army itself can go diagonally from A to C.

~~~

The above points are the closest i've managed to get to figuring out systematic patterns in the AI movement but they lead to some guidelines that do help a bit.

1. Clear all the non-orthogonal paths in each region. (Maybe only need to clear the ones on the best routes between adjacent regions.) Examples in the screenshot below. (This may only matter at region borders or if the non-orthogonality makes roads go in unnatural directions causing problem 1) above.)




2. Look out for regions that join at diagonals and edit the map to make sure they have an orthogonal path or bury the point under impassable terrain.

Example of this from the vanilla map in post #7.

3. Try to make the roads follow the same route as one of your own armies would if they were moving to an adjacent settlement (or to the border of that adjacent region). Add/remove hills/forests etc to make the fastest route go where you want it. Basically aim to make all the fastest routes from a settlement to adjacent settlements avoid clipping into mutually adjacent regions.


4. Make sure all the passable tiles in a region can be reached without leaving the region i.e check there is a path from the settlement to every tile in the region that doesn't require moving into another region.


5. A specific problem may occur with narrow sea channels (this includes inlets). Sometimes it looks as if the AI army thinks two land tiles are adjacent so if it ends on one side of the water it gets stuck as it can't physically move to the opposite side. The AI seems to get this problem often when trying to move from hamburg->stettin. Sometimes covering the specific tiles the AI gets stuck on with dense forest can help this. This may also be fixable by tinkering with how the sea surface is defined but i don't know about those files.

~~~

Ideally i think the AI path-finding would work best if the fastest path between every tile in the region to every other tile in that region was wholly inside the region.

An example of the kind of situations this would resove is in post 6.

Making regions conform to this rule is surprisingly possible but only if the regions conform to the *natural* movement paths determined by the physical geography. Valley type regions with a river running down the centre would generally need to be split into two though as rivers are only barriers in the TW games and not the combination of road/barrier they were historically.

So the ideal form of a region (in AI path-finding terms) would be like a wheel, with the settlement as the hub, each spoke being the natural route to each of the adjacent regions, and a rim path so that the fastest route between the far ends of each spoke was still within the region.

an example of what i mean by a "wheel", edited iconium region with a selected spy in the city showing the routes. the red lines are the natural routes to other regions, the black lines show how i've moved the border to create the rim.



~~~

Workarounds.

Using the above guidelines has only fixed 20-30% of the map problems so there's some other big factor or factors involved. You can workaround the problems by taking advantage of the fact that if an AI stack can reach it's target in one turn of movement then this seems to over-ride most pathing problems. One way is to just greatly increase base move points in the descr_character.txt file. This may cause more stalls from post-battle retreats but i haven't tested that. The second option is to have lots of little regions where the settlements are close to each other. Both options are doing the same thing which is reducing the average number of turns between settlements over the map, increasing the number of one turn moves.

Unfortunately there's another thing with MTW2 that seems to mean you could never get a map to work perfectly.



The screen shows egypt with three regions all of which have a working path between themselves and siwa. However, depending on how you set up the starting garrisons and the garrison at siwa the AI will choose to either attack it from one city or move units from more than one garrison and merge it to attack siwa. In my case i had 3 small garrisons in the 3 cities in the strat file which meant units from each took the paths shown and merged roughly where the "X" is. Because of the route they'd taken prior to merging one of the stacks had broke the mutually adjacent rule and the combined stack stalled after the merge. This happened every time unless some random event like brigands/revolts changed the pattern.

This happens all over the map too as MTW2 AI is much better at combining armies.

You can get round it at game start by re-arranging garrisons to have one big one in one city and small garrisons elsewhere and watching the early moves to check it is ok. Nothing you can do about the times it will happen later on in the game. Needs whatever is causing it to be fixed.

edit: this may just be a side-effect of non-convex regions. a map of fully convex regions seems not to get these problems.

~~~

I'll add to or refine this if/when i get more specific. Some path-finding problems seem impossible to fix. Some problems on the vanilla maps (either RTW or MTW2) seem impossible to fix without adding extra regions in areas of particularly complicated terrain.