Game AI stuff (1.5)

[nikolai1962]

this will be the new "update" post as i think i've found the fastest way to fix AI path finding with the least effort

so ignore all the stuff i said previously, instead...

New Sequence

1. start up the game/mod you want to map-check with each faction in turn

2. bring up the regions overlay with the "toggle_terrain region" console command

3. for each settlement select a unit in the settlement and use the right mouse click to show the fastest path to the settlement in each *adjacent* region

nb "adjacent" is defined as two regions having adjacent *passable* terrain. if *all* the adjacent tiles between two regions are impassable then the game *generally* seems to mark the regions as non-adjacent. there may be occasional exceptions to this where something has gone wrong but it is generally true.

4. note the cases where the fastest path between the settlements of two adjacent regions clips a third region (as it does it the above case of Sardis-Galatia) - these all need to be fixed as these are the primary cause of the AI path finding going wrong

5. also note the cases where the path finding arrow runs out before it reaches the target settlement - I think this can cause problems *sometimes* for an as-yet unfigured out reason and it's worth considering trying to fix them but not as a priority



6. I said previously to fix unreachable tiles as a first step but as you sometimes change what tiles are unreachable when you change region borders this step can be left to the end.

7. only *after* fixing all of the issues found in step (4) and step (6) start the game up as a remote faction and turtle (or use the -ai command) and watch the AI move looking for additional glitches

(or don't, just assume this process fixed the majority of cases and play short campaigns with each faction for fun and see if you notice any additional AI glitches while you're playing)

This sequence is dramatically faster than my previous attempts.

nb I'm not saying the game does path find like this (fastest path from settlement to settlement). I'm saying this process will highlight places in the game where the AI will often get stuck.

#

Reasoning

the underlying principle behind this sequence is the same; it's simply much more efficient

1) the path finding works (as shown by the player's path finding arrow)

2) path finding has a computational load

3) the game reduces the load by
a) limiting the number of path finding iterations allowed (as shown by the path finding arrow stopping after a certain distance)
b) using region to region pathing first and then unit to target pathing when close enough

4) path finding glitches occur when:
a) a unit in region A tries to path to a target in region A but the fastest path clips a different region
b) a unit in region A tries to path to a target in an adjacent region B but the fastest path clips through a third region C
c) *maybe* when the game's region adjacency database gets messed up somehow
d) temporary e.g. enemy unit blocks a valid path and the alternative path glitches

5) the perfect solution is making the map 100% "convex" which in this context means

the fastest path from any passable tile in a region to any other passable tile in the region is completely contained within that region

however this is very difficult and time consuming and what this new sequence does is recognize the AI uses some paths e.g. the ones between settlements, an order of magnitude more often than others and so glitches there are much more critical - so doing it this way round means you can fix 80% of the problems with maybe 20% or less of total necessary effort and far less time.

#

As I'm trying to find the fastest way to do this I moth balled the vanilla map editing i've been working on and started again from scratch on the vanilla map to compare speeds and this method is dramatically better.

On the vanilla map i found 26 region-pairs where the pathing broke the rule (i may have missed some).

(I knew almost all of them anyway from watching the AI get stuck but this method is much faster.)

There's also at least a dozen cases of the settlements being too far apart for the path finding arrow which may or may not be important and i'll worry about later. (I think it's worth having the list so if you notice something odd happening that has no region-clipping explanation then maybe it's connected to this.)

I'll be posting up how i fixed some of the 26 region-clipping cases from the vanilla map (although i've mentioned some of them before on this and other threads).

[nikolai1962]

Case Study 22, Sardis-Galatia

with the region overlay on you can see the settlement to settlement path clips the Pergamon region



switch to the "toggle_terrain choke" overlay to see if there is an easy fix moving region borders or rivers/fords



and if not try "toggle_terrain tiletype" to see if there is an easy fix through editing terrain type.



In this case the easiest solution is moving the Pergamon border back a couple of rows.



nb when you change anything you need to check it hasn't caused new problems among the regions adjacent to the one you edited.

#

For a long time I thought diagonals were a problem for the game's path finding and spent hours making all the paths orthogonal but that was wrong - the problem is diagonals near region borders are often the place where this region clipping problem occurs. Anywhere on the map where 3 or 4 regions join at a single point (as in this case) are prime candidates for this path finding bug.

This type of glitch can be 100% prevented by placing an impassable tile in the right spot at the junction of 3+ regions however I'd advise you do it at the end as there's a lot of places like this and the right spot depends on where the region borders are and you'll likely be changing region borders a lot.

I did it for this case as an example (if you can see the dense forest tile).



A lot of the 26 cases I've spotted from the vanilla map are a simple as this to fix (although not all).

[nikolai1962]

Case Study 23, Cappadocia-Galatia

fastest path clips into the Cilicia region



same thing looking at in with the choke overlay



bunch of ways to fix it but the simplest was nudging the upper ford down a few tiles

[ReluctantSamurai]

so ignore all the stuff i said previously

The design team must have REALLY been pressed for time to have missed such simple fixes as these

[nikolai1962]

@ReluctantSamurai

Yeah, I guess the people doing it were like me and either didn't know or didn't fully understand how the pathing worked so were operating on guesswork and trial and error.

#

Case Study 19, Alexandria-Petra

fastest path clips into Judea



with choke you can see an impassable tile - maybe an attempt to fix a problem?



the AI doesn't always get stuck here, it depends on which army gets assigned to attack Petra and where it starts from but when they do the army is generally just before the diagonal clipping move



moving the impassable tile down one row forces the roads to Judea and Petra to split sooner and prevents that move

[nikolai1962]

total number of region pairs i've found with clipping is now 30, done most of the simple ones, leaving the harder ones to last

Case Study 29, Salona-Patavium

slight clipping



easily fixed by changing ownership of a couple of tiles from Illyria to Salmatia



not a big deal but it makes the silver look like it's in Dalmatia so nudge that up one tile in descr_strat (moving resources in descr_strat when you change region borders is one of the few non-map file changes needed).

#

Case Study 30, Epirus-Illyria

Epirus is adjacent to Illyria (the mouse cursor is over the mountain pass that makes them adjacent) but the fastest path is through Dalmatia.



looking at the map in choke view there's no obvious way to change the path so need to change the region borders instead



I could block that pass (thus making Epirus-Illyria non-adjacent) by moving the Macedonia border to the left or Dalmatia to the right or I could move Illyria down or Epirus up so all the tiles along the fastest path are contained within Epirus-Illyria (so no region clipping) however wherever possible I like to make the region shape historical so in this case after looking at a few old maps I moved the Epirus border up so the fastest path is contained within Epirus.



(Illyria lost an olive oil resource so i should move that)

[nikolai1962]

still putting off doing the bigger changes in case it messes everything up so thought i'd look at one of the cases where settlements are too far apart for the right-click path finding (which may not be important but... maybe it is)

anyway Tingi->Cirta is fine



but oddly enough Cirta-Tingi is one tile short



if you build roads just in the Tingi region then path finding from Cirta-Tingi can reach substantially past Tingi



but if you build roads only in Cirta region the maximum path finding range is now actually a tile shorter



the fastest path goes around the nearby river



which if you look at it in choke view is a diagonal



and roads won't form if there's a diagonal, only orthogonally, which forces the road to Tingi to detour around to the ford.

Adding a ford closer to the direct path brings the Cirta-Tingi path within path finding range



alternatively, extending the Cirta region to the left brings the Cirta-Tingi path within range of the right-click pathing arrow if Cirta builds roads (as in this case more of the fastest path is along roads within Cirta region).



As the game often seems to add the "wild animal" trade resource in threes and the new region border at the river is the historical border between Mauretania-Tingitana and Mauretania-Caesariensis my guess is this is how the region was originally and it was changed to try and fix something (as when you're map editing by guesswork it's very easy to fix one problem and create a new one at the same time). So in this case I'll leave the wild animals resources in the Cirta region.

#

So what does all this suggest?

1) the CA dude way back when said the path finding could sometimes go wrong if settlements were more than around 50 tiles apart. I think this shows it's not 50 tiles but some amount of path finding iterations that on average comes to around 50 tiles. In some cases it might be less.

2) movement costs may matter indirectly as finding the fastest path through difficult but not impassable terrain is an obstacle also, just not as much of one as impassable terrain - so roads and difficult terrain may have an effect there

3) also when roads form along the fastest path between two regions they reinforce convexity but when they don't, they weaken it (which happens a lot as the game likes to average out multiple roads). This may not matter in most cases but it might occasionally thus forcing roads to follow the fastest path probably helps sometimes (but maybe only occasionally).

4) From observing I used to think the path finding had a problem with diagonals generally but that's not the case. Diagonals near region borders can create paths which lead to region-clipping and diagonals elsewhere can block optimal road formation (which can occasionally lead to region clipping) but otherwise the path finding handles diagonals fine. As diagonals can prevent roads forming this means deliberately adding diagonals to force roads to go where you want might actually be a useful tool.

5) *if* settlements being too far apart can cause glitches in the formation of the map.rwn file then roads bringing settlements within range during the game won't help but if it only causes glitches during the game then settlements being close enough after roads are built may be good enough.

(I won't do it on the base version of the map as I want it to be as vanilla as possible but in the future I think i will eventually add regions where they bring settlements within range of each adjacent region, just in case it helps.)

6) a lot of modders deliberately made some settlements very far apart in the hope it would stop the AI expanding in a direction they didn't want but in my experience it mostly doesn't work and often it just makes the AI waste even more resources sending multiple armies crawling slowly over 100 tiles of desert. In cases where you don't want to use impassable terrain to block this I'm thinking a better solution may be the exact opposite and give the unwanted direction a close by region with very high unrest instead. So instead of a dozen armies crawling over the desert towards a very distant settlement the AI just has one army constantly retaking the same close by settlement.

Just a thought.

[nikolai1962]

Case Study 24, 25, 26, Armenia->Pontus, Armenia->Cappadocia, Armenia-Media

24: Armenia-Pontus are adjacent by one route but the fastest path clips the Colchis region



25: Armenia-Cappadocia is too far to be sure what the fastest path is - it might be like this which would be okay



or it might be like this which would clip Pontus



if we look at the pathing arrow from Armenia to the ford



and to an adjacent tile on the other route



we can see both routes have very similar costs in pathing terms with the coastal route just pipping it.

looking at the tiletype overlay we can see why - the coastal route is longer but has mostly open tiles while the inland route is shorter but mostly hills.



so we could change a few tiles along the inland route from hills to fertile tiles to make that route the fastest but there might be another way which could fix both armenia-pontus and armenia-cappadocia at the same time.

if we look at the current Armenia-Cappadocia path we can see it goes a long way round



whereas the route near Pontus looks a lot shorter



however that route is currently blocked by the river and also, as Armenia is already adjacent to Cappadocia by another route, then if the fastest Armenia->Cappadocia path clipped through Pontus that would glitch the pathing.

if i push the cappadocia region up a little so armenia is no longer adjacent to pontus (except via impassable mountain tiles) then the game won't mind pathing to pontus via cappadocia and at the same time pushing the river near pontus up a tile creates a more direct armenia-cappadocia path which looks like it might be the fastest.

which seems to work (the distance is still too far for the pathing arrow to get the whole path but when cappadocia builds roads it's long enough for the cappadocia-armenia pathing)



and the Pontus->Armenia pathing arrow is also within range



but not Armenia->Cappadocia when only Armenia has roads



however Armenia->Cappadocia does come within range when both regions have roads thus confirming it's both the fastest path and that the game knows it



#

26: Armenia-Media

Armenia is adjacent to Media by this route



but the fastest path is much more direct and clips through Atropatene



one way to fix this might be to give the chunk of Media between the two rivers to Atropaten (light blue) so armenia-media are no longer adjacent.

this would make hatra-atropatene regions adjacent and the path between those seems okay if Armenia loses a tile or two.



it would also make atropatene-babylon adjacent but as it's too far for the pathing arrow it's hard to say if the fastest path would be this



which would be okay, or this



which would cross through media and break the region clipping rule.

After editing the region it seems that without roads the babylon-atropatene path would cross media (possibly causing the AI to glitch)



with roads in Media this path is reinforced (and as roads have increased the range of the pathing arrow so it now reaches all the way to Phraaspa we can be sure it's the actual fastest path)



however with roads in Atropatene it seems the fastest path switches to go through Atropatene which should be fine



so the Babylon-Phraaspa pathing might not cause a problem or if it does it might fix itself when Phraaspa builds roads but if it does turn out to cause a problem i can just remove the bridge between Atropatene and Babylon so the regions no longer count as adjacent.

I wouldn't usually like to remove a path between regions to fix a problem but I don't mind in this case as the Persian Royal Road (in terms of RTW regions) went Babylon-Hatra-Cappadocia so Hatra as a crossroads region seems appropriate.

#

After some testing this seems to work well. Generally changing a bunch of regions at once leads to new glitches somewhere but if so I haven't spotted them yet.

#

Anyway hopefully these case studies will prove useful to someone. I won't go through all the 30 or so i noticed on the vanilla map as it'll mostly be repeating myself.

The general pattern is the changes needed are either a) small edits involving: fords, river placement, a few region ownership tiles or placing an impassable tile or two or b) a rubik's cube type deal where you have to juggle a bunch of regions at once to ensure only the ones with valid fastest paths are adjacent in game terms (i.e. having a shared border with passable terrain).