Hello everyone,
This update will be slightly different than previous ones because it delves into some of the more technical aspects of the game. One of the problems I am tasked with solving is the always fun problem of obstacle avoidance and path finding of fish and other creatures.
Anyone who has played the game before has no doubt noticed that there are times when fish get a bit stuck and can't seem to figure out their surroundings. This is especially noticeable in aquariums where there are a lot of decorations creatively positioned about the place. In such aquariums when a fish wishes to seek out and eat some food that has sunk to the bottom of the aquarium it is especially difficult to navigate around these decorations in order to reach their meal.
Our fish have the ability to sense what is in front of them in a very basic way. It shoots out a laser beam from it's nose in the direction of it's food target. If that laser beam does not hit anything then it assumes there is nothing in it's way and it will swim towards the food. If it does detect something then it shoots out more laser beams at a wider angle and tries to find a space within it's vision where there is not obstacle. If it finds open space then it's swim direction is changed to this new avoidance direction and after a small period of time it attempts to swim in the direction of the food again and the process repeats itself.
When this process works well what you see is the fish swim around obstacles in order to get to their food target. When it does not work what you see is the fish going nowhere in particular or move towards then away then towards the target again but not actually making any progress.
This "laser beam" detection technique works in most cases when the fish is just going about it's business and going nowhere in particular. As soon as we give the fish a destination that has obstacles in between then things can go wrong.
A common technique used in games for decades is to partition 3d space into a grid structure that stores obstacle data and use that to compute a path from one position to another.
(to see larger image, right click and open image in new tab)
We make 5 grids at different resolutions. Starting from the left, the largest cell size knows only about the 8 cells within it's bounds that belong to the next grid resolution. Each of those 8 cells only know about the 8 cells from the next resolution that fit within their bounds and so on. The number of cells on the right most grid is 4096. Each of those cells needs to know whether or not an obstacle sits within it's bounds.
The simple way to do that is to run a piece of code that checks for collisions in every cell in every grid but that is wasteful. The optimised approach is to start by doing a collision check on the lowest resolution grid (left most). That will of course test positive for the substrate because its bounds is as big as the aquarium. We then step to the next resolution and run a check on 8 cells. The bottom 4 cells will test positive for the substrate but the top 4 cells will test negative. Logic tells us that if these top 4 cells cannot detect the substrate then none of the cells of the higher resolution grids that sit within the same space will detect substrate either. We can then skip doing collision checks on these cells and save some CPU performance.
Now that we have a reliable and fast way to get a good approximation of where all obstacles are we can then compute the path any between two positions.
The image above shows a path that have been computed from the position of a fish to the position of some food. A path is computed using what is essentially a type of sorting algorithm. The code starts at the cell nearest to the fish and then expands out to every surrounding cell that does not hold any collision data until it finds the cell closest to the target. Once it finds the target it then backtracks it's way to the fish position. It is this backtracked path that becomes the path that the fish will use.
We have implemented the basic well known version of the algorithm but the path it produces is a little weird looking sometimes. It correctly goes from fish to target but the route makes the fish look a little drunk. There are still improvements to be made.
Once our fish has a path they can then simply swim along it to get to where they want to go. They do not need to worry about encountering obstacles because the path already avoids obstacles. If a player moves an obstacle into the path it is then invalidated and recomputed to account for the change in obstacle position.
This technique will not be used with all fish behaviour. It will generally be used only when a fish absolutely needs to go to a specific location such as to eat food or locate a mate. We are only just scratching the surface of how useful these techniques will be in Fishery. This technique will allow us to have shrimps, snails and other creatures crawl around on things so we are another step closer to shrimps.
The grid structure will also be useful to help store other bits of information about the aquarium. It could be used to help Betta fish and Gouramis to figure out good places to build bubble nests or fish like plecos to find places to hide. It also allows us to fix old bugs like eggs dropping through decorations or substrate and fry being born inside objects.
This is just some of the progress we have been making in the previous few weeks. I am not entirely sure when the next build update will come but It should be relatively soon and it will include these new pathfinding features. As usual we wish you all a great weekend.
The Fishery Team