Skip to main content ↑ ↓
Topic: [patch] Station placement (road) for AI (Read 16067 times) previous topic - next topic

[patch] Station placement (road) for AI

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.

Re: [patch] Station placement (road) for AI

Reply #1 –
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.

Quote
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

Quote
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

Re: [patch] Station placement (road) for AI

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

Re: [patch] Station placement (road) for AI

Reply #3 –
Quote
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.

Re: [patch] Station placement (road) for AI

Reply #4 –
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 ...)

Re: [patch] Station placement (road) for AI

Reply #5 –
Quote from: z9999 – on
#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...

Quote from: prissi
(ANd there seems to be some changes too, which are not directly patch related, imho. No big deal though ...)
What do you mean?

Re: [patch] Station placement (road) for AI

Reply #6 –
The first three patches should not bee needed.

Re: [patch] Station placement (road) for AI

Reply #7 –
Quote from: gerw – on
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 ?

Re: [patch] Station placement (road) for AI

Reply #8 –
Quote from: prissi – on
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.

Re: [patch] Station placement (road) for AI

Reply #9 –
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 p****ed 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.

Re: [patch] Station placement (road) for AI

Reply #10 –
Quote from: prissi – on
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 p****ed 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.

Re: [patch] Station placement (road) for AI

Reply #11 –
Quote from: prissi – on
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?
Parsley, sage, rosemary, and maggikraut.

Re: [patch] Station placement (road) for AI

Reply #12 –
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.

Re: [patch] Station placement (road) for AI

Reply #13 –
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).

Re: [patch] Station placement (road) for AI

Reply #14 –
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.
Parsley, sage, rosemary, and maggikraut.
 

Re: [patch] Station placement (road) for AI

Reply #15 –
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.

Re: [patch] Station placement (road) for AI

Reply #16 –
Quote from: prissi – on
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.

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

Quote
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?

Re: [patch] Station placement (road) for AI

Reply #17 –
I splitted the topic.

Please continue there the discussion about custom path finding algorithms for ai's.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] Station placement (road) for AI

Reply #18 –
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?

Re: [patch] Station placement (road) for AI

Reply #19 –
Quote from: prissi – on
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.

Re: [patch] Station placement (road) for AI

Reply #20 –
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.

Re: [patch] Station placement (road) for AI

Reply #21 –
Quote from: prissi – on
For the first n-tiles to be straight is simple.
But it's not simple, if you allow multiple starting tiles, is it?

Quote
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?

Re: [patch] Station placement (road) for AI

Reply #22 –
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 ...

Re: [patch] Station placement (road) for AI

Reply #23 –
Quote from: gerw – on
@z9999: Are there still any crashes?

Yes.
As the first report, it failed to find road vehicle, then road_weg is NULL.
Quote
Message: do_ki():   rail vehicle 055D8028
Message: do_ki():   road vehicle 00000000

Re: [patch] Station placement (road) for AI

Reply #24 –
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...

Re: [patch] Station placement (road) for AI

Reply #25 –
I'm using default pak64-102.

Re: [patch] Station placement (road) for AI

Reply #26 –
@z9999: does this solve the crash?
Parsley, sage, rosemary, and maggikraut.

Re: [patch] Station placement (road) for AI

Reply #27 –
Quote from: prissi – on
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...

Re: [patch] Station placement (road) for AI

Reply #28 –
One could add basic terraforming to the AI waybuilder ...

Re: [patch] Station placement (road) for AI

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

Re: [patch] Station placement (road) for AI

Reply #30 –
Well, but then the wayfinder could not consider this tile ...

Re: [patch] Station placement (road) for AI

Reply #31 –
Quote from: Dwachs – on
@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.

Re: [patch] Station placement (road) for AI

Reply #32 –
Quote from: z9999 – on
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.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] Station placement (road) for AI

Reply #33 –
Quote from: prissi – on
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.

Re: [patch] Station placement (road) for AI

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