Map editing for AI path-finding problems.

**alpaca** · 04-25-2007, 19:00

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?

**nikolai1962** · 04-26-2007, 04:28

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.

**PorT_Lobo** · 04-26-2007, 17:37

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.

**alpaca** · 04-26-2007, 18:13

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.

**nikolai1962** · 04-27-2007, 21:28

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.

**SigniferOne** · 04-28-2007, 07:36

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

**alpaca** · 04-28-2007, 09:36

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