I have been tinkering with a little tactics game not so different from Fire Emblem. One thing I'm doing that I think is somewhat novel in the space is involving a technique I learned from studying Timely Dataflow: partially ordered costs for pathfinding. In Timely, it's used to represent complex versions of time that allow for multitemporal processing.

I've written about this before but back then I didn't really appreciate all the applications of them. Every time I want to do something, now, I find a way to represent it with a different kind of partially ordered cost. These things are awesome, man. You get so much cool stuff for free, and a clean, unified model.

Let's see what exactly I mean here, and see some applications.

Preferred Paths

The motivating example that got me thinking about this topic was the following problem:

A character on a grid wants to pathfind from point A to point B. Along the way from point A to point B, there are "hazards" that it wants to avoid. It can pass over hazards if it must, but we want it to choose a path that minimizes the number of hazards it passes.

Using an example from my previous post on the subject, the cat in this image wants to navigate this map. It can pass through the fire squares, but would rather avoid them:

The reason traditional pathfinding algorithms choke on this problem a little bit is that there's an optimality assumption that it violates. Traditional BFS-adjacent algorithms like Dijkstra or A* generally assume that two ways of getting to a given cell are equivalent for later pathfinding: if I get to X in the "best" way, that's the best way for every possible follow-up path. This assumption is violated by this problem, because if the cat in our image above is allowed to move five squares, the "best" path to X is different based on whether it wants to go to Y or Z after: if it just wants to go to Z, then it should walk around the fire. If it wants to go to Y, it has to walk through the fire.

The way we can model this is by a partially ordered cost:

struct Movement {
  squares: u64,
  fire: u64,
}

One Movement is only <= another Movement if it's better along every dimension.

Without getting too much into the actual algorithms we can use to pathfind with these costs (they're generally pretty expensive compared to regular, totally ordered costs, but all of my paths are pretty short, so I'm happy to just use the more expressive model), I implemented these costs so that I could do the things I described above. But the more I use them, and the more I encounter different designs that I think will require introducing bespoke logic and flags, the more I find that I don't need to, these partial costs are enough to implement all sorts of neat things.

Different Types of Movement

One kind of movement in the game I'm working on is flight. There are walls, and then there are chasms. It should be that only units with flight (because they have a jetpack or something) can go over those chasms.

The traditional way to implement this, I think, would be to have special edges tagged with "requires_flight," and then only "enable" those edges when the unit we're pathing for has flight. We can accomplish this without leaving the model of partially ordered costs though. My Movement struct, right now, looks like this:

pub struct Movement {
    pub squares: u64,
    pub flight: bool,
}

impl Cost for Movement {
    fn zero() -> Self {
        Self {
            squares: 0,
            flight: false,
        }
    }

    fn plus(&self, other: &Self) -> Self {
        Self {
            squares: self.squares + other.squares,
            flight: self.flight || other.flight,
        }
    }

    fn le(&self, other: &Self) -> bool {
        self.squares <= other.squares && self.flight <= other.flight
    }
}

This means I can just give edges that require flight an extra flight cost, and then only units that have flight in their movement capabilities can traverse them. In the examples below, the unit on the left has flight, and the unit on the right doesn't.

Limited-Use, Special Movement Skills

Like I said, that (flight) can be done with just turning edges on and off based on flags that the unit has. But there's an extension that I think needs more power, and partially ordered paths can provide it.

Imagine a variation where a unit can jump over a gap (I haven't implemented this yet, so I don't have a visual), but they're only allowed to jump over a maximum number of gaps in a single move. This is representable by adding a jumps field to the movement field. Using totally ordered costs to try to do this will be subtly wrong (unless a lot of care is taken) for the same reasons that it's wrong for the hazard example: later decisions care about what the earlier decisions were, so we need to be able to track a frontier of best paths as we go, rather than a single best path.

Different Costs of Movement

As one final example, in Fire Emblem, one property of cavalry is that they can generally move much further than infantry on a turn, but they incur higher movement costs than infantry on forested tiles.

We can again solve this by introducing a new dimension to our timestamps: no_horse, and when we have a forested tile, we have two parallel edges between them:

Now, units with no_horse can take the short, normal path (for them, this edge dominates the other, so the other won't ever be used), but cavalry units, which cannot take the no_horse edge, will be forced to take the more expensive edge into this tile, because they have no_horse: false which is less than the cost to take the cheap edge.

I'm not sure these are the best ways to implement these effects, but I've found it really nice to be able to stay in a single, unified model for pathing. I can add new hazards and kinds of traversal basically by just modifying this one Cost type. It's certainly not the most efficient way to do some of them, but for me, keeping everything in a nice, simple model has been really great. I'm sure I'll find more applications for these things as I go on.