I think I'm biting off more than I can chew...

[Therem Harth]

In ToME 2, drastically increasing MONSTER_FLOW_DEPTH and turning on the flow_by_sound option will make monsters better at tracking the player. But not good enough. You still get situations like this:

http://angband.oook.cz/screen-show.php?id=1941

The problem is that the monsters will never move *away* from the a character to reach him around obstacles, so they get stuck behind walls or in niches. And I really have no idea how to remedy this.

Help?

[konijn_]

I could only imagine that there is a sanity check that makes sure the monster is moving in the right direction ( not down and not right )

If there is such a sanity check, then you might be in a world of pain after removing it ;]

T.

[Therem Harth]

*invokes Wizard Mode and resurrects thread*

Okay, I've noticed that in Vanilla (3.2.0 or later) "smart" monsters go to great lengths to follow the player around. For instance, in my current V game I saw Sauron navigate his way out of a checkerboard room to come after my character. Even Trolls will occasionally move away from @ so they can intercept him.

How do current versions of V handle the dungeon flow stuff? This behavior is really great, and I want to bring it to T2.

[andrewdoull]

http://roguebasin.roguelikedevelopment.org/index.php/The_Incredible_Power_of_Dijkstra_Maps

[Narvius]

This is... this is... beautiful.

[EpicMan]

Yeah, I'm using those for a roguelike I'm making (yarg-roguelike on Google Code). The best improvement other than efficiency so far is free fleeing behavior (just flow in the opposite direction as pursuit, no need for extra logic).

Those are pretty amazing.

[AnonymousHero]

Am I missing something or isn't this just A* search with custom cost functions?

(EDIT: Not that figuring out those cost functions is all that easy, necessarily, but...)

[fph]

I was thinking about that, too, but the implementation seems different - I haven't worked out the big-Os but intuitively this feels worse than A*.

[EpicMan]

So in one sense it's worse than A* because you map out the whole level rather than quitting as soon as you find the path.

But with Dijkstra Maps, you just need to pathfind once when the player moves,and all the monsters who need to move to the player (or run away from him) can use the same map - just check the 8 adjacent squares and take the lowest-cost one (chase the player) or highest-cost (fleeing)

It's a lot better when you have many monsters pathfinding to the player.

[ekolis]

Wouldn't tunneling and the like require recalculations of the map?

[EpicMan]

Yes, you recalculate anytime the map changes - terrain alteration and player moves, etc. But you are only doing it once for all monsters (or all monster flows), rather than doing pathfinding for every monster.

[Therem Harth]

http://roguebasin.roguelikedevelopme..._Dijkstra_Maps

Wait a minute, that looks very much like what ToME does already. From the code comments:

/*
 * Hack -- fill in the "cost" field of every grid that the player
 * can "reach" with the number of steps needed to reach that grid.
 * This also yields the "distance" of the player from every grid.
 *
 * In addition, mark the "when" of the grids that can reach
 * the player with the incremented value of "flow_n".
 *
 * Hack -- use the "seen" array as a "circular queue".
 *
 * We do not need a priority queue because the cost from grid
 * to grid is always "one" and we process them in order.
 */

Or am I reading that wrong? Also, the code in Vanilla looks almost the same as in ToME 2...

[Therem Harth]

I think I've found another problem: when a monster has two equidistant paths to the player, it can't seem to decide which one to take, and gets stuck. Darn.

Edit: or perhaps that's the same issue?