FS#57 - (Ship) Pathfinder problem

Attached to Project: OpenTTD
Opened by Darkvater (Darkvater) - Tuesday, 21 February 2006, 01:01 GMT
Last edited by Celestar (Celestar) - Friday, 28 April 2006, 08:52 GMT
Type Bug
Category Core
Status Closed
Assigned To Matthijs Kooijman (matthijs)
Operating System All
Severity High
Priority Urgent
Reported Version trunk
Due in Version 0.4.8
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


Ship pathfinder can't find route to the destination (Ship 21 for player #3, but that becomes clear from the debug messages). Sure, this can be solved by increasing npf_max_search_nodes from the default of 10.000 but already at 10.000
there ARE still SERIOUS PERFORMANCE ISSUES with the ship pathfinding. It's not so nice when already a 512x512 map lags on my 1.8GHz Pentium M and the ships can't even find their destination (On 0.4.5 full-extra release build btw).

Any chance of further improvements?

The link to the forum post is at:
This task depends upon

Closed by  Darkvater (Darkvater)
Tuesday, 16 May 2006, 21:38 GMT
Reason for closing:  Fixed
Additional comments about closing:  r4896 - disabled NPF
Comment by Darkvater (Darkvater) - Tuesday, 21 February 2006, 14:37 GMT
I had an interesting comment from Tron on IRC. If I/he is not mistaken a pathfinder_node_max of 10.000 (which is set in the configuration file) searches a maximum of 10.000 tiles around the ship, right? That means an area of 100x100 tiles.
If this is so, something is severly broken as
1. the destination is closer than 100 tiles away
2. a big part of the area is land, so unaccessable to the pathfinder.

If this is not so I think it is a good idea to make it so. When you add a destination then you can check if the distance is bigger than the max_pf_nodesearch setting and given an error/warning?
Comment by Matthijs Kooijman (matthijs) - Tuesday, 21 February 2006, 19:54 GMT
The 10.000 nodes do not mean that it is limited to a 100x100 area, since A* is a directed search algorithm. That is, it searches in roughly the right direction instead of everywhere around. IIRC the 10.000 nodes are the maximum number of nodes looked at, where each node is a tile/track combination.

There used to be a limit on the distance between orders for ships, but that limit was removed for NPF, since there was no node or path length limit. After that NPF performance issues arose, and the node limit was introduced as a temporary solution. So far, I haven't been able to improve this further (have not had the time to work at it, that is), so perhaps restoring the limit between is a good idea. It should be a trivial change, removing one if, probably. People can still use buoys to bridge bigger distances.
Comment by Darkvater (Darkvater) - Tuesday, 21 February 2006, 19:58 GMT
So if it is a directed search, the results are even more worrying. It should be able to find the target even more easily than a pond-algorithm.
Comment by Darkvater (Darkvater) - Wednesday, 22 February 2006, 18:43 GMT
Problem seems even more serious: OpenTTD crashes (in that game) if NPF is enabled on a 64bit platform.

According the the crash-report the crash happened in the function:
0001:000172b4 @NPFSaveTargetData@8 004182b4 f npf.obj
Comment by DmitryKo (DmitryKo) - Tuesday, 28 February 2006, 20:21 GMT
It looks like the crash only reproduces itsels in OTTD 0.4.5 release binary from SourceForge, under both x64 and 32-bit Wndows XP. The latest nightly binaries and my own source code builds do not crash at all. Also, it looks like it has nothing to do with hardware Data Execution Prevention, because there's no DEP dialog shown, ever, and even the exceptions do not pop-up in most cases - the game just crashes silently.

It looks like it's a bug in MSVC 6 and its scope is limited to NX-bit capable processors... I guess I need external symbols for the 0.4.5 binary to actually debug against the source code, so if you're able to relink the OBJ files from the release with .PDB option enabled, maybe it would shed some light on the issue...

Comment by KUDr (KUDr) - Tuesday, 18 April 2006, 14:12 GMT
To uncover the 10.000 nodes mystery: each node is specified by a combination of TileIndex/Trackdir, not only TileIndex itself. So it can't cover 100x100 tiles area, but much less (like 30x30 tiles). I think that NPF works quite well for ships (at least my yapf type 1 has the same results, only they come bit faster). Type 2 seems to be better (can cover area like 50x50 tiles) since it uses different node model (TileIndex/ExitDir). But still the same problem - running it without limit takes seconds to find one long path. It will need something radically new. Not only different implementation of the same algo.
Comment by Darkvater (Darkvater) - Tuesday, 02 May 2006, 15:13 GMT
A good solution would be to just totally disable NPF for ships in 0.4.8 so it is not even possible to turn it on for them. Should actually make NPF usable again in combination with ships.
Comment by Darkvater (Darkvater) - Friday, 05 May 2006, 22:59 GMT
proposed fix by blathijs.