Map editing for AI path-finding problems.

[Re Berengario I]

I don't know if Nikolai has already kept it in account but some stack stalling is due to AI settings.

For example some conditions that pushed the AI to attack a region could be changed in the meanwhile. I witnessed it a lot during my AI experiments.


I also had the impression that attack/defend decisions are splitted in two consecutive turns (first turn attack evaluations, second turn defensive evaluations). This also could lead to a stall which isn't caused by the map.

[nikolai1962]

hehehe - major progress today :)

responses first...

I don't know if Nikolai has already kept it in account but some stack stalling is due to AI settings.

For example some conditions that pushed the AI to attack a region could be changed in the meanwhile. I witnessed it a lot during my AI experiments.


I also had the impression that attack/defend decisions are splitted in two consecutive turns (first turn attack evaluations, second turn defensive evaluations). This also could lead to a stall which isn't caused by the map.

Yup. One of the difficulties with this is knowing when they're stuck and when there is something else at play. One example is when they're outside a city in the sentry spot and adding more units to the army. Hard to be sure if they're stuck or on invade_buildup or something. The way you can *generally* tell is if you move the army to a nearby rebel region and see if it attacks on the next end turn. If it attacks the city then it was definitely stuck. Sometimes it will move to attack *another* rebel city that it can path to from the new position, sometimes it will head back to where it was before i moved it. They only attack the settlement they were stuck on.

They also seem slower on medium difficulty, at least on my test map. They often take a city and wait for a while instead of moving straight off to the next city like they do on VH. Mission frequency?

With the default AI profiles I'm restricting myself to only looking at the early game where factions are attacking rebel regions which makes it simpler. When wars break out between the factions all sorts of other factors come into play. Also most of my testing is with an AI profile that is attack rebel only (with invade_immediate) and invade_none/force_invade=false for all the other factions so i think that will cut out a lot of other possibile reasons for the AI not to be moving.

~~~

A general question: how would you reconcile the fact of perfect pathing (surprising but true, you were right) with the foibles that AI gets into?

Had a good bit of progress on precisely why it gets stuck today. Explained below.

You say that during player's turn only one stack is being moved so the full-strength can be used. But the same must be true for AI, who can only move one stack at any one time; so they could apply the full-strength algorithm first to the one stack, then to another, etc.

Ditto on alpaca's reply, that is precisely the problem--it can't. From what i've been reading each full strength path-find takes x amount of memory/puter cycles etc. If it moved all the hundreds of AIs using the full strength during the AI turn it would slow to a grind. (I don't know this personally, just what i read.) So games have to reduce the overhead by weakening the AI pathing except in a few special cases.

Finally, some minor questions: would you recommend that inaccessible islands that sometimes share region borders with mainland regions, should be separated into their own properly colored region, so that pathing to mainland regions won't be affected?

Good question. It is all about the region centre point and so it depends on how they calculate that. Basically depends on how they calculate the region centre. Could be:

1) averaging the x, y co-ords of the tiles in the region.
2) averaging the x, y co-ords of the *walkable* tiles in the region.
3) some kind of bounding rectangle incorporating the tiles in the region.
4) Something else.

If my current theory is correct and they calculate the centre point by 1) or 3) then those islands matter and can distort the pathing (sometimes in a good way). If it's 2) and they are all covered in mountains then they won't. Explained more below.

What's the conclusion on convex requirement. Is there one?

Definitely not a requirement on the tile-based pathing bit. It did do something though so i went back to look at it again and now i think it had an indirect beneficial effect on many regions but not because it was used mathematically. Will explain below. It *may* be relevant earlier, at the point where they generate the rwn file and (i think) generate some kind of table of which regions are adjacent. Games set in dungeons etc divide the space into convex polygons to create these region tables but given the nature of TW maps it is hard to see how the region-to-region pathing could work at all if it was a requirement.

It does however make a certain thing much easier (explained below) so i am sticking with my new "convexed" map for the time being.

There is still the possibility (tending to likelihood now) that the meaning of convex in Jerome's post was more to do with unreachable bits of regions.

Does opinion 10 say that there should be lots of moves for use, or that there should be few? Seems like the former, based on your other conclusions.

Larger amounts of movement points over-ride most pathing problems on a vanilla scale map because most of the pathing stalls happen between one and two turns of vanilla movement away from the target settlement. Increasing the movement points while keeping the map the same will increase the one-turn move effect which over-rides most stalls. It will depend on the scale of the map though. If the distance between cities was doubled and movement doubled you won't be gaining much (apart from a longer AI turn). I keep meaning to test the effect of increased movement on retreat problems but i never get around to it as i just don't like really long moves--feels too much like Rommel to me. Personal preference. No doubt though that increased movement points works. Doesn't fix the pathing problems but it does over-ride many of them (not all).

I think there are three distinct sets of pathing problems. Depending on the terrain movement costs and how they have weakened the full-strength algorithm i think there may be a "sweet spot" value for movement which gets round one of these sets of problems. Don't have a clear enough understanding of this one yet to be clearer than that.

re: opinion 18: yes in total, but not at the same time; the AI turns aren't calculated all together, but one by one, and by each stack within each faction's turn.

Yup, but it is cumulative. 600 AIs times 1/2 second = 5 mins. (Prob not really 1/2 second but you get the idea.) I've never tried to count the total number of stacks/agents but on a big map there could be...dunno, lots.

re: opinion 13: really? That would be a heartening conclusion overall, if true.

On my simple mini-map the AI never stalls except after a retreat. Takes 14 regions in 30 turns (can be much longer, depending on the recruitment options.) (This is starting with a general, 4 levy spearmen units and a motte and bailey castle with no buildings.)

re: opnion 11: how :-P

Imagine the map as a piece of paper divided into squares. Draw a load of blue sea on it. Add various impassable terrain and draw region boundaries. Then imagine cutting an individual region out of the piece of paper. Then cutting away the impassable terrain. Any walkable squares that aren't joined orthogonally will drop off the region. For some reason i have a gut feeling that matters to the algorithm somehow. I think tiles like that count as unreachable.

Also... on a more scientific level. One of the aspects i read about on the pathfinding googlefest was how to deal with diagonals. Basically the algorithm (A* is apparently the most common) uses a guess of the cost of the straight line distance to the goal. The euclidian straight line distance uses expensive routines like square root so games often use an approximation. The simplest one is what is called the "Manhattan" distance, which just counts the number of x and y moves and ignores diagonals completely. A step up from this is an approximation of the diagonal move. Some combinations of move costs combined with the diagonal approximation might cause a weakened algorithm to not be able to find a path. Maybe. Not sure on this yet.

re: opinion 1: very important one, also how :)

Changing the region boundaries changes the region centre point :)

That's that for now. It's all very provocative (in a good way). Very good post.

Ty :)


~~~

nikolai: It could be possible that the game uses a kind of large-scale pathfinding via road join points (where roads go over the region border). This way, the AI stacks would usually travel reasonably fast because travelling on roads is faster than through wild terrain and it could be pre-calculated quite easily.
If that's true, you should be able to stall the AI by putting a large stack between their target and them onto a road join.

Yup, that was one of my "possibles". It sort of does in a way but indirectly by way of the road routes taking a "best path" which the AIs will often follow even before there is a road there.. Thing that got me was when they'd take a wildly eccentric route *away* from a direct road path. Think i know why now, explained more below.

Keep up the good research

Ty :)


~~~

Ok, need to upload some screenies and back in a bit to explain a good bit of progress on figuring this out.

Did you ever wonder why the Iberians in RTW always landed armies on Palma that never attacked? Find out soon (maybe) :)


~~~

New Theory

Gave up trying to "convex" the map i'd been working on as i'd already added dozens of regions, all neatly fitted to the terrain etc so convexing the map added too many new problems at once. My simple minimap though has three things different from a normal map--rectangular regions, no obstacles (mountains etc) and all fertile tiles so no variation in movement cost and it has zero movement problems so thought i ought to take a second look at the convex thing just to be sure.

Started again with the plain vanilla map as fewer regions to deal with. Convex the regions. Added a couple in spots where i couldn't fit a rectangle while still conforming to the impassable terrain. Made sure i didn't have any unreachable areas. On the simpler vanilla map the process didn't make the pathing worse as long as i made sure to look out for areas i'd made unreachable by the border changes. Didn't magically improve things in a big way but did have minor beneficial effects in certain areas. Had the same problems in spain i had with my previous historical boundaries version of the map which was i could never get both spain and the moors to move well at game start. It was either one or the other (this is with 6-7 new rebel regions added to spain.) Finally twigged what i think is happening.

The game navigates from region centre to region centre which i'll call the hub. So if a stack is ordered to attack a settlement in another region it gets a path of regions to follow. Assuming the stack starts in region A and has to pass through region B on its way to attack the city in region C the sequence is either:

1) start location -> hub A -> hub B -> hub C -> city C

or

2) start location -> hub B -> hub C -> city C

(hard to tell if it goes to the hub of the start region with my current small regions - will see when i get to the steppe regions.)

this fits 80%+ of my observations, depending on how they calculate the region centre point. assuming the centre point is calculated simply by the average of the x, y co-ords of all the tiles in the region then it is about 80%. Might fit a higher percentage if they calculate it differently.

I think pathing to the hub doesn't require the AI to actually reach the hub but to get within some distance of it (2-4 tiles?) which i'll call the beacon distance. So it paths to the intervening region, gets within the beacon distance of the centre tile and then switchs to pathing to the next waypoint. If at any point it can't get to within the beacon distance of the waypoint then it stalls.

>>>>>>>I don't think the pathing will go through a city ZOC.<<<<<<

The first screenie illustrates the theory. The moors would send a stack to attack valencia through Toledo which would stall at the point illustrated. I think the stack got stuck in it's sequence because it couldn't get a path to the toledo region centre point because with the ford in the old position, (marked in black), the path was blocked by the city's ZOC. (Currently assuming the centre is the averaged x,y co-ords). When i moved the ford to its new position one tile to the right the path to the centre was unobstructed by the ZOC and the moorish armies going to valencia didn't stall at that point.





Similar situation except this time it was the spanish who got close to Estramaduras and stalled. (They'd been there a while before the moors attacked the city.) Again, estimating the centre point of the region it looks like the path to is was blocked by the city ZOC. Tweaking the city position and fords i eventually got it so both spain and the moors had a clear path to the estimated region centre and both factions would move to and attack the city.





The theory explains why i had such problems getting both factions to move at once with all those horizontal rivers and my penchant for blocking fords with cities. Either the centre point was one side of the blocked river or the other and so only one of the factions could path to attack the city. Even if the city itself had a closer unblocked path than the region hub.

Editing the spanish bit of the map according to this theory i now have all three factions able to attack all 6 of the rebel regions in spain.

caveat: according to the theory (and if the region centre is calculated by averaging the x, y co-ords) i don't think zaragoza should be attackable from pamplona but it is. Though actually, now i think of it it might just be close enough for a one turn move. Will need to check.

Basically however editing the map according to this theory is working.

How does this apply to palma?

If you look at the screenie at the original position of palma you can see where my estimate of the region centre tile is (including the co-ords of the little island to the west in the average.) From almost every landing point the city ZOC blocks the path to the region centre so even though a landed army might be right next to its target city it doesn't get the order to attack because it can't clear the previous hurdle of getting a close path to the region hub. (Up to this point most of the AI landings on palma didn't lead to an attack on the city. Only occasionally would an attack happen. I didn't notice what tile the landing was on though.)




I changed the city position on Palma according to the theory as shown below. Now all but one of the possible landing tiles can path to the assumed region centre without crossing a ZOC tile.



One test run. Moors had landed in what i think is the invalid tile and never attacked the city even though they were right next to it. Spanish landed later on one of the assumed ok tiles and attacked.




So, new theory, seems to be working. Might be *the* cause of one set of problems or at least very close to it. Hard to be sure without knowing how the centre point is calculated. Some of the regions were behaving in a way that made it look like the centre was one or two tiles away from where i'd calculated it. Also the beacon distance seemed to vary a bit--maybe move cost rather than number of tiles?

So what convexing the regions was doing was shifting the centre point . The reason it had *some* beneficial effects was probably because a lot of the vanilla regions have such odd shapes, some of them would have centre points out to sea, inside other regions entirely, or just shifted to be inside more complicated terrain. So my convexing, (while trying to keep the rectangular regions conforming to obstacles), was on average making centre points more "central". It didn't fix everything cos the core isn't the convexity itself but the clear path to the centre point.

Also, if the city is directly on the centre point of the region then it's ok.


~~~

I think there are three sets of potential pathing problems.

1) The initial generation of the region table and the game knowing which regions are adjacent. Might not be an actual problem just it seems sometimes that regions don't always know an adjacent region is adjacent.

2) The pathing via waypoints being blocked. The new theory is fixing all of these so far (though i've only done spain so far).

3) The third set are those cases where i think the specific movement cost of a particular path doesn't work with the weakened pathing algorithm the AI uses in the AI turn. May eventually be able to figure out the specifics but basically complicated paths with lots of obstacles and high cost terrain can get these problems. Also cases where the AI has to move away from its target to get closer i.e move around an onstacle, though this seems more rare in mtw2 than rtw. Editing the ground types and moving fords can often get round these but it is a trial and error process. Sometimes it is fixed easily, sometimes it isn't.

Hope that was clear.

[alpaca]

Hmm looks like a very good working theory. How did you calculate the average position though? Arithmetic mean of all tiles x and y positions?

[nikolai1962]

Hmm looks like a very good working theory. How did you calculate the average position though? Arithmetic mean of all tiles x and y positions?

Currently yes. It is correct for fully square interior regions but may not be for coastal ones or those with little islands attached to their regions. Hard to be sure for those especially when the coastline is very irregular.

[PorT_Lobo]

This topic is very important with lot's of info!!!!

Make sure CA get it!! Maybe with all this info, they can solve this BIG problem in the next patch (1.3 or Kingdoms?)!!! This must be solved by CA and in the official game..... this problem of passive AI in campaign map, it's to severe to be ignored by them.

[alpaca]

As for provinces with disjointed bodies of land: I'd do a kind of "flood fill" algorithm that only uses the region pixels connected to the capital by land for calculating a center point.

[nikolai1962]

This topic is very important with lot's of info!!!!

Ty

Make sure CA get it!! Maybe with all this info, they can solve this BIG problem in the next patch

Yeah. The map is definitely fixable if you know the rules and the AI performs vastly better when the pathing works.

As for provinces with disjointed bodies of land: I'd do a kind of "flood fill" algorithm that only uses the region pixels connected to the capital by land for calculating a center point.

Yeah i'm tempted to think it doesn't include disconnected land and you could easily see the possibility of them using the pathing algorithm itself somehow to determine centre points and possibly also region adjacency. I really ought to figure out a way to test how they calculate adjacency. I don't think it works right all the time. A lot of my observations would fit a case of, for example regions A, B, C, D, laid out as below,

AB
CD

where the AI actually goes (or tries to go) A->C->D instead of AB.