11 Oct, 2007, KaVir wrote in the 21st comment:
Votes: 0
DavidHaley said:
Woah! You've just added a whole flopful of requirements.


No, I've provided examples of the benefits of a grid-based system, because you specifically asked me to.

DavidHaley said:
All I have been trying to do is present general things to think about: you are attacking those general issues without knowing what the requirements are either, but you're talking as if every conceivable grid system will have the same requirements as yours. :shrug:


The requirement, as stated in the first post, is to have "a large grid system". You attacked the grid system approach, suggesting that Mabus should do something else - you then asked "What exactly do you gain by representing in memory the literal grid of ocean tiles?".

What I have been doing is answering your question. I have been pointing out some of the advantages of a grid system over your proposal - explaining to you why Mabus (or anyone else) might choose to store terrain data in that way.

DavidHaley said:
I have no idea why you feel justified in asserting that a non-literal-grid proposal necessitates the manual creation of that many rooms any more than a literal-grid proposal would. Could you please explain that?


I already did: "Your proposal requires every piece of non-ocean terrain to be a hand-made room. Mabus has said he wants "large ocean areas", but even if he wanted the same proportion of ocean to land as the earth (approximately 71% ocean) that 10000x10000 world mentioned earlier would still need around 29 million rooms of land."

DavidHaley said:
Obviously any room of interest needs to be generated by hand in either solution. If it's a generic room of a different terrain type, that's fine: you can make it a generic automatically-generated room in both systems.


If it's automatically generated, then you need some way to determine its terrain type. That's what the grid system does. Your proposal doesn't support that type of differentiation, thus this discussion.
11 Oct, 2007, David Haley wrote in the 22nd comment:
Votes: 0
KaVir said:
DavidHaley said:
Woah! You've just added a whole flopful of requirements.


No, I've provided examples of the benefits of a grid-based system, because you specifically asked me to.

That is not true. You have talked about a lot of features that you want to have, or think that other people would want to have. You have not addressed how a literal grid better suits the exact set of minimal requirements we were given. (You also haven't explained why you can do something that I can't do.)

In other words, you are jumping the gun by designing around requirements that haven't been given yet.

KaVir said:
The requirement, as stated in the first post, is to have "a large grid system". You attacked the grid system approach, suggesting that Mabus should do something else - you then asked "What exactly do you gain by representing in memory the literal grid of ocean tiles?".

As I said several posts up, you confusing the concept of a world laid out as a grid and the implementation of said grid as a literal array in memory. I'm not sure how else to say it. I am not attacking the notion of laying out terrain as a grid. I am attacking the notion of implementing it as a literal array in memory – even if you subdivide it.

Of course, if the requirements change (at the moment, there are hardly any other than "ships in the ocean laid out as a grid") the needed implementation will change.

KaVir said:
What I have been doing is answering your question. I have been pointing out some of the advantages of a grid system over your proposal - explaining to you why Mabus (or anyone else) might choose to store terrain data in that way.

That's fine and good. I've said several times that if desired features change, the implementation must change. I was working off of what we were given (which was not very much) and presenting general points. The most important general point being to not automatically assume you need a literal array in memory. That's one of the most common mistakes in data structure decisions for such large problems: to represent your data exactly the same way you think of it. A forgivable and understandable mistake but a mistake nonetheless.

Besides, many of the features you gave don't need a literal grid in memory, anyways.

KaVir said:
DavidHaley said:
I have no idea why you feel justified in asserting that a non-literal-grid proposal necessitates the manual creation of that many rooms any more than a literal-grid proposal would. Could you please explain that?

I already did: "Your proposal requires every piece of non-ocean terrain to be a hand-made room. Mabus has said he wants "large ocean areas", but even if he wanted the same proportion of ocean to land as the earth (approximately 71% ocean) that 10000x10000 world mentioned earlier would still need around 29 million rooms of land."

Thanks for repeating yourself – to be a little more blunt, I was trying to say that I think you are wrong in saying what you said. I felt that you had no justification the first time, and I still feel that way. :smile: To change my mind you'll have to explain, not repeat, yourself. (I thought that'd be pretty obvious.)

KaVir said:
DavidHaley said:
Obviously any room of interest needs to be generated by hand in either solution. If it's a generic room of a different terrain type, that's fine: you can make it a generic automatically-generated room in both systems.


If it's automatically generated, then you need some way to determine its terrain type. That's what the grid system does. Your proposal doesn't support that type of differentiation, thus this discussion.

Who says I have no way whatsoever of determining the type of a given cell? How can you possibly make such an assertion and take it seriously?

You are assuming that just because I don't have a literal array in memory that I have no way of talking about individual cells. Look, I'm sorry, but that's just plain foolish. I'm happy to explain it if you don't see why I'm saying this. I'm also happy to receive a proof of some kind that what I claim is impossible. (Good luck coming up with such a proof, though.)

Maybe you should try to think why exactly I am making this proposal and sticking to it so strongly instead of assuming it's broken every which way. I already showed why your worries about speed and lookups were baseless. Maybe, just as you didn't see that straight away, you are not seeing this straight away, either. Sorry for being blunt/harsh/out of patience. I'm just a little frustrated seeing you bash a system when you clearly don't understand it because you haven't thought it through enough. :shrug:

And yet again, obviously if new requirements pop up, the implementation has to adapt. That doesn't necessarily mean you need a literal grid, though. It just means you need to be more clever than what I proposed.
11 Oct, 2007, Mabus wrote in the 23rd comment:
Votes: 0
I apologize if I seemed vague. This is an initial design phase for this part of my project. As such I wanted general input, of any kind, that could be helpful. I still have not decided fully on what/how things will be done.

x, y, z
terrain type
travelable, land-able, shallow, impassible
occupied (boolean)

wind direction (none 0, nw 1, n 2, ne 3, w 4, e 5, sw 6, s 7, se 8, d 9, u 10)
wind speed
weather
visibility

room title (dynamic: visibility, terrain, occupied, weather, season, day/night)
room description (dynamic)
script file assignment

impassible name
impassible description

encounter calls

That's what I jotted down before I posted here.

So I was "picking your brains", I admit. Trying to flesh out my thoughts even before I began pondering the mechanics of doing it in Java, integrating it with existing CoffeeMud code, and working it into a MySQL database.

My thanks to everyone that posted.
11 Oct, 2007, David Haley wrote in the 24th comment:
Votes: 0
As you can see, the issue is quite complex (and contentious). :smile: And how to answer the questions depends very much on what exactly you plan to do. Here are some more thoughts based on this new information.



For the terrain terrain:
Your terrain requirements seem fairly simple. It appears from your new list that you are planning on only representing the ocean in this grid, and not the whole world: that makes things a little simpler. You should try to get an estimate of what percentage of the ocean will be in your terrain categories. I suspect that most of it (maybe even almost all of it) will be plain old ocean. As such, you should skew your representation schema to take advantage of that. (For instance, by representing explicitly the minority categories, and implicitly saying that all other categories are normal water.)



For the wind and visibility:
You should think about what exactly you're trying to accomplish. Do you really care what the wind is 500 steps away from your players' ships? Probably not. As such, you might want to consider a local weather model, where you only simulate your weather in the immediate vicinity of ships (perhaps visibility*2 or something like that). This way, you avoid the overhead of storing the entire weather model when most of it simply isn't relevant. An important point: the point probably isn't to create a fully accurate simulation: it's to create one that feels convincing to players. The difference is perhaps subtle but quite important… Clearly, it is better (space- and time-wise) to only store information for a handful of cells than all of your cells.)



For room titles etc.:
The generic tiles can have that information deduced from data not specific to that room. And the tiles that need customization can be considered as 'interesting' by my previous definition, and therefore exist as instantiated rooms or something like that.

For scripts, again, you probably don't need to be running the scripts unless there is somebody there to observe the effects. Some scripts actually matter, even if there's nobody there to observe the effects, because they have long-term effects (like spawning pirates to go raid towns or whatever). Other scripts are completely useless if nobody's there, like scripts that periodically echo something to the room. It might help to differentiate between the two as you set up your scripting system.

You might also want to consider some kind of block-wise or run-length compression for scripts, if wide swaths of terrain have the same script. (Same holds for pretty much anything, actually.)



But again, it's hard to decide on an implementation without having a more complete view of the features. That said, any system that needs to represent the whole grid in memory, even using macro-tiles, will have trouble scaling as you increase the size. A system based on "interesting-feature" rooms that need special treatment will scale well in the face of more uninteresting tiles (i.e. more open space).

Of course, if you only plan on having 1,000x1,000 tiles, you could just store the entire grid as-is in memory: that probably isn't going to kill you, although that depends on the current memory usage and your general requirements.
11 Oct, 2007, KaVir wrote in the 25th comment:
Votes: 0
DavidHaley said:
As I said several posts up, you confusing the concept of a world laid out as a grid and the implementation of said grid as a literal array in memory. I'm not sure how else to say it. I am not attacking the notion of laying out terrain as a grid. I am attacking the notion of implementing it as a literal array in memory – even if you subdivide it.


The solution you've suggested does a poor job of representing anything other than an empty, featureless ocean, with a relatively tiny number of different terrain types within it.

Storing the data in a literal array allows you to provide a wide variety of terrain detail.

Also note that after you wrote the post I'm replying to, Mabus also clarified what I'd previously already assumed as obvious - he wants different terrain types.

DavidHaley said:
KaVir said:
If it's automatically generated, then you need some way to determine its terrain type. That's what the grid system does. Your proposal doesn't support that type of differentiation, thus this discussion.

Who says I have no way whatsoever of determining the type of a given cell? How can you possibly make such an assertion and take it seriously?


Because you've described your system, and as it stands your proposal doesn't support automatically generated terrain types*, only empty ocean and "points of interest" - and you stated "Obviously any room of interest needs to be generated by hand in either solution".

Supposing the mud world were laid out like the Philippines - a lot of ocean, but with a great deal of land scattered across it:

http://upload.wikimedia.org/wikipedia/en...

How would you represent that with your system?


* Note that by "automatically generated terrain types", I assume you're talking about generating rooms on-the-fly with terrain types specific to their location (i.e., rather than just basic ocean, being able to generate large amounts of other ocean or land terrain types). If that's not what you meant, you'll have to clarify what exactly you're referring to.
11 Oct, 2007, KaVir wrote in the 26th comment:
Votes: 0
Mabus said:
x, y, z
terrain type
travelable, land-able, shallow, impassible
occupied (boolean)


Unless you want a lot of underwater detail, you probably don't need to store the 'z' axis.

What sort of terrain types are you after? You mention "land-able" and "shallow", but how much land detail do you want? Roughly what sort of percentage of the grid will be land?

Mabus said:
wind direction (none 0, nw 1, n 2, ne 3, w 4, e 5, sw 6, s 7, se 8, d 9, u 10)
wind speed
weather
visibility


You can generate weather patterns separately, it's not necessary to physically store anything.
11 Oct, 2007, Mabus wrote in the 27th comment:
Votes: 0
KaVir said:
Unless you want a lot of underwater detail, you probably don't need to store the 'z' axis.

I was thinking of 2 up (sky), water level, and 2 down (underwater). I could live with 1 up, level, and and 1 down, but I want the ability for flying/underwater boarding parties and attacks. A game coder can dream, eh?

KaVir said:
What sort of terrain types are you after? You mention "land-able" and "shallow", but how much land detail do you want? Roughly what sort of percentage of the grid will be land?

Terrain types can be handled by the existing code, and I can call them from there. Just thought it best to think about storing them in case I wanted to extend the water to small islands. The land-able would be spots where a large ship could dock. The shallow would require small boats. I have no idea what % will be land, but I imagine edges bordering existing areas and any small islands, so 1-5% likely.

KaVir said:
You can generate weather patterns separately, it's not necessary to physically store anything.

Weather was for two purposes. Moving weather "fronts" that will tick across the grid and for dynamic room descriptions/environmental scripts (high waves, calm seas, fog banks, etc.).

You are correct in that weather can (and likely will) be a seperate system, as I have done a lot of weather coding already in our game. The thought was to be able to call easily when needed. Could just tie it to the ships (which will be small multi-room areas) and have the check be where the ship-item is upon the grid.

I really appreciate the discussion.
11 Oct, 2007, KaVir wrote in the 28th comment:
Votes: 0
Mabus said:
KaVir said:
Unless you want a lot of underwater detail, you probably don't need to store the 'z' axis.

I was thinking of 2 up (sky), water level, and 2 down (underwater). I could live with 1 up, level, and and 1 down, but I want the ability for flying/underwater boarding parties and attacks. A game coder can dream, eh?


You can certainly do that, and support as many height levels as you like - but what I mean is you probably don't need to explicitly store the terrain data for different heights, as it can be calculated. For example you could say that anything above water level is 'sky' terrain, while anything below (to a maximum depth depending on the ocean terrain type at that x/y position) is 'solid water' terrain, and anything below that is 'solid earth' terrain.

Mabus said:
KaVir said:
What sort of terrain types are you after? You mention "land-able" and "shallow", but how much land detail do you want? Roughly what sort of percentage of the grid will be land?

Terrain types can be handled by the existing code, and I can call them from there. Just thought it best to think about storing them in case I wanted to extend the water to small islands. The land-able would be spots where a large ship could dock. The shallow would require small boats. I have no idea what % will be land, but I imagine edges bordering existing areas and any small islands, so 1-5% likely.


That's a very high percentage of ocean - how much physical space will each room represent, and how many rooms will the world consist of?
11 Oct, 2007, David Haley wrote in the 29th comment:
Votes: 0
KaVir said:
The solution you've suggested does a poor job of representing anything other than an empty, featureless ocean, with a relatively tiny number of different terrain types within it.

Storing the data in a literal array allows you to provide a wide variety of terrain detail.

Also note that after you wrote the post I'm replying to, Mabus also clarified what I'd previously already assumed as obvious - he wants different terrain types.

Well, sure, but from my very first post I also allowed for special rooms, that I called the "interesting" ones. A literal grid isn't the only way to have variety, as I have been trying to say. And since we're working with a 1-5% rate of non-water tiles, well, it really makes sense to represent just those and assume all other coordinates are plain water.

KaVir said:
Because you've described your system, and as it stands your proposal doesn't support automatically generated terrain types*, only empty ocean and "points of interest" - and you stated "Obviously any room of interest needs to be generated by hand in either solution".


Please explain why I can't automatically generate terrain and store it when needed? "By hand" doesn't mean that I have to painstakingly say "make a room here", "make a room here", "make a room here", it just means that I need to – one way or the other – specify where the terrain is. That data then needs to be entered into the system. Same thing whether or not it's a grid or "point-of-interest"-based system.

KaVir said:
Supposing the mud world were laid out like the Philippines - a lot of ocean, but with a great deal of land scattered across it:

http://upload.wikimedia.org/wikipedia/en...

How would you represent that with your system?


One way would be using spatial partitioning trees. There is no need to have any granularity whatsoever in the pure oceans areas. Basically, draw the tightest possible boxes around the land areas. Make a partition. Now treat that bounding box as the "world", and partition off as much of the water as you can (as there is no need to have granularity there). Draw bounding boxes around the land areas. Partition. Wince, wash and repeat.

Since you have no need for granularity in the big, empty ocean areas (which apparently account for ~95% of the terrain), it doesn't make sense to have macro-tiles over there since the whole swath is empty. Instead, it makes more sense to partition into the areas that don't need more detail, and those that do need more detail.

A pathological example for this algorithm is a checkerboard, where it is impossible to make partitions larger than one square. Of course, if for some reason the land mass had patterns (like a checkerboard or something) you'd change your approach (like encode the pattern using a compression algorithm of some kind). I posit though that a grid, even a macro-tile based grid, would be just as bad as the partition in this case, because if you think about it, a grid is a special case of a partition where all of the partitioned areas are of the same size.

You can look up e.g. "space partitioning" on Wikipedia for some more examples, some of which are more appropriate for some situations than others, naturally.

KaVir said:
You can certainly do that, and support as many height levels as you like - but what I mean is you probably don't need to explicitly store the terrain data for different heights, as it can be calculated. For example you could say that anything above water level is 'sky' terrain, while anything below (to a maximum depth depending on the ocean terrain type at that x/y position) is 'solid water' terrain, and anything below that is 'solid earth' terrain.

I find it interesting that you propose more or less the same idea – don't be explicit, leave it implicit – when it comes to the z axis as what I have been saying about the 2d grid, but when it comes to the 2d grid, you strictly refuse to leave the grid paradigm. :wink:

Of course, such a solution for the z axis might need to allow for points of interest, too, like sunken cities or whatever. It's really the exact same thing, just extended to three dimensions.

If you were to implement a space system, it'd be unthinkable to make a 3d grid of the world/galaxy. Even if you were to implement flight in the sky, it'd be bad to do that. My argument for this whole thread has been that the same reasoning applies to the plane (i.e. the two-dimensional space, in this case the sea) and not just three dimensions.
11 Oct, 2007, KaVir wrote in the 30th comment:
Votes: 0
DavidHaley said:
Please explain why I can't automatically generate terrain and store it when needed?


Because your system as described doesn't have any means of storing varied terrain types that cover large locations - if I ask "what's at room 1000/2500", your system will respond with either "nothing there, so its the default empty ocean terrain" or "its a point of interest". But how are you going to do that on a large scale?

DavidHaley said:
KaVir said:
Supposing the mud world were laid out like the Philippines - a lot of ocean, but with a great deal of land scattered across it:

http://upload.wikimedia.org/wikipedia/en...

How would you represent that with your system?


One way would be using spatial partitioning trees.


I said "with your system" - as in the system you've been talking about up until now, and the one I've been arguing against.

DavidHaley said:
There is no need to have any granularity whatsoever in the pure oceans areas. Basically, draw the tightest possible boxes around the land areas. Make a partition. Now treat that bounding box as the "world", and partition off as much of the water as you can (as there is no need to have granularity there). Draw bounding boxes around the land areas. Partition. Wince, wash and repeat.


I implemented a system like that in the past; it looked good on paper, but worked out poorly in practice. It was fine when I had big square forests placed on massive rectangular islands, but adding smooth detailed terrain soon become extremely unwieldy. I scrapped it and replaced it with an array, and it now works extremely well.

DavidHaley said:
If you were to implement a space system, it'd be unthinkable to make a 3d grid of the world/galaxy.


Not really, it would just be a matter of scale.
12 Oct, 2007, David Haley wrote in the 31st comment:
Votes: 0
KaVir said:
DavidHaley said:
Please explain why I can't automatically generate terrain and store it when needed?


Because your system as described doesn't have any means of storing varied terrain types that cover large locations - if I ask "what's at room 1000/2500", your system will respond with either "nothing there, so its the default empty ocean terrain" or "its a point of interest". But how are you going to do that on a large scale?

I just gave you a method to do that: using binary partitioning to represent precisely only the space you care about representing precisely.

What exactly do you think it means to say "it's a point of interest"? I feel somewhat offended that you think my system is so stupid as to be binary, when I've been saying all along how it lets you differentiate between normal tiles, that are not explicitly represented, and everything else, which you do represent. It's what makes me think that the proposal still isn't clear to you…

KaVir said:
DavidHaley said:
KaVir said:
How would you represent that with your system?


One way would be using spatial partitioning trees.


I said "with your system" - as in the system you've been talking about up until now, and the one I've been arguing against.


Mind-boggling! You really don't understand what I am talking about if you think that a space partition is somehow mutually exclusive with what I have been talking about. Look, I'm happy to explain it, just don't keep assuming it's a completely stupid system. There's an extremely good reason why I have been proposing this.

For that matter, I hadn't even proposed a precise implementation up until just now. I have no idea why you felt that you had any basis to say what the implementation can or cannot do. We weren't even talking about the implementation. What I have been proposing is to be intelligent about how you represent the world, and not waste space representing swaths of emptiness when you have much better ways of doing it. Only represent what you care about: the rest is implicit. I have been proposing a general implementation design principle, and only because you claimed the design was incompetent and useless did I provide an example (partitioning) to show to you that your claims were off-base. You are yet again confusing several levels of abstraction.

KaVir said:
I implemented a system like that in the past; it looked good on paper, but worked out poorly in practice. It was fine when I had big square forests placed on massive rectangular islands, but adding smooth detailed terrain soon become extremely unwieldy. I scrapped it and replaced it with an array, and it now works extremely well.

That's great. I've said over and over that different requirements suggest different designs, and naturally scale is one of them. Every problem has its own solution, although similar problems tend to have similar solutions…)

That said, dare I suggest that maybe the fault was yours in implementing the system, not the general system itself. *shrug* This technique has been shown to work time and time again for representing data sets, and not just terrain. (You've heard of binary search trees, I presume.) I really hate to say this, but maybe you should do some more background research on the issue.

KaVir said:
DavidHaley said:
If you were to implement a space system, it'd be unthinkable to make a 3d grid of the world/galaxy.


Not really, it would just be a matter of scale.

That you even think to say such a thing boggles my mind. Are you trying to be facetious? Space-system, hello? Big scale? Isn't that kind of the whole point of a space system: to have a very large space in which ships fly around, and with rather precise coordinate granularity?

Even a 100^3 system is 1,000,000 points. A more realistic size, say, 1,000x1,000x1,000, would be 1,000,000,000. More than a gigabyte's worth of memory to represent! (Counting pointers, overhead etc.) I can only conclude that either we have dramatically different notions of how big a space system is supposed to be, or you're saying things you don't really think due to the point of contention.

But obviously, if you only have one million points to represent, it's not as unreasonable to just stick it into memory. I'll happily grant that: what I dispute is that you'll really have that little to represent.
12 Oct, 2007, KaVir wrote in the 32nd comment:
Votes: 0
DavidHaley said:
What exactly do you think it means to say "it's a point of interest"?


Non-ocean rooms mapped over specific coordinate locations. You've already stated such, eg:

"You would need a system to denote certain important rooms, like the coast and ports I suppose and various "points of interest" in the ocean like islands, landmarks, magic whirlpools or whatever."

And:

"Obviously any room of interest needs to be generated by hand in either solution".

To handle terrain on a large scale you need to do more than just denote individual rooms - you need a way to represent vast numbers of rooms at a time.

DavidHaley said:
Mind-boggling! You really don't understand what I am talking about if you think that a space partition is somehow mutually exclusive with what I have been talking about.


The problem is that you're shifting the goal posts. I pointed out the flaws in your proposal, so you expanded that proposal (which is fair enough) and then claimed it was what you were proposing all along (which is rather cheap).

Some form of space partitioning can work in some cases, and I've recommended quadtrees in the past (for specific implementations), but overall I've still found arrays to be a preferable solution for the various world systems I've designed and implemented to date. I've also considered combining the two concepts, with each cell of the quadtree potentially containing a dynamically sized array of terrain data, but I'm not particularly happy with that approach either.

And no, the problem I had wasn't with my design or implementation. It was simply the wrong tool for what I was trying to do.

DavidHaley said:
KaVir said:
DavidHaley said:
If you were to implement a space system, it'd be unthinkable to make a 3d grid of the world/galaxy.


Not really, it would just be a matter of scale.


That you even think to say such a thing boggles my mind. Are you trying to be facetious?


Not at all, although I'd likely implement it in 2D rather than 3D. As I said, it's a matter of scale; a 100x100 array, with each element representing a section of space 1000 light years across, would provide you with a galaxy of around the same size as the Milky Way.

Although the individual solar systems would obviously need to be pseudorandomly generated, there could still be benefits to manually setting certain attributes for each section of space - perhaps modifiers to the seed for solar system attributes, so that certain sections of space are primarily human dominated, or mostly fall under a specific government, or generally frown on certain types of trade, etc.

Such an approach would allow you to tweak the values to encourage people to explore and trade over greater distances, rather than finding two neighbouring solar systems and trade exclusively between the two.

The specifics would obviously depend on the requirements of the game, but it's certainly not an "unthinkable" way of designing a space system.
12 Oct, 2007, David Haley wrote in the 33rd comment:
Votes: 0
KaVir said:
DavidHaley said:
What exactly do you think it means to say "it's a point of interest"?


Non-ocean rooms mapped over specific coordinate locations. You've already stated such, eg:

"You would need a system to denote certain important rooms, like the coast and ports I suppose and various "points of interest" in the ocean like islands, landmarks, magic whirlpools or whatever."

And:

"Obviously any room of interest needs to be generated by hand in either solution".

To handle terrain on a large scale you need to do more than just denote individual rooms - you need a way to represent vast numbers of rooms at a time.

I've been using "room of interest" slightly loosely and I apologize for that, but I would mention that it doesn't change the overarching point.

In the example you cite, room of interest means something that does indeed need to be crafted by hand simply by the nature of that thing, e.g. a room with particular descriptions that cannot, for some reason, be generated generically. Clearly, such a room would need to be hand-crafted in either system.

The other meaning I have been using is to distinguish the vast majority of tiles from the much smaller number (in this case, we have a ballpark 5% estimate) of "special" tiles.

Either way, the take-home message is the same: there is no need to represent the uninteresting points explicitly, and you should only be worrying about the very small number of interesting points.

KaVir said:
DavidHaley said:
Mind-boggling! You really don't understand what I am talking about if you think that a space partition is somehow mutually exclusive with what I have been talking about.


The problem is that you're shifting the goal posts. I pointed out the flaws in your proposal, so you expanded that proposal (which is fair enough) and then claimed it was what you were proposing all along (which is rather cheap).

Goodness – I'm not sure how I could have shifted posts when I hadn't even proposed an implementation up until just now. My point has been fairly consistent: don't represent what you don't need to represent. (it's starting to feel like a mantra…) I don't see that I have changed that point, but please do point out where I did.

KaVir said:
Some form of space partitioning can work in some cases, and I've recommended quadtrees in the past (for specific implementations), but overall I've still found arrays to be a preferable solution for the various world systems I've designed and implemented to date. I've also considered combining the two concepts, with each cell of the quadtree potentially containing a dynamically sized array of terrain data, but I'm not particularly happy with that approach either.

That's all fine, and I'd be happy to adopt a grid system where it is appropriate. If the world is too large, it is no longer appropriate. If the world is too homogeneous, it is not only not appropriate, but also very wasteful. I.e., just because a grid would work for a given task doesn't mean it's a terribly clever solution.

KaVir said:
And no, the problem I had wasn't with my design or implementation. It was simply the wrong tool for what I was trying to do.

That's fair enough in some cases, however I remain skeptical given how ready you are to allocate all this basically empty space. That's pretty much inherently wasteful. Obviously it depends on specifics. In this whole conversation, I've been trying to work with the requirements we have been given; the most recent is that the represented space is, for the most part (~95%) plain old ocean, with a small portion (~5%) being different tiles.

KaVir said:
(of the space system) Not at all, although I'd likely implement it in 2D rather than 3D. As I said, it's a matter of scale; a 100x100 array, with each element representing a section of space 1000 light years across, would provide you with a galaxy of around the same size as the Milky Way.

Err, ok, but how exactly are you positioning ships in this space? If you respond by saying "you give each ship a coordinate", I ask you next: why did you bother to cut the galaxy into these grids in the first place?

My question is quite simple, and it's the same one as before: what exactly are you gaining by using these macro-tiles?

I'd also dispute your claim that 2d is appropriate for a space environment but I suppose that's a non-code design choice and so not terribly relevant at present.

KaVir said:
Although the individual solar systems would obviously need to be pseudorandomly generated, there could still be benefits to manually setting certain attributes for each section of space - perhaps modifiers to the seed for solar system attributes, so that certain sections of space are primarily human dominated, or mostly fall under a specific government, or generally frown on certain types of trade, etc.

Not sure how a grid system makes this easier much less possible in the first place when compared to a partitioning system.

KaVir said:
The specifics would obviously depend on the requirements of the game, but it's certainly not an "unthinkable" way of designing a space system.

Well, yeah, but you also didn't describe what you initially said you were describing.

I said that it would be unthinkable to make an array representation of the world galaxy, because it has the same problems as an ocean, but even worse by being not only three-dimensional, but typically much larger in size to begin with.
You said it was a question of scale.
I said that was true but typically the scale is big for these things, and therefore, in the majority of cases, a literal grid approach simply isn't a good idea.
You said it wasn't because you have this other system that involves other stuff going on.

It seems that we are no longer talking about the same thing. :shrug:
12 Oct, 2007, KaVir wrote in the 34th comment:
Votes: 0
DavidHaley said:
The other meaning I have been using is to distinguish the vast majority of tiles from the much smaller number (in this case, we have a ballpark 5% estimate) of "special" tiles.

Either way, the take-home message is the same: there is no need to represent the uninteresting points explicitly, and you should only be worrying about the very small number of interesting points.


Mabus gave an estimate of 1-5% land, but no estimate for "special" tiles. If he has different tiles scattered throughout the entire ocean (either because there's little bits of the land scattered all over the place, or because there are many different types of ocean tile), then an array makes a lot of sense IMO.

But even if his world really was 95% identical ocean tiles, with 5% of land tiles squashed up together at one specific point, I'd still recommend going with an array - around the section of land (with any coordinate positions outside of that section giving the default 'ocean' terrain type).

DavidHaley said:
KaVir said:
And no, the problem I had wasn't with my design or implementation. It was simply the wrong tool for what I was trying to do.

That's fair enough in some cases, however I remain skeptical given how ready you are to allocate all this basically empty space.


I'm not allocating empty space, nor am I suggested that Mabus should do so.

DavidHaley said:
In this whole conversation, I've been trying to work with the requirements we have been given; the most recent is that the represented space is, for the most part (~95%) plain old ocean, with a small portion (~5%) being different tiles.


The requirement is that an estimated 1-5% of the terrain types will be land. Mabus hasn't specified much about the ocean other than that some parts will be travelable, some shallow and some impassable.

Three questions to Mabus:

1) Will the majority of the ocean be exactly the same terrain type, or will it be a mixture of different types of ocean terrain representing assorted factors (for example, things like currents, tides, reefs, hydrothermal vents, tidal rapids, whirlpools/maelstroms, oil fields, etc)?

2) Will the small amount of land be generally clumped together, or will it be scattered throughout the entire ocean?

3) How big will the entire ocean be? 1000x1000 rooms? 10000x10000? 100000x100000?

DavidHaley said:
KaVir said:
(of the space system) Not at all, although I'd likely implement it in 2D rather than 3D. As I said, it's a matter of scale; a 100x100 array, with each element representing a section of space 1000 light years across, would provide you with a galaxy of around the same size as the Milky Way.


Err, ok, but how exactly are you positioning ships in this space? If you respond by saying "you give each ship a coordinate", I ask you next: why did you bother to cut the galaxy into these grids in the first place?


Yes, you give each ship a coordinate position. As I said several posts back, "The grid isn't for storing ships and people, it's for storing terrain data". That quote was aimed at ocean-based terrain, which can be highly varied, but it could also apply to space if you need to keep track of other types of data.

And I already said why you might want to cut it up (you even quoted it): So that you could manually set certain attributes for each section of space. The example I gave previously was for seed modifiers, but you could also apply it to other things - perhaps it's a space-war game, where multiple factions try to dominate the galaxy by conquering it one section at a time. Perhaps the technology level of each section fluctuates depending on how much trading and/or combat goes on there.

There are many possibilities. As I said before, the specifics would obviously depend on the requirements of the game - but making a grid of the galaxy is certainly not an "unthinkable" solution. It's certainly something I would at least consider.

DavidHaley said:
I'd also dispute your claim that 2d is appropriate for a space environment but I suppose that's a non-code design choice and so not terribly relevant at present.


I'd use 3D coordinates for the position of the ships within each section of space, but what I was talking about here was the array of the galaxy itself; many large galaxies (including the Milky Way) are arranged in a flat disk-like configuration. A 2D shape is also much easier to represent to the players.
12 Oct, 2007, Scandum wrote in the 35th comment:
Votes: 0
DavidHaley said:
As for compressing the grid using macro-tiles: well, ok, but that only helps you if the whole macro-tile is of the same type. It would be easy to devise fairly realistic situations – e.g., archipelagos – for which that didn't work. Of course, you can still do things like run-length or block encoding, but that's a lot more complicated than a simple 2-layered grid.

You'd need about 1000 tiles to create a complex map. I'm not entirely sure if we're talking about the same thing here.

DavidHaley said:
You've heard of indexing, right? :wink: 2^25 = 33,554,432 so you'd need (in the worst case) 25 steps through a search tree to find a specific room.

You're not seriously suggesting to make a binary tree with 33,554,432 items are you? You'd blow any memory gains right out of the water that way, not to mention it'd take significantly longer to load it into memory.
12 Oct, 2007, Scandum wrote in the 36th comment:
Votes: 0
KaVir said:
Yes, you give each ship a coordinate position. As I said several posts back, "The grid isn't for storing ships and people, it's for storing terrain data". That quote was aimed at ocean-based terrain, which can be highly varied, but it could also apply to space if you need to keep track of other types of data.

If you use 16 bits to address tiles you might as well go the full 32 and address a data structure, in which case you can dupe and store whatever you want.
12 Oct, 2007, Mabus wrote in the 37th comment:
Votes: 0
KaVir said:
Three questions to Mabus:

1) Will the majority of the ocean be exactly the same terrain type, or will it be a mixture of different types of ocean terrain representing assorted factors (for example, things like currents, tides, reefs, hydrothermal vents, tidal rapids, whirlpools/maelstroms, oil fields, etc)?

2) Will the small amount of land be generally clumped together, or will it be scattered throughout the entire ocean?

3) How big will the entire ocean be? 1000x1000 rooms? 10000x10000? 100000x100000?

1) Yes, with a maybe. As I examine weather I will want calm seas, choppy, and high waves. It will almost all be rather featurelless saltwatersurface, but affected based on weather (and other affects).

2) Ports and small "Islands" which will be landable by 1 of two means. The ports and islands will be portal entrances to regular area types. These should persist as stationary points so they can be "navigated" to and mapped by players.

3) Undecided. 1000 by 1000 sounds about right, but I have not gotten that far. This is intial design of the system, and I understand that size matters in design. Just not there yet.

I was seeking general input into this before I got my full design plans together. In my mind I was thinking of using an x, y, z array to find and assign the ship-item placement on a grid. I am certainly open to other options, and again I really appreciate the discussion.
12 Oct, 2007, David Haley wrote in the 38th comment:
Votes: 0
KaVir said:
Mabus gave an estimate of 1-5% land, but no estimate for "special" tiles.

Same thing as far as the representation is concerned: it's something you need to differentiate from the vast majority of generic tiles.

KaVir said:
But even if his world really was 95% identical ocean tiles, with 5% of land tiles squashed up together at one specific point, I'd still recommend going with an array - around the section of land (with any coordinate positions outside of that section giving the default 'ocean' terrain type).

Yes, well, that's not what you were saying before (you were talking about the whole grid, or perhaps you just weren't expressing all of your thoughts), and you've also busily pointed out that the land probably isn't clumped together.

KaVir said:
DavidHaley said:
That's fair enough in some cases, however I remain skeptical given how ready you are to allocate all this basically empty space.


I'm not allocating empty space, nor am I suggested that Mabus should do so.


As soon as you allocate an array the bulk of which is taken up by generic tiles (i.e. all of which are the same) you have allocated what is essentially empty space.

KaVir said:
The requirement is that an estimated 1-5% of the terrain types will be land. Mabus hasn't specified much about the ocean other than that some parts will be travelable, some shallow and some impassable.

OK: let's assume that the 95% will be a mix of tiles, so that we can't just ignore the representation of all that stuff and have some extra work to do. That makes my points all the more relevant: it would be incredibly memory-heavy to allocate an array to represent the entire ocean space, not to mention simply not realistic for some sizes of ocean (unless you consider >1gb realistic). Even if you use macro-tiles, you still need to describe any disparity of terrain within that macro-tile.

KaVir said:
3) How big will the entire ocean be? 1000x1000 rooms? 10000x10000? 100000x100000?

This is the most important question. If we're talking about 1,000x1,000, then a straight array is ok (even if it's still a little wasteful). It'd be just a million cells, which is not that bad. However, if you go to 10kx10k (= 100,000,000 points) things get tight: you'd need several hundred mb to represent your space.

The other questions are important too, but subservient to this one. The others let you be more or less clever: this one determines how fundamentally clever your approach must be.

KaVir said:
DavidHaley said:
Err, ok, but how exactly are you positioning ships in this space? If you respond by saying "you give each ship a coordinate", I ask you next: why did you bother to cut the galaxy into these grids in the first place?


Yes, you give each ship a coordinate position. As I said several posts back, "The grid isn't for storing ships and people, it's for storing terrain data". That quote was aimed at ocean-based terrain, which can be highly varied, but it could also apply to space if you need to keep track of other types of data.[/quote=KaVir]
If you bothered to make the grid in the first place, it is redundant to store ship coordinates because they can be obtained by the cell in which the ship is.

If the grid is not of the same granularity as ships are allowed, that is, if a grid cell is bigger than a coordinate, things aren't as bad, but it's still worth asking whether you really needed to allocate so much space when so much of it is homogeneous.

KaVir said:
And I already said why you might want to cut it up (you even quoted it): So that you could manually set certain attributes for each section of space. The example I gave previously was for seed modifiers, but you could also apply it to other things - perhaps it's a space-war game, where multiple factions try to dominate the galaxy by conquering it one section at a time. Perhaps the technology level of each section fluctuates depending on how much trading and/or combat goes on there.

This isn't the same kind of mapping anymore. Now you're talking about political-type divisions. It might not make sense to represent them all using the same system.

KaVir said:
There are many possibilities. As I said before, the specifics would obviously depend on the requirements of the game - but making a grid of the galaxy is certainly not an "unthinkable" solution. It's certainly something I would at least consider.

I have the impression, as I said, that we're not really talking about the same thing anymore. The unthinkable solution I was referring to was a literal array to represent the space cells.


Scandum said:
DavidHaley said:
As for compressing the grid using macro-tiles: well, ok, but that only helps you if the whole macro-tile is of the same type. It would be easy to devise fairly realistic situations – e.g., archipelagos – for which that didn't work. Of course, you can still do things like run-length or block encoding, but that's a lot more complicated than a simple 2-layered grid.


You'd need about 1000 tiles to create a complex map. I'm not entirely sure if we're talking about the same thing here.

Neither am I. What exactly are you objecting to in my statement you quote?

Scandum said:
You're not seriously suggesting to make a binary tree with 33,554,432 items are you? You'd blow any memory gains right out of the water that way, not to mention it'd take significantly longer to load it into memory.

Why would it take longer to load into memory? It wouldn't if you were remotely smart about how you saved it to disk.

As for your other question, there are a few things to consider:
- I was pointing out to you that there isn't necessarily a huge speed penalty if you don't go with direct access arrays.
- You don't need to represent all 33k tiles, as I have been saying over and over again. Represent only what you need, all the rest is implicit.
- If the 33k tiles are in a bigger picture of many more tiles, then perhaps the price you pay with the 33M is a whole lot better than the price you'd have paid with the bigger picture.
- Binary trees of fixed size (e.g. a terrain map) can be implemented with a fixed-size array, eliminating all pointer overhead. (A clever optimization in this case given the fact that it won't grow.)

So yes, I am rather seriously suggesting that you can use indexing techniques to make your searching a whole lot faster, and that while it's as fast as direct access indexing, it's close. The BST was just a simple example to illustrate the point.
12 Oct, 2007, KaVir wrote in the 39th comment:
Votes: 0
DavidHaley said:
KaVir said:
I'm not allocating empty space, nor am I suggested that Mabus should do so.


As soon as you allocate an array the bulk of which is taken up by generic tiles (i.e. all of which are the same) you have allocated what is essentially empty space.


But I don't do that, nor have I suggested that Mabus do that. Right from the start I've been stressing the value of arrays for storing varied terrain.

DavidHaley said:
KaVir said:
The requirement is that an estimated 1-5% of the terrain types will be land. Mabus hasn't specified much about the ocean other than that some parts will be travelable, some shallow and some impassable.


OK: let's assume that the 95% will be a mix of tiles, so that we can't just ignore the representation of all that stuff and have some extra work to do. That makes my points all the more relevant: it would be incredibly memory-heavy to allocate an array to represent the entire ocean space, not to mention simply not realistic for some sizes of ocean (unless you consider >1gb realistic).


The array solution deals very well with highly varied terrain (as in scattered rather than clumped together), IMO much better than quadtrees and the like. The "realism" argument doesn't really hold any value considering that (1) the mud world is likely to be fictional rather than the Earth, (2) the array only needs to store data for the playable part of the ocean rather than the entire world, and (3) each array element could represent very large amounts of world (and include subtiles).

DavidHaley said:
KaVir said:
3) How big will the entire ocean be? 1000x1000 rooms? 10000x10000? 100000x100000?


This is the most important question. If we're talking about 1,000x1,000, then a straight array is ok (even if it's still a little wasteful). It'd be just a million cells, which is not that bad. However, if you go to 10kx10k (= 100,000,000 points) things get tight: you'd need several hundred mb to represent your space.


That depends on the implementation. Just because the world is 10000x10000 tiles, it doesn't mean he has to literally have an array of 10000x10000 elements. He could for example have a 1000x1000 array, each element of which is a "sector", with a sector storing 10x10 tiles. Much of the world could then be assembled from a few hundred sectors (a bit like creating a picture from pieces of a jigsaw puzzle).

However in this case Mabus has said that 1000x1000 "sounds about right", so it doesn't sound as though he's going to have a particularly large world anyway. This makes life easier.

DavidHaley said:
KaVir said:
Yes, you give each ship a coordinate position. As I said several posts back, "The grid isn't for storing ships and people, it's for storing terrain data". That quote was aimed at ocean-based terrain, which can be highly varied, but it could also apply to space if you need to keep track of other types of data.


If you bothered to make the grid in the first place, it is redundant to store ship coordinates because they can be obtained by the cell in which the ship is.


No, each element of the galaxy array represents 1000x1000 light years. That's reasonable for storing data about large sections of space, but personally I wouldn't want ships being forced to move exactly 1000 light years at a time.

Thus each ship would store its own coordinates, most likely 3D coordinates relative to their current sector. Astronomical units might be a more appropriate unit of measurement for spaceships.

DavidHaley said:
If the grid is not of the same granularity as ships are allowed, that is, if a grid cell is bigger than a coordinate, things aren't as bad, but it's still worth asking whether you really needed to allocate so much space when so much of it is homogeneous.


A 100x100 array isn't exactly large, and the point of my example was that the data being stored wouldn't be homogeneous. Asking whether or not it is worthwhile is fair enough, I was really just pointing out that it's not "unthinkable".

DavidHaley said:
This isn't the same kind of mapping anymore. Now you're talking about political-type divisions.


From an implementation perspective it doesn't matter what the data represents.
12 Oct, 2007, David Haley wrote in the 40th comment:
Votes: 0
KaVir said:
DavidHaley said:
As soon as you allocate an array the bulk of which is taken up by generic tiles (i.e. all of which are the same) you have allocated what is essentially empty space.


But I don't do that, nor have I suggested that Mabus do that. Right from the start I've been stressing the value of arrays for storing varied terrain.

I realize that, but unless your terrain is pathologically varied (e.g. checkerboard) you will have considerable homogeneity in your terrain even if there is some variation.

KaVir said:
The array solution deals very well with highly varied terrain (as in scattered rather than clumped together), IMO much better than quadtrees and the like. The "realism" argument doesn't really hold any value considering that (1) the mud world is likely to be fictional rather than the Earth, (2) the array only needs to store data for the playable part of the ocean rather than the entire world, and (3) each array element could represent very large amounts of world (and include subtiles).

For your first claim, I'd like to hear something to back that up. We're talking huge swaths of very similar terrain here (with the assumptions we've been given): allocating an array to represent all that isn't gaining anything and is in fact wasting a lot.

Re: realism, I didn't mean anything regarding Earth: I meant realism from a programmer's perspective. E.g., it is not realistic to design a MUD whose memory requirements are in the gigabytes.

KaVir said:
That depends on the implementation. Just because the world is 10000x10000 tiles, it doesn't mean he has to literally have an array of 10000x10000 elements. He could for example have a 1000x1000 array, each element of which is a "sector", with a sector storing 10x10 tiles. Much of the world could then be assembled from a few hundred sectors (a bit like creating a picture from pieces of a jigsaw puzzle).

You're going to have to explain yourself a bit. If your sector has any variation in it (which is an assumption you seem to have been running with) you will have to provide detail for that sector.

So instead of having 10k by 10k of cells of size 1, you have 1k by 1k of cells of size 100 sub-cells. You still have the same number of points in the end of the day. You haven't gained anything by doing this.

KaVir said:
However in this case Mabus has said that 1000x1000 "sounds about right", so it doesn't sound as though he's going to have a particularly large world anyway. This makes life easier.

Indeed it does. I'd still suggest to think hard about future scaleability, though: it'd really stink to write the array-based system and later find out you want to get bigger and can't due to inherent issues with it, unless you care to rewrite big chunks of code.

KaVir said:
DavidHaley said:
If you bothered to make the grid in the first place, it is redundant to store ship coordinates because they can be obtained by the cell in which the ship is.


No, each element of the galaxy array represents 1000x1000 light years. That's reasonable for storing data about large sections of space, but personally I wouldn't want ships being forced to move exactly 1000 light years at a time.

Then you aren't talking about the same thing I was. You aren't modeling the physical space and its contents anymore; you're modeling something else. (Like your tech-and-war example.)

KaVir said:
Asking whether or not it is worthwhile is fair enough, I was really just pointing out that it's not "unthinkable".

Perhaps a philosophical point, but for me if something isn't worthwhile, it's not worth thinking about. :smile:

KaVir said:
DavidHaley said:
This isn't the same kind of mapping anymore. Now you're talking about political-type divisions.

From an implementation perspective it doesn't matter what the data represents.

Of course it matters. Political divisions will be of rather sizable contiguous spaces. That means you can do very different things when it comes to representing those borders. Terrain and political regions, while both being maps of a physical space, will have very different patterns and distributions, so it makes sense to adapt implementation accordingly.
20.0/49