YAPF - Testers needed!

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

prissi · Post by **prissi** » 24 Sep 2006 09:11

Are there really any meaningful routes which passes the same tile twice?

Otherwise the number of tiles is much smaller. I most of my tries 98% of the routes are covering less than 10% of the tiles. The number of tiles could be a user configurable preset. The standard simutrans preset is 100000 nodes which works well even for 2048*2048 maps.

Even more, with 64Bit a pointer takes 8Bytes, thus any node will be at least 8+3+1+2+2+2=16Byte large, which is twice the size of an array. But I understand your concerns, and if memory was the most import consideration, the dynamic lists will be of course better in most cases.

EDIT:
I did some benchmarking on a rather small 256*256 map (using simutrans) with sorted heaps (insert slower, removal very fast), binary heap (everything balanced), HOT queues with sorted heap at the lowest pocket (HOT sort) and HOT queue with binary heap at the to pocket.

(route length was 453 tiles around a big peninsula sw/ne)
(24700/36500 tiles tested with different routes to them)

BINARY HEAP: 36/51ms
SORTED HEAP: 38/60ms
HOT queue with binary heap: 37ms/59ms
HOT queue with sorted heap: 41/68ms

Some with much two much longer paths (only binary heap vs. HOT queue with binary heap) with
binary heap:
HOT queue: 177/122 and 296/291

Now also I am convinced you have choosen the right heap organisation. It may be that the HOT queue with binary heap will at some point overtake the binary heap but the gain is very small.

bobingabout · Post by **bobingabout** » 04 Oct 2006 07:52

i was having a game with nightly r6504, and yapf gave me some problems. see attachments. the first 1 shows the route. first stop is to a station where there is no direct route from the depot. the 2 other attachments show the paths both NPF and YAPF took.

as you can see, with YAPF, the train never makes it to its first stop

KUDr · Post by **KUDr** » 07 Oct 2006 20:48

bobingabout: YAPF doesn't support 'ping-pong' using dead ends. It supports passing through depots, but not eol bouncing. Try to place one more depot at the crossing in front of 'Nanville Mne' station.

bobingabout · Post by **bobingabout** » 09 Oct 2006 14:14

i fixed it by adding an exta line, see where the brown tile is? that was a link seperated by a signal, to allow the 2 end bridged to act as a loop.

if you allow depot ping-pongs, you should allow station ping pongs, the shown setup works fine with npf, i'd expect it to work very sumular with yapf. i beleave the original path finder would ping-pong (because it was dumb, but it still worked).

KUDr · Post by **KUDr** » 11 Oct 2006 20:49

bobingabout: I am sorry, but I must disappoint you again. NPF doesn't support station bouncing as well. Only the depot bouncing is supported (same as YAPF). While NTP doesn't support any of them (no planned bouncing at all).

Both NPF and YAPF try to get as close as possible to the destination. But algorithms are bit different. So in some cases the final decision can differ. Then it can happen that one of them will accidentally get into station and will reverse. Then the train finds its way. The other one (YAPF in this case) makes different decision with very different result. So the bouncing you see in your example is not planned bouncing. It is accidental bouncing.

I hope you understand me better now (sorry for my english).

bobingabout · Post by **bobingabout** » 12 Oct 2006 07:37

i prefer NPF's solution

KUDr · Post by **KUDr** » 12 Oct 2006 13:38

hehe, what solution? That it accidentally decides differently in your particular map? Or that it is slower? Or better at all? What solution do you mean?

(like little boy, that declares that he prefers one toy, but plays only with another one)

bobingabout · Post by **bobingabout** » 12 Oct 2006 13:54

yapf decides that if it can't find a DIRECT route to go to another DEPOT, therefore it PING PONGS FOREVER between depots

npf decides that if it can't find a DIRECT route, to head in the general DIRECTION, which leads it to a DEAD END station, where it can turn around and go to where it was suposed to.

the 2 solutions are "Depot" for YAPF or "Direction" for NPF. the NPF 1 is a far better solution, because it gets you there in the end.

Brianetta · Post by **Brianetta** » 12 Oct 2006 15:19

prissi wrote:Are there really any meaningful routes which passes the same tile twice?

Yes. These meaningful routes involve loops of track which either cross themselves, or which feed back the way that they came. For example, a sharp left turn which is made possible by a larger loop to the right, or an end-of-line loop to allow a train on two-way single track to route to stations behind it:

Transport Tycoon Forums

YAPF - Testers needed!

Who is online