- 1313eresident
- Posts : 17
Reputation : 1
Join date : 2018-10-31
[RESOLVED] Pathfinding bug
Thu Jul 04, 2019 10:43 am
I have a feeling this has been reported in several other posts, but given the severity of the problem, I want to make a separate post for it.
It seems that all NPCs use an incorrect pathfinding implementation.
Whenever they need something (like, a toilet, a water dispenser or even a specific department room), they will always go to the position that has the shortest aerial distance, regardless of the walking distance towards that position.
So, for example, if you have a GP's office and a restroom right next to it, but these are not connected directly to each other, the GP will always go towards this toilet, even if it has to walk through the entire hospital to do it.
This is clearly not the way this should work, as NPCs should always go to the room that has the shortest walking distance, not the shortest aerial distance.
A good example of this is the 2nd Big Hospital sandbox.
The GPs in the Emergency department on the ground floor will always go to the toilets that are in the Cardiology and Neurology departments (ground floor) that are right behind them, even though the walking distance towards them is much higher than the walking distance towards the restrooms in the same department as they are.
Also, the game does not take into account that switching between floors with an elevator takes time, often prioritizing a restroom 4 floors higher over one at the current floor, because the aerial distance towards the first is slightly smaller than to the latter.
I would really appreciate it if this could be solved as fast as possible.
It becomes increasingly frustrating to deal with, as I have to design my hospitals in such a way that the restrooms (but also staff rooms and certain department rooms) are always at the same walking distance as their aerial distance.
What I find particularly surprising, is that there is even a sandbox hospital that has this problem in a very big way and becomes noticeable 5 minutes after starting with it.
It seems that all NPCs use an incorrect pathfinding implementation.
Whenever they need something (like, a toilet, a water dispenser or even a specific department room), they will always go to the position that has the shortest aerial distance, regardless of the walking distance towards that position.
So, for example, if you have a GP's office and a restroom right next to it, but these are not connected directly to each other, the GP will always go towards this toilet, even if it has to walk through the entire hospital to do it.
This is clearly not the way this should work, as NPCs should always go to the room that has the shortest walking distance, not the shortest aerial distance.
A good example of this is the 2nd Big Hospital sandbox.
The GPs in the Emergency department on the ground floor will always go to the toilets that are in the Cardiology and Neurology departments (ground floor) that are right behind them, even though the walking distance towards them is much higher than the walking distance towards the restrooms in the same department as they are.
Also, the game does not take into account that switching between floors with an elevator takes time, often prioritizing a restroom 4 floors higher over one at the current floor, because the aerial distance towards the first is slightly smaller than to the latter.
I would really appreciate it if this could be solved as fast as possible.
It becomes increasingly frustrating to deal with, as I have to design my hospitals in such a way that the restrooms (but also staff rooms and certain department rooms) are always at the same walking distance as their aerial distance.
What I find particularly surprising, is that there is even a sandbox hospital that has this problem in a very big way and becomes noticeable 5 minutes after starting with it.
- jan.oxymorondeveloper
- Posts : 2309
Reputation : 336
Join date : 2018-03-23
Re: [RESOLVED] Pathfinding bug
Thu Jul 04, 2019 6:38 pm
Hi, thanks for the message and the analysis!
Yes, this is a known issue/limitation, unfortunately with no easy solution. But let me try to give you some details:
When a character chooses their destination, a simple euclidean distance is used - the characters sometimes choose between dozens of objects and calculating path distance using the same algorithm the characters use to navigate around the map would easily take seconds (that's why character navigation runs on separate threads on the CPU where it can take its time without slowing the game down, and that's only one query for each character).
There might be some ways how to pre-compute at least distances between rooms which could help, but it of course gets more complicated, as patients would have to use other rules than staff and it still means computing hundreds or thousands of paths every time a wall/door/room gets placed (using a different algorithm like Dijkstra might help, but it would mean not being able to reuse much of the existing systems). We've even checked other games in the genre (like Prison Architect) to see what the usual solutions are, but it seems that everybody just lives with shortest distance. If you know about any examples, of course let us know!
Regarding the newest big hospital and the restrooms - maybe there's a workaround that we can implement, in some cases staff prefer equipment from their department (like common rooms), but I don't think it's currently enabled for going to the loo - this would probably be the best option at this point.
Btw - switching between floors always counts as a longer distance than anything on the same floor, so possibly the problem here is with reservation/capacity. Could you upload the save so we can check the specific situation?
Yes, this is a known issue/limitation, unfortunately with no easy solution. But let me try to give you some details:
When a character chooses their destination, a simple euclidean distance is used - the characters sometimes choose between dozens of objects and calculating path distance using the same algorithm the characters use to navigate around the map would easily take seconds (that's why character navigation runs on separate threads on the CPU where it can take its time without slowing the game down, and that's only one query for each character).
There might be some ways how to pre-compute at least distances between rooms which could help, but it of course gets more complicated, as patients would have to use other rules than staff and it still means computing hundreds or thousands of paths every time a wall/door/room gets placed (using a different algorithm like Dijkstra might help, but it would mean not being able to reuse much of the existing systems). We've even checked other games in the genre (like Prison Architect) to see what the usual solutions are, but it seems that everybody just lives with shortest distance. If you know about any examples, of course let us know!
Regarding the newest big hospital and the restrooms - maybe there's a workaround that we can implement, in some cases staff prefer equipment from their department (like common rooms), but I don't think it's currently enabled for going to the loo - this would probably be the best option at this point.
Btw - switching between floors always counts as a longer distance than anything on the same floor, so possibly the problem here is with reservation/capacity. Could you upload the save so we can check the specific situation?
- 1313eresident
- Posts : 17
Reputation : 1
Join date : 2018-10-31
Re: [RESOLVED] Pathfinding bug
Fri Jul 05, 2019 5:15 am
I currently do not see the problem with switching between floors anymore, as my hospital has grown so big that I don't notice it.
However, even when using restrooms from the same department, one can still run into this problem very easily (for example, emergency offices and trauma centers are usually some distance away from each other, but are from the same department).
It would obviously still solve the problem for quite a large portion and it does solve it in my scenario as well.
However, I am kind of surprised that this is such a huge issue.
Does the game not already have to calculate the pathfinding anyways, as the NPC has to get to that object somehow, without walking through walls and such?
And, redetermining where the closest toilets are would only be necessary when a toilet is placed, right?
I would however like to mention that the game has become significantly better since I last played it, especially the addition of random events and the more challenging milestones from insurance companies.
However, even when using restrooms from the same department, one can still run into this problem very easily (for example, emergency offices and trauma centers are usually some distance away from each other, but are from the same department).
It would obviously still solve the problem for quite a large portion and it does solve it in my scenario as well.
However, I am kind of surprised that this is such a huge issue.
Does the game not already have to calculate the pathfinding anyways, as the NPC has to get to that object somehow, without walking through walls and such?
And, redetermining where the closest toilets are would only be necessary when a toilet is placed, right?
I would however like to mention that the game has become significantly better since I last played it, especially the addition of random events and the more challenging milestones from insurance companies.
Permissions in this forum:
You cannot reply to topics in this forum