Darkvater wrote:

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?

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment121

matthijs wrote:

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.

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment122

Darkvater wrote:

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.

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment123

Darkvater wrote:

Problem seems even more serious: OpenTTD crashes (in that game) if NPF is enabled on a 64bit platform.
Link: http://www.tt-forums.net/viewtopic.php?p=409074# 409074

According the the crash-report the crash happened in the function:
0001:000172b4 @NPFSaveTargetData@8 004182b4 f npf.obj
NPFSaveTargetData()

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment128

DmitryKo wrote:

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

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment131

KUDr wrote:

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.

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment207

Darkvater wrote:

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.

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment249

Darkvater wrote:

proposed fix by blathijs.

Attachments

• noshipnpf.diff (2.46 KiB)

This comment was imported from FlySpray: https://bugs.openttd.org/task/57#comment261

Darkvater closed the ticket.

Reason for closing: Fixed

r4896 - disabled NPF

This comment was imported from FlySpray: https://bugs.openttd.org/task/57