Map editing for AI path-finding problems.

[nikolai1962]

Added a bit under the title "workarounds".

[nikolai1962]

Sorry, missed some posts.

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

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

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

Doh

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

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


~~~

I *think*

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

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

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

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

[alpaca]

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

[SigniferOne]

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

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

[SigniferOne]

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

Jerome posted:

A few other caveats about regions:
- they should be 'convex' (one landmass, no inaccessible areas)*
- they should have only one settlement and only one port
- all land tiles should be part of a known region
- each non-sea region should contain at least some fertile tiles
- continuous sea surfaces should form one region
- the maximum number of regions supported is 200
- the distance between the centres of any two adjacent regions should not exceed 50 tiles*

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

[nikolai1962]

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

Yup.

Some workarounds...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[nikolai1962]

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

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

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

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

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

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

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

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

So there's something else i'm missing.

argh, back to google.