10 Oct, 2007, Mabus wrote in the 1st comment:
Votes: 0
I have been coding a CoffeeMud (CM) codebase MUD for quite a while, and wish to add a ship system with large ocean areas. I have my designs for the code for ships, but large ocean areas using the current area code do not seem to match what I am thinking. Using the current code could be possibly problematic in system resources and functionality between my design and CM. As such I am going to design this code from scratch and then code it to work with the CM area/room/database code once complete.

Disregarding the current codebase, and looking at it from a pure design viewpoint:
* In general design what are the best methods for creating a large grid system?
* What should it include?
* What should I avoid?
* Any coded examples to look at? (codebase and language doesn't matter)

I look forward to any thoughts from you fine folks.
10 Oct, 2007, David Haley wrote in the 2nd comment:
Votes: 0
It depends on how large is 'large'. If you're talking a 1000x1000 grid, that's 1,000,000 locations, which might or might not be a lot depending on what you are putting into them. If you're talking about 10,000x10,000 that's 100,000,000 which is probably not-so-ok.

An important insight is that you really don't need to have an actual room structure for all the grid points unless something is actually in there. That is, you don't need a grid of instantiated Room objects: you could leave as null all the ones that aren't currently occupied, and when you needed to (e.g. somebody walks (sails) into one) you would instantiate the room. But you really don't need to leave rooms lying around.

Still, 100,000,000 null pointers is a lot of pointers. Assuming one byte per pointer (which is a quarter or an eighth of a more realistic assumption) that's 100meg of stuff, on top of the memory needed to actually represent the instantiated rooms. If you think about it, you probably don't need to store the whole grid even as null pointers. Instead, it suffices to instantiate just rooms that are present, along with their coordinates, and if somebody moves from one to the next, you just make more rooms with their coordinates. You would probably want to leave the rooms around in memory for a few minutes (or seconds) so you don't have to recreate the rooms if somebody's just walking back and forth for some reason.

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. Then, whenever somebody walked into a room, you'd have to check whether they were going into one of the special locations, in which case you wouldn't instantiate a generic ocean tile but instead look up the appropriate room (or generate an appropriate generic tile of that type). For instance, your coastline doesn't necessarily have to be all unique: but, you would need to know what happens if somebody beaches the ship there (unless of course you only allow stopping at ports).

Going back to your general questions:

What your system includes is up to you, really, and what you want your system to do. I can't really think of anything off the top of my head that would have to go into any grid system.

What you should avoid is allocating space needlessly, depending on how big your grid is and/or how much you want it to scale.

I don't really have an example on hand, though. :)
10 Oct, 2007, kiasyn wrote in the 3rd comment:
Votes: 0
its ocean, so you have lots of areas that are more or less identical


lets say a 30x30 block - this is one 'room' at a set of 'primary coordinates',

a ship would be assigned first the set of primary coordinates, which specify which block the ship is on, then more 'secondary coordinates', which give its position in the block
10 Oct, 2007, David Haley wrote in the 4th comment:
Votes: 0
I'm not sure why exactly you'd want to do that. You can access an absolutely huge grid with two ints, so I'm not sure why you'd need four. If you're representing it as a grid the cells of which are more grids, you haven't saved space, and arguably you've worsened the space requirements.
10 Oct, 2007, kiasyn wrote in the 5th comment:
Votes: 0
because

int map[300][300]; is a lot smaller than int map[3000][3000];

eg

#define MAP_SIZE 300
#define BLOCK_SIZE 50
int map[MAP_SIZE][MAP_SIZE]; // grid of blocks BLOCK_SIZE by BLOCK_SIZE each

class Ship {
public:
int x; // between 0 and MAP_SIZE
int y;
short subx; // between 0 and BLOCK_SIZE
short suby;
Ship( int xc, int yc, int sx, int sy ) : x(xc), y(yc), subx(sx), suby(sy) {};
int move( int xc, int yc ) { x = xc; y = yc; };
int blockmove( int sx, int sy ) { subx = sx; suby = sy; };
};

Ship ship( 0, 0, 0, 0 ); // ship is now on block 0,0, positioned in block at 0,0

ship.move( 20, 30 ); // ship is now on block 20,30

ship.blockmove( 30, 22 ); // ship is still at block 20, 30, but is positioned in the block at 30,22
10 Oct, 2007, KaVir wrote in the 6th comment:
Votes: 0
DavidHaley said:
It depends on how large is 'large'. If you're talking a 1000x1000 grid, that's 1,000,000 locations, which might or might not be a lot depending on what you are putting into them. If you're talking about 10,000x10,000 that's 100,000,000 which is probably not-so-ok.


Even if you went for 10000x10000, you wouldn't literally have to store it as an array of that size. An approach I used in the past was to store a 512x512 array of pointers to tiles of 10x10 rooms, with a separate 512x512 array of default tiles. That worked out at 1MB for the array of pointers, 0.25MB for the array of default tiles, and 25K for the 256 default tiles. The bumped list of up to 100 modified tiles (others were unloaded) took up another potential 39K.

If the majority of the world is ocean, he'd probably want to have larger tiles. Using the system I described above, except with 20x20 room tiles, would give you a world 10240x10240 - and still only use up around 1.5MB of RAM. Of course you'd still have to add on the memory overhead for normal rooms, as well as up to one room per player for the wilderness (and on that note, you don't need to keep creating and destroying rooms unless the player is entering or leaving a location with creatures or objects already in it - if they move from one empty room to another, you just reuse it).

I also posted about this on MUD-DEV, back when I was still working on it, and discussed some of the problems I encountered. The original poster might find my post of interest, although it's bit old now: http://www.disinterest.org/resource/MUD-...
10 Oct, 2007, David Haley wrote in the 7th comment:
Votes: 0
Kiasyn said:
int map[300][300]; is a lot smaller than int map[3000][3000];

What purpose is served by having a coarse grid? Why have a grid at all? That is my point… there's no need to have an entire grid of stuff that will be mostly empty, even if you make the first layer coarse. In your example, for instance, all you care about is the ship's position. You don't need any instantiated grid whatsoever to care about that. And then, the two coordinates are unnecessary complication.

KaVir said:
Even if you went for 10000x10000, you wouldn't literally have to store it as an array of that size.

I'm glad to see that people read my posts all the way through. :wink:
10 Oct, 2007, KaVir wrote in the 8th comment:
Votes: 0
DavidHaley said:
Why have a grid at all?


Because "large ocean areas" is not the same as "the entire world is one solid ocean". A grid is a reasonably easy and efficient way of storing varied terrain, and as Mabus specifically asked how to design and create "a large grid system" I think it's more than reasonable to answer that question rather than trying to make him justify his choice.

DavidHaley said:
I'm glad to see that people read my posts all the way through


I read your post through. Your proposal didn't address Mabus's requirements.
10 Oct, 2007, David Haley wrote in the 9th comment:
Votes: 0
Just because you are trying to implement a grid of terrain doesn't mean you have to implement it as a literal grid in memory. :shrug: If you instantiate a literal grid of mostly nothingness, you are being rather (well, very) wasteful. You are confusing the concept of a grid world with the implementation details of representing it.

In other words:
What exactly are you gaining by instantiating the entire grid as an array in memory, even if you are compressing tiles into macro-tiles? What exactly is gained by having all that information lying around as an array when the majority of it is just emptiness? Why bother instantiating things other than when necessary?


EDIT:
I feel the need to add that I wasn't in any way asking Mabus to justify his choice of having a grid of terrain. I was talking purely about implementation details. That you (= KaVir) interpreted it as such is indicative to me that you did not understand what I was suggesting. I hope the above explanation is enough to put us back on track.
10 Oct, 2007, KaVir wrote in the 10th comment:
Votes: 0
DavidHaley said:
If you instantiate a literal grid of mostly nothingness, you are being rather (well, very) wasteful.


He's not instantiating a grid of "mostly nothingness" though. He's instantiating a grid which contains large ocean areas.
10 Oct, 2007, David Haley wrote in the 11th comment:
Votes: 0
Yes, and those ocean tiles will for the most part be empty, no? Because there are no ships there, no? Therefore it makes sense to not represent a bunch of tiles with nothing in them. Only tiles that are "interesting" (i.e. have a person in them, or script running, or …) need to be instantiated.

My proposal uses space requirements proportional to the number of "interesting" tiles. A proposal that divides the grid into sub-grids is using space proportional to the size of the grid, despite most of that space not being important to actually instantiate.

The fundamental question I am asking you is:
What exactly do you gain by representing in memory the literal grid of ocean tiles? (even if you make those macro-tiles.)
10 Oct, 2007, Kayle wrote in the 12th comment:
Votes: 0
As far as implementing this goes, I'm not the best to ask, as I've yet to start the seafaring system for my mud, and when I do, it probably won't be snippetable simply because of how integrated with the rest of my world it will be. So I'll leave the first three questions alone and jump straight to the last one.

Mabus said:
* Any coded examples to look at? (codebase and language doesn't matter)

While I'm not 100% certain that SWR uses the kind of system you're talking about, their space code, while sloppily done, could prove useful to you in designing your system. The SWR Space system has a lot of shortcomings, such as the ability to fly your ship right through what should be a planet, but aside from those short comings, it does seem to me (and I'll admit I'm not very good at calculating out overhead or any of that like David mainly because I've never taken the time to memorize just how much memory each thing in code takes up) that the way they chose to implement it in the end seems to streamline the memory usage and overhead.

I'm sure KaVir could shed a little light into the SWR Space system for all of us if he took a moment to look it over. :tongue:
10 Oct, 2007, David Haley wrote in the 13th comment:
Votes: 0
The space system is a good example of not needing to literally instantiate the entire "grid" of 3d coordinates. Ships have their current position stored, and there's no need to have cells storing nothing.

A sea-ship system can be implemented the same way except that you are in 2d, not 3d. (And that's what I proposed.)

It can be useful to partition the space (not necessarily into even grids, mind you) depending on what your other requirements are and what usage you expect of the system. For instance, if it is a requirement that you want to be able to find a list of all ships within x distance of you, it can be helpful to rethink somewhat your system. (Still doesn't mean you need a literal grid, though.)

Kayle said:
(and I'll admit I'm not very good at calculating out overhead or any of that like David mainly because I've never taken the time to memorize just how much memory each thing in code takes up)

It's a little more than just knowing how many bytes things take up; it's a question of math and algorithms, really, e.g. understanding the combinatorics. The discussion about the greeting system a month ago or so is a good example.
10 Oct, 2007, Scandum wrote in the 14th comment:
Votes: 0
DavidHaley said:
What exactly do you gain by representing in memory the literal grid of ocean tiles? (even if you make those macro-tiles.)

Assuming it's not just all ocean you need to know if a tile, whether used or not, is land or ocean. If you don't you'd need some kind of algorithm that determines what can be found at a specific location, which is possible in theory, but I've yet to see one in practice. A good alternative is what kavir suggested, which is an easy way to compress the grid.
10 Oct, 2007, Guest wrote in the 15th comment:
Votes: 0
I'm also not very up on the kind of things David is getting into, but you may be interested in checking out the overland code either in AFKMud or from the snippet for Smaug. Though it may to the "bad" thing and loads the entire terrain grid into memory ( including ocean sectors ) it doesn't need to create a whole series of rooms to work. The system uses a single real room to stick everything in and the map shown to the player is based on what their coordinates are on it.

AFKMud also has some ship code we pulled from Altanos awhile back but was never finished. It's barely functional enough for someone to walk onto a ship and "sail" out to sea. In reality it's just a cheesy looking "4" on the overland map, but it might be useful to look through anyway.
10 Oct, 2007, David Haley wrote in the 16th comment:
Votes: 0
Scandum said:
Assuming it's not just all ocean you need to know if a tile, whether used or not, is land or ocean.

Yes, that is why I made the difference between uninteresting and interesting tiles. An island in the middle of the ocean would be 'interesting' in that you would need a different way of representing it. That still doesn't mean you need to instantiate the whole grid.

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.

That said, I was under the impression that the grid would be used to represent the ocean, and therefore would for the most part be water tiles with just the occasional island. If however the grid would be used to represent fairly heterogeneous terrain, you'd need something a little more clever.

As a tangent, let me explain more what I mean when I say that you only need to represent the 'interesting' things. Let's assume you're talking about whether a bunch of things are true or false. If the vast majority are true, and just a small set are false, then there is no sense in listing out all the true things. Instead, it makes more sense to list out just the false ones, and to check if something is true, you make sure it's not in that list.
This terrain business is basically the same. If the vast majority of your grid is water (which it would be for an ocean), there isn't any need to list all this information: instead, just list the things that aren't ocean (or are otherwise interesting) and everything else is ocean.

Scandum said:
If you don't you'd need some kind of algorithm that determines what can be found at a specific location, which is possible in theory, but I've yet to see one in practice.

Maybe I don't understand what you mean by the above, but what you're asking for sounds very simple to me. You could for instance index coordinates of 'interesting' tiles, and then to see if something is interesting, you just look it up in that index.
10 Oct, 2007, KaVir wrote in the 17th comment:
Votes: 0
DavidHaley said:
Yes, and those ocean tiles will for the most part be empty, no?


No, they will contain ocean terrain data.

DavidHaley said:
Because there are no ships there, no? Therefore it makes sense to not represent a bunch of tiles with nothing in them. Only tiles that are "interesting" (i.e. have a person in them, or script running, or …) need to be instantiated.


The grid isn't for storing ships and people, it's for storing terrain data.

DavidHaley said:
My proposal uses space requirements proportional to the number of "interesting" tiles. A proposal that divides the grid into sub-grids is using space proportional to the size of the grid, despite most of that space not being important to actually instantiate.


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.

Not only would your proposal be completely impractical from a size and effort perspective, it would also be horribly inefficient speed-wise - without a grid (which can be quickly accessed as an array), how are you going to efficiently search through 29 million rooms in order to find the one at the appropriate x/y position?

DavidHaley said:
The fundamental question I am asking you is:
What exactly do you gain by representing in memory the literal grid of ocean tiles? (even if you make those macro-tiles.)


The concept of "land".
10 Oct, 2007, David Haley wrote in the 18th comment:
Votes: 0
KaVir said:
No, they will contain ocean terrain data.

And just what is this ocean terrain data? "There is ocean here"?

KaVir said:
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.

I think you are making an extra assumption here. You're assuming that the entire world, not just the ocean, will be laid out on the grid. Obviously, if that were the case (which is not clear to me from the original post) the situation is somewhat different. It's still wasteful to instantiate the whole grid, but as I said in my previous post, you can do more clever things.

KaVir said:
Not only would your proposal be completely impractical from a size and effort perspective, it would also be horribly inefficient speed-wise - without a grid (which can be quickly accessed as an array), how are you going to efficiently search through 29 million rooms in order to find the one at the appropriate x/y position?

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. Of course, whether or not this matters depends on what exactly you intend to do with your grid.

Obviously all answers to all of these questions depend a great deal upon what exactly you are planning on doing. That shouldn't even be under question…

In this particular case, we are all working off of guesswork as to what exactly Mabus wants. If the goal is simply to create a plane in which objects can move around and bump into each other, you can use a dramatically different set up than something in which every tile is somehow relevant, as for a detailed weather simulation.

DavidHaley said:
The fundamental question I am asking you is:
What exactly do you gain by representing in memory the literal grid of ocean tiles? (even if you make those macro-tiles.)

The concept of "land".
You can represent "the concept of 'land'" just fine without explicitly representing the entire ocean grid… so you haven't really answered my question.
10 Oct, 2007, KaVir wrote in the 19th comment:
Votes: 0
DavidHaley said:
And just what is this ocean terrain data? "There is ocean here"?


Currents, tides (particularly in relation to intertidal zones), reefs, hydrothermal vents, tidal rapids, whirlpools/maelstroms, oil fields, islets, volcanic arcs, etc - not to mention the numerous underwater habitats of various marine organisms.

If ships are going to be a major feature of the mud then it's unlikely you'd want to classify all types of ocean terrain as the same - any more than a regular mud would classify all land terrain as "There is land here".

DavidHaley said:
I think you are making an extra assumption here. You're assuming that the entire world, not just the ocean, will be laid out on the grid.


Mabus would have to clarify his intent, but I think that's a reasonable assumption. The assumption that every element of the grid contains exactly the same ocean terrain tile is considerably less likely, in my opinion.

DavidHaley said:
Obviously, if that were the case (which is not clear to me from the original post) the situation is somewhat different. It's still wasteful to instantiate the whole grid, but as I said in my previous post, you can do more clever things.


You can do different things, but every approach has its drawbacks…

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.


…25 steps every single time you need to check what type of terrain a character is on - as opposed to 1 step for the array.

DavidHaley said:
You can represent "the concept of 'land'" just fine without explicitly representing the entire ocean grid… so you haven't really answered my question.


Requiring the builders to create 29 million land rooms - and then performing up to 25 steps instead of 1 every time you want to find a specific room - isn't a solution I'd consider to be "just fine".
11 Oct, 2007, David Haley wrote in the 20th comment:
Votes: 0
KaVir said:
Currents, tides (particularly in relation to intertidal zones), reefs, hydrothermal vents, tidal rapids, whirlpools/maelstroms, oil fields, islets, volcanic arcs, etc - not to mention the numerous underwater habitats of various marine organisms.

Woah! You've just added a whole flopful of requirements. Whatever, those assumptions cannot be confirmed or denied without additional input from Mabus. I was working from the minimal set of assumptions based on what we were given – I wasn't trying to color my comments with the bias of what I think his system should be.

KaVir said:
You can do different things, but every approach has its drawbacks…

And obviously you want to optimize those drawbacks for the operations you do most often. Without knowing what all the requirements are, we cannot completely answer that question. 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:

KaVir said:
…25 steps every single time you need to check what type of terrain a character is on - as opposed to 1 step for the array.

OK, well, please forgive the sarcasm, but… there are these things called pointers, and they're pretty cool…

KaVir said:
Requiring the builders to create 29 million land rooms - and then performing up to 25 steps instead of 1 every time you want to find a specific room - isn't a solution I'd consider to be "just fine".

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? 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.
0.0/49