hascode for level

[EricLang]

For programmers only http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

Again I would like to discuss a hashcode for a level in my new database.
it is needed to exchange data between different databases - for example replayfiles.
My first idea would be to take a 64 bits integer to hold to hascode.
The sequence could be a simple xor checksum
the first 32 bits:
- number of lemmings, rescuecount, skills etc.
- all terrain xpos, ypos, drawingmode
- all objects xpos, ypos, triggereffect, drawingmode
- all steel xpos, ypos, width, height
then over the next 32 bits:
- all bitmaps of the terrains/objects - doing not the colors but mask only (just the shape)

[Simon]

There are some probable collision scenarios here.

If the initial count is equal to the rescue/required count, then they cancel via xor, so all equal two values yield the same digest for an otherwise unaltered level. Altering the initial count happens fairly enough.

The hash is then only a measure against bitrot or network errors, but cannot distinguish between level versions.

You could make it more elaborate by arbitrary shifts and multiplications and hope such problems go away, but then it's easier to simply write all level data into a string and hash that with any popular cryptographic hashing algorithm.

Hashing such a string by a common algorithm is still the main advice. It is safe both against collisions from normal level editing and against deliberate collision attacks. It's also much easier to describe to people who want to implement the same system, because you merely have to describe string generation, not the publicly known algorithm with existing code for most languages.

-- Simon

[EricLang]

Ok thanks. I was not planning to do a "xor only". I will take some algorithm and test against a *lot* of levels.

[EricLang]

Again on the hash:

I tried a hash on levels which works fine.
Now the hash will be the same if
all properties of the level (title, releaserate etc.) are the same
AND all terrains are on the same position and have the same drawmode and same index
AND all traps are on the same position and have the same drawmode and same index
AND all steels are on the same position and have the same size and same index

So *not* included are the actual bitmaps the are refering to.
 
Would that be acceptable?

[namida]

I would consider not worrying about draw properties - just worry about stuff that has a functional effect.

So you probably want to consider:
- Stats
- Trigger areas
- The terrain solid/notsolid mask of the entire level as a whole (not of each individual piece). Ignore properties, just use the mask as a whole.

And ignore:
- Level name
- Screen start position
- Graphic set (if the terrain layout is exactly the same and so are the trigger areas, does it matter which set it's built in?)


I would also make sure there's a way to override it for level designers - If I'm fixing a level, I often use a replay to get through the parts that are unchanged *then* interrupt it when I need to do something different. In some cases, the existing replay may not even be affected (for example, Cunning 10 from LPII has been backroute fixed multiple times and yet the very original replay still works).

[GuyPerfect]

Could generate a hash on the resulting bitmap I suppose.