Posted by
| Nick Gammon
Australia (23,158 posts) Bio
Forum Administrator |
Message
| These are all issues I have been thinking about, and I admit that the solution is not totally simple.
First, the hashing idea. Certainly you could store the room descriptions, but I think that the hash is shorter, especially if you also have to store the name, the exits, and maybe nearby descriptions.
The whole idea of a well-designed hash is that it is very, very unlikely that you can get duplicates. A major reason for this is that hashes are used to "sign" documents digitially.
Say, for example, Shadowfyr gave me a digitally signed document in which he promised to pay me $100, and I could change that to read $100,000 and then make minor changes (like adding spaces, or slightly rewording it) and keep re-hashing it until I got the same hash, then the signature would not be very useful.
In fact, the MD5 hash is a 128-bit hash, and therefore has 2^128 possible combinations (340,282,366,920,938,463,463,374,607,431,768,211,456 combinations), so you can see that for a few thousand rooms, a collision is not that likely.
If you were worried, you could do a 256-bit hash (SHA256 which is provided in the MUSHclient Lua libraries) which gives you 2^256 combinations (115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 possibilities)
Even the 256-bit hash only requires storing 32 bytes (maybe 64 if you stored them in "hex" format).
The problem with duplicate descriptions is hard to solve as far as I can see. I agree that maybe hashing (or storing) the exits is not a great idea, and in any case something like "a path around darkhaven" could easily fail both our tests. My test of the exits might not help (the path might have various entries that are east and west) and Ksilyan's idea of proximity might also fail, as the paths are likely to be adjacent.
The only (fairly) certain test I can think of is to look into nearby rooms, using Ked's algorithm, and stop after getting one or 2 rooms away (and then going back, if we are able).
Here is an example of what I am talking about. Say there is a long north-south road in Darkhaven, where every room is called "Vertic Avenue".
Now as we enter each room we take all possible exits, and add their descriptions to our hash (or append them to the master description).
Now we have something like this:
Vertic Avenue -> east -> butcher -> west -> baker
This gives us a different hash from:
Vertic Avenue -> east (no room) -> west -> (no room)
or:
Vertic Avenue -> east -> arms supplier -> west -> cooking trainer
However the case of:
Vertic Avenue -> east (no room) -> west -> (no room)
might have multiple occurrences, which is why you probably have to try further afield. Using the terminololy from the algorithm above, you might need to generate 10 or so "particles" to guarantee uniqueness.
I can forsee other difficulties, though. For one thing, one-way exits might make it hard to go back to the room under investigation.
Maybe there is a more elegant solution? |
- Nick Gammon
www.gammon.com.au, www.mushclient.com | Top |
|