Page 2 of 2 FirstFirst 12
Results 31 to 57 of 57

Thread: Map editing for AI path-finding problems.

  1. #31

    Default Re: Map editing for AI path-finding problems.

    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.
    It's not a map.

  2. #32

    Default Re: Map editing for AI path-finding problems.

    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.
    Falas Português? Então participa no PorT Fórum de M2TW!!

  3. #33
    Harbinger of... saliva Member alpaca's Avatar
    Join Date
    Aug 2003
    Location
    Germany
    Posts
    2,767

    Default Re: Map editing for AI path-finding problems.

    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.

  4. #34

    Default Re: Map editing for AI path-finding problems.

    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.
    It's not a map.

  5. #35

    Default Re: Map editing for AI path-finding problems.

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

  6. #36
    Harbinger of... saliva Member alpaca's Avatar
    Join Date
    Aug 2003
    Location
    Germany
    Posts
    2,767

    Default Re: Map editing for AI path-finding problems.

    Quote Originally Posted by 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 :)
    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).

  7. #37

    Default Re: Map editing for AI path-finding problems.

    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.
    Last edited by nikolai1962; 04-29-2007 at 01:38.
    It's not a map.

  8. #38
    TW Modder Since 2005 Member DaVinci's Avatar
    Join Date
    May 2005
    Location
    Hamburg, Germany/EU
    Posts
    848

    Default Re: Map editing for AI path-finding problems.

    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
    Last edited by DaVinci; 09-18-2007 at 11:51.
    TWC Wiki: List of TW Modding Contributions 2005-2011
    Release 12.2012: Third Age TW Realism+
    Release 04.2013: Rise of the Samurai Realism+


    Support: Greenpeace
    LIVING ...WITH... WAR
    What's really more disappointing than dis-information and non-education?
    A certain degree of intentional ignorance paired with obvious stupidy /DV

  9. #39

    Default Re: Map editing for AI path-finding problems.

    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/showt...wpost&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.

  10. #40

    Default Re: Map editing for AI path-finding problems.

    Quote Originally Posted by 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
    Ty. I gave up again for a bit because it was driving me nuts :)
    It's not a map.

  11. #41

    Default Re: Map editing for AI path-finding problems.

    Quote Originally Posted by 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/showt...wpost&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 :)
    It's not a map.

  12. #42

    Default Re: Map editing for AI path-finding problems.

    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.
    Last edited by nikolai1962; 10-22-2007 at 12:07.
    It's not a map.

  13. #43

    Default Re: Map editing for AI path-finding problems.

    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.
    It's not a map.

  14. #44

    Default Re: Map editing for AI path-finding problems.

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

  15. #45

    Default Re: Map editing for AI path-finding problems.

    Quote Originally Posted by 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).
    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

    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.
    It's not a map.

  16. #46

    Default Re: Map editing for AI path-finding problems.

    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.
    It's not a map.

  17. #47

    Default Re: Map editing for AI path-finding problems.

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

  18. #48

    Default Re: Map editing for AI path-finding problems.

    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.
    It's not a map.

  19. #49

    Default Re: Map editing for AI path-finding problems.

    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)
    Last edited by nikolai1962; 11-17-2007 at 07:29.
    It's not a map.

  20. #50

    Default Re: Map editing for AI path-finding problems.

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

  21. #51

    Default Re: Map editing for AI path-finding problems.

    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

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

  22. #52

    Default Re: Map editing for AI path-finding problems.

    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.

  23. #53

    Default Re: Map editing for AI path-finding problems.

    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.
    It's not a map.

  24. #54

    Default Re: Map editing for AI path-finding problems.

    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
    It's not a map.

  25. #55

    Default Re: Map editing for AI path-finding problems.

    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?

  26. #56

    Default Re: Map editing for AI path-finding problems.

    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.
    Last edited by nikolai1962; 07-02-2008 at 21:11.
    It's not a map.

  27. #57
    Member Member irishron2004's Avatar
    Join Date
    Sep 2004
    Location
    California
    Posts
    183

    Default Re: Map editing for AI path-finding problems.

    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.

Page 2 of 2 FirstFirst 12

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