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

[Ronald Lamprecht]

Hi,

Johannes Hüsing wrote:
> The spec you linked to seemed less complete than the one you
> posted before, so I think this is the more recent version:
>
> Am 13.04.2008 um 19:37 schrieb Ronald Lamprecht:
> > > > > 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})
> > > > >
> > > > > As a shortcut groups of oxyds can be declared to be positioned either
> > > > > circular or linear. This declaration expands to all rules necessary to
> > > > > avoid any neighbour oxyd pairs.
> > > > >
> > > > > wo:shuffleOxyd({grp(ox1, ox2, ox3, ox4, ox5, ox6), circular=true},
> > > > >    {grp2, linear=true})
>
> I am not getting what you are driving at here.
>
> 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".

As written in the concept draft and in the refman:
> group         - a list of objects

That means a "sorted set".

"Subgroups" (in the mathematical meaning) do not fit the requirements 
(see below).

> Another method, but in most cases unfeasible, would be to list all 
> admissible
> permutations.
>
> A more geeky one would be to list the elements of a generating system
> of the permutation group, if the set of admissible permutations is a group.

Would not fit the requirements (see below).

> What do you mean my maximum and minimum conditions? Are these the
> maximum and minimum number of oxyd pairs in each group? It may be
> unfortunate to formulate restrictions on permutations without a 
> construction
> rule -- the proportion of admissible arrangements may be so small that
> one cannot rely on reshuffling until conditions are met.

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!

Looking at real examples there are never problems. The algorithm will 
calculate the number of remaining oxyd distributions for a check by the 
author.

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

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.

Every single oxyd can be excluded from the shuffling process.

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. For test purposes the author should be able to request the 
number of remaining distributions - this run may take several seconds.


We did well analyse the problem from the mathematical aspect, but we do 
not want to bother level authors with "permutations", etc. BTW the 
problem is mainly a graph theory subject. Andreas did do some research. 
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 :-)

> Maybe I'll just leave out shuffling until the new API is done.

Well, the shuffling is done and can be tested with the published 
development version. Some oxyd shuffling test levels are part of the 
test suit.

Greets,

Ronald