3d & Spherical maps discussion

[amjayee]

Great stuff here. I will do my best to discuss that soon, but as usual, I'm in a condition starting with "b". That condition will not, sadly, be helped by the fact that civ3 is coming in a week. I have pre-ordered the LE and it is highly likely to take up "some" of my time.

[VetLegion]

Limited edition, eh? too expensive for me, but if it is worth it I may also get it later. I dont believe it is limited at all
and no MP grr...


A few quick points: Leland, I was doing some calculations... however, I am bogged down with detail. I am trying to count the ratio of areas to tiles in a civ2 map and average region size, etc. problem is I want to do it on a standard large map, and it is a time consuming thing to do

I also tried to think fo a way to see how irregular average area is (lets call it irregularity factor) but the problem is that this is difficult to measure in real world maps I have of density, elevation, etc. Only data I can use is that of political maps, the ratio of border length to state area.

Since I can calculate the cost of an area I can see how much memory does vector option take on a civ2 map. But not completely. We do not have a density or population properties map in civ2, only a vegetation and elevation map.

I wanted to use civ2 map since it is only map with known resolution and is working and playable. I dont know how I can use a real world map of density or elevation or something, since resolution to use is unknown.

memory space rises with resolution with both solutions, but if we decide to keep the same ratios of number of areas to area size as in civ2, we can use civ2 to see will this pay of independant of the resolution we use, assuming irregularity factor is same. perhaps

key point discussed: memory an area takes is dependant on ratio of its borders to its 'area'. the longer and more irregular border is, more space is needed. the bigger the resolution, the more irregular borders are, but area is also larger so does the irregularity factor change? the more diverse map is, more areas are needed.... etc.

If anyone thinks we can do this another way, or knows a better way, tell me how, or just write here what system is better and why.

bottom line is I dont have any idea how to prove without doubt that areas are more efficient in size then tiles


I dont know have I made any sence I am a bit tired it is 2 AM here.
I am interested to see if someone has an idea on a better method to see this... perhaps without experiments alltogether?

I only have a gut feeling

[Leland]

It appears that both the tile-based and vector-based suggestions have their arguments, and neither is clearly superior to the other. They're just different. Furthermore, they both put heavy constraints on computing power and memory, but in different ways... we're just too inexperienced to estimate the exact consumption of computing resources beforehand. What we can estimate, however, is the trouble involved in programming the damn thing; I believe the tile-region-province trichotomy will be a lot simpler to do.

But, in the end it shouldn't be a question of easy programming rather than gameplay and what we want the game to be like. This is definitely a design issue, not a coding issue. This shouldn't be up to just me and Vet, we're only providing the background info for the decision.

To avoid confusion, let me clarify some terms that I will be using in the following:

Area: A vector-based description of an area in the map which has some common properties.
Region: A group of tiles on the map that share a set of properties.

I prefer these definitons because they illustrate that the difference between mine and Vet's approaches is not whether to use tiles or areas/regions, but instead should the tiles be dropped altogether. Vet prefers storing everything in areas, whereas I would go for a hybrid of tiles and regions. Here, I'll try to explain what the tile/region-based system would look like, and what I think the advantages and drawbacks are... like Vet said, it's a little bit complicated to do the same for areas but I believe that only shows that they are a more complicated bag of tricks to begin with.

First, the tiles are the absolute bottom layer in the system. There would be two kinds of information stored in tiles: the actual properties of a tile (terrain type, elevation, vegetation, population density), and references to the regions that occupy the tile. The latter may not be necessary since it's just a matter of optimization which one is better, storing references to regions in tiles or references to tiles in regions. For purposes of this example I am assuming that the tiles have references to regions because this way estimating the memory tradeoffs and complexity of the system becomes easier. Anyway, the amount of references that are needed in a tile depend on how many layers of regions do we want to use: it could be just one (for instance just the population layer, like we sometime planned), or several (religion, ethnicity, education, diseases, class structure, wealth, ...). In terms of memory consumption the actual properties of a tile will be relatively small compared to the region-references if there are more than a few region layers: in a million-tile map each new layer of regions adds one or two megabytes to the map size. This can be optimized a little bit (for instance, assuming that there are no populations in the ocean tiles or something), but it brings about tradeoffs between speed and memory so I'll just assume the worst case scenario that every single tile has these references.

It should be noted here that references to regions don't actually hold any data on the region, that is stored someplace else. So in addition to the basic tile map there would be a big pile of regions, probably taking at least as much space as the map itself.

For player's point of view, the map would in the end be a collection of tiles, but not in like in civ where the relatively low number of tiles makes it look like a chessboard. Instead, think of a high-resolution bitmap image. For example, I am writing this with screen resolution of 1024*768 (about the same as the intended granularity of our map), and I am not thinking of pixels that form the screen. Neither would the GGS player think about tiles when playing. I admit, he will have the map zoomed so that he can at least distinguish different tiles (whereas I cannot quite make out the individual pixels on my screen), but since there won't be a visible grid and the tile graphics will be just color coded, I don't think there will be much emphasis on the tiles in the player's mind. He will perceive the map as a group of differently color-coded regions. The edges of the regions would be a little bit rugged (following the edges of hexagonal tiles), but I believe they would be more detailed than the edges of equivalent areas, because the number of areas would have to be one or two orders of magnitude smaller.

The elevations, I think, will be more easily handled with tiles than vectors: when the player switches on the elevation layer in the screen, each tile would have a color based on the elevation value in its properties. These colors can easily be extrapolated so that the map on the screen would look like it was continuous... I believe that if the elevations were stored as vectors, the result would be uglier because there would be no small hills and variation, only the large picture (again, remember that the number of areas is a lot less than the number of tiles). For instance a terrain filled with hills and small lakes would look very simplified compared to the vector-based variation. The same applies to population densities, and perhaps vegetation. The tiles would rule here because of their higher level of detail.

On the other hand, regions in a tile-based map would be less continuous, and they'd look pretty much the same as they would in a vector based map. The difference is that vectors can be used more precisely (because they don't have to follow the tile noundaries): the edges of regions can be in any angle in a vector-based map, and it's possible to use better granularity than the 50km across tiles. The former advantage is lessened by the fact that in real world terrain does not follow straight lines anyway, so the rugged edge of a hexagonal tiles should be enough, and I seriously doubt that in a game with a global scope there is much use for smaller distances than 50km. If I could do any neat graphics about this I would, because I think I have a pretty good idea about my vision. Elmo, interested in helping me out here?

The bottom line is: with sufficient number of tiles the difference between a tile-based map (comparable to a bitmap image) and a vector-based map (a vector image) does not make vectors any more visually attractive. On the contrary, I think it is difficult to portray certain things in vector graphics (gradual changes in elevation, pop density and the like), whereas I cannot see where vector-based areas would be very beneficial. The more I think about it, the more sense having tiles makes, please shoot me down!

Some issues that I'd like to comment:

2d vs 3d map is always about tradeoffs, that is why there are so many earth projections used for the world maps, depending on what do you use them for. in GGS, our zoom level would be enough zoomed in so we can play effectively. This means pretty zoomed in, enough that earth roundness is not observable. hopefully, this will make distortions that have to happen when you show 3D earth surface on 2D coord system unobservable.

We may use same cordinate system, though some alterations are needed to cover for the distorsions.

That is assuming we go full 3D (amjayee clarification needed! ) with round spherical earth as a base.

I believe that this would not bring that many gameplay benefits. What I was thinking is to use 3D to show elevations on a basicly 2D map, on an earth that is flat and carried by turtles standing on an elephant, or a cylinder, like civ 2.

then we could use that simplified earth surface to generate a sphere to be used for a radar (civ2 ToT has this) or something else. This way we would have distortions on sphere instead of play map ( : ) and sphere would be much less used in gameplay. for a radar or some other unprecise thing.

Well, the way I see it the reason for using a 3d map is that it behaves like a globe, not that it just looks like it. If we are to use just one set of coordinates (be them catesian or polar), it means that there is only one map topology. Adding a flat map when the system is designed to be spherical would require all the algorithms that use the coordinate system to be rewritten. Having a pseudo-3d spherical map that just looks like a sphere but in fact is a cylinder does not have much gameplay value except for, as you said, some visual gimmicks. But that is not what we should be talking about when discussing 3d map.

This relates to the current discussion in the sense that it's impossible to have a spherical map with tiles, whereas with two-dimensional areas it is at least theoretically possible, though in that case we'd have to either give up the cylindrical map or code two sets of map algorithms for two coordinate systems. Not to mention that polar coordinates are more difficult to handle than cartesian. Anyway, if we had a fully 3d map then the problems between jumping from 2d to 3d is easier, but 3d coordinates take up 50% more memory than 2d coordinates, and it would be slightly more complicated to implement (though not any more complicated than switching the coordinate system on the fly).

I have said it before and I will say it again: spherical map may be unrealistic but I think it is not what this game is about.

The main issue about memory consumption is that there will be a lot of information stored just about the geometry of areas.

this may be the case, but it depends on the resolution we use. it is tempting to have resolution increased with system as felxible as this one. For example, if we have 3x3 squares on the map and the central one is mountain, it is a square. But if we use this areal representation, it is tempting to have that mountain more irregular to look more real. the more irregular (and realistic) it is, the more resolution of the whole game is increased, and more memory is used. I said that in a meeting, with higher resolution, it may take more space to store areas then tiles. But then again, we can increase resolution with tiles too, by adding more tiles, but that is not as intuitive as with areas.

I disagree. I think it is a lot more sensible to set a fixed bottom line for the resolution (in this case, tiles that are 50km across) and stick with it. The different aspects of the game have to be balanced anyway so that the different areas of the game (time spans, distances, and other details) are roughly about the same granularity. Changing this balance afterwards is an effort that affects the whole game, and fixing the tiles size is not the most critical issue. Besides, having 1 million tiles should be detailed enough for most purposes for a long time to come, if you ask me. I am often in afavour of more generality, but in this case I feel that the trouble involved in having a variable resolution is not worth the gains.

Terrain geometry data is connected to all other data in the game, as layers are above the map and in a way 'follow' the map. so all layers would have to have same resolution as terrain.

tiles are not holding any more info then areas.

What I meant by geometrical data was stuff that only tells where areas are, as opposed to what they are. The distinction is not that clear, I admit... but for example, think about an area that is defined by four vertices: that's four coordinates, which take a certain amount of memory. Then, you have the neighbouring tiles which also go through the same vertices, so the same coordinates are counted twice by necessity. And thirdly, you still need to store the information which areas are next to each other because it is too complicated to extract this information from a wireframe. The initial shape of the area is important game-wise, yes, but the other area boundaries going through the same vertices and the info about adjacent tiles is something that is not needed in a tile-based map, because each tile has the same shape and the same relation to its neighbours.

Similarly, the references to regions that are stored in tiles are the kind of information that tiles need but areas don't. But I think that with areas there will be a lot more of this "useless" data, and it is more difficult to compress away. At least I cannot think of a convenient compression scheme for problems stated above, whereas I can think several ways to reduce the number of region references in tiles...

I think player does not think about specific tiles anyway, instead of thinking '30,25 is grass', '30,26 is grass' etc, we zoom out a little and say 'this area between the lake and the mountain is grass.

There is a difference between the internal representation of the map, and the way player perceives it. I see no contradiction between having the terrain type stored in tiles, the player will still just look at groups of several tiles on the screen and think of it as an area. Human mind is very good at pattern recognition. But, I could argue that if the areas are represented as vectors there is a similar danger of player not thinking 'between the lake and the mountain is grass' instead of 'this polygon between the lake polygon and mountain polygon is grass'.

world is confusing. having a world map with all the layers: terrain, population, climate. it is a complex map with lots and lots of info that you need to think of. I dont see why it is more confusing then tiles, considering the resolution of tiles we were going to use anyway.

One way to cope with that confusion is to distinguish between properties that are better stored in tiles (like elevation, remember my previous example about hilly ground?) and those that are more suited for regions. I am skeptical about the notion that everything should be stored in areas.

you mention a few times that tiles are 'hidden' from player. what do you want them for then?

I guess this is more of a gut feeling than a sensible choice... but I feel that GGS should have more of a simulationist touch than other civs. Meaning, there would be lots of things going on that the player cannot possibly micromanage at once, but they'd still be there to make the experience realistic. This is just one step away from abstract games like chess towards a meta game where the real gameplay elements are not in the basic structures as much as they are superimposed on top of those structures. The simulation is not a game, it's just an instrument like the ball in soccer or the car in Formula 1, but that doesn't make it obsolete.

well, if we have 150 lake tiles for example, then you would have also a 'region/area' that would have info about which tiles it consists of and what is the property they share (water in this case).

so the question is, why have tiles, if the 'region/area' info is enough to represent both the location of tiles (enclosed within area borders) and their shared property (color of the area)?

But what if there isn't a one lake, what if there are 150 separate lakes (or islands, or hills, or whatever)? then storing the boundaries for each lake is a lot more troublesome than just pointing out that where the lakes are. As for storing double information, I think that in case of a single big lake your argument makes sense, but if there truly are 150 lakes to deal with but the general area has similar properties ("lakey") then it can still be put in one single region. Without tiles you'd have to have 150 small areas, or simply not store any information at all.

the less diverse an area is, the more memory advantages we get from 'areal' storing of info as oposed to 'tiled' storing. if some space is extremely diverse then there may be equal number of areas in it as would have been tiles, so there is no gain. but there are very few so diverse places, and I cant think of an example either.

One example I can think of are gradual boundaries of regions. Vectors always have sharp boundaries, and thus the middle ground between a desert and a rain forest could look quite abrupt. Of course, the gradual change can be represented by an area of its own but in this case the memory advantage is not big because the in-between area would be shaped so that it has a long boundary but still does not cover much ground. Same applies to rivers. It's true that tiles also have sharp boundaries, but at least there would be 10-100 times more of them than areas.

I think that we can devise compression schemes to make the tile-based system more efficient in case of oceans and other large, relatively uniform regions. Compressing

well look at it gamplay-wise. you can see all of terrain this way as you see it with tiles. on the other hand you dont always 'see' all the layers on terrain. so for gameplay purposes you can turn on/off different layers at will.

Disagree. Our plan has ben from the start to show the map as layers and that has little to do with whether the game internally uses tiles or areas. On the other hand, the large number of tiles makes it impossible to show everything as areas, neither of these systems can fully cover the other... it is a real design tradeoff.

another advantage is that I think areas (of tiles or no tiles) are more intinuitive way of thinking about the map. even with tiles, we would have some way to enumerate simmilar ones and show them in a layered way. for example when player wants to see islam coverage, an algorithm has to go through all the tiles, check their properties and display them if there is muslim pop there. having data grouped by areas instead of tiles means that effectively we have already calculated this information, and do not have to do it every time a display is required.

I agree that we need to enumarate some properties in regions. But I disagree that this would make the computation unfeasible. Especially since this is a turn-based game: the player doesn't need to get the response in milliseconds, it can take up to one second (or maybe even more) to actually seek the data. After it has been seeked once, it's stored somewhere in the memory temporarily and the speed is not an issue until next turn (or when player switches to anothe view and back). Besides, the areas also have their problems: what if player is looking at an area of Suahili speaking farmers, and wants to know what are their religions? The computer would have to check whether any of the religion areas overlap with the given language area and the farmer area.

one advantage is the memory, which would likely be less used if resolution is keept within reasonable limits. It is possible to use a pseudo random algorithm to show non-existant resolution for cosmetic purposes.

Cosmetics, schmosmetics. Everything should be real! And who says we can't use those cosmetic algorithms for tiles, thus making them even more detailed?

key point discussed: memory an area takes is dependant on ratio of its borders to its 'area'. the longer and more irregular border is, more space is needed. the bigger the resolution, the more irregular borders are, but area is also larger so does the irregularity factor change? the more diverse map is, more areas are needed.... etc.

Most natural borders like shorelines and such are fractals, so the length of the shoreline does indeed grow more than the size of the area. Difficult to estimate. Especially since some areas like rivers and canyons are differently shaped than deserts and oceans. Not to mention those pesky small hills that I try to squeeze into every sentence.

[Leland]

(I hit the 20000 character limit again...)

Well, to tell you the truth I also don't have concrete evidence. Maybe we should just settle this with a vote? Though I believe that tiles are a safer way to go because they are simple, and thus a less risky task to undertake. Would it be possible to come up with a hybrid that combines both tiles and vector-based areas?

[The Joker]

Ahh, bloody hell!

Things have really tied up this week. I have 3 projects for next week, so I don't really have any time at the moment.

I promise I will make it up to you. If not in the weekend then early next week.

Great discussion, BTW!

[VetLegion]

it will take some time to come up with a reasonable reply/answer

good post

[VetLegion]

This made me think, and I mean really think

I have come up with some solutions and even more problems came up but it was to be expected when going to this level of detail.

I ll try to write it up tonight.

[VetLegion]

But, in the end it shouldn't be a question of easy programming rather than gameplay and what we want the game to be like. This is definitely a design issue, not a coding issue. This shouldn't be up to just me and Vet, we're only providing the background info for the decision.

true

Ok. First I want to note that this thread is called '3d & Spherical maps discussion' but we have expanded it to discuss maps in general, and other related things. In these huge posts I am (and Leland too) discussing a few different things at once, so it really takes an effort from the reader to understand what is what. thanks for the effort

my biggest concern here is the memory aspect of storing data in areas. here are some thoughts on that.

first, imagine a civ2 map. It has a certain resolution, lets say it is 100x100 tiles. It consists of tiles. Now if we decide to describe it with vectors, would it take more space then with tiles or less? We keep the same resolution, the map is still consisting of 100x100 smallest indistinguishable objects but we do not use them.

lets say that one tile reserves one byte.

on the other hand, one area takes more memory. area has to have an origin (x and y), a property and a border.

in tiled storage:

Total memory) = number of tiles x Memory taken by tile

in 'area' type of storage, area takes:

Memory = 2 bytes (x and y) + 1 byte (property) + border bytes

minimum size area takes 4 bytes to represent as opposed to 1 byte with tiles.

so, to pay off in memory consumption, average area size (number of tiles (resolution) divided with number of areas) has to be 4 (tiles) or more.

I have been trying to think about proper vector representation, but I am total newbie on it, so for simplifying purposes lets have the most irregulary areas possible. borders of those areas are not lines or curves, they are broken as much as possible by the given resolution.

the border is following from origin point (and returning to it too). For its flow we need only two bits (00 - up, 11 - down, 10 - left, 01 - right). when border reaches the origin, it stops.

so area takes space: 3 (x, y, property) + number of 'tiles' in border / 4 (as there are 8 bits in a byte)

the larger area is, bigger the payoff. huge number of areas of smallest possible size is the worst case scenario.
we can say that map diversity = number of tiles (resolution) / number of areas.

if this diversity is such that average area covers at least 4 tiles, memory consumption will not grow.

can diversity be objectively calculated?

I wanted to do it with civ2 map, but it is too big and I cant be bothered. and world maps I have are not good for that kind of stuff.


Another important thing to notice about our maps as opposed to civ2 maps - flags.

Flagged values are values that have only a yes or no value. The entire civ2 map is a sort of based on flags: road on a tile, yes or no? whale resource, yes or no? grassland, yes or no?

that makes it such that map is very little space consuming, one flag is one bit. (I think civ2 uses only 2 bytes per tile, not sure though)

......................civ2...........GGS
elevation:.......flags..........value
vegetation:.....flags..........value?
structures:......flags..........values (objects with properties)

pop density:......-..............value
no. of muslims:.-..............value
no. of farmers:..-..............value
......//................-..............value

Total:...............2 bytes.......X bytes (where x is much more then 2)

fundamental issue with tiles is that tiles reserve space in memory that may or may not be used. ocean tiles in civ2 use 2 bytes although there are never stuctures on the ocean, nor forrests, etc.

the huge number of values (bytes, I hope 'int' wont be our smallest storage ) we are going to have includes besides usual layers, climate values and population properties. the later is huge, believe me

in lots and lots of world parts there would be large areas of uniform properties. it brings down to how diverse world really is? now that we have taken the worst case scenario to calculate with.

now to reply to your points Leland. lets see if I can break the character limit too

The bottom line is: with sufficient number of tiles the difference between a tile-based map (comparable to a bitmap image) and a vector-based map (a vector image) does not make vectors any more visually attractive.

it was not the point to make them visually atractive. they have to respect the resolution, so vector map of civ2 will be looking exactly the same as tile map - zero visually atractive. on the other hand on bigger resolution it will look less edgy.

On the contrary, I think it is difficult to portray certain things in vector graphics (gradual changes in elevation, pop density and the like)

it does depend on resolution. if you look at any world density map it looks like piece of cake, little more diverse in europe, but with large portions of gobi desert, siberia, oceans with little or no population (more important, it is uniform). and in tiles the bytes are still reserved.
elevation on the other hand, depends on resolution
I can imagine a worst case scenario with elevation ... but I cant be sure of it. I think elevation may be single most consuming thing for areas, together with vegetation perhaps. everything else is less diverse.


3D

Anyway, if we had a fully 3d map then the problems between jumping from 2d to 3d is easier, but 3d coordinates take up 50% more memory than 2d coordinates, and it would be slightly more complicated to implement (though not any more complicated than switching the coordinate system on the fly).

computer monitor is flat, and flat projections of sphere map make distorsions, which are very serious. whichever way we look at it, we are looking at tradeoffs. more even, I think such a thing as completely 3D map takes more work then it seems. we can ask Ron Hiller a question or two about it.
at the moment, I am not very pro sphere
from what I see neither are you, or are you

What I meant by geometrical data was stuff that only tells where areas are, as opposed to what they are. The distinction is not that clear, I admit... but for example, think about an area that is defined by four vertices: that's four coordinates, which take a certain amount of memory. Then, you have the neighbouring tiles which also go through the same vertices, so the same coordinates are counted twice by necessity. And thirdly, you still need to store the information which areas are next to each other because it is too complicated to extract this information from a wireframe. The initial shape of the area is important game-wise, yes, but the other area boundaries going through the same vertices and the info about adjacent tiles is something that is not needed in a tile-based map, because each tile has the same shape and the same relation to its neighbours.

this is important stuff

perhaps we can make areas border orientated, so we describe a border and keep info on which two areas it separates or something... it is important to note that areas only border with max two other areas.
the entire layer represents a property and different areas show density of that property.
information can be extracted from wireframe, for example an algorythm is needed for calculating is a point within area polygon or not... there is lot of calculating here that needs to be investigated. good points ... we have to think about it more.

One way to cope with that confusion is to distinguish between properties that are better stored in tiles (like elevation, remember my previous example about hilly ground?) and those that are more suited for regions. I am skeptical about the notion that everything should be stored in areas.

well, lets see then what should be stored in areas and what not. anything other then elevation? lets enumerate this stuff and see how much space does it take.

One example I can think of are gradual boundaries of regions. Vectors always have sharp boundaries, and thus the middle ground between a desert and a rain forest could look quite abrupt. Of course, the gradual change can be represented by an area of its own but in this case the memory advantage is not big because the in-between area would be shaped so that it has a long boundary but still does not cover much ground. Same applies to rivers. It's true that tiles also have sharp boundaries, but at least there would be 10-100 times more of them than areas.

ok, the gradual change. well as explained above, if area, however long its border, covers at least 4 (take this with reserve. maybe 6 or 10 if we decide more data is needed) tiles it has payed off. so even if it is one tile (I use tile here often as: 'the most gradual/smallest change resolution allows') wide and 100 tiles long it pays off.

I think that we can devise compression schemes to make the tile-based system more efficient in case of oceans and other large, relatively uniform regions.

I think we can not. a tile reserves a space in its array and thats it.

now back to your explanation:

First, the tiles are the absolute bottom layer in the system. There would be two kinds of information stored in tiles: the actual properties of a tile (terrain type, elevation, vegetation, population density), and references to the regions that occupy the tile. The latter may not be necessary since it's just a matter of optimization which one is better, storing references to regions in tiles or references to tiles in regions.

so these regions, what are they for? I am really lost here at what is represented by regions do they have borders? do they change?

that is all for now

[VetLegion]

what does this board have against empty spaces? I had to edit the post to fix the only table I put in. if putting a smiple table takes so much work, I wonder what would happen if I wanted to draw a picture and include it?

anyway Leland if I missed a point or two of yours, let me know. I feel like I was typing for ages.

[VetLegion]

perhaps we can make areas border orientated, so we describe a border and keep info on which two areas it separates or something... it is important to note that areas only border with max two other areas.

that is quite a neat idea I ll see if I can think of a way to make it feasible. since with areas borders take the most space, compressing mutual borders (keeping only one border and some sort of references to regions (two) it separates), especially long ones, would cut the space in half I hope we can do it that way, but I am bit too tired to think. anyway, this occured to me now and I havent had it in mind with the original post, so I think areas are quite lean even without this compression scheme.

[Leland]

Deja vu...

Last spring I thought about exactly that kind of storing system, that is to save the border of a region (I think I called them "areas" then... maybe I should search the meeting logs or something) as direction changes, except that I was concentrating on hexes instead of squares, and so that the border would also consist of tiles (so, no shared borders). The system seemed good enough, I just ran into trouble finding simple algorithms and such so I forgot about it.

Based on my experiences, I can say that your estimate has at least two faults:

1. 2 bits per border vertex/edge is not enough. You need to either have an ending value, or store extra information on how long the border is.

2. There are odd shapes that don't fit this model very well. Donut shape, which has two borders, is difficult to grasp... and shapes who border themselves (in these cases there is a danger that border reaches origin before it is supposed to).

Perhaps these issues can be solved by storing the real border instead of just a path of tiles... so I am not saying that we should go back to what I thought last spring (because Vet just made some comments that really show me how wrong my approach was) or that Vet's suggestion would be already discarded. On the contrary, this has put my mind spinning. Maybe later I can elaborate a new improved proposal based on my old ideas. But before that, I think we should clarify a few things (again).

Vet seems to strive for minimal memory consumption, but I think that it leads to maximal CPU consumption. The map is not a static piece of data, it has to be accessed very often and thus the representation of the map has to be such that possible queries can be done FAST. It's a lot more difficult to estimate the computing power involved since we don't know those algorithms... but from experience, I think it is safe to say that it's not trivial to determine whether a point is inside an area or whether two areas intersect, or any of that stuff. That is why I suggested that references be used to refer to regions... that just makes it very simple and very fast to answer the question "what regions does this tile belong to", and not terribly slow (with proper optimization) to answer "what tiles belong to this region". It's a tradeoff between memory and speed.

Vet wondered what the heck I meant with regions. I think I mentioned somewhere that I am using regions only to distinguish between tile-based thingys from free-form-vector-based thingys. What you described was regions, because of the underlying tiles. And when I said that the references to regions aren't necessarily needed in tiles, I meant exactly the kind of compression schemes that you talked about: that we store the information about which tiles belong to a region (e.g. a border that uniquely defines a group of tiles) along with the region properties.

Hmm. I have to get back to this subject when my brain works better.

[VetLegion]

1. 2 bits per border vertex/edge is not enough. You need to either have an ending value, or store extra information on how long the border is.

that is also an option, but since border has to end where it begun, no problem there. the extreme case where data for length/enging would be useful is when area is of smallest possible width (1 tile).

so we have: x, y, property, 00, 00, 00, 00, 00, 00 (end is reached - go back), 11, 11, 11, 11, 11, 11.

with this description it has to go all the way from origin to end and back, having one more bit to know when to stop may cut the space. on the other hand it works without it too, and it is not really consuming that much memory.

2. There are odd shapes that don't fit this model very well. Donut shape, which has two borders, is difficult to grasp... and shapes who border themselves (in these cases there is a danger that border reaches origin before it is supposed to).

many areas would have two borders ... with the compression scheme perhaps we can cut the memory needed.
about botdering themselves, I dont think it is a problem...?

[VetLegion]

Originally posted by Leland
Vet seems to strive for minimal memory consumption, but I think that it leads to maximal CPU consumption.

quit that 'Vet says' thing, I feel like I am not here

but from experience, I think it is safe to say that it's not trivial to determine whether a point is inside an area or whether two areas intersect, or any of that stuff. That is why I suggested that references be used to refer to regions... that just makes it very simple and very fast to answer the question "what regions does this tile belong to", and not terribly slow (with proper optimization) to answer "what tiles belong to this region". It's a tradeoff between memory and speed.

I agree, it is far from trivial. But if every tile has a reference to all areas or regions it belongs it is a lot of memory

[The Joker]

Incredible! This is the best discussion we've had for eons. Good work, guys. Really good work.

Finally I have had the time to read all of this thread, and so I have done.

Sadly I am not more sure now than I was before.

You both have really good points.

About memory/CPU consumption, it seems to be too dificult to say anything about which option is best at this point. But at the same time I do believe that computers will be so advanced when we really need them that this should not be an issue.

In stead we should decide on what option that offers the best gameplay value, looks best and is easier for us to do.

And I still believe that using Vet's areas is more cool than using tiles. I agree that the elevation this might be an issue for large areas, but if we have a "rockyness" property for each area, 00 being flat and 11 being high snow covered mountains we could solve some of this using just 2 more bits per area.

My main concern with areas, however, is whether we can do it. We are already way over our heads with this project (which is why it's so fun - I love doing things I'm no good at and learning from them!) that we might want to play it safe with the map, since no matter what it is not the main issue in the game, and so be able to proceed with development sooner.

So I think it all depends: Do you guys think that you can make a vectorbased map? If you think you can then that will be what I will vote for. If you are in serious doubts about it I believe that we should use tiles in stead.

What do you say?

[ElmoTheElk]

I totally agree with Joker here. If you (all programmers) can program a reliable vector based map, that would be very cool. But if you think that's gonna cost months, we'd better get back to the tiles and actually proceed in the development.

Elmo