Re: Specifying oxyd shuffling patterns, was: [Enigma-devel] Level "Crossfire in the making"

[Ronald Lamprecht]

Hi,

Johannes HXXsing wrote:
> Ronald Lamprecht <address@hidden> [Thu, Apr 17, 2008 at 10:57:54PM CEST]:
> > > > > > > To guarantee fair distributions and levels that are solvable the
> > > > > > > author can declare minimum and maximum conditions and groups of
> > > > > > > oxyds like:
> > > > > > >
> > > > > > > wo:shuffleOxyd({grp1, max=0}, {grp1, grp2, min=2},    {grp1, grp3, 
> > > > > > > min=1, max=1})
>
> According to your explanation this means that the maximum and minimum 
> conditions specify the number of oxyd pairs split up between groups,
> correct?

Yes - split up between groups, or in case of a single given group
contained within this group.

> > Johannes Hüsing wrote:
> > > There are several ways to restrict permutations. A more obvious one 
> > > would be
> > > to block the permutation, i.e. to form subgroups within which free 
> > > permutation
> > > is allowed. I don't know if this is what you mean by "groups".
>
> This would be achieved by setting the maximum condition to 0.
>
> > Minimum and maximum are arbitrary conditions concerning the given object 
> > sets. Note that the some objects may even be part in several sets - 
> > there are no restrictions at all!
>
> You mean if there are eight oxyds at the corners and the sides, one
> group can contain N, NW, W, SW, S, and the other S, SE, E, NE, N?
> I'd be lost then at what permutations would be legal then.

Yes, this would be an example of 8 oxyds and two groups on which we can
define limiting rules. The shuffling algorithm would not have problems
finding legal permutations. But nevertheless it is an uncommon example.

Let us look at a difficult, but more praxis related example that is part
of the test level suit (ralT019):

16 oxyds, represented by letters a-p:

a bcd
         ijkl     mnop
e fgh

with the following textual rules:

{{a,b,c,d},{e,f,g,h}} should contain min 2 split oxyd pairs
{{b,c,d,f,g,h},{m,n,o,p}} should contain min 3 split oxyd pairs

A solution is (a,i), (b,h), (c,e), (d,n), (f,o), (g,m), (j,k), (l,p)

The important level parts look like:
> ti["O"] = {"st_oxyd", name="o#"}
> ti["P"] = {"st_oxyd", name="p#"}
> ti["Q"] = {"st_oxyd", name="q#"}
> ti["R"] = {"st_oxyd", name="r#"}
> ti["S"] = {"st_oxyd", name="s#"}
> ti["T"] = {"st_oxyd", name="t#"}
>
> w, h = wo(ti, " ", {
> "S  OOO              ",
> "                    ",
> "         QQQQ  RRRR ",
> "                    ",
> "T  PPP              ",
> "                    ",
> })
>
> wo:shuffleOxyd({no["o#*"] + no["s#1"], no["p#*"] + no["t#1"], min=2, 
> log="solution"},
>         {no["o#*"] + no["p#*"], no["r#*"], min=3})

If you set the attribute "log" to "count" the number of solutions will
be calculated and printed on the log stream (34992 different oxyd pair 
distributions).

> Or do you mean that I can define several *partitions* of the set of 
> oxyd at once, restricting the number of oxyd pairs shared between 
> pairs of subsets in each partition? How does the algorithm determine
> if there is a solution?

If there is a solution the algorithm will find it :-)

> > Looking at real examples there are never problems. The algorithm will 
> > calculate the number of remaining oxyd distributions for a check by the 
> > author.
>
> And these distributions will be stored, so the algorithm runs only
> once?

No - with 16 oxyds and no rule you have

15 * 13 * 11 * 9 * 7 * 5 * 3 = 2.027.025

different distributions of 8 oxyd pairs!

> > > What do you mean by linear and circular groups?
> > A problem analysis from the practical real level world gives you the 
> > following usage cases:
> >
> > 1. a room/island with the oxyds at the border - the oxyds are arranged
> >    on a "circle" and it is sufficient to avoid adjacent oxyd pairs.
>
> OK -- I can imagine how to do this in O(n). 
>
> > 2. a path along which the oxyds are aligned - a "linear" pattern, where
> >    it is sufficient to avoid adjacent oxyd pairs, but the end oxyds
> >    may match (e.g. your boulder oxyds).
>
> How many times would you have to go back and forth along the path?

"circular" and "linear" rules do just avoid adjacent oxyds to build a
pair. If a level authors needs more complex rules for his aligned oxyds
he has to add additional rules himself.

> > 3. there is a critical path between two groups of oxyds that can only
> >    be passed a few times (e.g. a crack) - a maximum condition let us
> >    describe these patterns.
> > 4. a fair distribution requires that you always have to travel between
> >    two oxyd groups a minimum number of times - a minimum condition.
>
> This should also be doable with an O(n) algorithm, as long as there is
> only one partition. 
>
> > The further requirements on oxyd shuffling are:
> >
> > Besides the 1.01 colored oxyd pairs, 1.10 will support 3 special oxyds 
> > colors (fake, fart, bold - see refman). They occur in "any" number and 
> > will take in the shuffling process.
>
> Ouch. As each of these stones may occur an arbitrary number of times, 
> this means that storing all possible permutations is out of the question.

The rule based shuffling algorithm implementations is currently limited
to a total of 32 oxyds as I did use bitmaps stored in 32 bit integer
numbers. It could be extended to 64 bit, but I do think 32 oxyds are
enough for the poor player who has to solve the level.

> > Every single oxyd can be excluded from the shuffling process.
>
> Sure, by putting it into a size 1 group.

Putting an oxyd into a size 1 group does not prevent shuffling! The only
way "excluding" oxyds from shuffling by grouping would be to put 2 oxyds
in a group with a min rule that forces 1 pair within this group. And
even then the color would still not be fixed.

In the new API the oxyd stone has a boolean attribute called "noshuffle"
that defaults to "false".

> > At any point within the game the remaining not yet opened oxyds can be 
> > reshuffled (by a bold oxyd or a message). All rules have still to be 
> > observed.
> >
> > All possible shuffling distribution have to occur with the same probability.
> >
> > The shuffling has to be very, very fast! There is no requirement to 
> > generate all distributions on a real run - we just need a single 
> > distribution. 
>
> ok, so no storing of all permutations.
>
> > For test purposes the author should be able to request the 
> > number of remaining distributions - this run may take several seconds.
>
> yep, as you cannot know the number without enumerating them. 
>
> > We did well analyse the problem from the mathematical aspect, but we do 
> > not want to bother level authors with "permutations", etc.
>
> You are already doing so, only that you say "distribution" instead of
> "permutation".

When I speak of "distribution" I mean the pairing of the oxyds. After
the pairing distribution is chosen the coloring of the oxyd can be done
independently in a second step.

"Permutations" are all legal solutions of the colored oxyds.

The level author API has no need of both expressions besides warning the
author that there should be more than a single solution.

> > BTW the problem is mainly a graph theory subject. Andreas did do some research. 
>
> Well, it's combinatorics, which can be represented by graph theory,
> though not exhaustively.
>
> > But the published algorithms do either not fit the complex requirements 
> > or they are to slow and fat (as they do calculate all distributions). My 
> > algorithm is in praxis linear to the numbers of used oxyds :-)
>
> I'd be interested as to how you achieve this with mutiple partitions
> (if you use them). Maybe it's time to look at the source.

"In praxis" means that the worst case, given by rules that limit the
valid distributions to a single one, may result in testing all possible
2 million distributions. But you would need about a million rules to
force this worst case and it is anyway senseless to limit the
distribution to less than some thousand valid solutions.

Please have a look at the source (oxyd.cc and lua.cc for the translation
of linear and circular to min, max rules). Besides the window faces 
reflections it is likely the most complex algorithm in the engine. If 
you like to add comments and explanations to the problem and the
algoritms, you are welcome.

If you check the algorithm thoroughly please try to verify that every
legal distribution occurs with the same probability - I did not yet 
verify the influence of the single special oxyds on the probability.

Greets,

Ronald