Latest Posts

Topic: AI roads rework

Tibor
Joined: 2009-03-23, 23:24
Posts: 1231
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-03, 21:37

Hi,

I am spending some time reworking roads building in AI. What is the main news is that AI now calculates road distance from nearest warehouse to each flag and this is one of values used for building the road. It is more complicated, but AI considers also this info. Here are some screenshots




and here is the code:

bzr branch lp:~widelands-dev/widelands/ai_flag_warehouse_distance

I believe AI now builds fewer roads...I had not tested it on maps with botlenecks


Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 613
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2019-06-03, 23:00

looks good will test this as soon as I get some time


Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1264
Ranking
One Elder of Players
Posted at: 2019-06-04, 00:54

I'm not qualified to talk here. those roads are horrible, but they could be an improvement over the previous algorithm.

And I have no idea how to make a road algorithm either.

Edited: 2019-06-04, 01:06
Top Quote
Tibor
Joined: 2009-03-23, 23:24
Posts: 1231
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-04, 10:13

yes, the question is if these roads would be better or not..


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 2880
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2019-06-04, 11:42

The screenshots look like an improvement to me.


Busy indexing nil values

Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 613
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2019-06-04, 12:49

GunChleoc wrote:

The screenshots look like an improvement to me.

to me as well. I strongly believe with the new feature the Ai does ensure to not build roads that take a long detour anymore. by this less fields should be used for roads. A side effect is that it tries to ensure short ways to the next warehouse, which should improve effectiveness of the economy.
Improving the AI is not a one shot I believe it is along fight of improving deficiencies one by one. I think it won't be possible to have an AI that is doing perfect. The goal is making it always a small step better.
@ Kingofnowhere what exactly is so horrible with the roads?


Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1264
Ranking
One Elder of Players
Posted at: 2019-06-04, 16:47

hessenfarmer wrote:

@ Kingofnowhere what exactly is so horrible with the roads?

well, let's only loook at the first image.

  • From headquarter, go west and the second road is already 3 steps in lenght. On a major highway! that's an awful crippling of the late game transportation.

  • going north-east, the point where the road crosses water, there is a 3 steps road crossing the water. As the only point to cross water, that's a bottleneck. You absolutely want to avoid long roads on bottlenecks. To be fair, the way to avoid it (taking a detour with the road so that you can place the flag on the water border, and have two short roads starting from it) is not easy to see if you are not an experienced human.

  • keep going north-east, on the branch with the metalworks and the bakery, that junction really looks bad. the road takes an aunnecessary step westward, and it has to make all kind of 3-steps segments from there. ok, those are periphereal roads and so it's not a big deal if they are longer, but spaace can be saved.

  • there is no connection between north-east, north-center and north-west, even though it would be easier to make some. granted, there isn't much need to move wares between those places. still, it would only take 2 road segments.

  • from hq going east, the road goes south and then north again. it takes a large detour to reconnect to south, which is rreally not good. work should be made to rectify that road, especially as trees keep getting cut.

  • on the southern section, east of the two quarries, there are many tangles with long segments. those are pretty bad.

I admit, it's not really that bad, except for the southern snarl. I'm just a nazi when it comes to road placement.

I wonder if it would be possible to make the AI understand the difference between primary, secondary and tertiary roads. Very difficult, the rules aren't clear-cut. Also mmaking the AI understand that when it makes a skewed road to go around a temporary obstacle, like stone or tree, it can rectify the road once the obstacle is removed. i can see all manners of things gooing wrong with teaching the AI to pull down flags...


Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 613
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2019-06-04, 17:05

king_of_nowhere wrote:

hessenfarmer wrote:

@ Kingofnowhere what exactly is so horrible with the roads?

well, let's only loook at the first image.

  • From headquarter, go west and the second road is already 3 steps in lenght. On a major highway! that's an awful crippling of the late game transportation.

  • going north-east, the point where the road crosses water, there is a 3 steps road crossing the water. As the only point to cross water, that's a bottleneck. You absolutely want to avoid long roads on bottlenecks. To be fair, the way to avoid it (taking a detour with the road so that you can place the flag on the water border, and have two short roads starting from it) is not easy to see if you are not an experienced human.

  • keep going north-east, on the branch with the metalworks and the bakery, that junction really looks bad. the road takes an aunnecessary step westward, and it has to make all kind of 3-steps segments from there. ok, those are periphereal roads and so it's not a big deal if they are longer, but spaace can be saved.

  • there is no connection between north-east, north-center and north-west, even though it would be easier to make some. granted, there isn't much need to move wares between those places. still, it would only take 2 road segments.

  • from hq going east, the road goes south and then north again. it takes a large detour to reconnect to south, which is rreally not good. work should be made to rectify that road, especially as trees keep getting cut.

  • on the southern section, east of the two quarries, there are many tangles with long segments. those are pretty bad.

I admit, it's not really that bad, except for the southern snarl. I'm just a nazi when it comes to road placement.

I wonder if it would be possible to make the AI understand the difference between primary, secondary and tertiary roads. Very difficult, the rules aren't clear-cut. Also mmaking the AI understand that when it makes a skewed road to go around a temporary obstacle, like stone or tree, it can rectify the road once the obstacle is removed. i can see all manners of things gooing wrong with teaching the AI to pull down flags...

Thanks a lot. that gives us a better understanding of which part to work on. I agree next step would probably be avoid 3 step roads to a higher degree.
the current work done by Tibor is aiming at avoiding long tangles. From what I see this is more efficient near the HQ and less at greater distances, which is logical . the idea was that after the AI starts building warehouses, these would be centers of the road network as well. By this the tangles should be reduced around a warehouse.
Basically it is not teaching the Ai it is coding and a code has the big disadvantage, that it can't differ between situations.
I still believe this work to be major improvement. Thanks to tabor for doing all the stuff.


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 2880
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2019-06-04, 17:12

Maybe you could add something that the AI always tries to build roads in all 5 directions coming out of headquarters/warehouses, before placing any buildings near them? And then leave them there, even if the flags are unconnected at first.


Busy indexing nil values

Top Quote
WorldSavior
Avatar
Joined: 2016-10-15, 04:10
Posts: 1101
Ranking
One Elder of Players
Location: GER
Posted at: 2019-06-04, 21:20

GunChleoc wrote:

Maybe you could add something that the AI always tries to build roads in all 5 directions coming out of headquarters/warehouses, before placing any buildings near them? And then leave them there, even if the flags are unconnected at first.

Or even better: Not 5 roads, but just two double-roads of length 2.


“It's a threat to our planet to believe that someone else will save it.” - Robert Swan

Top Quote