Posted August 23, 2018
Hello everybody,
In this Dev Diary we want to provide you with an insight into the navigation system for characters in The Guild 3. This has been a major source of problems in the past and we needed to find a way to make it work reliably.
First, we needed to get an overview how the system works. There are two parts in the process of moving a character from 'A' to 'B'.
1. The game uses the network of streets to calculate a very rough path to the destination.
2. Using this path, the character can determine a direction in which he or she wants to be going at each point in time. This information is fed into a separate pedestrian simulation system. That simulation is responsible for moving all characters towards their destination in such a way that they will not collide with each other. A library is used for this simulation.
Problems of the old navigation system
We identified two main problems with the old system that we wanted to address.
1. Characters have 'hard' collision with each other. When they fail to avoid each other, they can get stuck.
2. The pedestrian simulation also produced some very unnatural looking movement. It would always attempt to shift the positions of characters to avoid collisions, even when the characters were not actively walking/running. This could lead to 'standing' characters getting pushed around fairly wildly. In rare situations even the target character of an action (for example pickpocketing) could get pushed away from your character trying to do the pickpocketing.
Additionally, character movement was often not associated with an animation. When a standing character would move to the side in order to evade someone approaching, he would do so by sliding across the floor in a standing pose. On top of that, the pedestrian simulation would not consider the line of sight of the characters. A fairly common occurrence was characters sliding across the floor in order to evade a cart that was approaching from behind.
Our approach towards a solution
Almost all of the problems we were observing were related to the pedestrian simulation system. Unfortunately the system provided very few options to tweak the behavior. We decided to look for alternative libraries to exchange it. One library that looked very promising was 'OpenSteer'. It had a convincing demo for pedestrian simulations where we could see ahead of time how it behaves. Furthermore, it provides tools for visually displaying what each character is 'thinking' at each point in time. And a quick look into the code of the library revealed that it was fairly easy to understand and change if needed.
OpenSteer works quite a bit differently than the previous library which aligns nicely with the problems we were observing. Each pedestrian in the simulation performs his/her own calculation regarding which other pedestrian he/she needs to evade. And it only does so while actively moving along a path, so there will be no more sliding of inactive characters. And finally there is no hard collision between pedestrians. If they fail to avoid each other, they will pass through each other, instead of getting stuck.
Integrating OpenSteer
The process of exchanging the old library with OpenSteer turned out to be a bigger undertaking than expected. OpenSteer expects each pedestrian to have a path assigned. The old library, however, only expected to have a direction and preferred speed provided for each character. This difference alone required us to make changes in many places of the code.
OpenSteer itself did not immediately work the way we hoped and required additional work. First of all, the pedestrians in the simulation were directly using the rendering system of the demo application for the visualization of their 'thinking'. We had to make this compatible with the rendering in The Guild 3.
The next issue we encountered was the fact that characters did not steer strong enough when they wanted to walk around a corner. This turned out to be caused by a difference in size of the world in The Guild 3 compared to the OpenSteer demo. In The Guild 3 everything is bigger and some of the steering force values were not independent of the size. Luckily, this was not too hard to fix once we had figured out the cause.
This process of identifying and fixing problems went on for a while. Noteworthy problems were:
- Height differences not being represented in the simulation which caused ships on the river try to avoid pedestrians on bridges across the river.
- Paths generating unreachable destinations below the surface of the terrain.
- Paths on bridges would vertically snap to the water surface, rather than to the surface of the bridge.
- Too fast direction changes when evading other pedestrians, which caused erratic movement.
For these issues it proved invaluable to have a way to visualize what a character is calculating internally. In many cases, simply activating the visualization was already enough to immediately see what was going wrong.
Here is one example of the visualization
(see attached image)
- The long red line indicates the general path for the character to follow.
- The orange lines indicate the width of the path. Characters will try to stay within the 'tube' of orange lines.
- The green and red circles indicate the predicted position of our character and one collision threat respectively. The fact that the circles are overlapping indicates that we are on a collision course.
- The blue circle indicates the direction our character will be aiming in order to avoid the collision.
Final words
Reworking this navigation system turned out to be a big task. But we think it was worth it. Now we are at a point where it works well and we should not need to make many more changes. And if we do need to make changes, it should be straightforward to do so.
Many of the changes to the navigation system were already included in the EA 0.5.3 update. Some additional improvements (especially smoother movement when avoiding collisions) will be launched with the patch EA 0.5.5. We are aware there are still problems with characters getting stuck 'in the traffic' and forgetting their destination/action. These are high on our priority list.
I hope this Dev Diary gave you an interesting insight into how the navigation system works. It was challenging, but also fun to work on this.
Christoph Erhardt
Gameplay Programming for The Guild 3
Purple Lamp Studios
In this Dev Diary we want to provide you with an insight into the navigation system for characters in The Guild 3. This has been a major source of problems in the past and we needed to find a way to make it work reliably.
First, we needed to get an overview how the system works. There are two parts in the process of moving a character from 'A' to 'B'.
1. The game uses the network of streets to calculate a very rough path to the destination.
2. Using this path, the character can determine a direction in which he or she wants to be going at each point in time. This information is fed into a separate pedestrian simulation system. That simulation is responsible for moving all characters towards their destination in such a way that they will not collide with each other. A library is used for this simulation.
Problems of the old navigation system
We identified two main problems with the old system that we wanted to address.
1. Characters have 'hard' collision with each other. When they fail to avoid each other, they can get stuck.
2. The pedestrian simulation also produced some very unnatural looking movement. It would always attempt to shift the positions of characters to avoid collisions, even when the characters were not actively walking/running. This could lead to 'standing' characters getting pushed around fairly wildly. In rare situations even the target character of an action (for example pickpocketing) could get pushed away from your character trying to do the pickpocketing.
Additionally, character movement was often not associated with an animation. When a standing character would move to the side in order to evade someone approaching, he would do so by sliding across the floor in a standing pose. On top of that, the pedestrian simulation would not consider the line of sight of the characters. A fairly common occurrence was characters sliding across the floor in order to evade a cart that was approaching from behind.
Our approach towards a solution
Almost all of the problems we were observing were related to the pedestrian simulation system. Unfortunately the system provided very few options to tweak the behavior. We decided to look for alternative libraries to exchange it. One library that looked very promising was 'OpenSteer'. It had a convincing demo for pedestrian simulations where we could see ahead of time how it behaves. Furthermore, it provides tools for visually displaying what each character is 'thinking' at each point in time. And a quick look into the code of the library revealed that it was fairly easy to understand and change if needed.
OpenSteer works quite a bit differently than the previous library which aligns nicely with the problems we were observing. Each pedestrian in the simulation performs his/her own calculation regarding which other pedestrian he/she needs to evade. And it only does so while actively moving along a path, so there will be no more sliding of inactive characters. And finally there is no hard collision between pedestrians. If they fail to avoid each other, they will pass through each other, instead of getting stuck.
Integrating OpenSteer
The process of exchanging the old library with OpenSteer turned out to be a bigger undertaking than expected. OpenSteer expects each pedestrian to have a path assigned. The old library, however, only expected to have a direction and preferred speed provided for each character. This difference alone required us to make changes in many places of the code.
OpenSteer itself did not immediately work the way we hoped and required additional work. First of all, the pedestrians in the simulation were directly using the rendering system of the demo application for the visualization of their 'thinking'. We had to make this compatible with the rendering in The Guild 3.
The next issue we encountered was the fact that characters did not steer strong enough when they wanted to walk around a corner. This turned out to be caused by a difference in size of the world in The Guild 3 compared to the OpenSteer demo. In The Guild 3 everything is bigger and some of the steering force values were not independent of the size. Luckily, this was not too hard to fix once we had figured out the cause.
This process of identifying and fixing problems went on for a while. Noteworthy problems were:
- Height differences not being represented in the simulation which caused ships on the river try to avoid pedestrians on bridges across the river.
- Paths generating unreachable destinations below the surface of the terrain.
- Paths on bridges would vertically snap to the water surface, rather than to the surface of the bridge.
- Too fast direction changes when evading other pedestrians, which caused erratic movement.
For these issues it proved invaluable to have a way to visualize what a character is calculating internally. In many cases, simply activating the visualization was already enough to immediately see what was going wrong.
Here is one example of the visualization
(see attached image)
- The long red line indicates the general path for the character to follow.
- The orange lines indicate the width of the path. Characters will try to stay within the 'tube' of orange lines.
- The green and red circles indicate the predicted position of our character and one collision threat respectively. The fact that the circles are overlapping indicates that we are on a collision course.
- The blue circle indicates the direction our character will be aiming in order to avoid the collision.
Final words
Reworking this navigation system turned out to be a big task. But we think it was worth it. Now we are at a point where it works well and we should not need to make many more changes. And if we do need to make changes, it should be straightforward to do so.
Many of the changes to the navigation system were already included in the EA 0.5.3 update. Some additional improvements (especially smoother movement when avoiding collisions) will be launched with the patch EA 0.5.5. We are aware there are still problems with characters getting stuck 'in the traffic' and forgetting their destination/action. These are high on our priority list.
I hope this Dev Diary gave you an interesting insight into how the navigation system works. It was challenging, but also fun to work on this.
Christoph Erhardt
Gameplay Programming for The Guild 3
Purple Lamp Studios
Post edited August 23, 2018 by Scandal781