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.)

https://img168.imageshack.us/img168/340/orthowp7.th.jpg (https://img168.imageshack.us/my.php?image=orthowp7.jpg)


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.

https://img337.imageshack.us/img337/114/iconium2og6.th.jpg (https://img337.imageshack.us/my.php?image=iconium2og6.jpg)

~~~

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.

https://img367.imageshack.us/img367/3388/mergestallvb8.th.jpg (https://img367.imageshack.us/my.php?image=mergestallvb8.jpg)

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.

[alpaca]

Very good post. I don't have anything to add atm, but if I do a bit of mapping (well it could happen) I'll have a look for this kind of stuff :sweatdrop:

[nikolai1962]

I don't have anything to add atm, but if I do a bit of mapping (well it could happen) I'll have a look for this kind of stuff.

Cool :)

I'll add more illustrative screenies as i find perfect examples of certain points. Working on the vanilla map for real now after my experimenting, starting with asis minor as that's the worst effected. The turks are already expanding much better. Will upload it when done.

[wilddog]

nikolai1962

Nice post. I hadn't looked into this in much detail before. However I will try and test some of this out.

Maybe there is a connection between what you've found out and the 'pathing' problem (my term) which causes a crash when maps are create with either a super sized region or very complex seas or rivers etc that can't be passed.

[nikolai1962]

Maybe there is a connection between what you've found out and the 'pathing' problem (my term) which causes a crash when maps are create with either a super sized region or very complex seas or rivers etc that can't be passed.

Wouldn't surprise me if that was true.

[nikolai1962]

An example of where this guideline/rule would have applied.


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.


Didn't take screenie at the time so drew some lines on the current map to show the situation when this glitch occurred.

The black lines were the borders of damascus/baghdad.
The red lines are where the road went with those borders.
"R" is a brigand stack that spawned.
"A" is the position of an egypt stack heading to Baghdad when the rebels spawned.

https://img187.imageshack.us/img187/1208/ex1oj0.th.jpg (https://img187.imageshack.us/my.php?image=ex1oj0.jpg)

When the game creates roads it takes the shortest route to the border of the adjacent region *but* when there are two roads close together it merges them along part of the route. In the situation above the road to jedda was pulled close to the damascus/baghdad border line because of this.

The egypt stack moving to baghdad switched to attack the rebels but because of the road it's fastest route took it over into damascus. This hit the region A to adjacent region B via a mutually adjacent region C problem and the stack stalled. It would have stayed there until it either revolted or some other army killed the rebels. (You can find out what is causing a stack to stall by using move_character and moving it around till it moves on its next turn.)

If all regions conform to the rule above then this problem will never happen. In vanilla mtw2 (or rtw) if you watch the AI after x turns with fow off you'll be able to spot dozens of AI stacks stuck like this.

[nikolai1962]

Example of a diagonal path stall.

Sometimes you'll see egypt stall attacking Damascus with an army in Acre that isn't moving. This will usually happen if they've attacked from jerusalem and lost *and* they have a stack in acre that isn't doing anything. They'll set the stack in Acre to attack Damascus and that stack witll stall.

https://img90.imageshack.us/img90/9633/ex2wv8.th.jpg (https://img90.imageshack.us/my.php?image=ex2wv8.jpg)


If you look at the screenie you'll see that the border point where jeruslaem, damascus and acre all meet is just before the mountains. This means the Acre stack tries to path through where i've drawn the blue line. However, i think the pathing works orthogonally and only figures out diagonal movement after it creates an orthogonal path. This would mean the pathing at that junction would go one tile right into jeruslaem region then one tile up to the corner tile of damascus region.

This hits the region A to region B through region C thing and the stack stalls until they revolt or damascus gets taken by some other stack.

This can be fixed by moving the mutual border point under the mountains.

[alpaca]

By the way Nikolai, you might want to check out my stripped-down map to test this more systematically.
You can create all kinds of setups there quite easily, and you can decrease the map size by a fair margin to generate the rwm faster (it's already faster than vanilla anyways I think)

[nikolai1962]

By the way Nikolai, you might want to check out my stripped-down map to test this more systematically.
You can create all kinds of setups there quite easily

Yeah, i d/l ed it precisely for that reason. Trouble is i'm a bit obsessed with semi-fixing the vanilla map so i can actually play the game without getting frustrated seeing all the AI armies standing around not doing anything. I'm planning on just getting the vanilla map semi-working then using your thing to make a new test map to figure out the rest.

[SigniferOne]

Excellent post Nikolai, will be very interesting to put it to use. Have you consulted a very similar study of pathing in RTW? They started along very much the same lines as you did, and I think they got further along in RTW. Considering that both games have almost exactly the same maps, the results should be comparable between the two studies.

[Lusted]

Nikolai did the ai pathfinding thing for RTW i believe.

[nikolai1962]

Have you consulted a very similar study of pathing in RTW?

Yeah, Lusted is correct. I started looking at this for RTW but got sick of trying to guess what makes it work, or rather not work. Had to try again for MTW2 as it had the same problems of AI armies standing around lost all over the place. The guidelines above solve at best maybe 20% of the problems though so i'm still missing big pieces of the puzzle.

[SigniferOne]

Are you using the autoplay switch, to play through the first X turns automatically? I was pretty positive it's been transfered over from RTW, but so far haven't seen people mention it.

[alpaca]

No, the system has changed. You need to play hotseat and switch control of the last control faction to the ai, that basically has the same effect.

[SigniferOne]

Ah yes, here it is I found it: How to jump to a future year (https://forums.totalwar.org/vb/showthread.php?t=75576)

There's far too much wisdom interspersed all throughout the ORG (and some at TWC), with no one place to go look for it. But it's there :)

[alpaca]

Yeah but that is because compiling it into one thing would require an almost complete knowledge of every modding aspect. Not to mention the insane amount of work.

[nikolai1962]

Added a bit under the title "workarounds".

[nikolai1962]

Sorry, missed some posts.


Are you using the autoplay switch, to play through the first X turns automatically? I was pretty positive it's been transfered over from RTW, but so far haven't seen people mention it.

I wish. I'd been wearing out my clicking finger on the end turn button. I looked on the forums and it seemed not to have been carried over to mtw2.



No, the system has changed. You need to play hotseat and switch control of the last control faction to the ai, that basically has the same effect.

Doh



Maybe there is a connection between what you've found out and the 'pathing' problem (my term) which causes a crash when maps are create with either a super sized region or very complex seas or rivers etc that can't be passed.

Been googling some mathematics stuff (wish i'd thought of this before). From what i can gather so far path-finding is highly intensive and the above quote seems very likely to be true. Quite possibly what caused the rtw map crashes when the sea was too big too. I think they may have improved their long-distance algorithm but kept the short-distance one. Maybe.


~~~

I *think*

All your map regions need to be convex polygons - definition here

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

sea is probably a single "cluster" (technical term hehe)

damn i could have saved myself an freaking ridiculous amount of time if this proves to be what it's all about. though i think there's something more going wrong too as i don't see yet how the crossing a mutually adjacent region thing would mess it up. maybe it is a side-effect. dunno

[alpaca]

Dude, making every province convex is nearly impossible if you want at least a bit historical borders...

[SigniferOne]

That kind of sucks if all regions need to be convex. I suppose there's a workaround where a previously concave region is split into two convex ones, but that's an unnecessary hassle. Try changing all regions to convex and seeing if they still have the recalcitrant problems. Also, the autoplay feature discussed above should save you a lot of time.

Caliban, what do your AI-pathing guys think about our discussion?

[SigniferOne]

Nikolai, in this old thread (https://forums.totalwar.org/vb/showthread.php?t=50437) by Myrdraal on map-making in RTW, there are a few interesting comments by then-CA-helper Jerome:


Jerome posted:

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
- all land tiles should be part of a known region
- each non-sea region should contain at least some fertile tiles
- continuous sea surfaces should form one region
- the maximum number of regions supported is 200
- the distance between the centres of any two adjacent regions should not exceed 50 tiles*

*: not doing these things shouldn't cause a crash, but it may cause the AI to mess up.

[nikolai1962]

Dude, making every province convex is nearly impossible if you want at least a bit historical borders...

Yup.

Some workarounds...



That kind of sucks if all regions need to be convex. I suppose there's a workaround where a previously concave region is split into two convex ones, but that's an unnecessary hassle.

Is one of them, as mentioned by Signifer. It's very definitely a hassle but all historical regions will have had sub-regions so breaking some critical ones into two won't be so bad.

You might be able to use impassable terrain somehow to block out the non-convex bits. Depends how it works. I don't think that it can be that a non-convex region in itself can mess up the path-finding as most of the regions on the map are that way and my experience is thatregions usually only have problems from certain directions. So it may be that the problem hits when it is non-convex in the direction the AI is travelling. So some bits of non-convexity may not matter.

Also the "lots of movement points" or "very close settlements" workarounds are options too. So if there is a region which is impossible to make convex then just make sure an adjacent region's settlement is within one turn's movement of the bugged one.

Might depend a bit on how the impassable terrain is handled.

Does fit with all my AI watching though. Even fits some of the things i thought i was imagining i.e shifting a border contained entirely within impassable terrain messing up the pathing.

Generally though i think the point is that this will be an easy cure for *some* map path-finding problems. It is much easier to have a clear potential solution than just trail and error. In the end there is still a lot of ways for the AI to mess up. I'm mostly just interested in fixing the places they stall right at the start of the game, which is only a subset of the total.



Try changing all regions to convex and seeing if they still have the recalcitrant problems.

Too many on the vanilla map to try yet. I need to decide whether it will be too much hassle. I used alpaca's stripped down thingie to make a minimap--rectangular regions, offset so none of them join at a diagonal. Pathing works perfect. I sort of knew it would as i had a map like that before (without the offsetting), just i didn't know why. Still get stalls after retreats though.



Nikolai, in this old thread by Myrdraal on map-making in RTW, there are a few interesting comments by then-CA-helper Jerome:

Yeah it was that convex comment which finally clicked in my head to stop looking at the problem as if it was a map of real geography and look at it for what it is. A purely abstract collection of x,y co-ords that gets passed to an algorithm with rules. When i was trying to figure this out with rtw i was thinking of it in entirely the wrong way--trying to straighten roads etc. Came to the same conclusions (hence the wheel thing in the first post) but in a very roundabout way.


Caliban, what do your AI-pathing guys think about our discussion?

I'm guessing they know it's a problem. From what i've read complex path-finding is ultra hard on puter resources, so games mix and match algorithms to save overhead. Using one of the ones that could handle a realistic map may be out of the question. Dunno though.

Be useful to know more though. Might be able to narrow the "rule" down more as i don't think it is 100% true that *all* the regions have to be 100% convex. Pretty sure direction matters as almost all the coastal ones are non-vex with all those little inlets. How sea/internal water is handled matters i think.

[nikolai1962]

Try changing all regions to convex and seeing if they still have the recalcitrant problems.

Changed the southern third of the regions on my main edited map to make them more convex (in the landward direction for coastal regions). I'd already been adding and changing regions according to my guidelines so a lot of them i'd made more convex by accident, (as the guidelines unwittingly fits in with the convex thing), but the pathing is still not perfect.

1. It got much better in the turk starting area. Had already added four little regions as a workaround, added two more to make all of them convex and the turks *finally* expand reasonably smoothly. (Almost all interior regions.)

2. It got much better in the egypt starting area initially until i changed something else which makes egypt stall pretty much completely now. The regions still look convex so something else is screwing with it. (Red sea?)

(BTW the vanilla pathing between gaza->jerusalem doesn't work. doesn't notice in the vanilla game because gaza is close enough to make it a one turn move for an army starting at the gaza "sentry spot".)

3. It got much better in spain for the spanish faction but didn't help the almost entirely stuck moors at all. There's something wrong with the map near valencia as i've literally had dozens of different region layouts and none of them are any better than vanilla when it comes to the AI pathing to valencia.

4. Didn't help in britain. Only way i've ever got the scottish AI to work consistently is to rig the city distances and make their third general younger so he comes of age instead of being around at game start. (Complicated sea again?)

From my first look at AI path-finding stuff on the web it seemed one of the main path-finding algorithms uses a similar technique to the floodfill in a graphics program. If i understood it correctly the basic version of that technique is the one that requires a convex polygon. Another technique mentioned was having sectors with only the join info between sectors being saved. So i was thinking maybe the game regions would be sectors with the internal pathing being handled by the floodfill technique and the inter-region movement via saved "join-tiles". This doesn't fit the rather eccentric choices of region->region paths the AI will sometimes choose though.

So there's something else i'm missing.

argh, back to google.

[alpaca]

Haha keep up the good work (and if possible throw a few good links into the round so I can suss them in) ~;)

[nikolai1962]

Haha keep up the good work (and if possible throw a few good links into the round so I can suss them in)

These were my starting points

http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths

http://www.gameai.com/pathfinding.html

trying to delve into specifics now.

~~~

Thought collection

opinion.

The strategic AI can never be a challenge without either much better pathing or giving the AI very large amounts of money. If you don't like fighting the same battle over and over with multi-stacks of AI armies then you need better pathing. Hence my problem.


observations from AI-watching and map-editing with rtw and mtw2

1. moving region boundaries can change the pathing

2. moving region boundaries, even if the changes are completly within a block of impassable terrain, can effect the pathing.

3. areas of a region that are unreachable from the rest of the region can effect pathing.

4. sometimes the game doesn't seem recognize an adjacent region as adjacent (clue is when the AI will land an army by ship from an adjacent region)

5. the AI seems to move across long distances fine but has problems when it gets close but still further than one turn away.

6. sometimes an AI stack will move to a region and stall on the edge of, or the first tile of the final region.

7. changing something on the map in one area can effect the pathing in a completely different area.

8. On a complex map the AI will often (but not always) stall when moving from region A to region B if the path clips across a region C that is mutually adjacent to both A and B via passable terrain. Doesn't seem to happen at all on my simplified map.

9. the AI has a preference for attacking cities from the south-west.

10. changing movement potential effects the pathing, either via adding movement points or by effectively decreasing movement by adding more difficult terrain to the map.

11. orthogonality matters somehow

12. In rtw an AI would often have problems when they were close to their target in a straight line but an obstacle made their actual path take them further away. seems very rare in mtw2

13. Pathing problems seem to only happen to stacks with a city target. (Possibly i don't notice other times.)

14. AI supporting armies often seem to be happy to get within (roughly) two tiles from the city itself.

15. sometimes a stack will be given a target and not move at all. this is most noticeable at game start.

16. an AI army will often stall after a battle, especially after a retreat from a siege assault. this happens a lot less on a simplified map. it seems to only effect stacks that have a city target. it seems at least partially related to pathing.

17. an AI army will sometimes move only one tile. happened a lot in rtw, especially over fords. can happen at other times. haven't noticed it so much in mtw2

18. There are potentially many hundreds of AIs that need to have their path calculated in the AI turn.

19. Most importantly, the pathfinding code itself works perfectly. When a player selects a unit to move and right clicks on the map the game displays the movement arrow of least movement cost and that's where the stack goes. It never goes wrong in any circumstances. When you select a unit the green overlay shows all the movement paths. It never goes wrong.

~~~

AI pathfinding stuff from Google.

1. There are algorithms that will always return a best path on a map like MTW2 or RTW.

2. These algorithms are computationally expensive.

3. Games have to use multiple pathfinding mechanisms to tweak the computational cost.

4. One tweak is to weaken what is called the heuristic of the algorithm so it doesn't look for the best path, just a close path.

5. Another is to artifially tweak the movement costs of tiles so the algorithm spends less time looking for the best path.

6. A third tweak involves how you treat diagonal moves. calculating the square root of the dx,dy squared being the most expensive and therefore least used for mass AI moves.

6. A common technique (apparently) is to use regions as a kind of macro-tile. With a table of regions, region centre points and their adjacency, an AI can navigate long distances without having to search the whole map for their goal. they first use the regions table to get a path of regions A->C->F then use the expensive tile pathfinding algorithm to find the (much shorter distance) path between the hub points of those regions. Switching back to the tile algorithm when they reach the goal region for the final move to the target.

7. The pages mentioning this technique imply the standard method for doing this involves breaking the regions into convex polygons.

~~~

Current conclusions.

1. When it is the player's move the game knows there is only one stack/agent being moved at a time so it can use the full strength pathing which won't fail.

2. Observations 1-7 (and maybe 8) lead me to think the game is using regions somehow as a macro pathfinder. If it does then that may be part of what it is doing when it generates the map.rwn. However, there's no way TW regions are ever going to be all convex ploygons except on the most simplified maps. There may be a cleverer algorithm i haven't come across that would generate a distance table for regions such as those in a TW game. That algorithm will still have rules though and figuring them out and editing the map accordingly will improve the AI pathing. Alternatively they may just use the full-strength pathing algorithm to generate a region table. Currently tweaking my much-edited vanilla map along the lines of making the region boundaries convex in the directions of travel until i get a better idea.

This system requires each region to have a centre point for the AI to aim at. If the game uses the regions as a macro pathfinder how does it calculate the centre? If it a simple average of the x,y co-ords of the tiles in the region then could it be glitched by some coastline shapes and those little islands that are part of the land regions? The "goal" setting on these long range moves may be weaker i.e not reaching the "centre" tile of a midway region but getting within 2-3 tiles maybe as i think this would be cheaper to compute.

3. Pathing algorithms have a start tile and a "goal" tile. Observation 9 makes me think the goal tile for a city is maybe not the city itself but the sentry spot for a city (usually the bottom left of the tiles around the city depending on terrain). Making sure there is a clear path to this tile for each city may help.

4. Observations 10-12 all look like the kind of things that could happen with "weakening" tweaks to the pathing algorithm. So basically certain combinations of terrain might cause the algorithm to not return a valid path under certain combinations of movement cost and movement points.

5. Observations 13-14 make me think stacks with a city target have a stricter "goal" setting which in combination with the algorithm weakening tweaks makes them more prone to getting stuck.

6. When building the regions distance table (if they do) and using the terrain tiles to calculate it, if they used the full strength algorthm to generate the table but used the weakened algorithm when actually moving the AIs that might be behind some of the glitches. this might relate to observation 15.

7. the retreat/post-battle stall could (and probably is imo) be caused by more than one thing. in some cases it is simply the AI retreating to a tile with a pathing problem.

8. observation 17. dunno. more googling

9. observation 18.

a)The meaning of convex in the context of a TW map. With all fertile tiles and no obstacles the best region shape may be a convex polygon but is that the correct shape when the varying movement costs of tiles is taken into account.
b)If the AI is using tile based pathing from A to B why should it care if it finds itself in C for part of the route?
c)Why doesn't the AI care about crossing a mutually adjacent region when the regions are convex polygons on a simplified map (or is it the movement cost/terrain)

10. Game may give AI stacks with a city target a first sweep with the full strength algorithm for up to one turn of movement. If it finds the goal it moves, if it doesn't it cuts off and uses the weakened algorithm. This would explain the one turn move effect.

11. "might" not be possible to get perfect pathing on a large realistic map

12. "might" not be possible to get perfect pathing on a large realistic map without very long end turns

13. definitely possible to get perfect pathing on a small simplistic map (apart from retreat stalls)

14. "might" be a cut-off point where you can get perfect pathing on a quite large, quite realistic map.


~~~

another pointer to the game using a region distance/adjaceny table is the low number of regions they have in the vanilla game. these tables require the region number squared records of however many bytes. so 60 regions require 3600 times x bytes and 200 regions require 40000 times x bytes.

AI end turn slows down a lot as you add more regions. mods with large maps might want to consider agent limits and more expensive units to cut down on the total number of moving AIs.

[SigniferOne]

Nikolai, top notch post.

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? 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.

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?

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

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.

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.

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

re: opnion 11: how :-P

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

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

[alpaca]

Do you realize that each AI turn would take minutes if the game used perfect pathing for every freaking unit it moves (and it generally moves almost every unit once per turn at the least)?

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.
Keep up the good research :2thumbsup:

[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.


https://img338.imageshack.us/img338/6640/stall1bqm2.th.jpg (https://img338.imageshack.us/my.php?image=stall1bqm2.jpg)


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.


https://img338.imageshack.us/img338/8567/stall1vj0.th.jpg (https://img338.imageshack.us/my.php?image=stall1vj0.jpg)


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.)


https://img338.imageshack.us/img338/5474/palma1ar5.th.jpg (https://img338.imageshack.us/my.php?image=palma1ar5.jpg)

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.

https://img338.imageshack.us/img338/6020/palma2ff4.th.jpg (https://img338.imageshack.us/my.php?image=palma2ff4.jpg)

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.

https://img338.imageshack.us/img338/8559/palma3le6.th.jpg (https://img338.imageshack.us/my.php?image=palma3le6.jpg)


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.

[SigniferOne]

re: alpaca, I'm assuming you're theorizing about how you'd solve that problem if you were coding it? A flood fill could work, but another option would be to work off descr_regions, and find the extreme pixels which share the same color; that way you wouldn't have to process all the pixels in the region, only four pixels that form its outermost 'square' limits. That is, if the pathing algorithm works off the center of the province at all, which I suppose would be a reasonable thing to do.

Nikolai: excuse the denseness, but what did you mean about calculating adjacency? Maybe if we pool in our comp. sci. minds here, something useful will come out :)

[alpaca]

re: alpaca, I'm assuming you're theorizing about how you'd solve that problem if you were coding it? A flood fill could work, but another option would be to work off descr_regions, and find the extreme pixels which share the same color; that way you wouldn't have to process all the pixels in the region, only four pixels that form its outermost 'square' limits. That is, if the pathing algorithm works off the center of the province at all, which I suppose would be a reasonable thing to do.

Nikolai: excuse the denseness, but what did you mean about calculating adjacency? Maybe if we pool in our comp. sci. minds here, something useful will come out :)
Oh, a flood fill would be very fast imo, probably faster than tracing the outlines of every region.
It's under the assumption that the game uses every land tile that belongs to the province for calculating a center of mass.

With calculating adjacency Nikolai means the process of figuring out which provinces are neighbors to each other (with the arbitrarily shaped regions in the game a not-so-easy process).

[nikolai1962]

With calculating adjacency Nikolai means the process of figuring out which provinces are neighbors to each other (with the arbitrarily shaped regions in the game a not-so-easy process).

Yup. If they are using region-hopping (which it seems to be) then the way it is normally done (according to my AI path-finding Google-fest) is the game creates a region table (map.rwn?) which contains various bits of info including which regions are adjacent to each other. They can then use this to create a macro-path of regions to follow to their target region. The same info for two regions may be what the "isneighbour" condition is looking at.

According to Google this is done much easier if the regions you are using are convex polygons cos of some relatively simple vector maths. Not sure that really makes sense for the TW regions though. The region table might be a sort of nxn table where n is the number of regions with info like the x,y co-ords of the centre and a flag for adjacency or something. I'm buried in the trees at the minute so can't focus on the woods :)

Example, map with 4 regions A, B, C, D laid out as below (S = sea)

SC
AB
SD

then the region table might be

-ABCD
A1100
B1111
C0110
D0101

with "1" as adjacent and "O" as not-adjacent. dunno though, now i typed it out seems a lot of redundancy. either way it needs some mechanism to determine adjacency and it seems logical to me it might be stored in the map.rwn.

From my AI watching though I'd say the game often doesn't know a region is adjacent so i think something often goes wrong with the region adjacency calc. Hence why it would be good to know how it's done as it's possible region shape comes into it. I'll look at this more when my map is more finished and try and see where and how often the AI takes an odd region-path to a target and compare it with how often it does the same on the vanilla map.

It's kind of a seperate issue as with the tile-based pathing working the AI can still find it's way to a target region even if it has taken a longer route than neccessary. Faster if it takes the direct region->region route though so worth figuring out eventually, if possible.

~~~

My map is starting to work very nicely now though. Just the sector from the balkans to turkey to do. Though the balkans is proving tricky and turkey will be worse cos of all those diagonal mountains. I was aiming at all the rebel regions being taken by turn 30 using my "attack rebels only" AI profile (apart from the very distant ones like Volga-Bulgar). It's getting close to that even with the default profile so pretty pleased.

~~~

nb. If the region's city is one tile from the centre then it can cause the AI difficulty finding it cos of the overlap of the city's ZOC. There seems to be a special case in the code when the city is exactly on the centre point though. No problem then.

[DaVinci]

Hey nikolai, great to see you are still at investigating the AI behaviour. I can remember it well, how you started that, in 2005, wasn't it on the old RTR forums?

Keep up this excellent work (seeing the date of you last post is pretty old).

P.S. I just put a link to this thread into our current M2 dev forum :yes:

[SigniferOne]

Nikolai, it occurred to me that recent developments in toggle_terrain could help you greatly in really understanding AI and pathfinding. See this thread: http://www.twcenter.net/forums/showthread.php?goto=newpost&t=122162

For instance, if you "toggle_terrain choke", you can see exactly where there are chokepoints on the map, what areas seem passable but game-wise aren't, can investigate what squares AI armies should not be allowed to spawn at, etc. I think it could really be a great tool for you.

[nikolai1962]

Hey nikolai, great to see you are still at investigating the AI behaviour. I can remember it well, how you started that, in 2005, wasn't it on the old RTR forums?

Keep up this excellent work (seeing the date of you last post is pretty old).

P.S. I just put a link to this thread into our current M2 dev forum :yes:

Ty. I gave up again for a bit because it was driving me nuts :)

[nikolai1962]

Nikolai, it occurred to me that recent developments in toggle_terrain could help you greatly in really understanding AI and pathfinding. See this thread: http://www.twcenter.net/forums/showthread.php?goto=newpost&t=122162

For instance, if you "toggle_terrain choke", you can see exactly where there are chokepoints on the map, what areas seem passable but game-wise aren't, can investigate what squares AI armies should not be allowed to spawn at, etc. I think it could really be a great tool for you.

This looks like it might be fantastically useful--thanks. I un-installed MTW2 out of frustration at not being able to fix 5-6 of the last map problems I had on the vanilla map. This made me re-install to try again :)

[nikolai1962]

Recap

1. One set of AI pathing problems is caused by what I'll call "movement potential". A map with lots of clear tiles and move points set to be high will have a high movement potential. A map with lots of obstacles , high-cost terrain, and move points set low has a low movement potential. So either increasing movement points or reducing the complexity of the map reduces AI movement problems.

Increasing move points slows the AI turn. Controlling the total number of AIs via agent limits and recruitment can compensate for this. If the slower turn is caused by the AI not being passive anymore because half their armies are stuck then it is well worth it imo.

(Agents can cause movement problems too so having limits is a good thing anyway. Also they need less armies when half of them aren't stuck.)

~~~

2. The AI navigates multiple regions by waypoints from region centre to region centre. This includes attacking an adjacent region. They need to have a path to the region centre first, then they path to attack the city itself.

They don't travel to the exact region centre, only to where they have a clear path within a certain distance (possibly one turn's move away). They only attack a target city in the final region after they have completed that step. The pathing doesn't seem to go through a city's ZOC. So if the path to a region centre goes through a choke point that is blocked by a city's ZOC then the AI army stalls.

(Signiferone's post about toggle_terrain should help immensely with this.)

One side-effect of this is that the cities of coastal regions should never be one tile away from the coast. If an AI army lands orthogonally adjacent to the city then it will have all it's movement options blocked by the city's ZOC. They should be on the coast of more than one tile away.

~~~

3. A perfectly working map requires all regions to follow the rule below:

The fastest path from any tile in a region to any other tile in that region should be completely contained within that region.

I think this is the mathematical equivalent of being "convex" in the context of variable movement cost.

It is possible to do but it takes forever and i wouldn't reccommend it as it doesn't in itself fix all the problems as most are caused by 1) and 2). The most likely routes between two adjacent regions should follow this rule.

~~~

4. I think the map.rwn generates and contains pathing info to help speed the AI turn. Any pathing error contained in the map can then find it's way into the map.rwn and cause odd movement problems in the game, sometimes in unrelated areas of the map.

If you are working on a map's path-finding, and a section of the map that was working, suddenly stops working after an edit in a different area of a map, then it is a bad idea to go back and re-edit the previously working area--just carry on with each area of the map in turn. When a map starts to work perfectly it will happen all at once. (I've only achieved this with a non-simplified map once, the vanilla rtw map, as I usually give up in a fit of frustration but it is possible.)

~~~

5. Some AI stalls happen after a battle. This either only happens to an AI army that has orders to attack a city or is very rare for an AI army that doesn't have orders to attack a city. It happens most often after an AI army retreats from a failed siege assault. This problem almost completely stops happening on a perfectly working map, but not absolutely. So there is a separate non-pathfinding related aspect to this problem which is probably not solvable by modding.

~~~

Conclusions:

1) Increase movement points.

2) Watch early AI expansion for regions the AI gets stuck on. Check out the most likely route between the sentry tile of the start region to the estimated centre tile of the target region and from there to the sentry tile of the target city. Make sure the path is contained within the two regions and doesn't have to cross a third mutually adjacent region, and that the path isn't blocked by the target city's ZOC blocking a choke-point.

3) Some AI path-finding problems aren't fixed by doing those two things, most of the remainder can be fixed after a huge amount of map editing, a small number seem insoluble whatever you try. For these cases it is a lot easier to just re-arrange start positions so that a faction holds the problem city at the start and/or add new regions to bring the distance between cities in a problem area to within one turn of movement. The aim here not being to create a perfect map but just to get the AI's early expansion working better so they are less passive.

4) Some other stuff I'll mention in the other, non-pathfinding AI thread.

[nikolai1962]

Something I forgot to mention...

When I did my google-fest into path-finding there was a mention that games sometimes don't count impassable terrain as impassable during the path-finding sweep. Forgotten the reason why but IIRC it was to help with puter resources or something if instead they just give impassable terrain a high movement cost. Under normal circumstances this would be fine as the path-finding would then avoid those paths but it struck me as maybe being a cause for one particular "movement potential" realated glitch.

This glitch is when an AI is trying to move to a target and has a long *but narrow* stretch of perpendicular impassable terrain and the AI gets stuck on the wrong side of it with their target city very close in a straight line but very far if the AI goes round the obstacle e.g an AI army from a city to the north heading to a city directly south but with a long but narrow range of east-west mountains in the way. If the game did use the system of giving high movement cost to impassable terrain in the path-finding sweep, then this might explain this problem of AI armies getting stuck on the wrong side of the obstacle. The path-finding code would come back with the best path being through the impassable terrain but when the AI tried to move the normal movement code would say no way forward.

A possible solution in this case would be to make sure the terrain along the "going round the obstacle" path was low-cost terrain and making the impassable barrier thicker i.e 2-3 tiles of mountain/forest instead of one. Haven't tested this theory as it was more of a RTW problem but i think it is likely to work.

[SigniferOne]

Well, should be easy to test -- make a big stack, create a big cliff, impassable, and make an enemy target on the other side of it (a weak army or an empty city).

[nikolai1962]

Well, should be easy to test -- make a big stack, create a big cliff, impassable, and make an enemy target on the other side of it (a weak army or an empty city).

Yeah, it's more of a RTW problem though and I've quit testing occult map stuff now on principle as it always gets me too angry at the game :furious3:

From now on I'm just sticking with what I need to do to get the early AI expansion going well and the recapped rules are working fine for that so far. Bit too well as the game seems to crash when an AI faction gets 45 regions. Only tested it that far once though so maybe it was something else.

[nikolai1962]

Orthogonal paths.

Pretty obvious now i'm using the toggle_terrain command-- the AI doesn't like them pesky diagonals. Easy to spot and fix with toggle_terrain choke. Kill em all :)

Got the modded vanilla map working pretty well now. If i can extract all my other changes and just leave the map with the edits and added regions I might try and upload it somewhere.

[SigniferOne]

Wait could you write a little more about how toggle_terrain choke helped with this problem? Also, re-reading the orthogonal problem above still didn't make it clear to me but I'll try to think about it more...

[nikolai1962]

It's simply that the path-finding doesn't like diagonal paths (imo). Not sure if it messes it up directly or causes it to try and find a non-diagonal route which leads it into problems. If possible you want every path on the map as a neat orthogonal route with no diagonals.

Using toggle_terrain choke helps you get away from seeing the map as a seamless whole just by showings you the tiles clearly, (and the impassable terrain that creates the diagonals). So it helps by letting you see what the game is using underneath the pretty but illusionary surface of the map.

These diagonals I'm talking about include those created by an AI trying to avoid a city's ZOC. The last bit isn't actually possible everywhere on the vanilla map as some regions there isn't anywhere to place the city where it doesn't cause a block in one direction or another, but the more diagonals you get rid of then the pathing gets noticably better. It's not dramatic but it's noticeable.

[nikolai1962]

Thanks to TosaInu I uploaded an edited vanilla map wrapped up in mod form. I extracted as much of my other changes as possible to leave it as much like vanilla as I could to give a reasonable comparison. Didn't want to redo my modded strat file though so all the factions start off in the red which slows em a bit but never mind.

Says in the enclosed readme that 60% of the pathing problems were fixed, not so, meant to say 60% of the *starting* problems were fixed. (Even that's not really true as i keep seeing new ones now i'm finally getting to look at the campaign AI.) Will fix more in batches from time to time.

Might be of interest to someone :)

(Removed link temporarily as I've made some progress in my diplomacy AI and I'm thinking of uploading the current WIP version of the full MapMod in the hope of some feedback on how well it works--will add new link back when i get it)

[SigniferOne]

Definitely Nikolai, this will prove most excellent to our mod, thanks a lot!

[nikolai1962]

Naval Landings

Made a few of these by trial and error on both the RTW and MTW maps and been thinking back to what i did looking for a pattern. (Creating them by the trial and error method being a total pain.)

I'm thinking the pathing probably works the same way as the rest does but the start point isn't likely to be the town so it's probably the port. (I've definitely made some just by randomly moving the port.)

Monkwarrior on the RTW version of this thread noticed that naval landings seemed to be between the closest land in the x,y direction.

So if you want to create a particular naval path from one region to another then it might be you'd want to move the port in the start region to point at the target region, see if the target region is the closest land in an x,y direction, then see if the landing points have a clear path to the target city (or target region centre) in the usual way i.e avoiding obstacles and ZOC.

Dunno. Might work.

Not gonna test the theory out myself as it will remind me too much of all the hours spent on my perfect RTW map that i deleted by accident :embarassed:

But the theory would fit most of my map observations (with the usual caveat that none of my observations have been 100% consistent).

[CavalryCmdr]

Not really my specialty, but I've noticed that (using the vanilla map) Russia has a hard time 'finding' some of the bigger regions and Egypt has a hard time 'finding' Jadda, yet the Moors will jump at Timbucktu and Arguin.

I dont know if this is related to the whole convex-concave thing or not but..

In the descr_regions.txt arguin has arguin as a resource. Like many others this resourse appears not to be used. There is only one posible path there, and it dose not cross, nor approach the region center, yet the Moors shoot for it right from the word go.

[nikolai1962]

Yeah, how impassable terrain affects the "region centre" idea is still a mystery to me. Interesting point about the arguin resource. Noticed it but hadn't given it any thought.

[nikolai1962]

The position of a region's port determines the rough direction it looks for naval expansion targets e.g move the naples port to the coast near naples and sicily doesn't land at durazzo any more.

Naval landings are however also *very* heavily influenced by the invade settings in the campaign AI file. You can make them land further or shorter distances by changing the invade priority.

Most of the roughly 50% unfixable "path-finding" problems look like they are also related to the campaign AI.

See the campaign AI thread for gradually explored details :dizzy2:

[Bravedude]

So an improved AI (such as Ultimate AI 1.6?) along with your all of your tips and suggestions for improving the path finding would eliminate all AI army movement problems and make the game as challenging as it should be or greater?

[nikolai1962]

Very belated reply to Bravedude as I got sick of map modding again and uninstalled TW again :)

The answer is yes. The AI is much better when it is moving smoothly and combined with the potential for better campaign AI with MTW2 you at least have a chance at creating a challenging game without resorting to just giving the AI lots of money and endless stacks.


Final Recap

Missed the battles so had to re-install again to try some mods. Usual frustration at seeing the AI get stuck so had another attempt to get to the bottom of it with fresh eyes.

Option 1.

Final theory is the map is a collection of data and exists as a whole. The "map" data is all connected and effects every other part of the map. It's not like separate modular chunks. If the data isn't perfectly formed then you get a lot of path-finding errors between particular regions and the error doesn't neccessarily relate to anything specific about that path. A good 40-50% of the places where an AI army gets stuck when moving to attack a target settlement the stack will stall at some point, more than one, but less than two turns moves away. The path to the target may be complex or completely open, makes no difference.

These all disappear when you have what I've been calling a perfectly "convex" map. In terms of a normal TW map I believe the definition of this is where:

The fastest path between any tile in a region and any other tile in a region is completely contained within that region.

The only way to get near-perfect AI pathing is if you do this. It is possible but very time-consuming, increasing exponentially with the number of regions. I personally don't think I could stand doing it again with anything bigger than something like the RTR Iberian conflict map with 20-ish regions.

However you can get a much improved and just about bearable (to me) AI movement...


Option 2.

1. There are some (10-20% ish) pathing problems that are related to something specific about the individual path to the target settlement. For example where the AI army is quite close to the target settlement but there is a wide barrier in the way that it has to go round to reach the target. These can be fixed by fairly simple map edits. Problems like this are fairly obvious once you spot them.

2. Orthogonal paths. As mentioned above this helps markedly, it doesn't directly fix the places where the AI gets stuck but it seems to generally improve the AI's overall movement. The scale of improvement is around 10-20%. An example of what I mean is I had the vanilla MTW map set up so that the factions only attacked rebel regions and I'd test how many turns it took for a faction to get to 50 regions. With the vanilla map it was roughly around 120 turns and with the edited map it was around 100. This didn't cure the problem I was trying to fix of specific factions being crippled by early pathing problems but it has a generally beneficial effect.

Roads will only form along orthogonal paths so this effect may simply be that making everything orthogonal means the game gets to pick the most optimal road routes.

The "toggle_terrain choke" command makes this process infinitally easier though it is still a bit of a chore on a large map. The benefit is incremental though so you can see an improvement even after only doing part of the map, whereas the "convex" thing you only really see the improvement right at the end.

***3***. The AI likes to have one general per city plus a few spares. Captains get promoted when the faction has a spare slot. For the first time I noticed that captain-led armies that have been assigned to attack a settlement seem to get priority for this. What this means is *eventually* all AI armies that are stuck en route to attacking a settlement will have a general. This "eventually" may be a very long time if the faction has a surplus of generals when the captain stack is assigned but on average over a whole game this is very significant. What it means is a trait based solution becomes vastly more useful than I'd previously thought.

Create a "MoveFix" trait that gives a move bonus up to 100%. I split mine into five levels with 20% each. Trigger it for AI only on CharacterTurnEnd when they are out of a settlement with 100% movement left. Clear it on CharacterTurnEnd after they've moved. This will fix all the 40-50% of path-finding problems that seem to have no obvious cause and which always take the form of the AI army being stuck more than one but less than two turns away from the target, at least all those where the army is general led, which as I say, now looks like it will be a much larger percentage over the course of a whole game.

This is a great fix in terms of cost-benefit as it takes almost no time to do.

Only tried it so far in a test situation with just one faction and an empty map so not sure yet how it will work out in a complicated mod but shall see. Might be just enough to make the game bearable again :)

4. Few minor things which also affect AI expansion that I noticed again:

Brigands should be semi-frequent but the brigand units should be very weak imo.
Pirates should be semi-rare and the individual pirate units should be very weak (*greatly* affects naval expansion).
Flash floods should be removed as they seem to mess up the movement permanently.


edit: forgot a couple of obvious things.
Increasing base move points helps but if, like me, you don't like seeing the armies whizz around too fast then this trait solution is potentially a boon as it goes after it's used.

Make sure the AI builds roads as a priority - I've forgotten which one it is now, I think it's the "trader" one. I set all of them to whichever one it is.

[irishron2004]

Thank you, Nikolai1962 and SigniferOne. This is part of the info I was searching for and a very timely post. Probably won't allow it but reps to both.