A list of events/advice, but with no two happening too close together?

Authoring General Design Discussions
1

So I have a problem in constructing randomly produced dialogue. I have 10 pairs of pieces of advice that contradict each other, and I want the user to have the opportunity to look through them all.

But here’s the thing: I don’t want the contradictory pieces of advice to appear next to each other too soon.

It’s possible to just random-shuffle the pieces of advice until no two opposite ones are adjacent or even 2 apart. That probably wouldn’t take too many iterations. It took on average 60, which would be acceptable, even with JavaScript, which can be slow.

But that got me thinking of ways I didn’t have to rely on the mercy of the RNG. And I came up with this, where the corresponding bits of advice are a1/b1, a2/b2, etc.

With n pairs of contradictory advice, sort (1, …, n) in random order. Let L1, L2, etc be the elements of the new list.

Then you could have a new list of (a(l1), a(l2), …, a(ln), b(l1), b(l2), … b(ln))

(Note–we can and probably should give 1/2 chance of flipping a(l3) and b(l3), etc.)

For instance in a simpler example 1,2,3,4,5 might go to 2,4,3,5,1 and then 2a,4b,3b,5a,1b,2b,4a,3a,5b,1a.

As I can assume people won’t play through my effort more than once (it would be for Neo Twiny Jam) they wouldn’t see this sleight of hand until it was too late. But I wanted to check if other people thought of a different solution so the distances are staggered more naturally and if any people had general thoughts on randomly or at least pseudo-randomly spacing events so certain pairs/groups don’t come too close.

3 Likes
2

if you want to make the pairing less obvious then you may want to generate a random derangement?
permutations - Generating a random derangement - Mathematics Stack Exchange
It also has a link to an algorithm but thats getting rather deep in mathematics :stuck_out_tongue: you might as well list a1…aN in original order and then b1…bN in random sorted order :stuck_out_tongue: Still has a chance of 1 in N of bN immediately following aN though.

Nvm your approach looks more random than what I was thinking of…

2 Likes
3

I’ll sometimes use what I’ve always called relaxation though I don’t know if that’s quite an accurate use of the term. Shuffle all the elements randomly and then push each pair farther apart. Of course, this may push other pairs closer together, so iterate until all the constraints are met, or you hit too many iterations. But it usually only takes a few iterations, if the problem isn’t too tightly constrained.

I’ll do this for placing objects in 2D space: generate random x,y coordinates, then check each pair and push them outwards until they’re a minimum distance apart. If there are too many objects it’ll settle into them pushing into basically a hex grid (as packed circles do) but if you have enough extra space it works well. And it’s usually pretty easy to code.

2 Likes
4

Is the advice coming from just one NPC? Or multiple? One thing you could do is have multiple NPC’s, each one with one good piece of advice and one bad piece of advice. This is a favorite device of R. Wayne Schmittberger’s (my favorite puzzle writer). That makes it a fun way to deduce what is right and what is wrong (assuming the player eventually realizes that everyone is saying one right thing and one wrong thing)

Otherwise - I had a really similar problem to this when trying to figure out the hint system for Midsummer’s Eve. I didn’t come up with a very elegant solution yet :joy: so I’m following this thread :eyes:

2 Likes
5

Haha, usually I would be writing puzzles. But this time I am going for a different effect.

Yes, this seems tricky! You definitely want to be able to give the player information, but not too much too quickly, and not too much duplicated.

I’m assuming you mean how to divvy up the hints among the NPCs and not the order in which the NPCs give you each hint.

It might be worth a separate thread to work out, because what you have is qualitatively different, and others may have different ideas from me. But I’ll take a shot here. There I think you have (let’s say) 6 NPCs each with potentially 4 clues each and you want to be able to get all 12 clues, but balanced. Since some clues follow the others, you probably don’t want someone who gives hints 9-12 for example.

So why not assign them as follows, where they only pick from 1 hint if you have 0-2 points, they give 2 for 3-5, 3 for 6-8 and 4 for 9-11?

  • NPC 1: 1-6-7-12
  • NPC 2: 2-5-8-11
  • NPC 3: 3-4-9-10
  • NPC 4: 1-4-7-10
  • NPC 5: 2-6-8-12
  • NPC 6: 3-5-9-11

This is all very vague but I hope it’s a start!

1 Like
6

Thanks! Yes, that seems quite useful. It seems like it would go along pretty quickly, even with the potential regression you noted of, say, (4 15 5 3 …) moving the 5 off to the end, but then 4-3 are too close. It would be fun to run a program to see how many changes, on average, are needed.

Your idea got me cued into one approach that feels hacky, but it also feels reasonably randomized:

  1. sort the odd numbers 1, 3, 5, 7, …, 2n-1 in random order
  2. place 2 first. We can just choose a random number between 0 and n inclusive, then disqualify anything within 2 of 1. So for instance in the unshuffled 1 3 5 7 9 11 (with n = 6) would have 7 possibilities where you could insert the 2, but inserting at array element 0, 1 or 2 would be wrong. So we would pick random(3, 7). Then we’d pick a number from 0 to n+2 for 4, etc.
  3. of course if 1 is in the middle at first we would have to tiptoe around it e.g. 5 3 1 7 9 11, slots 1-4 would be illegal. But that’s not too bad … we could say, if the forbidden number is at index z, then slots z-1 to z+2 would be illegal unless z was close to the edge. That means 4 of the n+1 are illegal, so we pick a random number from 0 to n+1. If it is >= z-1, add 4. if z > n-2 then pick a number from 0 to z-2. If z <= 2 pick a number from z+2 to n+1. (My arithmetic may be off on the edge cases. But I hope the general procedure makes sense.)

This algorithm will be unable to produce some valid sequences. For instance, the trivial

2 4 6 8 10 12 1 3 5 7 9 11

won’t be possible, since we would have to place the 2 by the 1 to start. To get around this, I suppose we could sort the even numbers randomly before dropping them in. But that feels like it is getting too cute. There looks to be enough to work with.

7

shuffle-relax.zip (886 Bytes)

OK, not as simple as all that, but a lot of fun once you get it going. Seems pretty efficient, too, unless this is still buggy (they’re surprisingly tedious to check by hand). But the numbers I’m getting are that if you only want to avoid them being adjacent, it averages slightly less than 1 swap per run (averaged over 100 runs), and then going up from there it averages about 3 swaps per space apart? Even going up to 6 spaces apart it was around 18 swaps on average and the bad individual sets were pushing 30 swaps.

Anyway. Thanks for a fun little puzzle!

2 Likes
8

I’m interested in this problem, basically later I must handle a situation whose I have basically two NPC together with the, and avoiding mutual justapoxitions and incongruences in their banter/reacting isn’t easy. Tentatively, I’m for a “priority system” of sort, the prioritary reaction excluding the incongruities from the other NPC’s selection of reaction, if not even leading the other NPC to support/second the prioritary reaction. The question is, this mechanism can be extended for the few turns needed to not be close together ? Sincerely, I can’t answer this crucial point.

Now my attention is on a pair of events whose by nature are sequential, buth both together form an high wall of text, and I’m looking how to give some space between the two long texts without render innatural, gratuitous, the justapoxition (and one of these event MUST keep its naturalness)… so I’m following this debate.

Best regards from Italy,
dott. Piergiorgio.

2 Likes
9

If you can exclude the reactions based on a single past reaction, then can you extend that by looping over a list of priority reactions and excluding incongruities based on all of them?

Because if you can do that, then you should be able to use a list as a queue, so each turn you add one priority reaction to the tail of the queue, and if the list is longer than the desired delay, remove one reaction from the head of the queue.

2 Likes
10

Interesting idea, later I’ll add it to inotes.t (the “source” of only commented notes of my WIP) Thanks.

oh, and being a long-timer OS user, I perhaps care too much on commenting things… some opinion on the ratio code/comments ? sorry for the drifting…

Best regards from Italy,
dott. Piergiorgio.

11

Is the first advice random? I’d simply use weighted random, (selection) sorted by most distance, with most recently viewed advice be a closer distance.

With proper initial weights, it should be fine, even if they cycled on eventually.