Freeze and eventually crash when "There is no way."

[Steini64]

Steps to reproduce (include any configuration/script required to reproduce)

1. Click on any unreachable tile (for example house) or island with no walkable way fast / multiple times. When it displays "there is no way" the client heavily freezes and sometimes even crashes when you keep spamming leftclick on that tile.

Environment

OS: Windows 10
Protocolversion in use: 10.77
I use a mostly unmodified, default code (maybe two months old) with slight, for this bug non-relevant changes.

The only relevant change applied to the code is the Idle-walkanimation fix for Protocolversion >= 10.10
@see #642

[iryont]

It happens because A* algorithm tries to calculate the path until it hits the limit. In general it is not a bug, but since those calculations are quite heavy it takes a while for A* to come up with a result.

The general fix to parallelize A* calculations is not a trivial task. I will leave it open until someone rewrites it though.

[Steini64]

Hmm that makes sense, thats for the explanation!

I have another idea, wouldn't it help to write a handler that only permits one A* Calculation at a time and other attemts will be rejected or better said the action will be canceled? (Similar to the next-action-delay in the server)?

The calculation goes afaik only for the path-find of the own player when you click somewhere on the map right? So there is maybe no need for full asynchronous execution / handling because you have no use of multiple paths at the same time anyway. You can only follow one path at once.

I will try what I can accomplish and eventually contribute my results later.

[gesior]

@iryont

1. Why A* executes so long? On server it executes findPath very often and it all goes in main thread of server without any lag.
   Is it because there are black tiles and A* search until limit of complexity?
   Maybe some 'check % of black tiles in square fromPos to toPos and reduce maximum complexity' hack would work?

2. Why client freezes? Is it because GUI somehow queue mouse clicks or 'findPath' calls while other 'findPath' is running? Is client freezed for time of execution of findPath?
   Maybe there is a way to detect these multiple calls and show some message in client, not call findPath so often?

---

Question to some pro: Is GUI (LUA) in other thread then 'findPath' calls?

[iryont]

Game server does calculate the path within the creature view only, so it is hardly a demanding task. However, in the game client we do calculate a lot more outside the visible rectangle. The growth of tiles is exponential, so it becomes a problem.

The only reason we do calculate path beyond visible rectangle is to know whether the path is findable in the first place. The game client doesn't use all of those calculated tiles later on, in fact, it discards every tile beyond visible rectangle or it limits them to 127 tiles if those tiles were seen before and it calculates the path again with the same mechanism over and over again until we hit the destination.

The game client is frozen until the calculations are complete.

I suppose a few tricks would be enough to make it work much better, but I haven't thought about it yet.