Large scale maps

[trollson]

Greetings,

 

Before I start this evenings delvings, I thought I'd finally get one idea out into the forum (one of several). I don't know whether this fits into the current architecture (probably not!), but it may be of interest all the same.

 

In the current game, the world is defined by the 3D maps, with instant travel between (ships, teleport, death...). This does mean that the entire continent is relatively small -- as a character could walk across all maps in less than an hour (I suspect, but haven't tried!). It also means that the continent is divided into traversable/mapped areas, and untraversable/unmapped areas.

 

My approach would been to start with a fully traversable large scale map -- movement on which would be more akin to the map view in the EL client, and not rendered in 3D. The information required for these large scale maps would just consist of the map image, and some coarse terrain definition. This would allow the clients to determine the best path between two points (as I understand it, the server currently has to perform path finding on the 3D maps?).

 

The 3D rendered areas would then be mapped onto rectangles on the large scale map. If a traveller's path enters one of these areas (as determined by the server given the client generated path), they enter the 3D map at the equivalent point on its boundary.

 

Interesting features:

• New 3D areas can be added as desired without changing the traversability (constrained only that they do not overlap, and reflect the large scale terrain).
   
  
• These 3D areas do not need to be declared -- they may require players to stumble upon them.
   
  
• It scales! The world can be as big as you want, and the detail can be added over time.
  

Opportunities:

• Ships still provide direct 'safe' travel along known routes (major towns and cities). The land equivalent would be wagon trains or caravans.
   
  
• Factor in movement speed on the large scale maps; mode of travel -- foot, horse, boat, wagon, eagle -- different terrain costs (again, client side calculations).
   
  
• Following roads would be safe, but travel off roads may spark a random encounter (server held monster maps!), for which stock small 3D maps for each basic terrain type could be used.
   
  
• The large scale maps may come in different scales, allowing more detail in interesting areas (+/- buttons on the map window?). See OpenGIS software, or any online map database for examples (far more complex than we would need!).
  

Implementation notes:

• I am not proposing that players are made to sit and wait while there character trudges hundreds of leagues of nowhere. While the movement should not be instantaneous, it would be sped-up relative to movement across 3D areas. Some other costs could be applied to restrict transcontinental unsupported travel (food, gold?).
   
  
• Once a client discovers a detailed area, it should be added to the map view for easy navigation and revisit.
  

The spark for these musing was me revisiting Middle Earth RPG modules by ICE, which start with the huge continent of Middle Earth, and then go into incredible detail in certain areas. The maps are really superb works of art. If we tried to do this in the current EL framework, then we either detail a tiny corner of it, or reduce the scale and lose the grandure/epic proportions of the place. Most of these modules are available as PDF on the web now -- though I don't know their copyright status.

 

 

Anyway, time to get back to some serious harvesting...

[Lyanna]

I see. It seems very similar to the Fallout map system, where there are certain "interesting" areas (read: towns, places, ruins, etc.), separated by a whole lot of terrain, and travel is shown on the map-screen, rather than actual 3D movement.

 

Generally, I like the idea, for the reasons you've stated above. (Especially about the ability to add "hidden" areas waiting to be discovered, as well as the fact that you're right - the continent is way too small).

 

What I'm afraid of is that it might be too ambitious for a small project like this game... It would be amazing to have it, of course - but whether it would be practical to do so is the question.

 

*sigh* It would be nice though...

 

-Lyn-

 

P.S. By the way, this is the best Suggestion format I've seen in a long while. Very nicely organised and stated, trollson.

[trollson]

Thankyou Lynanna,

 

I don't see why this should be too ambitious. Leaving aside coding issues for the moment (comments on the current architecture anyone?), the initial "world" resources would just require a large-scale continent map and associated meta-data. This would serve as geographic framework into which areas could be detailed over time. Initially play could be limited to a manageable corner of the continent (though players would be free to wander aimlessly around the wilds).

 

It does require that the client be able to download/update 3D mapped -- I am not sure whether this is currently the case, but I imagine it should.

[crusadingknight]

This would allow the clients to determine the best path between two points (as I understand it, the server currently has to perform path finding on the 3D maps?).

 

That's only for 12 spaces. To cross a whole map, the client takes the load.

 

 

 

download/update 3D mapped

Download objects you mean? Or whole maps? Either way, that takes way too much bandwidth, and the client would still have to load them in an efficient manner, as holding them all in memory would be impossible... That's the main reason why we have multiple small maps.

[Grum]

This would allow the clients to determine the best path between two points

This would allow cheating.

All pathfinding is done by the server, so that noone can define his own private teleports on the map, walk through mountain, etc.

(as I understand it, the server currently has to perform path finding on the 3D maps?).

Well, a map with obstacles is by definition 3D. If there are no obstacles, pathfinding is real easy.

That's only for 12 spaces. To cross a whole map, the client takes the load.

More or less. The client takes coarse steps (12 spaces? possibly, i don't know), and each of these still has to be ok'd by the server.

[crusadingknight]

More or less. The client takes coarse steps (12 spaces? possibly, i don't know), and each of these still has to be ok'd by the server.

 

That's the step size the pathfinder uses.

Edited April 7, 2005 by crusadingknight

[Roja]

It certainly is an interesting idea, and I do know games that work like that.

Although...I don't see much of a point in it, in this game. Sure the maps are small(not that we can't support bigger maps, but for the sole fact that it takes a long time to create a map in the quality detail necessary to look good in the game).

 

In response to some of the points you made:

1. Random monster attacks in the non-3d map areas: well, we also have monsters randomly coming up and attacking you too. The difference is that if you're paying attention you see the attack coming. Of course you do have to be in the right maps. As I said before, I have played games like you described, and I honestly can say that I HATED the random monster attacks that I could never possibly see coming. I much prefer to see my enemy, and to run away from it if possible

This game is also not meant strictly for fightrs, we don't want to force people into fighting if they dont want to. So with the way we have it now, they can avoid it, and have a better chance at getting away. Not that I don't think that the other way would make for an interesting game of it's own...but it's just not Eternal Lands.

 

2. More maps can also be added here at anytime. We're working on a 2nd continent now, which is also pretty small, however after that we can make even more! Maybe even a huge continent eventually...we still, can always add more maps

 

Anyway I thankyou for posting your ideas

[trollson]

crusadingknight:

Download objects you mean? Or whole maps? Either way, that takes way too much bandwidth, and the client would still have to load them in an efficient manner, as holding them all in memory would be impossible...

 

I would envisage that a 3D area is only downloaded when first encountered (or updated if change was permitted). The area represents static information, so can be cached by the client. There shouldn't be any reason to try to hold all maps in memory (is that what is done in the current client implementation?).

 

I must admit that I haven't checked the size of a 3D map. Surely a lot of data is replicated -- stock objects being reused? If bandwidth from the game server is at a premium, then just return the URL of some other repository.

 

 

Grum:

This would allow the clients to determine the best path between two points

This would allow cheating.

All pathfinding is done by the server, so that noone can define his own private teleports on the map, walk through mountain, etc.

No, why should this be the case? Since, as you point out, there are no dynamic obsticles, path finding is a case determining the minimum-cost route between two points. The server would still have to perform the movement along this route.

 

Teleportation would not be possible. The worse cases would be that the route is suboptimal (crossing mountains rather than using a pass), or invalid (walking into the sea without water wings). The result would be slow (or costly) movement, or premature termination of the journey, with wet trousers.

 

Roja:

I honestly can say that I HATED the random monster attacks ...

This game is also not meant strictly for fightrs,...

I only suggested this as a means to make life a little more interesting, or to discourage walking through the wilderness (or encourage, depending on the player's intentions!). The nature of the encounter (distance) would vary depending on terrain and perception, and need not involve an involuntary fight.

 

For that matter, I have had encounters in EL which where pretty much involuntary (and brief) random encounters on entering a new map!

 

Roja:

More maps can also be added here at anytime...

Maybe even a huge continent eventually...

Sure, but as I understand it you either have to do an entire continent of joined 3D maps, or have areas which players cannot enter until they are detailed.

 

 

I guess you could connect maps via 'wagons/caravans' to cover long range/instant land travel as per ships for sea travel.

[Roja]

Yeah we just easily connect them by placing temporary teleportals until the maps that would join those maps are made.

[crusadingknight]

I must admit that I haven't checked the size of a 3D map. Surely a lot of data is replicated -- stock objects being reused? If bandwidth from the game server is at a premium, then just return the URL of some other repository.

 

We hold the map we're on in memory, with each object's stats. (Though we only render the visual sectors). And the client doesn't have unlimited bandwidth, either...

 

 

EDIT: Just a demo, here's current sizes of maps:

ls -l maps/*.elm

-rw-r--r-- 1 user Nessuno 113356 Dec 1 17:20 cave1.elm

-rw-r--r-- 1 user Nessuno 18292 Dec 1 17:20 cave2.elm

-rw-r--r-- 1 user Nessuno 40036 Jun 5 2004 cave3.elm

-rw-r--r-- 1 user Nessuno 326668 Jan 6 14:31 guildmap_co.elm

-rw-r--r-- 1 user Nessuno 1305164 Jan 24 01:15 map11.elm

-rw-r--r-- 1 user Nessuno 71564 Jan 23 16:28 map11_crypt.elm

-rw-r--r-- 1 user Nessuno 406484 Jan 4 20:07 map11_insides.elm

-rw-r--r-- 1 user Nessuno 2163892 Jan 25 01:11 map11_insmsch.elm

-rw-r--r-- 1 user Nessuno 282228 Jan 6 15:49 map12.elm

-rw-r--r-- 1 user Nessuno 319668 Jan 4 22:41 map12_cave.elm

-rw-r--r-- 1 user Nessuno 271772 Oct 17 13:04 map13.elm

-rw-r--r-- 1 user Nessuno 371748 Oct 17 13:04 map13_castle.elm

-rw-r--r-- 1 user Nessuno 32740 Feb 15 2004 map13_insides.elm

-rw-r--r-- 1 user Nessuno 217764 Jan 15 2004 map14f.elm

-rw-r--r-- 1 user Nessuno 200284 Oct 17 13:04 map15_cave.elm

-rw-r--r-- 1 user Nessuno 531580 Oct 12 2003 map15f.elm

-rw-r--r-- 1 user Nessuno 1792188 Mar 20 2004 map2.elm

-rw-r--r-- 1 user Nessuno 70468 Apr 25 2004 map2_cave.elm

-rw-r--r-- 1 user Nessuno 366676 Jan 15 2004 map2_insides.elm

-rw-r--r-- 1 user Nessuno 215572 Jan 21 21:10 map2_insidescastle.elm

-rw-r--r-- 1 user Nessuno 502324 Jan 4 23:45 map3.elm

-rw-r--r-- 1 user Nessuno 88348 Mar 19 2004 map3_insides.elm

-rw-r--r-- 1 user Nessuno 326108 Aug 23 2003 map4f.elm

-rw-r--r-- 1 user Nessuno 258868 Jan 15 16:13 map5nf.elm

-rw-r--r-- 1 user Nessuno 128324 Jan 15 2004 map5nf_insides.elm

-rw-r--r-- 1 user Nessuno 586460 Jan 6 16:36 map6nf.elm

-rw-r--r-- 1 user Nessuno 157604 Jan 4 19:44 map6nf_cave.elm

-rw-r--r-- 1 user Nessuno 329036 Apr 13 2004 map6nf_insides.elm

-rw-r--r-- 1 user Nessuno 1272180 Mar 10 2004 map7.elm

-rw-r--r-- 1 user Nessuno 163308 Jan 4 19:46 map7_cave.elm

-rw-r--r-- 1 user Nessuno 369364 Jul 21 2004 map7_insides.elm

-rw-r--r-- 1 user Nessuno 237836 Apr 29 2004 map8.elm

-rw-r--r-- 1 user Nessuno 324556 Oct 17 13:04 map8_catacombs.elm

-rw-r--r-- 1 user Nessuno 19180 Feb 14 2004 map8_insides.elm

-rw-r--r-- 1 user Nessuno 595580 Feb 14 2004 map9f.elm

-rw-r--r-- 1 user Nessuno 76900 Dec 14 2003 map9f_insides.elm

-rw-r--r-- 1 user Nessuno 29924 Nov 30 2003 maparena1.elm

-rw-r--r-- 1 user Nessuno 61932 Feb 2 2004 mapnewbie.elm

-rw-r--r-- 1 user Nessuno 18132 Nov 30 2003 mapnewbie_insides.elm

-rw-r--r-- 1 user Nessuno 41980 Jan 23 16:27 mapportalroom.elm

-rw-r--r-- 1 user Nessuno 203788 Oct 12 2003 mapunderworld1.elm

-rw-r--r-- 1 user Nessuno 75108 Sep 1 2003 mine1.elm

-rw-r--r-- 1 user Nessuno 261876 Jan 3 15:49 misc1.elm

-rw-r--r-- 1 user Nessuno 106452 Mar 28 2003 neo.elm

-rw-r--r-- 1 user Nessuno 361012 Jan 7 20:57 startmap.elm

-rw-r--r-- 1 user Nessuno 26356 Jan 23 16:25 startmap_insides.elm

Edited April 7, 2005 by crusadingknight

[trollson]

crusadingknight:

EDIT: Just a demo, here's current sizes of maps:...

 

Back home now, so I have had a look at the elm files. As shown in your listing, the largest one is some 2.1M (map11_insmsch.elm). However, these files are highly compressable -- bzip2 reduces them to an average to 7.5% if their original size, the largest one to 157K, which is not an infeasible download -- in the scheme under discussion these would only be down loaded on first encounter (say, 5 minutes on a 56K modem).

 

Hmmm, this line of thought will end in a directory replication segment in the client...

[crusadingknight]

However, these files are highly compressable -- bzip2 reduces them to an average to 7.5% if their original size, the largest one to 157K

Not a bad idea. In fact, LZMA is, what, 110% as effective as bz2? So, with that, we could download and update maps without an entire client update.

 

If some way could be made of interposing map files unto a very large, and very sparse file (to keep monsters to their relative maps, etc.), that would be great. (Ie, when coords are within x && x+l && y && y +l, we're told to load z map, and dump it when we leave that specified area....

 

But I'm not the one who'd have to do all that work, and I have no idea even how feasible it would be.

[trollson]

crusadingknight:

If some way could be made of interposing map files unto a very large, and very sparse file (to keep monsters to their relative maps, etc.), that would be great. (Ie, when coords are within x && x+l && y && y +l, we're told to load z map, and dump it when we leave that specified area....

 

QED

 

Well, sparse files exist on both Windows 2000/XP (NTFS 5) and Linux (not sure which disk formats). But I don't think that is what we want here, since sparce file support cannot be guarenteed on all platforms.

 

There are plenty of ways to register areas in a larger space -- either by rectangular areas in some quad tree (?) hierarchy, or even just a RLE array of integer keys to mark areas covered by respective detailed maps (each of which would add a maximum of 4 x MAP_Y_SIZE integers to the total size).

 

Presumably monsters wouldn't be able to leave their respective detailed/3D maps for the same reasons that they cannot leave them at present. Just allow each boundary square of the 3D map to serve as a portal.

 

Then add a condition that if there is no underlying 3D map for a players 'world' position, then the 3D view is not available. A few improvements to the EL client map view, possibly more map scales, and the client route planner (calculated by the client, but vetting and walked by the server)...

 

There, easy peasy.

 

 

 

PS: Notes on moving to resource syncing for Unix/Linux:

• Resource directories would have to move to under '/var/', since may not have the right to write to '/usr/...'.
  
• Could implement the sync as a daemon (service on Windows). Allows background synchronisation, and satisfy multiple concurrent users. Could even use bittorrent to load spread.
  
• Some sort of signing (PGP) of resources to ensure that they are 'official' would be needed (ie., originate unmodified from EL HQ).
  
• Dependancy tracking -- maps may require additional new objects to be added to the local resource cache.
  

Edited April 8, 2005 by trollson

[crusadingknight]

Then add a condition that if there is no underlying 3D map for a players 'world' position, then the 3D view is not available. A few improvements to the EL client map view, possibly more map scales, and the client route planner (calculated by the client, but vetting and walked by the server)...

Impose on a sparse map. Taking off 3D view is a bad idea in any game.

 

As well, I think sync is a bit advanced for what we need - the http transfer already implemented in the client would do the job. And bittorrent.. well, in my experience, a bad idea on the Dial-up front, even though output is only 1/4th of network traffic.

[trollson]

crusadingknight:

Impose on a sparse map. Taking off 3D view is a bad idea in any game.

 

Then what would the 3D view show when there is no underlying 3D data?

 

My assumption here is that there would be a complete 2D map, even if just at the continental scale. The sparce-ness being the presense of detailed 3D areas.

[crusadingknight]

Then what would the 3D view show when there is no underlying 3D data?

sparse >adjective: thinly dispersed.

 

I mean, this map would have SOME data, just not much. A tree here and there, maybe some shrubs. This is easy enough to do, so nobody would even need to do it manually. (srand() and rand(), or maybe use the entropy pool to place tree with random x, y positions and ratations, maybe variable height too), to generate a map (once, I mean, not on every client computer ), and when we're not on another map, just default to our position on the large map.

Edited April 8, 2005 by crusadingknight

[trollson]

Right I see what you mean. I was thinking in terms of data structures as usual

 

By entropy pool, do you mean the method of using determinable seeds to generate reproducable pseudo-random patterns? (ie, the placement of trees in the woods is random, but returning to the same woods, they are in the same positions).

 

This has always been a favorite of mine, since Elite days

 

I like the suggestion -- so long as the terrain could be generated on the fly.

 

Any generator would have to be able to cope with linear feaures (roads, rivers), as well as terrain boundaries.

[crusadingknight]

I like the suggestion -- so long as the terrain could be generated on the fly.

That'd be fun, but see what I said - one-time generation, then distribution. This way there'd be no way to cheat the server by walking through objects. (And, pseudo-random generation on heightmapped terrain would be just weird...)

[trollson]

crusadingknight:

...one-time generation, then distribution. This way there'd be no way to cheat the server by walking through objects.

 

I think that having to pre-generating even sparse elm files would produce a lot of data for a large continent.

 

I didn't mean to suggest random generation on the fly, but generation according to a predetermined algorithm, using random number sequences with determined seeds. Both the server and client would use the same method (and I assume that it is the server which determined whether the avatar has walked into something?).

 

For example, given coarsely determined geography, an algorithm could be written to generate repeatable but simple terrain for the 3D area at a sample point given (where one sample point represents a reasonably sized 3D area):

• The coordinates of the sample point, used to seed the pseudo-random number generator(s).
  
• The geography defined at the point -- terrain type, altitude, secondary features (road, river).
  
• The geography of the surrounding points, to handle transitions.
  

Think of this as an ultimate form of compression, rather than random generation!

[freeone3000]

Wouldn't they have to be at the same location? Same randomization method doesn't mean the same result. Unless you have same location, some weird things would happen.. unless I'm missing something...

Edited April 8, 2005 by freeone3000

[trollson]

freeone300:

Wouldn't they have to be at the same location? Same randomization method doesn't mean the same result. Unless you have same location, some weird things would happen.. unless I'm missing something...

 

OK, a simple example:

 

One 'coarse' grid point on the continent may represent 100x100 area in 3D. Assume that we just need to put trees 'randomly' into this 3D grid, with say 10% chance that a square will have a tree.

 

Random number generators really only produce pseudo-random sequences of numbers, according to the particular algorithm inside them (see: Knuth volume 2). They are typically started by setting some seed value. Now, re-use the same seed, and you get the same series. Use any other seed (even +/-1) and the series should be completely different.

 

So, take the position of the large scale grid (say, a latitude-longitude pair) and use this to get a unique seed for the random number generator used to roll for the trees. The same 3D map can be regenerated at any time given the same seed, and the same 'forestation' algorithm.

 

So, in a large forest, each 100x100 3D area would have a different scattering of trees, which would be the same each time it was re-visited. But this map does not have to be stored between visits.

 

This method was used to great effect in games such as Elite (c.1982?), and Elite Frontier (c.1990?) -- the latter included a map of the entire galaxy, at least at a scale of several million star systems, but fitted on a couple of floppies!

 

Of course, you need a well designed algorithm to create decent random terrain; but this has been done many times before..