Page 3 of 5 FirstFirst 12345 LastLast
Results 61 to 90 of 121

Thread: Game AI stuff (1.5)

  1. #61

    Default Re: Game AI stuff (1.5)

    I must admit i was pretty surprised to see the MTW map was so full of the same problems and to see the AI still stalling after retreats etc. As you say some of these flaws (like Tribus Sakae) should be so obvious it's baffling they weren't looked at. I guess it all comes down to the strategic aspect of the TW games being designed more as battle generators than a strategy game. It seems it is not a priority compared to the tactical side.

    Admittedly it is a an uphill struggle to turn the strategy map side of the game into something good.
    It's not a map.

  2. #62
    CeltiberoRamiroI Member Monkwarrior's Avatar
    Join Date
    Apr 2004
    Location
    Salduie/Caesaraugusta/ Sarakusta/Saragossa
    Posts
    828

    Default Re: Game AI stuff (1.5)

    Only a brief comment about the AI behaviour in campaign.

    We have observed (disappointed I must say ) that the behavior of the same factions, with the same core attitudes, the same diplomatic stances, the same armies, the same regions, etc, is completely different when run over RTW engine or when run with BI.exe.

    We had optimized the AI behavior en different provincial campaigns, to adjust it to history (up to the possibilities of the engine), but all this work is completely useless if we use BI.exe.

  3. #63
    Finder of Little Oddities Senior Member Makanyane's Avatar
    Join Date
    Jan 2006
    Posts
    2,220

    Default Re: Game AI stuff (1.5)

    Monkwarrior, that's very interesting to know, I know a lot of people have theories about one .exe being better but hadn't seen much in the way of examples of differences. Is either .exe behaving more logically in relation to diplomacy or campaign strategy? Or do you think it is that things have been done in the .exe for the path finding for armies that have lead to the differences in the way your campaign plays out?

    Only thing I've noticed as distinct difference in BI is that rebels tend to move to 'capture' watchtowers, whereas in RTW I think they stand on road more - if that sort of thing changed there could well be other 'priority' changes for AI movements.

    If nikolai still has some of earlier test set-ups maybe we could persuade him to lend them out so we can see if they behave same way under RTW and BI?
    Not used mods before? Looking for something small and fun?!
    Download the:

  4. #64
    CeltiberoRamiroI Member Monkwarrior's Avatar
    Join Date
    Apr 2004
    Location
    Salduie/Caesaraugusta/ Sarakusta/Saragossa
    Posts
    828

    Default Re: Game AI stuff (1.5)

    Quote Originally Posted by Makanyane
    Monkwarrior, that's very interesting to know, I know a lot of people have theories about one .exe being better but hadn't seen much in the way of examples of differences. Is either .exe behaving more logically in relation to diplomacy or campaign strategy? Or do you think it is that things have been done in the .exe for the path finding for armies that have lead to the differences in the way your campaign plays out?

    Only thing I've noticed as distinct difference in BI is that rebels tend to move to 'capture' watchtowers, whereas in RTW I think they stand on road more - if that sort of thing changed there could well be other 'priority' changes for AI movements.

    If nikolai still has some of earlier test set-ups maybe we could persuade him to lend them out so we can see if they behave same way under RTW and BI?
    Well, it is difficult to answer to such questions. I don't know if it is more logical or not, but it seems to me that in BI the AI has different "triggers" or "objectives".
    As I explained some posts before, we wanted to simulate the real expansion of the historical factions. In that way we stablished "barriers" made by superfactions or faction (not slave) limits. The landings and troop transports by sea were also triggered by opening a second land expansion front, and hiding the corresponding culture in the surrounding regions.

    But with BI the same configuration doesn't produce the same results. Now the second land front is not interesting for the AI, and it seems more interested in close targets, even in case they are separated by sea. Even the faction parameters (bureaucrat and so on) don't seem to code the same behavior.

    Sorry but we have not studied more systemathically the AI. Just some observations to see that our previous work was useless in BI.

  5. #65

    Default Re: Game AI stuff (1.5)

    We had optimized the AI behavior en different provincial campaigns, to adjust it to history (up to the possibilities of the engine), but all this work is completely useless if we use BI.exe.
    Ouch.


    If nikolai still has some of earlier test set-ups maybe we could persuade him to lend them out so we can see if they behave same way under RTW and BI?
    I lost my beautiful little test map by accidental deletion many moons ago sadly and i could never bring myself to make another one. Tragic really as it was so useful. I should have uploaded it somewhere before i trashed it.


    I don't know if it is more logical or not, but it seems to me that in BI the AI has different "triggers" or "objectives".
    I got MTW2 recently and have been looking at how the AI is coded. The AI has a list of potential attack and defend responses it calculates for each opposing faction. Seems quite possible the list was revised for BI.

    and it seems more interested in close targets, even in case they are separated by sea
    Sounds like they fixed the naval path-finding a bit too which would effect it.


    Can easily block factions in now with the AI modding in MTW2. Could create a blocking "northern roman" faction with a passive AI and the "main roman" faction could be set to never attack it. No roman units in MTW2 though :((
    It's not a map.

  6. #66

    Default Re: Game AI stuff (1.5)

    I think the work you guys are doing here is tremendous and very noteworthy. Any chance you could start condensing it, because it is very hard to follow unless you were following the thread from the beginning.


    thanks, and keep up the good work,
    RM3

  7. #67

    Default Re: Game AI stuff (1.5)

    New thing proving to be significant with AI pathfinding. If a stack in region A wants to attack a target in adjacent region B but the fastest route for the stack takes it through a mutually adjacent region C then it gets stuck.



    Screenshot shows an example (using MTW2 but i'll bet it is the same in RTW). The old route in yellow was the fastest path for a stack near Budapest that had Zagreb as it's target. As armies can go diagonal but roads can't, the path cut across the corner of the vienna region on the way. This caused that particular stack to be stuck and it didn't move until someone else took zagreb and it got it's orders cancelled. By removing the ford across the river the new fastest route followed the road and didn't cut across the Vienna region and the stack started moving to zagreb on it's first turn thereafter.

    So far it is proving to be a major cause of AI stacks not moving on game start.


    (edit: I think this may be why making region boundaries follow the natural obstacles often, but not always, improves the path-finding.)

    ~~~

    I think the work you guys are doing here is tremendous and very noteworthy. Any chance you could start condensing it, because it is very hard to follow unless you were following the thread from the beginning.
    I will eventually. Though I'm pretty sure now of a lot of the general mechanics of the AI (mostly confirmed by the newly moddable bits in MTW2) I'm still not 100% about the path-finding. The "convex" regions only fixes about a 1/3 of the AI movement problems in a map. Currently this new one is looking like it might be behind another big chunk. Some bits like the retreat bug you can't mod out but when i'm nearer to 80% sure of the path-finding probs i'll try and condense it.


    ~~~

    Naval landings.

    Comment from Dimebagho on another thread makes me think the "convex" problem may apply to the sea region too. From testing with MTW2 i don't think the code is much different and i suspect the big improvement in naval AI in MTW2 is *possibly* the result of having seperate sea regions for seas that don't connect e.g the red sea. Haven't tried it yet though.


    edit: this is the thread

    https://forums.totalwar.org/vb/showt...01#post1469701


    ~~~

    One thing confirmed from the MTW2 AI files is that relative military strength, including that of allies, is hugely significant in determining the AI's actions towards other players and diplomacy is pretty much all about buying factions off so they leave you alone temporarily and very little else. Which is ok as long as you know that's how it is designed i guess.

    Also the AI is coded to hate the human more than the other AI factions. Though you can mod that out now.
    Last edited by nikolai1962; 03-19-2007 at 03:51.
    It's not a map.

  8. #68

    Default Re: Game AI stuff (1.5)

    Remembered something I always forget which is that one way to make regions non-attackable by the AI is to completly surround the region's city with hills. This has the same effect when partial i.e if the only route from region A to the city of region B is completely blocked by hill tiles. (Stops scotland attacking york by land in MTW2 for example).

    Armed with these three pieces of the jigsaw,

    1) Convex regions
    2) Pathing from one adjacent region to another through a *mutually* adjacent region.
    3) Hill blocking

    I started editing the vanilla MTW2 map again from scratch. This time instead of previous method of fixing the non-convex bits followed by loads of trial and error editing I just looked for those three possible causes for each of the places where the AI gets stuck in the early game vs rebel regions. Between them they were the cause of 2/3 to 3/4 of the problems and the process was *vastly* quicker than the previous method.

    Still a few places where the cause is not apparent so still at least one more piece of the jigsaw to find. However, apart from the times the retreat bug bites the AI is eating up the rebs much better.

    ~~~

    Number 2) is so far proving to be the biggest cause of the path-finding probs. The non-convex regions seem more inclined to make the AI take weird routes from A to B rather than to make the AI stacks stall directly. (Though the weird paths often indirectly cause the stall, sometimes it is the other way round and a direct path causes it. Knowing the actual cause now means these cases can be fixed.)
    It's not a map.

  9. #69

    Default Re: Game AI stuff (1.5)

    1) Convex regions
    2) Pathing from one adjacent region to another through a *mutually* adjacent region.
    3) Hill blocking
    Spoke too soon. This isn't directly true as none of these will *neccessarily* fix the path-finding problems, although they all have seemingly fixed problems in the past.

    The map isn't a map it's a collection of x,y co-ordinates arbitrarily grouped together into regions. This data then gets applied to an algorithm which will produce viable pathways *if* all the data is properly formed according to the rules of the algorithm. Whatever those rules may be.

    Any change to the map will change the potential pathways.

    The *regions* data aren't independent of each other and a change in one part of the map may have an odd side-effect elsewhwere (literally you can change the border of yerevan and an army in scotland that previously moved on game start is suddenly stuck again).

    Even if the three rules above are correct then changing the map to conform to those rules can actually make the path-finding worse as the map will already contain workaround fixes for the lack of data conformity. That is, if the original map was made without conforming to whatever the rules are then the original map-editor will have made trial and error changes to get the AI moving. Those original *fixes* can then become new problems to find when you make the data conform.

    This is very frustrating.
    It's not a map.

  10. #70

    Default Re: Game AI stuff (1.5)

    Back to the drawing board - apologies while i use this thread as a thinking pad :)

    Case Study

    Sticking to one theory at a time - non-convex regions. Just make the map fully convex first before trying out other things.


    Testing with.

    1)All factions set to a created AI profile that only lets them attack rebel regions.
    2)Brigands/pirates greatly reduced.
    3)Starting rebel garrisons removed.
    4)Initial faction standings taken out so AI only dislikes rebels.


    Benchmark - Vanilla map problems.

    (There are more but these were the first i noticed)

    England.
    1) Attacks Caernavon, gets stuck in mountains two tiles away.
    2) Builds army outside nottingham, (hidden in trees), also stuck.
    3) Attack Rennes, if lose and retreat can end up taking a weird path behind Caen and getting stuck behind some forest.


    Scotland.
    1) Northern army takes inverness.
    2) Southern army set to target York but stuck.


    France.

    1) Toulouse army set to target zaragoza but stuck.
    2) None of initial french regions seems to see bordeaux.
    3) Paris/Rheims seem to target Bruges after the initial french targets are taken but stuck.


    Spain

    1) General Vaasco targeting zaragoza but stuck.
    2) Generally target along west coast instead of closer regions - not exactly a problem but odd.


    Portugal.

    Prioritize west coast of europe instead of closer rebel regions.


    HRE

    Bologna stack targeting Florence but stuck (a guess as it doesn't leave city).


    Hungary

    Starting stack targeting Zagreb is stuck.


    Russia

    Starting armies find way to first two targets but new army built in novgorod targets smolensk and stuck.


    (some of these won't happen with rebel garrisons removed - just reminding myself to check later)

    ~~~

    So re-loading vanilla map files and starting again doing only these things.

    1. Making the impassable terrain more blocky. Compacting mountain/dense forest and making the passes through them more distinct. Replacing stray pixels with woods/hills.
    2. Making sure impassable desert and deep ocean don't have traversable terrain buried inside.
    3. Making sure all lakes/internal water is the specific red the game generally uses for such.
    4. Making sure the islands you can't land on are 100% impassable pixels, just in case.
    5. Trying to find and edit all instances of non-convex regions.


    ~~~

    Stage 1.

    Started with scotland and worked across russia, the steppe and back round in a loop to hungary/vienna region - roughly a third of the regions checked. Thought i'd run a quick test to see what had changed so far.


    The Good.

    1) England now fine. Take Caernavon, York with no hitch.
    2) France now sees and takes bruges.
    3) HRE now takes Florence.
    4) Stuck Hungarian army now moves.


    The Bad.

    1) Scotland now completely stuck - both northern and southern armies won't move.
    2) France still can't see Bordeaux or Zaragoza
    3) Spain/Portugal no change
    4) Russia->Smolensk unchanged.
    5) Hungary now can't find Iasi anymore.
    6) New problem - egypt no longer sees Jerusalem
    7) Possible new problem with both breslau and magdeburg - may just be AI has switched priority of taking settlements. Both taken but later and by different factions coming from different directions to vanilla.


    The Oddly

    Hungarian army that used to move from budapest towards zagreb now heads to prague despite mountains in the way. stops then heads for zagreb

    ~~~

    This is the sort of point where before I'd start trying to change other things according to other theories but i'll try and stop mayself until i have a fully convex map. (Assuming i can spot all the non-convex tiles.)

    ~~~

    Notes to self.


    Current thinking vis a vis region interdependency.

    1. Map changes in any region can affect all adjacent land regions - (certain).
    2. The sea confers adjacency when it is working correctly (highly likely to certain).
    3. all region data is inter-related and any data non-conformity anywhere can affect the path-finding in any region (possible).

    possibilities re the sea region conferring adjacency:
    a) shared coastline
    b) shared coastline within certain range
    c) global

    case points
    a) Behaviour of spain/portugal
    b) road network in gaza (sometimes map edits change the roads in gaza to the way they'd be if cairo was a land neighbour but all the cairo-gaza border was impassable, like a river with no fords.)

    ~~~

    New theory.

    Even though armies can move diagonally I think the path-finding only works orthogonally (up-down/left-right)

    So a region with a border like

    MF
    MF
    F

    where M are mountain tiles and F are fertiles tiles may glitch because when the impassable tiles are taken out of the equation you end up with

    XF
    XF
    F

    If the path-finding only works orthogonally this region would then become non-convex.

    (Assuming impassable tiles must be taken out of the equation because of the small unlandable islands.)

    ~~~

    Other theories

    1) Not only must the region be convex but all movement in the region from one tile to another must be within the region. Not as impossible as it may sound).

    2) Movement between two adjacent regions must take place within those two regions. The path must not cross into a mutually adjacent third region.

    ~~~

    PFEs don't occur on a regional basis but on a region to region basis. A PFE is possible between region A and region B while region A to region C is fine.

    PFEs can be uni-directional e.g region A to region B may not work while region B to region A does work.

    (PFE = path-finding error)

    ~~~

    AI stacks don't seem to have problems navigating to settlements within it's own regions.

    ~~~

    Actually three cases of PFE

    1) AI faction sees a region as a neighbour, sets a stack to attack but the stack has a PFE and doesn't move.

    2) AI faction sees a region as a neighbour, sets a stack to attack, the stack moves to the target but gets stuck on a certain tile along the way.

    3) AI faction doesn't seem to see the region as adjacent at all.


    Consequence.

    Areas like central europe with a lot of small regions with a lot of borders suffer from PFEs less because if a region has a PFE with one of its neighbour regions it will be attacked soon enough from another direction. Might be worth breaking up big steppe/desert type regions in cases where they only have one neighbour.

    ~~~

    the distance between the centres of any two adjacent regions should not exceed 50 tiles
    does this mean the distance between settlements or some mathematical centre of the region's tiles. could possibly glitch if shape of region was particularly weird?

    ~~~

    (apologies again - if/when i have this finally figured out i'll make a proper path-finding tutorial)
    Last edited by nikolai1962; 03-26-2007 at 01:55.
    It's not a map.

  11. #71

    Default Re: Game AI stuff (1.5)

    EDIT: deleted wrong info as i re-tested map changes with wrong mod sleeper out of sleepiness. apologies to anyone who i inadvertently misinformed.

    ~~~

    Tip for checking map pathways/convexity etc.

    Double spy movement points, move them to centre of each region then click end turn so you can see the green movement overlay as in the screenie.

    (Turn 10 and all but one of the non-faraway steppe rebel regions gone hehe)

    Last edited by nikolai1962; 03-26-2007 at 19:42.
    It's not a map.

  12. #72
    blaaaaaaaaaarg! Senior Member Lusted's Avatar
    Join Date
    Feb 2005
    Posts
    1,773

    Default Re: Game AI stuff (1.5)

    Any chance of you uploading the fixed map files at some point?

  13. #73

    Default Re: Game AI stuff (1.5)

    Any chance of you uploading the fixed map files at some point?
    Yes, that's definitely the aim but...

    I was hoping no-one had seen the last post before i could change it cos yesterday i sleepily re-tested using the wrong mod folder - so it's not all fixed yet after all - argh.

    Since found a bunch more non-convex tiles that i missed on the first sweep so all is not lost :)

    When i've got it figured out and have fixed files and simple rules to follow then i'll definitely be uploading and tutorializing as i found out from my previous fixed rtw map the game is vastly better when the AI is performing as intended.
    It's not a map.

  14. #74

    Default Re: Game AI stuff (1.5)

    Case Study part 2

    1. Changed a chunk of the non-convex tiles as mentioned above. A quick test showed some definite changes in AI movement.
    2. Found and changed a bunch more which didn't effect things much, at least in the areas i was focused on. Starting to think the convex thing was more of a minor thing than previously. Began making individual fixes for individual region problems.
    3. Noticed i'd missed the non-convex caribbean islands. Changing those seems to have messed up a few of my individual fixes so currently back to original theory.

    -->Non-convex tiles add some kind of distortion into the path-finding algorithm. The distortion may be semi-benign e.g an AI army ordered to attack a settlement to the south but it heads north one turn and then back south again, or it may lead to the AI army being stuck. The non-convexity may not be the specific cause of the stalling--it may be the distorted path breaks some other rule the algorithm uses.<--

    The first bunch of non-convex tiles included most of the big chunks and most of the islands. This seemed to have a noticeable effect.

    The second bunch were mostly small e.g a single tile on the wrong side of a river. These changes didn't seem to have much effect.

    The last bunch were all islands. This seemed to have a noticeable effect.

    Makes me think the distortion is greater when there is a larger gap between the non-continous region tiles. Or possibly the sea has an effect on all regions with a coastline so islands are specifically influential. Hmm.

    ~~~

    Starting again.
    It's not a map.

  15. #75

    Default Re: Game AI stuff (1.5)

    Embarassing thinking aloud when you're wrong. I think wishful thinking and having too many mod folders got the better of me. Fourth attempt making sure *all* non-convex tiles were fixed and *nothing* else changed and it's not the panacea i was hoping for. It does effect path-finding but in small, localized ways and not a general distortion of the algorithm. Bugger.

    Condensed what i think i've learned into a set of guidelines here

    https://forums.totalwar.org/vb/showt...51#post1485851

    I put it in the MTW2 forum as i was using the MTW2 map to test ideas. It's the same in RTW though. The trial and error method of fixing the path-finding is a little easier with the guidelines than just using pure guesswork but it is still a very slow process.

    Far easier to set the movement rate to cover the average distance between two settlements on your map. Trouble is that makes the AI armies look like Rommel. Oh well.
    It's not a map.

  16. #76

    Default Re: Game AI stuff (1.5)

    Place holder type post. I plan on using this post to put some stuff I discover. I will be working on the RTW map, but it wont be as thorough as your research Nikolai


    Silly question, but how do you skip to a certain date?
    Last edited by Roman_Man#3; 03-31-2007 at 05:50.

  17. #77

    Default Re: Game AI stuff (1.5)

    Place holder type post. I plan on using this post to put some stuff I discover. I will be working on the RTW map, but it wont be as thorough as your research Nikolai
    Cool


    Silly question, but how do you skip to a certain date?
    Not sure what you mean. If you mean the start date of the game it is set in the descr_strat file near the top.
    It's not a map.

  18. #78

    Default Re: Game AI stuff (1.5)

    I mean a console command. like

    data -189

    or something like that. To skip to a certain date.

  19. #79

    Default Re: Game AI stuff (1.5)

    I mean a console command. like

    data -189

    or something like that. To skip to a certain date.
    Don't know, sorry.
    It's not a map.

  20. #80
    Finder of Little Oddities Senior Member Makanyane's Avatar
    Join Date
    Jan 2006
    Posts
    2,220

    Default Re: Game AI stuff (1.5)

    @Roman_Man#3 - You can use Epistolary Richards year jump mod - but I think only if you are running under the BI.exe
    https://forums.totalwar.org/vb/showthread.php?t=65109

    He's set up scripts to use the slavs who don't start on map, and Sassanids. I switched it for EoD to use two factions which weren't used in campaign but in descr_strat as dead_until_resurrected (as otherwise it can hang if your faction is fighting Sassanids when it stops). You could try experimenting with it under RTW - scripts are quite short and you only need to change faction names (in scripts and advice / triggers), but I suspect it might need a dead_until_resurrected faction, in which case I'm pretty sure you'd need to run it -mod under bi.exe. If you do that for testing and your mod is designed for RTW you should note what Monkwarrior said about getting completely different results when running RTW mod under BI.

    If you can get it to work for RTW please do report. Btw, I don't know of any way to do it under console command or -ai.
    Last edited by Makanyane; 04-01-2007 at 19:42.
    Not used mods before? Looking for something small and fun?!
    Download the:

  21. #81

    Default Re: Game AI stuff (1.5)

    The AI has an odd preference for attacking settlements from the SW. I didn't notice this in RTW but maybe i just didn't notice it. Definitely happens in MTW2 and the path-finding seems mostly identical. Given a choice of routes to a city the AI seems to choose the one that will lead to a SW approach. Doesn't matter in wide open regions but in mountain terrain with narrow passes it can be significant as it may make the AI avoid or run into the mutually adjacent region problem. Or, in cases with very long narrow passes an AI army may go on a very long trek around the mountains trying to reach the southern end and get lost.

    This also means AI factions will expand better to the north-east.

    ~~~

    Added a couple of examples to the condensed path-finding thread.

    https://forums.totalwar.org/vb/showt...51#post1485851
    Last edited by nikolai1962; 04-06-2007 at 07:29.
    It's not a map.

  22. #82

    Default Re: Game AI stuff (1.5)

    The AI path-finding doesn't seem to like settlements completely blocking fords. Which is a shame as i like to do that a lot. No wonder my test map got suddenly worse.

    Adding little border regions in between two existing regions with a problem is proving to be pretty good in terms of effectiveness/time taken. Sometimes because of bridging a long gap with a one turn move to a settlement and sometimes because it fixes a path-finding glitch somehow.

    Historical path-finding must have used a similar algorithm as changes to the spain regions on the vanilla map have come out looking quite close to the regions on some maps of medieval spain i d/l ed.
    It's not a map.

  23. #83

    Default Re: Game AI stuff (1.5)

    Wrong about more stuff. Been googling, convex means something else when related to path-finding. Something about convex polygons. Other thing about disconnected chunks of regions will be part of that somehow but not the whole thing. Will figure it out.

    Also in my googling, games apparently often use multiple path-finding mechanisms to improve game speed, some for long-distance and another for short. This would fit in with my observations that the path-finding messes up mostly between one and two turns away form the target whereas it can handle long paths well. Bit of luck i may be able to figure out what the map rules are by looking at this stuff.

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

    praise google
    Last edited by nikolai1962; 04-15-2007 at 08:17.
    It's not a map.

  24. #84

    Default Re: Game AI stuff (1.5)

    Nice bit of progress on the path-finding that seems to be fixing a lot of AI stalls.

    https://forums.totalwar.org/vb/showp...5&postcount=29

    scroll to bit titled "New Theory".
    It's not a map.

  25. #85

    Default Re: Game AI stuff (1.5)

    Final recap on this map stuff on the MTW2 version of this research.

    https://forums.totalwar.org/vb/showp...4&postcount=56
    It's not a map.

  26. #86

    Default Re: Game AI stuff (1.5)

    10th anniversary (ish) update post...

    #

    Why Bother?

    There's lots of epic mods for RTW and MTW but ultimately the thing that puts me off playing them for anything but the shortest time is the game's path finding (or the very long AI turn caused by increasing base movement to fix some of the path finding). My original plan was learn how to fix the path finding using the small vanilla map and then once figured out, apply it to the bigger maps of my fave mods. This proved to be too difficult but I recently had a third attempt at the vanilla map after a (very) long break so I thought I'd post some final conclusions on what the problems are and how they can be fixed (and they can be fixed, it's just takes a lot of time) and finally what, based on my experience, is the best way to go about trying to fix a big map if anyone ever decides to do so.

    (I haven't played/modded any of the games after MTW2 but I know this path finding info is the same for MTW2.)

    #

    Problem

    Flaws in the RTW (and MTW) path finding means the AI armies constantly stall while moving to attack settlements. When the pathfinding is working properly the AI is relentless but when it's not the AI is like a baybee.

    #

    Causes

    The path finding algorithm itself works perfectly - you can see this when you select one of your own units and hold the right mouse button down - the game calculates the best path to the tile your cursor is over. A* path finding (or similar) is guaranteed to find a path if one exists if you give it enough time (and memory) to do so - hence the underlying problem (probably).

    When the player is engaged with one unit the calculation time for the path is not an issue (although memory might be - notice the game will only allow the path to be calculated for around 40 or so tiles). However during the AI turn there may be hundreds or even thousands of path calculations to be done which could lead to long AI turns if the path finding isn't constricted/optimized in some way.

    One way this is commonly done is by using regions. The game map is divided into regions and the game will generate a database of connected regions (this is probably what is in the map.rwn file) and so instead of an AI path being from from tile x to tile y (maybe 40 tiles separate) it becomes:

    1) my current tile is in region A and
    2) my target tile is in region C so
    3) look in the database for the shortest path of regions between A and C

    and if that list is region A -> region B -> region C then the path finding becomes:

    1) find path from current position in A to the border of A and B
    2) when crossed into B find path from B to border of B and C
    2) when in (or near) region C move to target tile.

    Doing this divides the path finding into smaller pieces which might then only require looking a dozen tiles ahead ahead instead of forty.

    However if the map isn't set up just right then this process can glitch.

    #

    Three Main Types of Path Finding Glitch

    Path finding algorithms generally require the map grid to be "convex" which basically means when moving within a region or from one region to an adjacent region there is no clipping through another region and if the path finding is split into two stages:

    1) start region to a region adjacent to target region

    and

    2) adjacent region to target tile

    that gives two ways to glitch.

    1) adjacent region to target tile

    This glitch happens in many places and is relatively easy to spot. What happens is the source and target are in adjacent regions but the fastest path to the target tile clips a 3rd region.

    Click image for larger version. 

Name:	sidon.jpg 
Views:	125 
Size:	371.0 KB 
ID:	20364

    Sidon and Damascus regions are adjacent but the fastest path from Sidon and some of the other tiles in the region clips through a third region (either Judaea or Antioch) which makes the path finding glitch and the army in question gets stuck usually until another army takes Damascus.

    This can also happen when the two regions are only adjacent via a diagonal move and the *equivalent* orthogonal move clips into a 3rd region.

    As mentioned the cure for this is making the regions "convex" which gets the name cos when the map grid is made up of tiles with the same movement cost the regions needs to be convex polygons.

    https://www.mathopenref.com/polygonconvex.html

    However when you have tiles with varying movement costs I'd guess the mathematical equivalent is

    the fastest path from any walkable tile in a region to any other walkable tile in that region has to be completely contained within that region
    and some equivalent rule for the region to region pathing (although my guess would be if all the regions are internally convex the region to region pathing is automatically convex also).

    These glitches aren't necessarily cured by more movement points as the glitch is caused by the region clipping.

    These glitches are ***much*** easier to fix if you know about the "toggle_terrain choke" console command which shows you the impassable and walkable tiles.

    Click image for larger version. 

Name:	sinai.jpg 
Views:	124 
Size:	271.4 KB 
ID:	20365

    (nb some of this kind of pathing bug have been fixed in the vanilla game e.g. if you remove the impassable tile shown in the top center of the above toggle_terrain image the road shifts and makes the fastest path to Petra clip regions and the army stalls.)

    #

    2) region to region pathing

    This is either less common or just harder to spot and I think mostly involves cases where the region to region movement database gets mixed up in some way so the game thinks 1) two regions are adjacent when they're not or 2) doesn't think they're adjacent when they are or 3) the stored fastest path along a chain of regions is messed up for some reason.

    There's a possible example of this kind of region to region clipping problem here.

    Click image for larger version. 

Name:	petra.jpg 
Views:	112 
Size:	308.1 KB 
ID:	20363

    This doesn't happen every game as it needs the army in Petra to be assigned to attack Damascus and a specific combination of roads having been built when it is assigned but when it does you get a large army in Petra which doesn't move and no other egypt armies moving to attack Damascus - which is the usual sign an AI army is stuck.

    If you start a game as egypt and take Petra and then hold down the right mouse button to show the fastest path to Damascus, then without roads the path (by regions) goes Nabatea-Judea-CoeleSyria

    Click image for larger version. 

Name:	petra02.jpg 
Views:	102 
Size:	325.4 KB 
ID:	20366

    ...but after various road combinations are built it can go Sinai->Nabatea->Coele-Syria or maybe even Sinai-Judea->Nabatea->Coele Syria.

    No way to be sure without knowing the source code but I think the AI army in Petra glitches here because the stored region to region path and the current fastest region to region path are different i.e. it may expect the fastest path to be from Judea to Coele Syria but it's via Nabatea instead.

    #

    3) A bridge too far

    Click image for larger version. 

Name:	vindex.jpg 
Views:	113 
Size:	366.4 KB 
ID:	20367

    This is very common - an AI will move to (or start the game at) a certain distance more than one but less than two turns of (80 MP) movement from their target and then stall. If you use move_character to move them closer, if roads get built, if they get a trait which boosts their movement, if you increase base movement points or any other thing that gets them within one turn's movement of the target they move and attack.

    As you can probably see from the image there is no obvious logical explanation why the army gets stuck which is why it's very important to test which path finding bugs can be fixed with more base movement points. If you don't you can waste hours trying to fix a problem which is either a) not related to convexity or b) it is but it's related in an indirect way which is buried out of sight, like for example the target region's borders didn't get stored properly in the map.rwn.

    I can understand the clipping issue cos it's extremely difficult to get the complicated RTW regions to be mathematically convex enough for the path finding but assuming the path finding is region to region first then switching to finding the target tile when close enough then it makes no sense to stop the region to region movement where the AI isn't actually close enough for the next stage of pathing to kick in and it seems to me this would be obvious in development so as it's so common *and* these type of glitches are mostly fixed by higher base movement points *and* higher base movement makes the AI turn take longer with the player twiddling their thumbs then...

    my guess is the game was developed with higher base movement and as more factions were added and more AI units were moving around the AI turn got too long so they reduced the MP to 80 and it was too late to redesign the map around the new movement base.

    #

    4) Small Fry

    There are other issues like the pathing seems to prefer settlements near the center of the region and doesn't seem to like settlements blocking fords/bridges and a lot more but the three main categories above are the majority and my guess is many of the little ones (and maybe the entire third category) may be fixed by making the map more convex overall so should be left to the end imo.

    #

    Solutions

    So the solutions to the path finding problem(s) are

    1) make the map mathematically convex
    and
    2) have base movement points that suit the map

    #

    New Problems

    The new problems resulting from the solution are

    1) making the map convex is very difficult, time consuming, frustrating and easy to mess up

    2) the simplest fix for a lot of path finding is increasing base movement rate but this can make the AI turn drag on too long especially on a big map with lots of regions and moving units.

    #

    Convexity

    Complex Cases

    Making regions convex is much easier since someone discovered the toggle_terrain choke command which shows you the walkable and impassable tiles but it can still be difficult.

    An illustration of toggle_terrain choke showing one example of the convexity problem.

    Click image for larger version. 

Name:	lugdun.jpg 
Views:	117 
Size:	354.9 KB 
ID:	20368

    If you look at the region borders around the mountains in the lower center you can see the fastest path from one border tile to the other will automatically clip into the adjacent region. One way to fix this is to pull the border back towards the center, another would be to push the border forward.

    This situation illustrates the general principle of making regions convex when they contain difficult terrain shapes which is you generally need to either 1) make a region smaller so it fits snugly inside difficult terrain or 2) make them bigger so the difficult terrain is buried inside the region and not on the borders (CA tried to improve the path finding of the Barbarian Invasion map in this way imo.)

    #

    Simple Cases

    There are also simple cases. Unreachable tiles break the convexity rule and with terrain_toggle they are relatively easy to spot and fix. The vanilla map has a bunch.

    Click image for larger version. 

Name:	unreachable.jpg 
Views:	107 
Size:	326.8 KB 
ID:	20369

    (nb in this case unreachable rebels can spawn on those tiles making rebel chasing AI armies glitch)

    Also if a region has walkable tiles that are reachable but not from their own region then that will automatically break the convexity rule also.

    Click image for larger version. 

Name:	caucasus.jpg 
Views:	100 
Size:	250.6 KB 
ID:	20370

    There are also some cases where it seems that if tiles are connected but only by diagonals then there may be problems but that may be a function of other issues so i'd leave them till later.

    #

    Increasing Movement Points

    The problems with this are threefold:

    1) A long AI turn is a drag no matter how good the rest of the mod is.
    2) It doesn't fix clipping glitches (or maybe it fixes some but not all, can't recall).
    3) It needs to be proportional to region/map size - increasing region size by 50% and movement by 25% probably won't help.

    Even so unless the map is perfectly convex (where increasing base movement is not necessary) then increasing base movement is probably a necessary component of a fix.

    #

    Best Way to fix a Big Map?

    1) edit the map separately

    Lots of things can effect how well an AI faction expands: unit stats, recruitment, traits, unrest etc so if you're testing path finding map edits by how well the AI expands at the same time as changing other things then your other changes may make you go round in circles - so have a separate mod folder where you only change map stuff.

    2) clear the decks

    I'd clear out everything like complex trait systems, scripting, events etc from your separate map editing version of the mod that could distract from the map editing, slow down the AI turn or tempt you to start playing the game instead of watching the AI. You want the AI turn as fast as possible as you'll be doing it a lot.

    3) provincial campaigns

    Provincial campaigns within a mod folder are a neat way you can make map edits and still switch back to the original campaign map for comparison tests. It's also a safe way to version control your map editing. Create a "mapedit01" provincial campaign (there are tutorials for this), edit the map files there, and when you think you have a solidly improved version copy the map files to a mapedit02 provincial campaign and work from them so you can go back to 01 if you screw up

    4) start simple

    The simplest cases of non convexity are unreachable walkable tiles and walkable tiles in regions which aren't connected. I'd suggest trying to get all of those first as your mapedit01 version before moving on.

    5) do a movement point test early

    The way I test at the beginning is start a game with an out of the way faction, put everything on auto manage and then watch one of the AI factions expand for say 20 turns or so making notes of where one of their armies gets stuck. (A lot of them will have armies stuck on turn one.) Then do it again with more movement points so you can see which are fixed that way. You may eventually still want to edit those spots to make pathing easier (i.e. cost fewer movement points) but as you'll be changing a lot of other stuff to fix convexity it's more efficient to worry about them later. (And judging by my test maps in the past, making the entire map convex somehow fixes a lot of these glitches as well.) The bugs left after increasing base movement will then mostly be confused regions or clipping (aka convexity).

    6) alternative setup for (5)

    I found the most productive way was to strip out the strat file almost completely leaving just two factions with two settlements (any settlement not specified in the strat file is created as a rebel village). Put the first faction/settlement on an island out of the way (this will be your faction) and then put the other faction/settlement where you want to test the map - say one region in Iberia - and then watch the AI's first few moves making notes of where it gets stuck. Then move the start settlement to another region in Spain and repeat (nb the AI can get stuck going between two regions in one direction but not in the other) until you have a list of bugs for Iberia.

    7) alternative to step by step approach

    This may seem a bit backwards to some but how I would actually go about trying to make a big map convex after past experience is I'd keep a copy of the original regions files for future reference but then i'd erase/merge most of the regions to create macro regions which are naturally convex due to terrain e.g. Iberia, and then break the macro regions down into sub-regions. It's a lot easier to spot naturally convex sub-regions within these macro regions and do them first than it is to move around lots of existing region borders in a complex and cluttered map. Once you have the naturally convex macro and micro regions done then fill in the rest.

    8) In other words

    It's too much work for me but if I was advising someone else on how to fix a big complex map now I'd do the opposite of how I learned to do it. Originally I watched a standard mod and then gradually cut everything out but map related stuff and fiddled with the existing regions one by one coming at convexity from the wrong direction. Much better to *start* with region convexity in mind, hence start with big convex macro regions, test that works (if possible, the macro region settlements may be too far apart), then carve out any naturally convex sub-regions within the macro regions and then finally artificially make whatever is left over into convex regions (mostly by using dense forest borders).

    (If the map is reasonably accurate then historical regions should arise naturally. Exceptions to this may be needing to split some historical regions into two pieces e.g. north and south or east and west of a river.)

    #

    In a nutshell

    The best way to learn how to spot AI path finding bugs may be the way I did it originally which was

    1) watch a standard game/mod run and note where the AI gets stuck
    2) see which are fixed by increasing MP and which aren't (i didn't do this but should have done)
    3) try and fix each glitch separately with map edits (but not the MP related ones)
    4) eventually realize that when the map edits worked it was mostly by accidentally making a region more convex
    5) consciously make regions more convex one by one
    6) eventually get the whole map working

    but the sequence I'd actually advise now is:

    1) create a separate mod folder for map editing
    2) strip out scripting etc that isn't needed for map editing
    3) use provincial campaign folders for version control
    4) merge/erase the original regions into naturally convex macro regions
    5) create artificially convex macro regions out of the rest
    5) carve out naturally convex sub-regions within the macro regions
    6) create artificially convex sub-regions out of the remainder
    7) test each step using a two faction, two settlement setup
    8) from time to time run longer test games with the -ai switch to compare the new map's performance with the original

    The End
    Last edited by nikolai1962; 12-22-2017 at 15:43.
    It's not a map.

    Members thankful for this post (2):



  27. #87
    Senior Member Senior Member ReluctantSamurai's Avatar
    Join Date
    Feb 2008
    Location
    USA
    Posts
    2,483

    Default Re: Game AI stuff (1.5)

    Excellent work!

    A lot of AI behavior that I've observed is now much clearer. It seems that the difficulties created by CA in switching to a 3D map were both unexpected and ultimately too time consuming to fix given the deadlines the design team had to work with. However, when it became apparent that AI turns were taking far too long to complete due to the intense # of calculations that needed to be done, I think some limitations on the game should have been imposed (not an easy decision when you are trying to create an award-winning game with huge mass appeal).

    Perhaps reducing the number of factions:

    Armenia is probably superfluous; Scythia in the time frame of the game is probably ahistorical; Rome, in reality should have only two factions (Julii and Scipii); Dacia is probably excessive; and perhaps Spain. The great conflicts between Rome and Carthage, Rome and the Barbarians, Rome and the Persians, and Rome vs the Hellenic States should have been the focus, IMHO, and would still have made for a great game

    Limiting the number of stacks a faction can have (including naval). Economically, this should have already occurred, but when AI factions get economic bonuses at lower difficulty settings, this allows for recruitment beyond normal means. Limiting the number of diplomats/spies/assassins at any given time might also have helped (and I assume the same map calculations are necessary for each one of those units as it is for an army stack), and has the added benefit of reducing "game clutter", as I like to call it.

    I wish I had the time to tackle the map problems, as map-making has always been a passion of mine. Ten years ago, I made a whole series of maps for a WW II game called Pacific General. I got good enough at it that campaign designers were constantly asking me to create maps for their campaigns. In a much simpler system, a single map (which included the research of topographical maps, vegetations types, cities/roads/etc) would run 80 to 100 hours to complete. A campaign of 10 scenarios, with ten new maps, nearly 1000 hours

    I can only imagine how much time a completely revised RTW map would cost
    High Plains Drifter

  28. #88

    Default Re: Game AI stuff (1.5)

    It seems that the difficulties created by CA in switching to a 3D map were both unexpected and ultimately too time consuming to fix given the deadlines the design team had to work with.
    I think that was it.

    reducing the number of factions...Limiting the number of stacks a faction can have...Limiting the number of diplomats/spies/assassins at any given time might also have helped
    yes that is a big part of it - lots of units with bad path finding or fewer units with computationally expensive path finding

    A campaign of 10 scenarios, with ten new maps, nearly 1000 hours
    ouch
    It's not a map.

  29. #89

    Default Re: Game AI stuff (1.5)

    addendum to latest update post #86

    scrapped latest attempt at fixing vanilla map using the bottom up method (which is):

    1) watch AI to see where it gets stuck
    2) try to fix each one separately

    to compare that with starting from scratch with the top down method (which is):

    1) assume from the start that most path finding problems are connected to non convexity
    2) mentally divide the map into its most naturally convex macro regions (e.g. Iberia)
    3) make map edits that reinforce the convexity of the macro regions you pick
    4) within each macro region rearrange the borders of its internal sub-regions to make each region more convex

    early days but so far the top down method would appear to be about an order of magnitude better/faster. if this continues i may be able to enjoy RTW/MTW again. quite pleased
    It's not a map.

  30. #90
    Senior Member Senior Member ReluctantSamurai's Avatar
    Join Date
    Feb 2008
    Location
    USA
    Posts
    2,483

    Default Re: Game AI stuff (1.5)

    Here's a quick question...would some judicious re-routing of roads help? Seems like a lot of path-finding problems arise when a stack has to get to Province C from Province A via Province B

    Also, how much have you looked at the naval aspect of path-finding? Carthage, in particular, suffers horribly because the AI can't seem to identify viable targets, or even if it does, it can't decide how to get there. So many times I've seen Carthage recruit units, move them onto a fleet just off-shore, and then do absolutely nothing with them, even when Carthage comes under siege. Even worse, those units just sit there when Carthage falls, and many times lost with all hands when the fleet comes under attack and sunk
    High Plains Drifter

Page 3 of 5 FirstFirst 12345 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Single Sign On provided by vBSSO