Finding the path to the nearest body of water

I had a fantastic realisation yesterday when I discovered that the pathfinding system could be used for far more than navigating between a set source and destination!
The pathfinding system uses an expansive algorithm which progressively determines accessible locations, whilst maintaining links of how to get to that location. The system isn’t perfect, and won’t always find a path, even if one exists. It also doesn’t guarantee the shortest path, however one major benefit is to do with the implications this has on general search problems.

Seeing as this is a greedy algorithm, and doesn’t backtrack, if a cell has been visited, by definition of the system, it means that there is definitely a path to that cell via some means. Once a cell has been visited, it then evaluates areas accessible to that cell and locks that cell so no further modifications can be made. At that moment, a path is determined to have been found by a simple function which checks if the cell that was just locked is within a certain distance (normally a block or two) of the desired destination.

New Power!

By simply replacing this destination check with any check we want, we can re-purpose the pathfinding system for all kinds of common tasks! So i’ve spent the last day re-engineering it so that as well as regular navigation, you can also submit requests for general search problems:

Find a path to edge of nearest water source

Find a path to nearest block of type “Dirt”

Gameplay and AI Implications

What this means in terms of practical utility is that AI programming once again has just become easier for us! We can now get AI to do more and with ease. For example, if we wanted an AI to walk around, searching for trees to chop down, this is something now possible under the current system!

The great thing is that it is also just as cheap as regular navigation, so rather than having to first write an algorithm to scan for trees (assuming you didn’t have that data directly), and then navigate, finding a tree can just be part of the accessible path search.
It would take the same amount of processing time to find a path to that tree using the search process than it would if you already knew where the tree was and wanted to find a path to it (as the algorithm still has to traverse from the source to the destination).

We are also experimenting with other cool improvements for the AI combat mechanics such as telling the AI to “Find the nearest place that is in line of sight of player”. Currently, whilst the AI only shoots in line of sight, if the player is unaccessible, but potentially in line of sight, the AI won’t navigate to them.
Similarly, we can now tell the AI to hide by running a search for “Find a point that is out of line of sight of the player and atleast 10 blocks away”.

Or tell something to run away by simply finding a path to a location which is 20 blocks away.

I’m really excited for what this means for the game as a whole! The best part is, these conditions are incredibly easy for us to add, as most of them just involve the replacement of a simple check in the path search process :D!

Vitality Discord Server

The Vitality discord server is lighting up right now :) Feel free to come join us, pitch your ideas and join in community discussion: https://discord.gg/nVPaDhf

We also announce streams and more, including live chat rooms during game testing streams :)