Game AI stuff (1.5)

[nikolai1962]

I'm gradually getting psyched up to delve into RTW map-making/editing

It's actually semi-fun now I've figured it out better. Originally I didn't know about toggle_terrain or the convexity issue so i did it all by trial and error and even a small map was a total nightmare but now it's not so bad.

I'm a short way away from finishing up on the vanilla map (as much as i can without adding extra regions) and after I've stashed that version somewhere safe so i never have to do this again I want to try a few separate experiments on a copy to see how best to deal with very mountainous regions and then after that look at the BI and MTW2 maps to see if they are equally quick (at least relative to last time).

...are all map editing commands done through the console, or are there third party tools to use?

the commands which show different map overlays (toggle_terrain region/tiletype/choke etc) are all console commands.

map editing itself is done by editing the map files: map_features.tga, map_regions.tga and map_groundtypes.tga. I use gimp for this. There may be other useful tools but if there are I should probably know but don't :)

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