FOV and pathfinding concept, maybe variant material

[Therem Harth]

So I've been messing around a bunch lately with a custom roguelike in Rust, and since I'm using tcod-rs there's a lot of cool stuff available from the API. And it gave me a couple of ideas. They might make it into this roguelike, and/or I might try to implement them in an Angband variant.

1. Bulky monsters that can block FOV.

IMO this would make sense as a flag. For my current project I'd probably have to do it by making bulky monsters set the tile they're on to block sight, and unset when they move, which... is kind of hacky but yeah.

Anyway, I think this could create some tactically interesting stuff; e.g. incentive to duck behind a large monster to get out of LOS of spellcasters or archers.

2. A* pathfinding for monsters that includes monster-occupied squares as unwalkable.

Why? Because if I understand A* correctly, this can result in automatic flanking behavior. Again, for the current project I'd have to use kind of hacky methods for this. But I like the idea of automatic flanking, especially in combination with monsters that block LOS.

The combination of these two seems especially intriguing to me, as far as creating a faster paced and more claustrophobic game.

[Derakon]

A* is not hard to implement, but be aware that it scales poorly with map size and number of actors. Angband maps can have thousands of open cells to route through and hundreds of monsters doing that routing, so I suspect you'll find that a naive implementation won't run acceptably even on modern computers.

What you may be able to do is use the existing heat map-based pathfinding until monsters get close, and then switch to A*. That limits the amount of space that A* has to handle and also the number of units that may be using A*.

In any case, good luck! I look forward to hearing about what you produce.

[Therem Harth]

@Derakon

Yeah, I'm using tcod's implementation, which I'm assuming is at least somewhat optimized. So far, no performance issues, which is better than can be said of my (custom, simplistic) heatmap pathfinding it replaced. Part of this is probably that the maps are a lot smaller than for Angband (which is okay, it's supposed to be a more limited and claustrophobic-feeling game).

Anyway, thank you for the good luck wishes! And if you know ways to optimize heatmap recalculation, I'd be interested in hearing them. I'd done mine using a spiral algorithm to pass through every spot on the grid in approximately concentric order; going through the whole grid linearly and repeatedly a la various example implementations produced lags of at least several seconds per recalc.

[Derakon]

Yeah, for smaller maps with fewer units, A* should be just fine as-is.

Heatmaps: what language are you in? Python is not great for that kind of thing (doing large numbers of similar operations). As I recall, Pyrel had a C library specifically for generating heat maps.

[Therem Harth]

custom roguelike in Rust

https://www.rust-lang.org/ for those unfamiliar, and using tcod-rs: https://lib.rs/crates/tcod

Poor performance is absolutely not a problem with Rust itself; it is basically designed as a replacement for C++. I'm pretty sure the issue was with my implementations. But yeah for some reason it didn't occur to me to look for heatmap-related crates, d'oh.

Edit: part of the reason I originally went with heatmaps was because they looked a lot easier to implement well myself than A*.

[Derakon]

Welp. Sorry about that; clearly I'd forgotten your original post. I don't know much about Rust, but if you post your implementation, there may be some unnecessary loop layers or something that can be pruned out.

[Therem Harth]

'Tis alright! Hmm, lemme dig up the implementation... Okay, relevant old code below, from this commit:

https://gitlab.com/miramor/wandering-cyborg/tree/7ded4da6327bd5fa91ef37fbff0bd2f44a35ebe2/src

in dungeon.rs:

pub fn neighbors(x: i32, y: i32) -> Vec<(i32, i32)> {
    let neighbor_cells = [
        (-1, -1),
        (-1, 0),
        (-1, 1),
        (0, -1),
        (0, 1),
        (1, -1),
        (1, 0),
        (1, 1),
    ];

    let mut neighbor_coords = vec![];
    for (dx, dy) in neighbor_cells.iter() {
        let (nx, ny) = (x + dx, y + dy);
        if nx < 0 || nx >= MAP_WIDTH || ny < 0 || ny >= MAP_HEIGHT {
            break; // bounds check
        }
        neighbor_coords.push((nx, ny));
    }

    neighbor_coords
}

fn reset_ai_val(map: &mut Map, x: i32, y: i32) {
    let mut new_ai_val = map[x as usize][y as usize].mon_ai_val;
    for (nx, ny) in neighbors(x, y).iter() {
        let (nx, ny) = (*nx, *ny);
        if new_ai_val > map[nx as usize][ny as usize].mon_ai_val {
            new_ai_val = map[nx as usize][ny as usize].mon_ai_val;
        }
    }

    if new_ai_val < map[x as usize][y as usize].mon_ai_val {
        map[x as usize][y as usize].mon_ai_val = new_ai_val + 1;
    }
}

pub fn recalc_mon_ai_map(map: &mut Map, player_x: i32, player_y: i32) {
    for x in 0..MAP_WIDTH {
        for y in 0..MAP_HEIGHT {
            map[x as usize][y as usize].mon_ai_val = 100;
        }
    }

    map[player_x as usize][player_y as usize].mon_ai_val = 0;

    for (x, y) in ManhattanIterator::new(
        player_x,
        player_y,
        MAP_WIDTH.max(MAP_HEIGHT).try_into().unwrap(),
    ) {
        if (x < MAP_WIDTH) && (y < MAP_HEIGHT) && (x >= 0) && (y >= 0) {
            reset_ai_val(map, x, y);
        }
    }
}

[Pete Mack]

Hmm. What is MAX X and MAX Y? You are computing values for something like 40,000 squares, instead of ~500 (the number of floor squares.)

[Therem Harth]

Pete Mack:

pub const MAP_WIDTH: i32 = 80;
pub const MAP_HEIGHT: i32 = 43;

Not sure what you mean? Edit: oohhh I think I see, yeah, there are a bunch of places I should have been checking for walls/blocked squares and did not.

[Derakon]

So, here's generally how I'd go about implementing that kind of heat map:

cell_stack = [player_pos]
next_stack = set()
depth = 0
while cell_stack or next_stack:
  if not cell_stack:  # Done processing this depth, move to the next
    depth++
    cell_stack = list(next_stack)
    next_stack = set()
  pos = cell_stack.pop()
  if map[pos] > depth:  # Haven't processed this cell before
    map[pos] = depth
    for neighbor in neighbors(pos):
      if (neighbor is traversible and map[neighbor] > depth):
        next_stack.add(neighbor)

In other words, you have a stack of cells to process that are at the same "depth" (distance from the player), and a stack of cells that will be at the next depth. All neighbors of cells in the current stack that have not yet been processed get added to the next stack. Once the current stack is empty, increment depth and start processing the next stack instead.

Note that next_stack is actually a set, so that any cell can only be added to it at most once. I convert to a list when next_stack becomes the current stack for easier popping. I also check whether a cell has been processed both before adding it to a stack and after popping it. The former helps keep the stack size down, the latter accounts for the potential that there's multiple ways to reach a cell...though it might not be necessary in this case.

[Therem Harth]

Mm, gotcha. I was going loosely based on a Python implementation I found, but failed badly at translating it I guess.