Map editing for AI path-finding problems.

**wilddog** · 04-01-2007, 13:30

nikolai1962

Nice post. I hadn't looked into this in much detail before. However I will try and test some of this out.

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.

**nikolai1962** · 04-05-2007, 01:20

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.

Wouldn't surprise me if that was true.

**nikolai1962** · 04-05-2007, 01:37

An example of where this guideline/rule would have applied.

Ideally i think the AI path-finding would work best if the fastest path between every tile in the region to every other tile in that region was wholly inside the region.

Didn't take screenie at the time so drew some lines on the current map to show the situation when this glitch occurred.

The black lines were the borders of damascus/baghdad.
The red lines are where the road went with those borders.
"R" is a brigand stack that spawned.
"A" is the position of an egypt stack heading to Baghdad when the rebels spawned.

When the game creates roads it takes the shortest route to the border of the adjacent region *but* when there are two roads close together it merges them along part of the route. In the situation above the road to jedda was pulled close to the damascus/baghdad border line because of this.

The egypt stack moving to baghdad switched to attack the rebels but because of the road it's fastest route took it over into damascus. This hit the region A to adjacent region B via a mutually adjacent region C problem and the stack stalled. It would have stayed there until it either revolted or some other army killed the rebels. (You can find out what is causing a stack to stall by using move_character and moving it around till it moves on its next turn.)

If all regions conform to the rule above then this problem will never happen. In vanilla mtw2 (or rtw) if you watch the AI after x turns with fow off you'll be able to spot dozens of AI stacks stuck like this.

**nikolai1962** · 04-05-2007, 01:57

Example of a diagonal path stall.

Sometimes you'll see egypt stall attacking Damascus with an army in Acre that isn't moving. This will usually happen if they've attacked from jerusalem and lost *and* they have a stack in acre that isn't doing anything. They'll set the stack in Acre to attack Damascus and that stack witll stall.

If you look at the screenie you'll see that the border point where jeruslaem, damascus and acre all meet is just before the mountains. This means the Acre stack tries to path through where i've drawn the blue line. However, i think the pathing works orthogonally and only figures out diagonal movement after it creates an orthogonal path. This would mean the pathing at that junction would go one tile right into jeruslaem region then one tile up to the corner tile of damascus region.

This hits the region A to region B through region C thing and the stack stalls until they revolt or damascus gets taken by some other stack.

This can be fixed by moving the mutual border point under the mountains.

**alpaca** · 04-05-2007, 11:58

By the way Nikolai, you might want to check out my stripped-down map to test this more systematically.
You can create all kinds of setups there quite easily, and you can decrease the map size by a fair margin to generate the rwm faster (it's already faster than vanilla anyways I think)

**nikolai1962** · 04-06-2007, 06:15

By the way Nikolai, you might want to check out my stripped-down map to test this more systematically.
You can create all kinds of setups there quite easily

Yeah, i d/l ed it precisely for that reason. Trouble is i'm a bit obsessed with semi-fixing the vanilla map so i can actually play the game without getting frustrated seeing all the AI armies standing around not doing anything. I'm planning on just getting the vanilla map semi-working then using your thing to make a new test map to figure out the rest.

**SigniferOne** · 04-09-2007, 18:05

Excellent post Nikolai, will be very interesting to put it to use. Have you consulted a very similar study of pathing in RTW? They started along very much the same lines as you did, and I think they got further along in RTW. Considering that both games have almost exactly the same maps, the results should be comparable between the two studies.