I'm attempting to write an AI for the game Slay the Spire. One of the tasks it will need to do is navigate the map. The map is a directed acyclic graph with the same start and end node.
Each node (including the end node) will have 2 values associated with it: Expected value and death probability. The goal of the AI should be to maximize the expected value without dying. So far, none of this seems tough.
The twist here is that the death probability changes over time. Some nodes (elites) have high volatility: The death probability may go up or down drastically as we move through the map. The pathfinding algorithm would need to consider adjacent alternatives. A path that allows me to switch to a low-volatile node if things are getting tough is important.
As an example, the following map has two major routes. Both routes have an elite (the creature with horns), but the one on the right is a forced elite, while the one on the left can be skipped if death probability is too high. The ability for me to be flexible mid-route is an attractive feature, and one I'd like to take into account when pathfinding somehow.
How can my path-finding algorithm take into account adjacent paths/path flexibility? Is this even a job for pathfinding at all?
