OpenTTD / OpenTTD/OpenTTD

[Bug]: CalcClosestStationTile on a huge docking area makes Yapf fail pathfinding on first attempt

Open
#12,193 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

component: pathfinder
Dominant language
C++
Stars
8.3k
Forks
1.3k
Avg merge
1d 20h
Merged PRs (30d)
37

Description

Version of OpenTTD

20240228-master-gc4f9479507

Expected result
  1. CalcClosestStationTile (or some other) should return all of the 8 docking tiles.
  2. High level pathfinder returns a path towards the east side.
  3. Low level pathfinder estimate cost is computed for each of the 8 destinations.
  4. Low level pathfinder finds the optimal path on attempt 0, a path towards the southwest side.
Actual result
  1. CalcClosestStationTile returns a single tile and it happens to match ship's current position.
  2. High level pathfinder returns a path towards the east side.
  3. Low level pathfinder fails to return a path on attempt 0. It is trying to pathfind to the ship's current position.
  4. Low level pathfinder finds an unoptimal path on attempt 1, restricted to a corridor. The path towards southwest would be the shortest should the low level pathfinder not fail on attempt 0.
Steps to reproduce

dock station spread.zip
The ship leaving the depot is inside the huge docking tile area of the dock station and wants to find the shortest path to it. Only 8 tiles are actual docking points for the ship, and they are in 3 separate water regions. The 3 docks belong to the same station.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the case with the attached dock station spread.zip save and trace CalcClosestStationTile together with the high- and low-level pathfinders. Compare the first and second pathfinding attempts against the four expected results, including all eight docking tiles and the optimal southwest route. Done means the first attempt evaluates the valid destinations and finds the optimal path.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
game-dev
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.