The Tavern

The idea of this proposal is to introduce terrain that only affects the player, never monsters. Call it special cave mud, vines that grab at you from the ceiling, forcefields of zot, whatever. The point is when you move on a tile with this stuff, it takes .4 auts more to get through it, no matter what. No flying over or swimming through it to avoid the penalty. It does not affect monsters at all. It has no combat effect. It's not like shallow water.

Where do you put it? You put at least two tiles worth of this stuff in every cycle in the dungeon layout. If there's a way for the player to walk around and come back to the same place without a normal move speed monster gaining any turns on them by taking a shorter path, the player must walk through at least two mud/vine tiles to make that happen. I won't describe exactly how this can be made to happen, but it is algorithmically computable etc. Not magic, not rocket science.

It should also be placed around stairs so that luring to stairs always gives monsters some moves on the player. I'd say about four tiles worth would be a good target. You want to place it a bit sparsely so that normal, short distance repositioning is not too severely punished, but long distance luring/kiting, luring to stairs, and pillar dancing become significantly less practical. In particular, you don't want a lot of this stuff around junctions and doorways, you want it in big stripes across open areas and breaking up longer stretches of corridors.

Now you might ask, why not just make monsters move faster? Well, seems to me that if this were such a good idea, it would already have happened, but the main thing is to preserve as much as possible on the length/time scales viewed as within the realm of legitimate crawl tactics, while penalizing the long distance, infinite cycle, and stair abuse stuff. This is why it's good for it to be terrain, so that the player can avoid it when executing normal tactics.

As far as digging goes, just make tiles where walls have been dug out always have this terrain, so the player cannot cheez their way around it. It is good for digging to have a tactical downside anyway.

This is an interesting idea that I haven't seen before. I like a lot of things about it, but I'm concerned that auto explore may put players into situations where they have a substantial quantity of the new terrain behind them; situations they would try to avoid manually.

Yeah, it's important for it to be sparsely placed so that you don't unluckily land in a lot of it. I'd say veins of it 2 squares wide in the open, placed so that you that get some fixed number tiles on a typical shortest path of length X. Around stairs, you'd lay it on thick, but if you autoexplore into that, at least you're near stairs.

Naga already struggle to kite, lure, and pillar dance on account of movement delay, but playing one of them successfully means you actually want to execute these tactics even more. Since they can't kite a long distance when they attract too much attention, they have to religiously lure monsters long before normal-speed species would feel threatened. If they don't, eventually they'll find that it is too late. They can't lure as well, so they spend more time doing it because the result is even more important to them than normal.

A global player nerf to movement speed might do some useful things to the game, but I would expect it to have exactly the opposite effect on luring than the effect you are looking for.

Yes, I too am skeptical about the extent to which luring can be eliminated. It would remain the case luring is your best option in some cases and the overall player nerf may well create new situations where that's the case. On the other hand, losing a turn against monsters every cycle around a pillar and two turns on any approach to a staircase makes a pretty big difference over the current situation and kills some of those most facile tactics.

Doesnt seem this would actually fix pillar dancing unless every wall square has kudzu near it, in which case, normal repositioning will be effected as well.

Also wouldnt fix just standing on the stair and shouting+stairdancing over and over.

Hm, what if there was a defensive bonus for standing still, that only took effect after X turns

The point of pillar dancing is that you do it repeatedly to recover hp/mp and/or scum energy randomization to create a gap so that you can get upstairs. This would stop both of those uses.

You'll notice that I do not claim that this will fix stair dancing, only that it penalizes long distance luring to stairs. I would also remind you that there is an entire dungeon branch based on stair dancing, which should give you a feel for how much will to fix it exists.

Unless every single wall tile that isnt part of the outer wall of the level has at least one mud/vine terrain sticking out of it at a cardinal direction, pillar dancing will still be possible. You just find the one wall tile that doesnt have mud/vine sticking out at a cardinal and run around it diagonally... therefore, to eliminate pillar dancing, all such tiles will need to have mud/vine sticking out of them. This means that normal move tactics (ie, in and around corridors and walls) will be eliminated by your proposal.

And the point about stairdancing is, if players cant lure, they may simply abuse stairdancing more to compensate, leading to just as tedious a game as before.

You are mistaken.

How are they mistaken?

I think we should keep the issues of luring and of stair-dancing separate. Each is hard enough to tackle on its own, no need to conflate them. If we had a way to counteract luring which puts more emphasis on stairs, well, than we'd think about how to nerf stairs afterwards.

The proposal itself is novel and interesting. I have my own new idea for doing something against luring, but I'll definitely keep terrain in mind. Thanks!

Well, try drawing yourself some mock-up crawl maps and decide for yourself whether his claim about how this terrain would have to be placed holds up. I believe you will see it is very easy to devise patterns of terrain that break up cycles in the map in a way the player can't avoid as he describes without using a huge amount of it.

@dpeg: thx.

Indeed Shard1697 is incorrect, it woudn't require every wall square have kudzu adjacent, it would require (at minimum) that every contiguous chunk of wall that doesn't connect to an outer-border have terrain adjacent to it somewhere, and that in the event you have a non-optimal walking space (think a big "C" where you don't need to walk along the inside of the "C" part) that it not be in that area (the interior of the "C")

There are also some non-trivial patterns that form an effective "loop" , that you would need to apply terrain to, as a simple example, given two horizontal lines of walls of the same length, I can treat it as a big square:

In this example (@ is the player, M is a monster, and T is a terrain square), even though terrain is attached to both contiguous wall sections, I can simply ignore the terrain and walk around the two disparate wall sections as if it wasn't there. (The space between the two disparate wall sections is technically "non optimal walking space" when talking about walking around the square that encompasses the two sections) There would need to be terrain on the "outside" of the loop (This gets weird and complicated when you add more complexity to it, for example what if there are three sections like that, or one to the left or right that's perpendicular to these two, keep in mind that I can also figure 8, or adjust the diagonal slightly if need be to avoid terrain if it's in a slightly wrong place)

This makes reliably detecting all "loops" that one could exploit fairly difficult, and a heavier-handed solution that was more certain would probably result in enough terrain that it violates the "mostly be able to re-position in combat normally" condition, It'd be an interesting problem to solve, but I'm not sure the solution doesn't devolve into brute-forcing every path from every single square that the player could start at (I don't think that is reasonable, personally). You could also do something like draw a diagonal line every of terrain 3 squares, of course I would call that "impeding normal combat repositioning" but I'm sure everyone has a different threshold for that.

As a non-trivial example, try to figure out the minimum placement of terrain squares needed to force the player to step through one while pillar dancing in the following:


Then create a generic algorithm that applies that terrain without applying more than is needed.

Also what happens when digging, does that create new Terrain squares (What if the player isn't creating a loop? Does it matter?)

Perhaps a simpler form of this effect can be achieved by having the player periodically take .4 extra to move creatures in LOS (Although moving while monsters are in LOS isn't a totally reliable indicator of "luring" either) that way you wouldn't have to worry about where the player was, only how many steps they'd taken. You could flavor it as the player "stumbles" or "ducks trying avoid an attack" or something, I would want to indicate that it's about to happen on the display somehow, as having it happen at unpredictable periods sounds really annoying, and having it happen at predictable increments would be worse, as you'd have to count steps so you knew. I'm not sure that has an easily solvable UI that isn't also overbearing, maybe a status light that said like "Sure steps(3)" indicating how may more steps you could take until you'd stumble or something? Or I guess it could be an unpredictable interval, but I don't think I'd enjoy not knowing how many steps I had to re position in combat safely.

Look into algorithms for finding minimal spanning trees. They can be adapted to do stuff like what's described in the OP. Also, the digging issue is in the OP.

The problem isn't optimizing once you've detected all the nodes (That's well documented and easily computed), it's detecting the nodes in the first place.

For example, given this map:

There are 5 different loops you can make, 3 of which have 3 or more possible equally optimal paths.

You could declare that this is an undirected graph and interpret every point as a node, but then you don't need the minimum spanning tree, you need the minimum number of *collisions* between all the possible trees that form loop paths.

Or you could declare the points where you 'turn the corner' as your nodes, in which case it becomes a trivial problem, but how do you detect the nodes them in that case to begin with, how do I reliably say "this point is the one that you must cross in order to make any of N loops" where N is potentially unbounded (Drawing a diagram of it is beyond my willingness to do so in a terminal, but let's say you have a central "circle" with varying width circles around it, where's your "corner" which squares are the "nodes", in your undirected node graph, the places you could "land" or "take off from" the central circle is only limited by the number and shape of the shapes which surround it.

An example:



There's always a system of curves connecting the components of wall such that any given loop encounters one of the curves. Discretizing two such systems carefully will give you suitable terrain. So the question is how to find such a system.

I just woke up in a really shitty hotel without eating since yesterday morning, so this is probably going to contain errors, but here's a little outline of an algorithm for you: The nodes of your graph are going to be connected components of wall in the level. The edges will be represented by player traversable paths that connect a tile adjacent to one of these components to a tile adjacent to some other component. It's fine if these paths have only one tile. You don't have to be very careful about choosing these paths, you can just take shortest paths between suitable randomly chosen pairs of tiles, but generally you want to do this a little bit efficiently so you can get as little terrain as possible. You want an edge for every pair of components. Now pick a spanning tree of this graph that is minimal with respect to total path length. Put the terrain along the corresponding paths, thickening them as necessary to be sure the player can't avoid it locally by moving diagonally.

Now you probably notice that you only want a "small" spanning tree for this graph, so probably a lot of the paths we took above don't actually affect the outcome and can be thrown out. Heuristics like introducing only edges up to some particular length should work and keep the number of paths you have to find under control.

Well, right, but that doesn't produce the *minimum possible* number of such terrains, only a set of terrains that's guaranteed to break all possible loops.

Your example even has several more terrain squares that would be strictly speaking required.

If we aren't trying to guarantee that we put as few terrain squares as possible, only that the loops are guaranteed to be broken, then yes, that solution is trivial (or at I can think of a very easy solution off the top of my head.)

Whether it qualifies as "not really restricting normal repositioning" is a subjective qualification, of course.

You should think about it. I think you'll see you can't get away with significantly fewer and less intrusive terrain tiles that what's described in the above algorithm with some obvious optimization to choice of edges in the graph described there.

4 instead of 8, is it significantly fewer?

This is why I chose not to discuss the details of this in the OP.

Is there a guaranteed path without those special tiles to stairs? Otherwise I don't see much difference with something like -Swiftness which is applied for running too long distances with monsters in view.

Well, I only chose to mention it because the 'minimum possible' solution is challenging, the solution you propose isn't minimal, but works just fine, as long as your target isn't "minimum possible tiles", that is what i would consider the 'obvious' solution, and as you say, you can make some tweaks to it such that it's *less* intrusive (choice of edge, number of divided segments, etc.) but getting to a minimum possible solution is challenging.

If you're argument is that solution is "good enough", that's fine, I don't specifically agree or disagree, it's just not what I found interesting.

You might also possibly be able to prove that there is no algorithm that can make the same no-looping-without-encountering-terrain guarantees which will put less terrain tiles into place.

Right, these kinds of optimization problems can have some interesting math to them.

Another thing here is that you want it to be clear to the player that when they encounter this stuff, there's no way to get around it, so while you can get away with fewer tiles if you just want to punish pillar dancing by putting the terrain near corners so that if the player goes around they lose turns to monsters cutting the corner, you really want to make all kinds of long distance luring slower and less advantageous. You would probably put veins of the stuff in open areas and bits of it in long corridors just for good measure, even when there isn't a cycle problem.

Or we might just generate a dungeon without any circles...

But then that'd be boring! Nonlinearity for the win!

I find manual exploration more boring and I suspect autoexplore will be very bad with this new terrain features. Without circles autoexplore will be really close to manual exploration I think.

Please explain. I only count three loops: around the pillar on the left, around the pillar on the right, and around both together.

1.You can make a figure 8 around the two

2. You can go around the left side of the left wall, make a loop around the right wall, then go back around the one on the left side of the left wall in the other direction.

Actually you can do that swapping left for right too, so that is one i missed in my account (bringing the total to 6) although the "backside of the right wall" loop is pretty awkward, and almost identical to the figure 8 for which squares you need to step on.