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.