YAPF - Testers needed!

mart3p · Post by **mart3p** » 17 Jul 2006 15:58

I have found a bug when using YAPF for road vehicles. Vehicles trying to find a depot, can be sent to an opponent's depot if that is nearest. In the attached test savegame, one of the AI's buses (green vehicle 4) is continually trying to enter one of my depots. It is unable to enter so loops around and tries again.

If I switch off YAPF for road vehicles, it fixes the problem.

This is a great way of sabotaging the opponent's road vehicles but I‘m sure it‘s not intended.

I’m using the nightly build at r5508.

Panzerfather · Post by **Panzerfather** » 20 Jul 2006 20:22

Got a bug which ends in a fatal error:

openttd: yapf/hashtable.hpp:228: void CHashTableT<Titem_, Thash_bits_>::Push(Titem_&) [with Titem_ = CYapfRailNodeT<CYapfNodeKeyExitDir>, int Thash_bits_ = 10]: Assertion `&slot.Find(new_item.GetKey()) == __null' failed.

Added the savegame, the game crashes around the 8th October.

mart3p · Post by **mart3p** » 22 Jul 2006 15:07

KUDr: While working on my patch to implement drive-through road vehicle stops, I came across a few problems with YAPF. Some, I have already reported in posts above, but I thought it might be useful for you to see the solutions I came up with. I'm not sure that my changes/hacks are the correct way to fix these problems, but thought they might at least show you where the problems are.

1. Road vehicles preferring bends (as reported above).
Making the cost for road bends YAPF_TILE_LENGTH + 2 seems to work ok. Of course it would be best to make '2' a 'road_curve_penalty' config setting.

2. Road vehicles finding opponents depot (as reported above).
I added a line to FindNearestDepot in yapf_road.cpp, that returns false if the depot found, is not owned by the vehicle's owner. It would be better to only search for the owner's depots in the first place but I couldn't see an easy way of doing that.

Code: Select all

 Node& n = Yapf().GetBestNode();
   TileIndex depot_tile = n.m_segment_last_tile;
   assert(IsTileDepotType(depot_tile, TRANSPORT_ROAD));
+  if (!IsTileOwner(depot_tile, (Owner)v->owner)) return false;
   Depot* ret = GetDepotByTile(depot_tile);
   return ret;

3. Multistop problem.
In function YapfRoadVehDistanceToTile in yapf_road.cpp, the scaling of the distance returned by the function is 10 times what it should be. There is a TODO note already in the code regarding this.

Code: Select all

// TODO: change road YAPF unit from 10 to YAPF_TILE_LENGTH

To determine which road stop bay to use, Multistop uses the returned distance plus a weighting based on the number of vehicles already using the bay. Because the returned distance is 10 times the correct value, this has the predominant effect. Replacing the values of 10 with YAPF_TILE_LENGTH, fixes the problem.

4. The goto depot command is not always working for road vehicles.
This is not a YAPF problem but effects YAPF's depot finding. See bug report at: http://bugs.openttd.org/task/249 There is a note in the code in SetOriginFromVehiclePos:

Code: Select all

// sometimes the roadveh is not on the road (it resides on non-existing track)
// how should we handle that situation?

- this bug is why it happens.

Darkvater · Post by **Darkvater** » 01 Aug 2006 13:00

Thank you for the comment on SourceForge mart3p. I will leave this up for KUDr to look over and fix when he comes back.

Please also close any bugreports then.

Luckz · Post by **Luckz** » 02 Aug 2006 11:46

mart3p wrote:2. Road vehicles finding opponents depot (as reported above).
I added a line to FindNearestDepot in yapf_road.cpp, that returns false if the depot found, is not owned by the vehicle's owner. It would be better to only search for the owner's depots in the first place but I couldn't see an easy way of doing that.

But what if you enable the option to let vehicles actually use other players' depots? IMO it would be advisable to have it check for that option.

mart3p · Post by **mart3p** » 02 Aug 2006 16:28

Luckz: I presume you are referring to the "Allow depot sharing" option for the subsidiaries patch in the MiniIN. My bug report above is relating to the trunk code which doesn't have this option.

But thanks for pointing this out anyway. I will check if depot sharing is working using YAPF in the MiniIN and I'll post a MiniIN fix if a change is required.
Edit: I've checked the MiniIN code and YAPF depot finding does check the "depot sharing" option.

Darkvater · Post by **Darkvater** » 14 Aug 2006 22:37

mart3p wrote:2. Road vehicles finding opponents depot (as reported above).
I added a line to FindNearestDepot in yapf_road.cpp, that returns false if the depot found, is not owned by the vehicle's owner.

r5897

mart3p wrote:4. The goto depot command is not always working for road vehicles.
This is not a YAPF problem but effects YAPF's depot finding

r5898

I've added these two fixes as KUDr seems away for a very long time and didn't feel appropiate to wait any longer as there are working fixes for these. When you (KUDr) get back, you can refine these commits if you like.

Thank you mart3p for the patches.

suikerpluimpje · Post by **suikerpluimpje** » 22 Aug 2006 14:18

I've bin using yapf for a savegamae with more then 800 vehicles, and the started to slow down after about 750 vehicles.

With the normal pathfinding meganism, the game would have been unplayable.

I realy like YAPF.

Now, the only thing I need to do is find a way to create highway's...

KUDr · Post by **KUDr** » 26 Aug 2006 23:32

mart3p: thanks a lot for your hard work on YAPF. Just fixed the
2. Road vehicles finding opponents depot (r6160)
so, that it doesn't fail to find the depot if opponent's depot is closer.

the rest I'll check soon (hopefully)

Edit: done (r6162-3, r6164)

KUDr · Post by **KUDr** » 27 Aug 2006 09:57

Panzerfather: r6166 /trunk/yapf/yapf_base.hpp: -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)

Mateo · Post by **Mateo** » 27 Aug 2006 17:09

Does YAPF set any penalty for railroad crossings? Preferably there should be a seperate penalty value for each four railway type. Obviously maglev crossings should have the highest (and actually a very high) penalty.

Please see the attached screen shot. At least with maglev and monorail crossings road vehicles should prefer the tunnel route. Also it would be nice if the road is blocked, vehicles should try to find alternative path.

Tested with r6176.

KUDr · Post by **KUDr** » 27 Aug 2006 19:26

Mateo: When the alternative (safe) way is significantly longer (>3 tiles) than the direct one (or it contains curves/ slopes) than its cost is higher than the cost of unsafe way. So your truck driver will prefer the unsafe way.

Try to make the path with tunnel shorter than the other path with crossing. Or you can increase config/yapf/road_crossing_penalty value from 300 to 800 or even more.

mart3p · Post by **mart3p** » 31 Aug 2006 21:47

The problem of road vehicles preferring bends has reappeared. It seems that the line in settings.c:

Code: Select all

SDT_VAR     (Patches, yapf.road_curve_penalty, SLE_UINT, NS, 0, 1 * YAPF_TILE_LENGTH, 0, 1000000, STR_NULL, NULL),

was removed by the changes made at r6186. It also seems that the change from SDT_CONDVARs to SDT_VARs made at r6174 was also reverted by r6186.

RiTi · Post by **RiTi** » 31 Aug 2006 22:01

In the CFG file there are all settings for YAPF. Maybe I have missed a topic or a message, but is there a explanation for these settings (what/where do they all stand for)?

KUDr · Post by **KUDr** » 01 Sep 2006 07:48

mart3p: yes, i see. But don't understand why. Probably by accident. Ask Rubidium on IRC.

Edit: rubidium * r6296 /trunk/settings.c: -Fix (r6186): some more (YAPF) settings were affected by accident. Thanks to mart3p for noticing (and to SVN for failing to mark the changes as conflicts).

RiTi: yes. Names of variables should be self-explanatory for anybody who knows how A* algorithm works. If not, tell me and i can add more comments into settings.c.

DaleStan · Post by **DaleStan** » 01 Sep 2006 09:38

"For anybody who knows how A* algorithm works".

Wonderful. And for those of us who don't, like me? Or Aunt Tillie[0]? Is she required to learn the A* algorithm, or are you going to write appropriate comments into openttd.cfg (not the source)[1] so she has half a chance of figuring it out for herself?

"Allow your users the luxury of ignorance." -Eric S. Raymond, TAOUU

[0] If you're programming anything that an end user might possibly interact with, and you don't know who Aunt Tillie is, you should probably go read TAOUU. This post will still be here when you get back.

[1] This bears repeating. Document openttd.cfg in openttd.cfg, *NOT* *IN* *THE* *SOURCE*. If you want Aunt Tillie to be able to use yapf_option_foobar_138_21_gamma, put the documentation, or at the very least, a brief summary, within a few lines of yapf_option_foobar_138_21_gamma, not at the other end of a grep on another file that she doesn't even have, and probably didn't even know exists, and probably didn't want to know.

KUDr · Post by **KUDr** » 01 Sep 2006 12:10

DaleStan: I can be wrong, but I think that openttd.cfg still doesn't support comments. Last time when I discussed it with developers, I was told, that openttd.cfg is not something the regular user should interact with. Therefore there is no reason to support comments in cfg. If you don't agree, discuss it somewhere else please as it has nothing to do with YAPF.

If I am wrong and you show me the way how I can comment YAPF options in the cfg (so that they appear automatically when you start and exit the game) then I will do it. Otherwise I can document it only in the source.

If you are so ignorant and don't bother to read any A* article to understand it, then:
1. you should not change any of those settings
2. it should be enough for you to switch YAPF on/off for each of 3 transport types using UI
3. any explanation of those setting I can give you would not help you as it will require some level of A* knowledge

Edit: forgot to answer. Your Aunt Tillie doesn't need to understand cfg file at all. The only what she needs to understand is that green button means ON and red button means OFF. But she would never ask "is there an explanation for these settings?".

Post by **Rubidium** » 01 Sep 2006 13:31

mart3p wrote:The problem of road vehicles preferring bends has reappeared. It seems that the line in settings.c:
Code: Select all
SDT_VAR     (Patches, yapf.road_curve_penalty, SLE_UINT, NS, 0, 1 * YAPF_TILE_LENGTH, 0, 1000000, STR_NULL, NULL),
was removed by the changes made at r6186. It also seems that the change from SDT_CONDVARs to SDT_VARs made at r6174 was also reverted by r6186.

That happened due to the fact that I started the fix of r6186 before 6174 and the revision that added the road_curve_penalty to the settings. I have updated to the latest revision before committing and SVN failed to notice that there was a conflict and it 'just' ignored the changes KUDr made, which resulted in the fact that I effectively reverted them.
This reversion is fixed in r6296.

prissi · Post by **prissi** » 15 Sep 2006 17:36

Since I did a lot of work with the simutrans wayfinder, I was curious and had a look at YAPF.

Did you ever compared with a single array of node pointers and a bitmap (for visited tiles) instead of a binary heap? In all my trys for a more or less worst case map in simutrans (1024*1024 with only a single path of 2560 tiles for a ship between two towns close together and thus about 75% of the map tiles need to be accessed) the array was 4-12 times faster than the binary heaps or a single list. (On my machine, Athlon 1700 with 750000 tiles visited with an array it took about 4-6s and with a binary heap about 24s.)

Imho, this is due to the linear data reprensentation, which is gentle to look ahead caches and the pipeline for copy/move operations (even though they are o(n/2) in theory), as long as the array is in the cache, new/delete and move can be very fast.

Even brute force search through linked pointers or through an array (both needed) the array is much faster, like a factor of 3-4. (Maybe, because the pipeline have to wait for the address to arrive before able to try with the next while the next array address could be calculated and already loaded.)

However, I have to admid, that I did not completely could follow the pathfinder with it many subclasses and thus to try this myself.

KUDr · Post by **KUDr** » 23 Sep 2006 08:51

prissi: it could be faster in some cases, yes. But having single array of all nodes instead of list of visited nodes would mean in worst case to allocate and maintain 48M nodes (2048x2048x12trackdirs) in one block. Suppressing one node size to occupy minimum (4 bytes) it is still 200MB of memory. It is wasting of memory (the most valuable resource). Such array can't fit to any cache, but paging could happen much more often if you have not enough physical memory. So it would be faster on newer PCs with enough memory and slower on older PCs.

The memory consumption was one of the most offten questions i received during YAPF development. It was considered critical. Ships need much faster algorithm that can do the job without having to visit so many nodes. Improving speed 4x on good PCs doesn't help much.

If you think you can write faster PF for ships in OTTD, feel free to try it. If it will work and will be way faster, everybody here will support you i guess (including me).

Transport Tycoon Forums

YAPF - Testers needed!

Who is online