[patch] Station placement (road) for AI

[gerw]

This patch modifies bauer/wegbauer.*. Now you can calculate a route from several starting points to several end points. The wegbauer will find the best one. To this end, I also added a implicit typecast T -> vector_tpl<T>, which constructs a vector with one element.

Now, road stations are always placed at the best tile found by wegbauer. For rail stations both ends of a station are tested and the best one gets connected.

[z9999]

Sometimes crash with same messages.
I don't know you can reproduce this or not, but I will attach the game for pak64.
http://simutrans-germany.com/files/upload/AI2-01.sve
I tried 3 times and all crashed.
After loading the savegame, click fast-forward button and wait.

sim_ai.exe caused an Access Violation at location 0060e0a4 in module sim_ai.exe Reading from location 0000000c.

Registers:
eax=00000000 ebx=0766e538 ecx=00000000 edx=00000000 esi=0572f008 edi=f9000cd6
eip=0060e0a4 esp=0023e51c ebp=0023fa18 iopl=0         nv up ei pl nz na po nc
cs=001b  ss=0023  ds=0023  es=0023  fs=003b  gs=0000             efl=00000206

Call stack:
0060E0A4  sim_ai.exe:0060E0A4  weg_besch_t::get_topspeed() const  weg_besch.h:101
   ...
    * @author Hj. Malthaner
    */
>   uint32 get_topspeed() const { return topspeed; }
   
   /**
   ...

005B5AA5  sim_ai.exe:005B5AA5  WinMain  simsys_w16.cc:757
00401247  sim_ai.exe:00401247
00401298  sim_ai.exe:00401298
7C817067  kernel32.dll:7C817067  RegisterWaitForInputIdle

Message: ai_goods_t::do_ki:   Consider route from 製鉄所 (22,34) to 資材販売店 (116,3)
Message: vehikelbauer_t::vehikel_search:   Found car Stahlwagen
Message: do_ki():   rail vehicle 055D8028
Message: do_ki():   road vehicle 00000000
Message: do_ki():   check railway
Message: vehikelbauer_t::vehikel_search:   Found engine H-Trans-Pantheress
Message: vehikelbauer_t::vehikel_search:   Found engine Hunslet
Message: vehikelbauer_t::vehikel_search:   Found engine 1Dampflokomotive
Message: vehikelbauer_t::vehikel_search:   Found engine Ed2x2
Message: vehikelbauer_t::vehikel_search:   Found engine JNR_C11
Message: vehikelbauer_t::vehikel_search:   Found engine BRV36
Message: vehikelbauer_t::vehikel_search:   Found engine 3Diesellokomotive
Message: ai_goods_t::do_ki():   Engine 3Diesellokomotive guess to need 7 rail cars Stahlwagen for route (wooden_sleeper_track)
Message: do_ki():   check railway
Message: ai_goods_t::do_ki():   Netto credits per day for rail transport 9.29 (income 24.39)
Message: ai_t::suche_platz():   at (22,34) for size (2,2)
Message: ai_t::suche_platz1_platz2():   no suitable locations found

[gerw]

It can't reproduce it. Can you give me a backtrace? Thank you for testing.

[z9999]

Program received signal SIGSEGV, Segmentation fault.
0x0060e0a4 in weg_besch_t::get_topspeed() const (this=0x5b5aa5)
    at boden/wege/../../besch/weg_besch.h:101
101             uint32 get_topspeed() const { return topspeed; }
Current language:  auto; currently c++
(gdb) #0  0x0060e0a4 in weg_besch_t::get_topspeed() const (this=0x5b5aa5)
    at boden/wege/../../besch/weg_besch.h:101
#1  0x005042db in ai_goods_t::suche_platz1_platz2(fabrik_t*, fabrik_t*, int) (
    this=0x7c9501bb, qfab=0x23e5a4, zfab=0x1c, length=28)
    at player/ai_goods.cc:252
#2  0x005b5aa5 in WinMain (hInstance=0x69004d, hPrevInstance=0x720063,
    lpCmdLine=0x73006f "\tﾈ\tﾉ\tﾊ\tﾋ\tﾌ\tﾍ\tﾎ\tﾏ\tﾐ\tﾑ\tﾒ\tﾓ\tﾔ\tﾕ\tﾖ\tﾗ\tﾘ\tﾙ\tﾚ\tﾛ\tﾜ\tﾝ\tﾞ\tﾟ\t", nShowCmd=6684783) at simsys_w16.cc:757

Thank you for trying.
Is this useful ? I have never used gdb before.

[prissi]

Sometimes AI wants to built connected stations to transport more goods (i.e. medicals and chemistry). Therefore it should be checked too, it traget is next to existing station.

(ANd there seems to be some changes too, which are not directly patch related, imho. No big deal though ...)

[gerw]

#1  0x005042db in ai_goods_t::suche_platz1_platz2(fabrik_t*, fabrik_t*, int) (
   this=0x7c9501bb, qfab=0x23e5a4, zfab=0x1c, length=28)
   at player/ai_goods.cc:252

That's weird. With length==28, line 252 shouldn't be reached.

And with only 7 rail cars, length shouldn't be 28 anyway...

(ANd there seems to be some changes too, which are not directly patch related, imho. No big deal though ...)

What do you mean?

[prissi]

The first three patches should not bee needed.

[z9999]

That's weird. With length==28, line 252 shouldn't be reached.

And with only 7 rail cars, length shouldn't be 28 anyway...
What do you mean?

As I said I have never used gdb before. Something wrong with me.
Problem is not there.
Problem happened because of road_weg==NULL. I don't know why, but it needs to check that road_weg is valid or not, doesn't it ?

[gerw]

The first three patches should not bee needed.

gcc complained about these constructors, since I added another constructor in vector_tpl, to have a implicit convertion T -> vector_tpl<T>. With T=int this collide with the other constructor in these cases. Anyway, the 0 in these constructors can be omitted, since the default constructor creates vectors with zero elements.

[prissi]

In that case I would rather omit the implicit declaration, since this side effect will irritate programmes for ages. A i = vector_tyl<int>(1); i[0] = xyz; is not so much more code either.

I was mandantory in the old code that a vector has a constructor with a number, since it could not grow (yes it was static). This was released to make simutrans more dynamically in its economy. But I am not sure that too many implicit stuff is good. (Imho it is evil.)

Also putting the check for zielpos into the array means that for station area = 3 (not so uncommon, i.e. pakHajo) 48 fields must be tested each step. Keeping in mind, that on larger maps the AI builds long ways, this makes the routine very slow (almost half of the normal speed). Imho, a less expensive way would to calculate the route and check afterwards, where it enters the needed coverage area and decide from there on.

If the check should go into wayfinder, then maybe another koord with the extension of the search rectangle should passed to it.

next_coord was needed to reduce calculation time. Otherwise it will do many tests in the wrong direction first when going south west. And in AI mode both directions are calculated. (This is the second reason, why imho thing should be done afterwards.)

EDIT:
I think it will go back to patches, even though I admit freely that the AI location search coul dbe greatly improved.

[gerw]

Also putting the check for zielpos into the array means that for station area = 3 (not so uncommon, i.e. pakHajo) 48 fields must be tested each step. Keeping in mind, that on larger maps the AI builds long ways, this makes the routine very slow (almost half of the normal speed). Imho, a less expensive way would to calculate the route and check afterwards, where it enters the needed coverage area and decide from there on.

If the check should go into wayfinder, then maybe another koord with the extension of the search rectangle should passed to it.

next_coord was needed to reduce calculation time. Otherwise it will do many tests in the wrong direction first when going south west. And in AI mode both directions are calculated. (This is the second reason, why imho thing should be done afterwards.)

One possible solution is:
Only allow several starting koords. Then you can use the old wegbauer code, but have to add all starting tiles to the queue first.

[Dwachs]

next_coord was needed to reduce calculation time. Otherwise it will do many tests in the wrong direction first when going south west. And in AI mode both directions are calculated. (This is the second reason, why imho thing should be done afterwards.)

I do not see, how using next_koord speeds up computation (ie line 1074 in wegbauer.cc). Imho, it only determines in which order the four neighbours are checked. However, all suitable (the good and the bad) ones are added to next_gr and to the queue. The value of new_f then determines when (and if) this neighbors are token from the queue. That is, the quality of a tested tile in terms of the A* heuristic is only taken into account when inserting in the queue. Is the order if the insertions that important to computing time?

[prissi]

Maybe the next_coord stuff is no longer needed. It would save some time then to remove it. I did the profiling around here a long time ago and now I am also starting to doubt their neccessity. Maybe I looked at the code too long.

The idea of using several starting tiles and a single end tile is appealing from calculation effort point of vue. But I think the AI must look itself at the way and decide where it enters the coverage area (or where it gets close) and try from there on (as also terraforming might be needed). However, this is only my personal view.

[gerw]

I've tested the time of wegbauer_t::calc_route with different implementations (each 20 runs, summed up; 320x256 map):
1. unpatched: 10s
2. patched, start and end is vector with one tile: 10s
3. patched, start and end is vector with 7x7 = 49 tiles: 22s

The time of one run fluctuates very much, so I summed up. Even if you connect two 7x7 rectangles, it takes only the double time. (It's the same time, if you calc first a forward and then a backward route, in order to place both stations!)

If you consider an other heuristic: with the (minimum) rectangle (containing all end-points) as an heuristic, calculation can be speeded up. I will test this next time.


The attached patch is a version I created yesterday. It considers the stations, that are already at an station.

Todo:
Remove implicit conversion T -> vector_tpl<T>
Change heuristic?

Edit: In the patch file (simwerkz.cc), you can found the code I used for testing (commented out).

[Dwachs]

the results look promising!

The worst case scenario I can imagine is, if the routes for different start/end tiles differ completely, so that the search has to explore double as much tiles.

[prissi]

I think, the forward backward feature is no longer needed. Its main effect were different bridges (since those started on different tiles then) and the first curve. However with the new bridge implementation and with several start tiles there will be only very special cases where it makes a difference. Thus skipping the forward-backward and using an array as start we can keep almost everything the same but smarten up AI.
For the endtile a rectangle heuristics may be best. Only for abs_distance<2*size there will be checks for zielpos.is_contained().

The main problem arises, when an AI tries to connect two 500 tiles away factories. If this takes 20s, this means that for 20s no user interaction is possible. The game continues, the mouse is frozen and keystrokes also do not work. Therefore my feeling is to keep it as short as possible without loosing too much gain.

Also rail AI need better station placement; probably this is even more urgent but also more difficult. For this a target rectangle is needed with a value for the last straight tiles. Maybe then a real AI only routefinder is needed with its own tile list to avoid freezing the user interaction. Then also "expensive" stuff like terraforming can be considered.

[gerw]

I think, the forward backward feature is no longer needed.

You get me wrong, I didn't mean the 'REVERSE_CALC_ROUTE_TOO'. I (want to) said, that if you have only several starting tiles, but only one end tile, you have to do two searches: First A -> B, to find the best tile at B and then B -> A, to find the best tile at A, however, it's possible, that you don't find the best combination of tiles at A and B.

Its main effect were different bridges (since those started on different tiles then) and the first curve. However with the new bridge implementation and with several start tiles there will be only very special cases where it makes a difference.

That isn't true in general. The current implementation isn't perfect: It won't find a road connection A->B, but finds B->A in the appended screenshot.

For the endtile a rectangle heuristics may be best. Only for abs_distance<2*size there will be checks for zielpos.is_contained().

I'm not sure, if this is needed. A heuristic, which is 0 on the rectangle (resulting in an BFS), would be sufficient, imho. And maybe a heuristic, as you suggest, isn't a monotinic heuristic for A*.


Does the ANode-array in route.h takes 19MB (max_route_steps = 1,000,000), or I am failed with simple arithmetic? Then much memory would be needed, if every AI gets its own routefinder. But it's a very elegant idea. Maybe we should think of one array for the player and one for all AIs?

[Dwachs]

I splitted the topic.

Please continue there the discussion about custom path finding algorithms for ai's.

[prissi]

Then several starting tiles and ending tiles with a heuristic when to check for ending tiles (i.e. an ending reactagle) is needed. Maybe also add additional support that the first x tiles must be straight and on the same level to accout for trains too?

[gerw]

Maybe also add additional support that the first x tiles must be straight and on the same level to accout for trains too?

But also the last x tiles have to be on a straight line. I think this rather complicated (or even impossible) with the current implementation of A*. A correct implementation of A* has to consider the last x tiles of each tile.

[prissi]

For the first n-tiles to be straight is simple. And for the last tiles to be straight: This can be entered into the same heuristics which check for reaching the final square region.

[gerw]

For the first n-tiles to be straight is simple.

But it's not simple, if you allow multiple starting tiles, is it?

And for the last tiles to be straight: This can be entered into the same heuristics which check for reaching the final square region.

Can you explain this further?

Edit: New measurements with rectangle heuristic (now 50 routes):
7x7 -> 7x7: 23s
1x1 -> 1x1: 20s
unpatched: 21s

Any further objections?

Edit: 100 routes, without sync_steps:
7x7 -> 7x7: 36s
1x1 -> 1x1: 30s
unpatched: 32s

Edit: appended patch file. It still contains the commented code for testing the speed of the wegbauer.
@z9999: Are there still any crashes?

[prissi]

Your profiling seems very good.

Enforcing straight track is easy. Search depth is know, thus for the second and until n-1 tile no curve is allowed. Can be even enforced by the costs ...

[z9999]

@z9999: Are there still any crashes?

Yes.
As the first report, it failed to find road vehicle, then road_weg is NULL.

Message: do_ki():   rail vehicle 055D8028
Message: do_ki():   road vehicle 00000000

[gerw]

Do you use a clean pak64? Does the unpatched version crash, too? I don't touched these parts of the code. However, there should be enough checks, to avoid a crash. I have no clue what's going on...

[z9999]

I'm using default pak64-102.

[Dwachs]

@z9999: does this solve the crash?

[gerw]

Enforcing straight track is easy. Search depth is know, thus for the second and until n-1 tile no curve is allowed. Can be even enforced by the costs ...

I think it isn't that easy. Have a look at the screenshot. You want to calculate a route (with 3 straight tiles) from (A, B, C) to (D), which is located somewhere in the north. First you do a step for A and B, but you can't continue due to the slope. But you also can't find the route starting in C, because the tiles A and B are already marked.

I don't have a clue, how to handle this. All approaches I had fail in some situations...

[prissi]

One could add basic terraforming to the AI waybuilder ...

[gerw]

Then you fail if there is not a slope but a house (or something else).

[prissi]

Well, but then the wayfinder could not consider this tile ...

[z9999]

@z9999: does this solve the crash?

I don't know.
Your patch don't work with gerw's patch. So, I can't test it.
My problem happens only with gerw's patch.

[Dwachs]

I don't know.
Your patch don't work with gerw's patch. So, I can't test it.
My problem happens only with gerw's patch.

Your reports however look like the crash happens in another function, ai_goods::step. It seems that some errors are not caught the right way.

[gerw]

Well, but then the wayfinder could not consider this tile ...

Which tile?

I thought about this problem (rail station placement) the whole last week, but I don't think there is an easy solution. Every solution I had, failed in some special cases. These cases might not occur often in games, but I didn't like to include something, which doesn't work in some cases.

Maybe you could include the current patch and then we can fumble with the rail station placement.

[prissi]

Sorry but this patch has non-resolvable conflicts in wegbauer. Could you please use svn diff against current version. Thank you.