11 Jun, 2009, Runter wrote in the 161st comment:
Votes: 0
David Haley said:
Runter said:
With that definition any 2d array to find any type of data with a list member would be a hash.

Welllll technically it could be, although it would be a fairly terrible hash table, losing basically all benefits of hashing. :tongue:


Which is my point. It's unintuitive to call that a hash me thinks.
11 Jun, 2009, Scandum wrote in the 162nd comment:
Votes: 0
Runter said:
I'm curious of why you call it hashed since it bares no resemblance of what a hashed data-type would function like.

It bares a resemblance to string hashing as is common in Diku muds, though primarily the compression part of it. Though the official name of that is a shared string table.

Would 'shared' be a better definition? So then we'd speak of a shared tile index grid and a tile pointer grid.
11 Jun, 2009, David Haley wrote in the 163rd comment:
Votes: 0
Well, Diku MUD string hashing is actually hashing, although yes, it implements a shared string table. It's not that the "official name" is a shared string table: that's just the concept whereas the hash table is the implementation. E.g., "set" vs. hash table vs. binary tree: the latter are ways to implement the abstract data type. What you're describing isn't hashing, it's something else…

I suspect that if one were to actually use a hash table to implement the world, you'd end up with something more memory efficient than what you proposed, as you wouldn't have to store a bunch of pointers, even if they all point to the same thing.


(btw, the thought of data structures "baring" anything is kind of scary… how about "bearing"? :tongue:)
11 Jun, 2009, Scandum wrote in the 164th comment:
Votes: 0
David Haley said:
I suspect that if one were to actually use a hash table to implement the world, you'd end up with something more memory efficient than what you proposed, as you wouldn't have to store a bunch of pointers, even If they all point to the same thing.

I don't think a data-less algorithm would create a realistic world map, but I could be wrong.

A 2nd layer of compression should work well though and should significantly decrease the load and save time of the world map.

David Haley said:
(btw, the thought of data structures "baring" anything is kind of scary… how about "bearing"? :tongue:)

English being my 2nd language showing through. :)
11 Jun, 2009, David Haley wrote in the 165th comment:
Votes: 0
Scandum said:
I don't think a data-less algorithm would create a realistic world map, but I could be wrong.

I must have missed something… how did we start talking about data-less algorithms?

Scandum said:
A 2nd layer of compression should work well though and should significantly decrease the load and save time of the world map.

I agree that a lot could be accomplished with compression, even something fairly simple like run-line compression.
11 Jun, 2009, Runter wrote in the 166th comment:
Votes: 0
David Haley said:
(btw, the thought of data structures "baring" anything is kind of scary… how about "bearing"? :tongue:)


Delayed jab. Nice. :P
11 Jun, 2009, David Haley wrote in the 167th comment:
Votes: 0
I live to serve, Runter. :devil:
11 Jun, 2009, Scandum wrote in the 168th comment:
Votes: 0
David Haley said:
Scandum said:
I don't think a data-less algorithm would create a realistic world map, but I could be wrong.

I must have missed something… how did we start talking about data-less algorithms?

You were talking about using an actual hash table. In which case you'd need a key generating algorithm.

The way I see it if you use anything other than the key to generate an index you're dealing with compression, rather than hashing.
11 Jun, 2009, David Haley wrote in the 169th comment:
Votes: 0
Scandum said:
David Haley said:
Scandum said:
I don't think a data-less algorithm would create a realistic world map, but I could be wrong.

I must have missed something… how did we start talking about data-less algorithms?

You were talking about using an actual hash table. In which case you'd need a key generating algorithm.

The hash function has nothing to do with what the map looks like.

Scandum said:
The way I see it if you use anything other than the key to generate an index you're dealing with compression, rather than hashing.

I guess this might be another case of non-standard usage of a term, then.
11 Jun, 2009, Scandum wrote in the 170th comment:
Votes: 0
Hrm, we're probably talking about different things now. How about refining the terminology as following:

If you would attach a linked list of rooms (or objects) to an unshared tile that'd be a form of hashing and a lot more efficient (cpu wise) than a global linked list, and quite likely faster than a global binary tree.

So in that regard the pointers in the grid would function either as a shared tile pointer, or as an unshared tile pointer dual-functioning as a hash bucket.
11 Jun, 2009, David Haley wrote in the 171st comment:
Votes: 0
I would much rather that we use the terms to mean what they normally mean. A hash table is something that takes an object, translates it to a number (with the hash function), and uses that number to find an appropriate bucket. It's an orthogonal concept to "tiles".

A hash table doesn't make its buckets do things if they're empty. Things are either in the hash table or they're not. Basically you're taking some kind of map handling default tile logic and conflating that with the notion of a hash table data structure.
11 Jun, 2009, Runter wrote in the 172nd comment:
Votes: 0
We'll have to leave this debate for scholars to drone over in years hence. It's not like there's actually an industry accepted term or definition for hash functions we can turn to anywhere. ;)
11 Jun, 2009, Scandum wrote in the 173rd comment:
Votes: 0
David Haley said:
A hash table doesn't make its buckets do things if they're empty. Things are either in the hash table or they're not. Basically you're taking some kind of map handling default tile logic and conflating that with the notion of a hash table data structure.

If it's such a new and daunting concept I guess that means I get to give it a brand new name, and hence I dub it a 'shared container table', accessed by a pointer grid.
12 Jun, 2009, quixadhal wrote in the 174th comment:
Votes: 0
David Haley said:
Quote
If you want to display a map, you can call your generation function on a range and only create the single room you are in (but show X rooms around if you like).

No, for this to work, you would have to generate every room always in the exact same order – in other words, to guarantee that the random generator produces the same values, you need to make sure that not only do you start with the same seed, but also you generate the rooms in a deterministic order. So, just running on some range would violate that, and you would not necessarily get the same things as if you started from a different range.


Nope, you're not seeing what I was talking about. If you use a coherent noise function (IE: Perlin), the same point will always yield the same value.

If you're using a plain old PRNG, then you have to be at the same point in the sequence, yes. That means you'd have to loop through generating your numbers from X_MIN and Y_MIN to whatever your current x/y coordinates are, which is ugly but you don't need to actually generate the rooms. Of course, in that case, you have a fixed size anyways, so you might was well just pre-build your grid.

I prefer the coherent noise approach, as you don't have to limit yourself in size, just ensure that the coordinates line up and that your function's range is going to give decent results (IE: you're using a granularity that will give each coordinate a similar but different value, so you don't end up with 4000 grassland in a row).

As to the pointer-grid issue… If we're talking C here, that's a horrible memory hog, since you do need X * Y pointers, regardless of how you handle the rooms themselves. It would be far better to use a function f(x,y) that would return a room, since it could use a bucket hash internally, which might only be 1000 buckets that get rooms generated and added to them as needed. If we're talking a language that supports hash tables/associative arrays, then you're good… since they would handle keeping it a sparse array internally.
12 Jun, 2009, David Haley wrote in the 175th comment:
Votes: 0
Scandum said:
David Haley said:
A hash table doesn't make its buckets do things if they're empty. Things are either in the hash table or they're not. Basically you're taking some kind of map handling default tile logic and conflating that with the notion of a hash table data structure.

If it's such a new and daunting concept I guess that means I get to give it a brand new name, and hence I dub it a 'shared container table', accessed by a pointer grid.

It's not new and daunting, it's just a misuse of terms. :shrug:

quixadhal said:
Nope, you're not seeing what I was talking about. If you use a coherent noise function (IE: Perlin), the same point will always yield the same value.

Sorry, it would appear that I responded too quickly, I somehow missed that you specified the kind of generator. I assumed you were talking about a random number generator, not a coherent noise function. Maybe it's that such functions aren't actually random, so I got tripped up by reading that: noise functions like this are actually entirely deterministic. (They just give answers that look random on a small enough scale.)
12 Jun, 2009, Scandum wrote in the 176th comment:
Votes: 0
quixadhal said:
As to the pointer-grid issue… If we're talking C here, that's a horrible memory hog, since you do need X * Y pointers, regardless of how you handle the rooms themselves. It would be far better to use a function f(x,y) that would return a room, since it could use a bucket hash internally, which might only be 1000 buckets that get rooms generated and added to them as needed. If we're talking a language that supports hash tables/associative arrays, then you're good… since they would handle keeping it a sparse array internally.

Most muds with a wilderness use 2 character grids, so switching to a pointer grid is often only a doubling of the memory, or quadrupling with 8 byte pointers. Another thing to keep in mind is that a pointer grid becomes more efficient (memory wise) than a binary tree the moment 33% of the rooms are used. So if someone is planning to have a 25 to 50% occupation you're likely to save memory, not to mention the speed advantage since finding every rooms in a 100x100 square in a binary tree isn't a cpu friendly activity. For a 1 million room wilderness or 1 million tile wilderness it's the most efficient (cpu wise) approach, and also the most efficient approach (memory wise) with a high load.
12 Jun, 2009, Runter wrote in the 177th comment:
Votes: 0
Scandum said:
quixadhal said:
As to the pointer-grid issue… If we're talking C here, that's a horrible memory hog, since you do need X * Y pointers, regardless of how you handle the rooms themselves. It would be far better to use a function f(x,y) that would return a room, since it could use a bucket hash internally, which might only be 1000 buckets that get rooms generated and added to them as needed. If we're talking a language that supports hash tables/associative arrays, then you're good… since they would handle keeping it a sparse array internally.

Most muds with a wilderness use 2 character grids, so switching to a pointer grid is often only a doubling of the memory, or quadrupling with 8 byte pointers. Another thing to keep in mind is that a pointer grid becomes more efficient (memory wise) than a binary tree the moment 33% of the rooms are used. So if someone is planning to have a 25 to 50% occupation you're likely to save memory, not to mention the speed advantage since finding every rooms in a 100x100 square in a binary tree isn't a cpu friendly activity. For a 1 million room wilderness or 1 million tile wilderness it's the most efficient (cpu wise) approach, and also the most efficient approach (memory wise) with a high load.


Epic fail.
12 Jun, 2009, David Haley wrote in the 178th comment:
Votes: 0
Why are we talking about binary trees so much?
12 Jun, 2009, Runter wrote in the 179th comment:
Votes: 0
David Haley said:
Why are we talking about binary trees so much?


We should start calling them double-headed-list snakes.
12 Jun, 2009, Scandum wrote in the 180th comment:
Votes: 0
David Haley said:
Why are we talking about binary trees so much?

I know, much easier to use a hash table.. oh wait..
160.0/181