Monster path finding in 4.0.5

[Derakon]

because he tunnels AND causes confusion. do you know how many @s i have lost to that stupid thing?

If you're dying to this monster, then you need to prepare for it. Umber Hulks are far from an impossible challenge even if you're underlevelled; you just need to play smart.

Stay out of melee with them -- scrolls of Phase Door should be standard kit for every character, and they move at normal speed, so even if you don't see them before they break down the adjacent wall, you'll still have a turn to respond.

If you do get confused, you can try to kill them in melee; they have very little health and it doesn't take much to get them to flee.

Or you can drink CSW/CCW and hope that they miss their confusing attack, giving you a chance to phase away.

If you drink Speed, then you can drink CSW/CCW and be guaranteed a turn to get away.

You can use a Staff of Teleport even when confused, so that's also a good escape option if you've found/bought one by the time Umber Hulks show up.

[Pete Mack]

Phase door and illumination is certainly the preferred option, or just sucking up and fighting for a strong fighter with good damage. Mage should certainly phase door before it gets to a square away, then acid bolt etc. No real threat to a priest, since they are evil, and a single Orb will send them fleeing.

[Nick]

I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:

• Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
• Sight: If the monster sees the player, they can head straight for them. Easy.
• Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
• Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I have this basically working in development now. I will push it out for people to look at fairly soon, once I have made suitable changes to monster sound sensitivity and sleep counter values.

[Philip]

Also, never fight an Umber Hulk when there are other moderately nasty monsters around, particularly in melee. This is one reason to have good stealth. Not only do you not have to fight many things, the things you do have to fight you fight alone.

[PowerWyrm]

because he tunnels AND causes confusion. do you know how many @s i have lost to that stupid thing?

This isn't an issue anymore now there are mushrooms of the clear mind.

[Pete Mack]

Those are pretty rare. I never keep them. (I do sometimes keep ESP mushrooms.) Deaths to umber hulks are just too rare to bother with--it's not like the original Rogue, where they were utterly deadly.

This isn't an issue anymore now there are mushrooms of the clear mind.

[PowerWyrm]

Those are pretty rare. I never keep them. (I do sometimes keep ESP mushrooms.) Deaths to umber hulks are just too rare to bother with--it's not like the original Rogue, where they were utterly deadly.

You need to keep them if you lack rConf, not really for Umber Hulks, but more for Ariel.

[Pete Mack]

You need them only if you decide to melee a monster that hits to confuse. Beyond some really weak monsters, that means Cat Lord, Ariel, Thuringwethil, high giants, nightmares, and ethereal dragons--the latter two of which an endgame strong fighter can kill even if confused. Not a real problem.

[Nick]

The latest builds on the nightlies page now have the new pathfinding algorithm.

It will not be perfect.

My aim with this first attempt was to get the basic principles right, and then alter things as people notice things wrong with it. So please, report differences you're seeing, especially when monsters are doing dumb things.

[t4nk]

The latest builds on the nightlies page now have the new pathfinding algorithm

Now that looks like how I expected pathfinding to work!

[t4nk]

 * The biggest limitation of this code is that it does not easily
 * allow for alternate ways around doors (not all monsters can handle
 * doors) and lava (many monsters are not allowed to enter lava).
 */

So you can build three heatmaps? If you want to speed it up, you can use one of those overly clever programming tricks For example:

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef uint16_t heatmap_grid_type;

struct heatmap
{
	heatmap_grid_type **grids;
	heatmap_grid_type *underlying;

	int width;
	int height;
};

struct heatmap make_heatmap(int width, int height)
{
	assert(width > 0);
	assert(height > 0);

	struct heatmap heatmap = {
		.width = width,
		.height = height
	};

	const size_t access_size = sizeof(heatmap_grid_type *) * height;
	const size_t grids_size = sizeof(heatmap_grid_type) * height * width;

	char *mem = malloc(access_size + grids_size);
	assert(mem);

	heatmap_grid_type **access = (heatmap_grid_type **) mem;
	heatmap_grid_type *grids = (heatmap_grid_type *) (mem + access_size);

	for (int y = 0; y < height; y++) {
		access[y] = grids + y * width;
	}

	heatmap.grids = access;
	heatmap.underlying = grids;

	return heatmap;
}

void wipe_heatmap(struct heatmap *h)
{
	memset(h->underlying, 0,
			sizeof(*h->underlying) * h->width * h->height);
}

void free_heatmap(struct heatmap *heatmap)
{
	free(heatmap->grids);

	heatmap->grids = NULL;
	heatmap->underlying = NULL;
	heatmap->width = 0;
	heatmap->height = 0;
}

/* demonstration */

int main(int argc, char **argv)
{
	int width = 3;
	int height = 5;

	if (argc > 2) {
		width = strtol(argv[1], NULL, 0);
		height = strtol(argv[2], NULL, 0);
	}

	struct heatmap h = make_heatmap(width, height);

	wipe_heatmap(&h);

	for (int y = 0; y < h.height; y++) {
		for (int x = 0; x < h.width; x++) {
			printf("(%d, %d) == %d\n",
					x, y, h.grids[y][x]);
		}
	}

	putchar('\n');

	int i = 0;
	for (int y = 0; y < h.height; y++) {
		for (int x = 0; x < h.width; x++) {
			h.grids[y][x] = i++;
		}
	}

	for (int y = 0; y < h.height; y++) {
		for (int x = 0; x < h.width; x++) {
			printf("(%d, %d) == %d\n",
					x, y, h.grids[y][x]);
		}
	}

	free_heatmap(&h);

	return 0;
}

That eliminates intervening malloc's metadata and increases cache coherency; you also get to use memset() to wipe the heatmap (similar trick is used in ui-term.c).

[Nick]

 * The biggest limitation of this code is that it does not easily
 * allow for alternate ways around doors (not all monsters can handle
 * doors) and lava (many monsters are not allowed to enter lava).
 */

That was actually a bit of comment from FAangband that got left there accidentally

Thanks for the heatmap code, though, I'll likely use that.

[Ingwe Ingweron]

The latest builds on the nightlies page now have the new pathfinding algorithm.

It will not be perfect.

My aim with this first attempt was to get the basic principles right, and then alter things as people notice things wrong with it. So please, report differences you're seeing, especially when monsters are doing dumb things.

Monsters have seemingly become significantly dumber. For example, in a moated dragon pit, @ just sat in the far corner of the moat from the door and could lead the big D's out singly or in pairs. Even though the room was lighted and monsters were awake, they didn't come streaming out the door to mob the @. They just sat in their room, apparently sniffing the scent of @, but having no idea how to exit the room to find him.

[t4nk]

Monsters have seemingly become significantly dumber. For example, in a moated dragon pit, @ just sat in the far corner of the moat from the door and could lead the big D's out singly or in pairs. Even though the room was lighted and monsters were awake, they didn't come streaming out the door to mob the @. They just sat in their room, apparently sniffing the scent of @, but having no idea how to exit the room to find him.

Hmm, maybe that's because monsters are basically deaf? Dragons have hearing 20 (see monster.txt), so they can only hear the player from 20 - SKILL_STEALTH grids away.

[Ingwe Ingweron]

Hmm, maybe that's because monsters are basically deaf? Dragons have hearing 20 (see monster.txt), so they can only hear the player from 20 - SKILL_STEALTH grids away.

But, don't dragons have excellent sense of smell?