Pathfinding for Artificial Intelligences in Video Games
For developers of the soon-to-be-released video game Rain World, the most appealing aspect of their work is their AI. A struggle for many game developers is programming how entities inside the game (that are not controlled by the player) behave themselves. Perhaps an entity simply moves along a set path with complete disregard for the player. Or perhaps an enemy will move straight to the player in all situations, attempting to attack the player in the process. But how can you feign intelligence in an instantiation of a computer program? How can you make that enemy seem real, or even clever?
Rain World’s developers shed some light on their tackling of these questions. The linked posts are a discussion of pathfinding. Pathfinding, put simply, is exactly what it sounds like. Enemies (lizards) need to find their way to the player (a “slugcat”), and in doing so, choose the most efficient path. Below is what a given in-game area may look like to a lizard.
A rigid network used by the enemy AI.
Lizards must find the shortest, fastest, or, more generally, most appropriate path for a given context. Perhaps an injured lizard might seek the fastest path away from a player, in order to heal. In any case, the lizards use their knowledge of the network to find the best path from their current node to the destination node. This translates to a smooth view for the player:
A player-seeking lizard altering its path.
What is really interesting is that each lizard can update the status of its network. What if its legs are injured, and it can no longer climb up poles? The lizard will then remove edges from certain nodes, should it find that they are not traversable. Assuming this does not leave the graph disconnected, the lizard will then find the best path given the updated network.
A crippled lizard finds another way.
One could imagine this pathfinding module working as a simplified version of our in-class example of cars choosing routes between cities; in this case, there is only one player. But lizards give paths certain values depending on which state it is in, and then choose accordingly. Although they do not mention it, one can imagine the developers adding a game theory aspect to this pathfinding algorithm. Perhaps taking the player’s usual or otherwise most probable actions into consideration, and choosing a non-intuitive path as a result.
POST 1: https://www.kickstarter.com/projects/rain-world/project-rain-world/posts/914855
POST 2: https://www.kickstarter.com/projects/rain-world/project-rain-world/posts/975341
Are you a fine arts major?
A sophomore CS major in engineering, actually.