One would think you don't grasp the concept since you wouldn't want to be having anything point to NULL when using a hashed pointer grid. Fortunately I got better things to do than argue on the net.

Um, I clearly edited and replaced NULL with a default room, like you said. But you know what? Who cares what it points to. It doesn't matter. A pointer is 4 bytes regardless of what it points to.
Nobody is arguing about the memory saved from not having duplicate instantiated data.

Yeah, I don't really get it either… it doesn't matter what pointers actually point to, if things are shared or not… as soon as you have a billion pointers to anything, even to the same thing, you have a billion times the size of a pointer (which I've started thinking of not as 4 but 8, but yeah). Maybe the confusion is that one person is talking about a full grid of pointers and the other is talking about a hash table, except that the other said "hashed grid" which implies a, well, grid of pointers, not a hash table.

Why have you started thinking of pointers as 8 bytes? On 64 bit architecture?

I'm sure we're talking in the same direction here so I'm going to also assume you know that I was never talking about a big 2d array of pointers like ever, even on disk. Quite apart from the fact that storing location 53,31 (say) that doesnt exist because of the walls around it would be stupid, it would be the sign of a very bad model. I think I actually might have to shoot someone for even contemplating such an excess.

What I was aiming at was that I could store the rooms that DO need to exist however I like (flat file, database, lolcode, xml or even smeared on the side of a herd of wombats) and all that would matter is that I could find and load the the tiles I needed as quickly as I needed them. When theres nothing to store, store nothing, not even a pointer to nothing*.

And I'm convinced you also understand this ;)

[edit: * with a couple of caveats: for speed it is sometimes good to assume a certain size of nothing so you can quickly add things in without having to allocate memory (which is slow) - when storing persistently, store nothing when there is nothing to store]

Yes, exactly. Most of my development is on 64-bit machines these days. (Out of curiosity, why else? :tongue:)


It seems like every time this conversation comes up on this forum, there are massive misunderstandings left and right because everybody has their own world design in their head, and are communicating some implementation details without having fully expressed either their high-level design or even the rest of the code.
That's why I'm relatively uninterested in talking about implementation under all the cards are on the table, because with so much variation of detail not only on the high-level but in the implementation, it's far too easy for so much to get lost in translation and people just end up talking past each other, eventually assuming that everybody is complete stupid.

I mean, seriously, when people start thinking that others (who presumably are at least half-competent, right?) are completely seriously talking about storing a fully instantiated grid of a billion or more pointers, I think we all need to realize that there has been a bug in the communcation, ne?
I don't think the productive goal is to "score points" by proving how one's mental conception of an idea, viewed in the best possible light, is so much better than one's mental conception of somebody else's idea, viewed in the worst possible light…

I'm understanding what you are saying.
But yeah, well, my concern is mostly two fold.

1. To be able to create the most massive wilderness possible. KaVirs number of locations is a good place to start. 1Billionish
2. To be able to readily access data from locations (such as terrain type) without tossing away access efficiency. (Eg: An overmap spamming 200 elements.)

I think it goes without saying there has to be some type of dynamic loading involved. Even just keeping nothing but 1byte for each wilderness room adds up too fast.

A good compromise might be dividing the wilderness up into square sectors that can be loaded and released as required. I'm not sure I am feeling loading each location individually even with caching.

I don't think anyone here is an idiot and this is actually a topic relevant to my design on a Ruby codebase I am writing. Anyone have an ideas to bounce?

I think KaVir said he had grids of 10x10 tiles which means he immediately reduces his problem space by a factor of 100… So 1 billion becomes 10 million and thats only 31620 x 31620 (ish) array elements which can be represented by a one dimensional array of (very roughly) 64k if we assume 8 bytes per pointer..

Not much at all really? And we can also assume that some of that space is never used or used rarely. So even better :)

[edited for my crap maths]

The confusion seems to be that Runter is comparing a gridless implementation to a grid implementation, and at the same time confuses room grids with tile grids and specifically attacks a hashed pointer grid instead of attacking grids in general. It doesn't help that KaVir occasionally speaks of rooms when he means locations, and my own terminology is far from solid either.

A hashed pointer grid would be a O(1) hash table, it's not memory efficient, but at least it's not wasteful like a binary tree which has a 12 instead of 4 byte overhead and is O(LogN) on top of it. For very large worlds you'd still be screwed with that, unless the world is empty, which in turn is a major game design issue.

It's possible to have a completely gridless wilderness, but you'd still have to store stuff on disc.

I think a hashed pointer grid of tiles would be the best way to go for a 1 billion locations wilderness, storing objects within the unhashed tiles they are located on, which will save the trouble of crawling large lists and trees.

That all depends on some type of dynamic loading. Otherwise inside of the tiles you still have just as many locations requiring data. (Presumably at least 1 byte for each terrain type.) and an additional 8 byte over head for every tile.
1 billion locations is still 1 billion locations regardless of what is containing them. My question is on the specifics of dynamic loading/caching. Since I'm assuming that is on the table axiomatically.

My idea would be loading any tile attempted to be accessed for a certain duration. If an overmap spans multiple tiles it still makes it pretty seemless. Right?

I think if you ask around you'll find that most people here already know I'm slow. So it's no surprise I would be confusing something. ;)

Well, unless we're all talking about tiles being only one type of terrain? But I can see wanting different types of terrain inside of a tile. This seems like an implementation detail that shouldn't be assumed. (In fact completely diverse tiles possibly.)

Maybe the assumption is a tile will be nearly all the same so all we need is a list inside of the tile of locations not the same as the tile terrain type?

And maybe this is where the train of thought has been being derailed.

What KaVir and subsequently most people refer to is a collection that contains tiles with one type of terrain, and various tiles that contain fields bordering forest, a pond within a field, a road winding through hills, etc. A typical implementation has somewhere between 500 and 10.000 tiles so you'd need a 2 byte index at the very least to access the tile list. So it's assumed that a tile can contain various terrain types.

If you use hash pointers you still have 500 to 10.000 default tiles, but you could generate custom tiles on the fly, and make tiles more complex so a tile can also function as a container, which obsoletes the need for slow global lists.

are you answering your own questions here?? :D

As far as I understood, a tile was just bit of data which would determine the description associated with it. The "controller" would dynamically interlace the descriptions of surrounding tiles with the current tile like, as KaVir said, a jigsaw puzzle. But a jigsaw puzzle with only 256 peices that keep getting re-used.

(correct me if I'm wrong)

So really all you are only *representing* the billion rooms with a one dimensional 64K array, 256 tiles and a clever description and content handler that fooled the user into thinking they were in a different location based on their (and I stress *their*) coordinates.

Several people have mentioned terminology confusion, so maybe there should be a collective effort to stop making assumptions about things and be more clear. The difference between "location" and "room" in somebody's head can be very great; the difference between "hash table" and "hash grid" can be great in somebody else's. This conversation is hard enough to have when everybody is speaking the same language, but when people use the same words to mean different things or different words to mean the same thing, well, it's basically hopeless and people just get upset and other people's perceived stupidity…

I don't really see what the problem is, hash table and hash grid can easily be looked up on wikipedia or in some other programming reference, and I thought it had already been determined that a room was both a container with exits and a description where as a location is just, well, an object with a discription and nothing more.

What we do have is a problem where one person might be coming at the problem from an implementation pov (as you pointed out) and one trying to set out the general behaviour of the system? Or possibly a paradigm mismatch like we have sometimes?

Okay. This is what I wasn't understanding. And let me see if I'm understanding the implementation right.

If we have a world broken into smaller grids or tiles, let's say each of these tiles is a 25 by 25 giving 625 possible locations in each tile
But instead of storing this data in memory we could simply direct it to a template for the tile.
Like you said, it could be a solid grid of one kind like a plane or maybe a template for a dessert oasis. Or maybe a section of road.
But the point is each of these locations would have certain definitions without individually needing their own data storage. Simply knowing
where they are in relationship with the template tile would be enough.

Essentially this would make the required memory for the templates negligible by comparison, as well.

Am I getting this right now?

And if so, I'm sorry I came across snarky earlier. I simply was not understanding the proposed solution.

Or maybe I'm just dumb so I need things explicitly spelled out for me. :)

Well, I just checked Wikipedia for a "hash grid" and didn't find anything. It's not a term I've ever heard before, and googling for "hash grid" (with quotation marks) brings up only 236 results, suggesting to me that it's not a commonly used term. For these reasons, I hesitate to comment on it, and it is likely that any discussion of the data structure is likely to be based on confusion and/or misunderstanding – which will only lead to wastes of time and frustration. :thinking:

So yes, not only are there problems of implementation vs. general behavior, but also, being lax in terminology just makes it that much harder for us to understand each other. I think it would really help if the vocabulary were set straight one way or another.

I'm guessing it's a hash table with 2 keys to the bucket. Should be perfect distribution.