I am now 90% done with the generation and saving of Global Piece ID’s (gpid).
I have one final design issue I am not quite sure how to tackle.
The GameModule and each Extension have their own sequence of gpid’s commencing from 0 so we need to prefix each Extension gpid with a unique identifying string.
I’m not sure whether to auto-generate a random string and just use that, or allow the user to enter an ID String. If a module has multiple extensions, then a non-blank ID is mandatory.
Perhaps both - default the ID string to a unique random string, but allow the user to over-ride it.
Joel, you seemed to indicate you might have some code to create a unique id?
The Extensions loader can compare the ID strings of all Extensions loaded and warn of any clashes.
Thanks Joel. 32 characters is a bit over the top as I only uniqueness between the different Extensions belonging to a single module. I guess I can just take the last few characters of a genererated uuid.
I would be very careful about generating a random “namespace” with too
few bits, since if a module designer gets unlucky and has a collision,
he’s screwed.
I think the chances of this would be so remote as to be not worth worrying about. I think we just give the designer the option to over-ride it with something meaningful.
The main reason for not using a hugely long id is for display reasons. I am displaying it in the PieceDefiner at the moment.
I’m not sure what guarantees of uniqueness you get from the Java UUID
for subsets of the characters.
If all you care about is a single module, then you should be able to
do that just by incrementing a counter during editting. 32 bits then
gets you 2-4 billion pieces, and nobody is making games quite that
big (yet).
If you need to support extensions as well, they could also be given
unique numbers. At the cost of some additional size restrictions,
one could dedicate the top byte of a 32-bit word to identify which
extension one has. That limits extensions to between 127 and 255
(excluding the main module), and restricts the unique IDs inside the
main module or any extension to 24 bits, or only 16 million. Should
be enough.
We let the module designer specify the extension namespace himself.
The only way you could get a clash that way is by pulling in extensions
from more than once source. In that case, one or more extensions need
to have their namespaces renamed. The only problem remaining is how to
update pieces which came from namespaces which have been renamed.
Nothing guarantees uniqueness of random UUIDs at all, despite the name.
It’s just that generating two identical random strings of that length
is ridiculously improbable. When you go with something significantly
shorter, you’re asking for trouble.
I am going to generate a random 6 character id for the extension when it is created, but let the designer over-ride it. This get’s round the problem of people not bothering to generate an id.
The probability of clashes is still so remote as to not be worth spending braincells on.
I will add a check to the extensions loaded to report duplicate namespaced extensions.
I propose to do that by placing a large warning notice saying don’t change your extension id if you ever want to update existing saved games.
Just my 2 cents: generating random IDs in the hope that there are no
collisions just sounds like a bad idea. I can see someone using the
same seed on two different occasions and then pulling their hair out
because they can’t figure out what’s wrong with their module. The
numbers are never really random…
On Jan 28, 2008, at 5:23 AM, Michael Kiefte wrote:
Well, the fundamental problem that these random UUID generators are
trying to solve is a hard one: How do you generate a globally unique
ID without resorting to either
a) A shared name manager who doles out those addresses
or
b) Communication between ALL instances of the program generating
names
The best you can really do is to provide some probabilistic estimate of
the likelihood that any two IDs are really unique. That is one reason
that the built-in Java UUID mechanism generates such large strings. It
both provides a larger potential space, thus directly minimizing the
chance
of collisions, and it (in some forms) allows various tweaks which also
reduce the chance of random collisions.
There are a set of standards for various forms of UUID (sometimes also
called GUID – Globally Unique Identifier), which have different demands
on the outside information made available to the system. The type 4
(random) type is the most commonly used because it does not require any
outside information (such as host name, access to ethernet MAC address,
etc.) While it would be possible to, say, set up the Vassal server to
be a central namespace manager, it would mean that you couldn’t create
any new extensions or whatever without both being connected to the
internet
and having the Vassal server up and running.
Perhaps it could be a combination of a semi-unique identifier chosen
by the user as well as a randomly generated string? This has the
advantages of both a deterministic identifier (a perceived unique
identifier for an entire module for example, or even the module name
itself) as well as a random element. This is how I use the tempfile
-p command in Linux.
The chances of generating a duplicate in the first place is so small as to be insignificant. The only significant risk of a duplicate being generated is by allowing the user to over-ride my randomly generated code and manually entering a duplicate.
If a duplicate is generated, it is easily detected, reported and fixed.
Therefore, no fancy code is required to generate these id’s. I am seeding the id with the final 6 characters from a call to java.util.UUID.randomUUID().toString() but allowing the module developer to override this.
At module load time, I am checking the id’s on all extensions loaded and reporting any duplicates.
