Monster path finding in 4.0.5

[Nick]

Nick, please take a look at how "passable rubble" is being addressed in pathing. Sauron couldn't "find" @ because of passable rubble. A little stone to mud, and then Sauron could home right in on him. Regular rubble used to block his progress, but not his pathing, but passable rubble didn't used to prevent Sauron's pathing at all.

Excellent, thank you.

[Ingwe Ingweron]

Nick, please take a look at how "passable rubble" is being addressed in pathing. Sauron couldn't "find" @ because of passable rubble. A little stone to mud, and then Sauron could home right in on him. Regular rubble used to block his progress, but not his pathing, but passable rubble didn't used to prevent Sauron's pathing at all.

[Nick]

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.

Good, thanks. I was expecting to have to adjust numbers, but have not actually done any real playtesting myself

[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?

[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]

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.

[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.

[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).

[t4nk]

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

Now that looks like how I expected pathfinding to work!

[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.

[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.

[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]

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]

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.

[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.