Openrct2: Pathfinding problems when guests going home; No Entry signs involved

[chess123mate]

OS: Windows 10
Version: v0.1.2-develop
Commit/Build: d91fd13

Certain configurations of No Entry signs and/or stalls cause the guests who are trying to go home to get stuck in loops.

Reproducible in RCT2 (vanilla)? (I don't know; I can't load up the park in vanilla due to "lack of add-on" and didn't want to recreate it by hand at this time - I tried a smaller version in OpenRCT2 that I would be able to load up in vanilla, but couldn't get it to work)
Multiplayer? (Haven't tested)

Save game: Forest Frontiers - Pathfinding Glitch.zip

Cheats were used in the Save Game (Forest Frontiers) to manipulate the guest statistics (including initial money, current happiness/money/etc) and to spawn in a large number of guests; I might have enabled ones that allow a large number of trains/car and the unlock of operational limits as well.

Screenshots:

Same park with paths invisible:

As shown in the screenshots, the guests are stuck walking between the tile to the lower-left of the Information Kiosk and to the tile in front of the Balloon Stall (the left-most Balloon Stall, ignore the other one for this bug). If a guest has a park map, they check it at each end of this short walk. They start to find their way to the exit if any of the following happen:

• Information Kiosk is removed
• Balloon Stall is removed (though for this one, they take a very round-about way to get to the exit)
• Removing any path adjacent to the 2 tiles they are stuck on except the one on the other side of the No Entry sign 1 tile directly left of the Balloon Stall (you can also delete either path they're stuck on)
• There are a large number of No Entry signs that can be disabled/removed that let the guests escape the problem area:

Every sign with a yellow star on it, you can disable/remove and the guests will immediately go to the exit with the quickest route - even when it's the signs in the bottom of the screenshot, where the guests don't even go through those signs.

I'm not sure how, but certain combinations of disabling (and maybe re-enabling) let them escape into a much larger loop (though there are also lots of guests still stuck in the original 2-tile section):

(Edit)

Here's about as much of the park as I could remove while still exhibiting the bug:

After further experimentation, I discovered that if you delete the problem area (the 2 tiles they're stuck on) and then rebuild it exactly the same, the bug disappears in the simplified version and is partially fixed in the original (in the original, the guests are no longer stuck on those 2 tiles, but they are stuck in a larger loop (the same one you can see the guests walking in in the last screenshot in the original post)). I can't figure out how to recreate the bug after deleting those 2 tiles (other than reloading the save).

[duncanspumpkin]

This is hardly an issue. If you create a complex park peeps can't find there way. The solution is to not create such a complex layout. At some point we do plan to improve the path finding. At the same time though we will not make it perfect as that is not realistic and it would break some of the strategy of the game

[zaxcav]

I agree that the path finding should not be perfect. Imperfections should be by design though, and that's not the case here.
This is a genuine fault with how I handle no entry signs in the "junction" detection of the heuristic search.
Details for those interested:

I assume that a path is a junction when it has more than 2 exit edges, since a junction needs 1 entry edge with a choice of 2 or more different exit edges. This works fine where no "no entry" signs are on the path element because every exit edge will also be an entry edge. However it's wrong when "no entry" signs are involved, because there will be entry edges that are not exit edges. Accounting for "no entry" signs correctly, a path element is a junction when the total exit edges plus the used entry edge is more than 2.
Edit: even the above explanation is overly complex and not completely correct. A junction is simply a path element with more than 2 edges. The amount that are entry vs exit edges is irrelevant. The current code only counts the exit edges. This is wrong.

I've implemented a simple fix which resolves this, fixing the above park. However, my code base is months out of date and I want to do some regression testing before I will consider submitting a PR.

[Gymnasiast]

I disagree with the label non-bug. I do consider it a bug, so I went for a middle ground and picked discussion.

[chess123mate]

Note: I have updated my initial post with further details under "(Edit)"

I don't see how guests being stuck between 2 tiles due to pathfinding _isn't_ a bug, especially since there is so much you can delete and suddenly the guests can pathfind again (and also if zaxcav has a "fix", it's hard to claim that the fix is for something that isn't a bug).

I've had great difficulty in recreating the bug - even, as I mentioned in the above edit, when I delete and recreate the problem area (unfortunately I don't remember what I did originally to construct the area - that is, what order I built things, what I demolished, etc). If zaxcav's solution fixes code that relies on state that could potentially be reset/fixed by reconstructing the paths (or surrounding stalls), then I have no concerns. Otherwise, I wonder if there's another bug hiding somewhere. I browsed through the code and noticed that pathfinding acts differently if a path has the "wide" flag. What I witnessed is what I would expect if a "wide" flag had been set/maintained incorrectly - this would explain why rebuilding the area let the guests escape the glitch. (I'm just guessing, of course.) But is the "wide" flag modified if you delete a stall? Are there other flags in paths that are used by pathfinding and are modified by deleting No Entry signs, stalls, and other paths?

Since Gymnasiast has called it a "discussion" and it's already been brought up, I'll mention my thoughts on what duncanspumpkin has said about about the ideal pathfinding for OpenRCT2.

Realism isn't necessarily fun (there are unrealistic aspects already in RCT - ex, guests staying on paths and obeying No Entry signs; guest don't collide with each other; etc). Further, in real life I expect people to be able to adapt to complex paths (even if it takes them a while to learn the area).

RCT's path complexity limitation forces a certain level of functionality, or guests get stuck, damaging or ruining your park (unless you fix it, of course). On occasion you have to think around this limitation (fun problem solving), but a lot of the time it's led to me wanting my paths to be as straight as possible, "for the sake of the pathfinding limitations". Therefore, for the purposes of art/creativity, I think it would be better to make guests be able to handle anything, even if they have to backtrack a lot to do it. That guests would backtrack on complex paths would still lead to penalties, so sensible paths would still be encouraged, just not enforced as strictly. The code already seems to support this behaviour, though it's limited to the 4 most recently visited junctions (according to a comment I read). Theoretically, I think staff should "know" the park and be flawless pathfinders. Shouldn't guests with a map also be able to figure out where they are and pathfind correctly?

[zaxcav]

The ORCT2 pathfinding is fundamentally limited by design. It's simply not a good algorithm.
Declaring a particular behaviour to be a bug or not is not appropriate without analyzing the implementation and determining why something is happening.
I did this analysis last night and this is a bug.
The implementation does not handle "no entry" signs properly. It's close, but still wrong.
The fix for this bug is simple.
I also spent several hours regression testing the changes with the collection of save games I have that demonstrated lots of different issues in the path finding previously. Fixing this issue does not appear to otherwise degrade the effectiveness of path finding.
I will submit a PR with the fix soon.

[pizza2004]

Since this says discussion and it was already brought up, I'd like to say that while I don't think it should be 'perfect', any guest with a map should never be wandering assuming they have a destination in mind. If they encounter an area where there's more than one way to go they shouldn't automatically choose the shortest per se, but like, they should be able to pull out the map and just go where they need to.

I have less of an opinion on what would work best if they don't have a map. I think a balance should be struck between realism, simplicity, and fun. Only thing I can think of to say about it is that maybe something could be thought of that has to do with the 'line of sight' of the peeps or restricting how far ahead they can see on the path or something.

Wide paths are probably the trickiest thing I can think of to decide how to handle though.

[Gymnasiast]

The algorithm will never be perfect, because that is both complicated and expensive (in terms of CPU and RAM usage). Also, many guest do not have a destination and will walk around randomly. Finally, even if the algorithm gets too perfect, there is always the opportunity to introduce jitter.

However, I put the 'discussion' label on it because there was initial disagreement over bug status. It wasn't an invitation to discuss pathfinding in general. That would be more appropriate for the dev chat.