Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old September 30, 2019, 04:44   #1
Therem Harth
Knight
 
Therem Harth's Avatar
 
Join Date: Jan 2008
Location: New England winter
Posts: 923
Therem Harth is on a distinguished road
FOV and pathfinding concept, maybe variant material

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.
Therem Harth is offline   Reply With Quote
Old September 30, 2019, 16:27   #2
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,946
Derakon is on a distinguished road
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.
Derakon is offline   Reply With Quote
Old September 30, 2019, 20:00   #3
Therem Harth
Knight
 
Therem Harth's Avatar
 
Join Date: Jan 2008
Location: New England winter
Posts: 923
Therem Harth is on a distinguished road
@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.
Therem Harth is offline   Reply With Quote
Old September 30, 2019, 23:44   #4
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,946
Derakon is on a distinguished road
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.
Derakon is offline   Reply With Quote
Old October 1, 2019, 00:46   #5
Therem Harth
Knight
 
Therem Harth's Avatar
 
Join Date: Jan 2008
Location: New England winter
Posts: 923
Therem Harth is on a distinguished road
Quote:
Originally Posted by I
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*.
Therem Harth is offline   Reply With Quote
Old October 1, 2019, 00:52   #6
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,946
Derakon is on a distinguished road
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.
Derakon is offline   Reply With Quote
Old October 1, 2019, 01:05   #7
Therem Harth
Knight
 
Therem Harth's Avatar
 
Join Date: Jan 2008
Location: New England winter
Posts: 923
Therem Harth is on a distinguished road
'Tis alright! Hmm, lemme dig up the implementation... Okay, relevant old code below, from this commit:
https://gitlab.com/miramor/wandering...f44a35ebe2/src

in dungeon.rs:
Code:
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);
        }
    }
}
Therem Harth is offline   Reply With Quote
Old October 1, 2019, 01:43   #8
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 5,419
Donated: $40
Pete Mack is on a distinguished road
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.)
Pete Mack is offline   Reply With Quote
Old October 1, 2019, 01:58   #9
Therem Harth
Knight
 
Therem Harth's Avatar
 
Join Date: Jan 2008
Location: New England winter
Posts: 923
Therem Harth is on a distinguished road
Pete Mack:

Code:
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.
Therem Harth is offline   Reply With Quote
Old October 1, 2019, 02:26   #10
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,946
Derakon is on a distinguished road
So, here's generally how I'd go about implementing that kind of heat map:
Code:
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.
Derakon is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Pathfinding - monster home Sky Vanilla 2 October 3, 2017 03:38
[3.5-dev] New refactored FOV crashes PowerWyrm Vanilla 3 April 18, 2013 14:01
Passwall monster pathfinding fizzix Vanilla 0 February 20, 2012 04:48
Post NSFW material? Rizwan Idle chatter 1 September 12, 2009 16:52
LOS/FOV/projections in NPP/Sangband half Development 1 July 21, 2009 23:49


All times are GMT +1. The time now is 13:10.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.