Internship - Week 16 - Faster wander behavior
Hey there,
This week we noticed that the FPS(frames per second) is way too low for the number of creatures that are walking on the map. We ran the tests on PC, so imagine how slow it was running on mobile phone's and tablets. We would like to run around one hundred creatures at a decent frame rate.
Testing
Testing went very well and fast because of unity's build in profiler tool. This showed us exactly where the problems were. One or two weeks ago I decide to change the wander behavior for all creatures, I was just done with the path finding and thought it would be way easier to use the path finding for the wander behavior instead of the implementation we had at that time. It worked a lot better but now, we found out that it is a lot heavier on the CPU. Unity's profiler showed us that around 70% of the time was spend on calculating the wander behavior for each creature. At this point it was clear to us that we needed to change this to something much simpler. We also figured out that changing this wander function to something very simple, should give us the performance boost we need for a decent frame rate.
Wander behavior
So, lets talk about the way we changed the wander function and maybe a bit about how it worked, the first time I created it, before the path finding.
old:
The old version before I changed it to path finding, was pretty bad when I look back on it now. The algorithm would look at its neighbors(up, down, left and right) to find the direction it is going to move in. When there were multiple directions it could move in, the algorithm would choose one at random. With the direction decided, it would randomly pick a number between 3 and it's detection range. This number was the amount of steps it would walk in the chosen direction. When it finished the random amount of steps or when it hit a wall, it would start over. The algorithm also was not able to walk in the same direction it just came from.
Image 1: showing directions that Image 2: showing the amount of steps in
can be picked. the left direction.
This algorithm had some big flaws. It got stuck very easily and once it got stuck it was very difficult for the algorithm to get itself unstuck. Look at the situation in image 3. It would be very hard for the algorithm to escape this situation. It was only possible to escape if the creature starts at the left most tile and randomly picks the right amount of steps to end up in front of the opening. Now it still has to pick the right walking direction to escape, which is a 50% chance. The situation would be even worse when it would be stuck in a small room, where it can move in 4 directions.
Image 3: creature stuck in small corridor.
There was also a small annoyance when the creature would walk into a dead-end and the only possible direction was backwards. the creature would get stuck in the dead-end for one tick because the algorithm is not allowed to go backwards. The tick were the creature was stuck, would reset the last walked direction, because of this it was able to go backwards the next tick. This was not a game breaker, but it still annoyed me.
Image 4: moving to dead-end. Image 5: stuck in dead-end. Image 6: escaping dead-end.
I think it is pretty clear now, why i thought switching to path finding was a good idea.
new:
The new way is quite a bit different, instead of picking a random direction and walking in this direction for a certain amount of steps, the algorithm picks a direction every step. This direction is randomly picked from one of the four directions(forwards, backwards, left or right). Forwards has the biggest chance to be picked and backwards the smallest. Right and left have a chance that is somewhat in between. This way it is way less likely to get stuck and it will never get stuck in a dead-end. The algorithm is also many times faster than using path finding, while giving the same results.
Lets have a look at how it works:
Loop through the four directions a creature can walk in. for every direction, you check if the neighbor tile has the "Walkable" property. If this is the case, add the direction to an array and check if the directions is the same as the last walked direction or if it is the opposite direction. If the direction is the same(forwards), add 64(chance to be picked) to a second array. If the direction is the opposite(backwards) of the last walked direction, add 1 to the second array. If it is not forwards or backwards, add 16 to the second array.
Image 7: showing chances for each direction.
Image 8: Showing the code that sets the directions.
When this is done, we take the total sum of all the chance values in the array and pick a random value between 0 and the total sum. Now we loop through the array of "Walkable" directions and find the direction that corresponds to the random value.
I know this is a bit vague so let me give an example: Lets say we can only walk forward and backwards. we will have an array with the forward and backwards direction it in and a second array with 64 and 1 in it. The combined sum is 65, so we pick a random value between 0 and 65(including 0 and 65). Depending on the order of the array, we either check if the value is between 0 - 64 and 64 - 65 or we check if the value is between 0 - 1 and 1 - 65. It doesn't matter in which order the directions are added to the array, as long as the direction and its chance value are in the same place in both arrays.
Image 9: Showing the code that picks the next direction.
Results
Changing the wander function did the trick. Now we are able to get one hundred creatures on the map with a very decent frame rate. Sometimes the easiest way is not always the best one, in this case, using the path finding for the wander function was the easiest but clearly not the best option.
Flee behavior
While I was finishing up the wander function, I had an idea. I could probably use the same algorithm and use it to make a flee function. When a creature sees a predator, he will turn around and walk backwards. Now we can use the wander function to guide him away from the predator. The wander function has a high chance of walking forward, which is want we want because the creature needs to get away from the predator that is behind him. The only thing we have to do is make the chance to walk backwards as small as possible, We don't want it to walk towards the predator. The only thing we really need to program for this is a way to detect predators that are in front of the creature and change the creature's last walk direction, so it will most likely walk in the direction it came from.
