• Advertisement

Archived

This topic is now archived and is closed to further replies.

Large Map Management

This topic is 5975 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am designing a Tile based Map engine, and I want to be capable of have landscapes that are incredibly large. I don''t want one huge map though. I want to break it up into smaller maps to use less memory. What is the best way to setup this kind of engine? I have been thinking of creating smaller maps of a uniform size, like 100 x 100, and using a spreadsheet to store where the maps go. Would this work? I was also looking into Quad trees, to help with the drawing of the maps. Any thoughts on the subject would be appreciated. Thanks in advance!

Share this post


Link to post
Share on other sites
Advertisement
I''m doing the same thing. I dont think these days you are going to
have any trouble creating large maps using tiles. Tiles were origanaly
dreamed up to alow for large areas back in the day of little
resources. Even old machines now have more than enough
juice to run a tile engine without too much trouble. The main
issue in memory will most likely be the amount you use for animation
and the number of individual tiles you alow. The size of the map
itself probably won''t concern you much. You shouldn''t have to
make each section a uniform size. Only do that if your game
calls for it. My first engine alowed for what ever size I wanted.
I had an undeclared array that held the tile values for the
active portion of the map. I belive I may have had to do some
type casting trick to look them up in the 2d array with the current
dementions I was using at the time but It worked great. The array
was actualy an array of pointers to tile sructures with information about the tile and othes that might be layered on top
of it. There are ways to make the levels any size YOU need. You
dont have to be forced into any set box size. Anyway I don''t
realy know as much as I pretend to. Most everything I know
I read out of a couple of articles written by people much smarter
than I am. I guess you my have already checked the ones here out.
Maby this will help a bit and hopefuly all the other smart guys
here will have some good tips.

Share this post


Link to post
Share on other sites
Maybe I should explain more. I have the basic Map Engine done. But what I want is huge areas, like maybe maps that are 5000 x 5000 big, maybe even larger. I think having a single map this big would hit the FPS. So I was thinking that if I have maybe 100 x 100 maps, I could put them like so.

Map1--Map2--Map3
Map4--Map5--Map6
Map7--Map8--Map9

If each of these are 100 x 100, that would create a 300 x 300 map for me, then I could only draw the sub-map that I am in. Or 2 of them if I am traversing maps. For example, if I was in Map 9, there would be no need to draw maps 1, 2, 3, 4, and 7. I would only have the draw the map that I am in, and the ones adjacent to it, for when I move into them.

I just really was wondering what would be the best method to organize this.

Edited by - Lunatic Raven on September 23, 2001 5:40:03 PM

Share this post


Link to post
Share on other sites
I''m just fealing chatty today. I though I would mention that
By recomendation I used liked list to define layers to concerve memory.
I defined my map as an array of structures with the tile
data something like this.

tile_stuct
{
tile_struct next*;
char type;
}

I used unsined char to give me 256 tile types at one time
but an int
would give you as may as you wanted. Or you could just
point directly at the image data in memory if you wanted.

Someone correct me if I''m wrong on amounts but
thats one byte for the type and 4 bytes for the pointer.
and maby another byte if you wanted to add an event value
to let you know if its solid gound VS pit or somthing.
A total of 8 or so bytes per tile. In a world where we messure
bytes by the million don''t worry about running out of space on
area alone. My old version ran under dos without and extender and
I had maps that were of reasonable size then.

Share this post


Link to post
Share on other sites
Sorry I typed the last thing durring your second post. You shouldn't
need to worry about your fps getting hit. Size wont matter since
you will only be drawing a set amout each time. One screen. Everything else is simply ingnored. If your game requres AI updates
to char off screen that might hurt abit but you wont even need to
check if each tile is on screen. You will simply accsess your
tile array at the current XY position and blit them ignoring the
rest. That make any since? I'm going kinda fast.

You will no doubt want to break your over all areas down for
logic sake. Say as the "Alien ship" and the "Home World" or
what ever. You might try having maps and submaps. Submaps
being each displayable unit of a map. The map just being the
over all collection of smaller maps that are joined together
as you see fit.

Edited by - Goober King on September 23, 2001 5:56:52 PM

Share this post


Link to post
Share on other sites
quote:
Original post by Goober King
Someone correct me if I''m wrong on amounts but
thats one byte for the type and 4 bytes for the pointer.

That''s true, although some compilers may add a few more bytes to pad the struct.



~~~~~~~~~~
Martee

Share this post


Link to post
Share on other sites
Well if what you are looking for is to only draw what you will see on the screen and not everything else just take your world coordinates, figgure out which tile the coordinates corespond to in your map array or however you stored your map. Show however many tiles you need to fill the screen. something liek this:

//the amount of tiles it will take to fill the screen
screen_tile_fill_x=world_x+20;
screen_tile_fill_y=world_y+20;

world_x=5;
world_y=5;

for(int x=world_x; x for(int y=world_y; y

//Blt all of your tiles according to x and y
//if the tiles don''t fill the whole screen than increase the till fill
// all of this is assumeing that you have a function that already blts or copies the tiles that you want and also that you have two global variables keeping track of the world coord which you should have for scrolling


}

}


anyway that is just a stripped down version. you would have to add all of your tile checking a copying code. but with this it will allow you to store the whole 5000x5000 map in say a array and then only copy the tiles that the user will see and not worry about any of the others so instead of bltting 5000x5000 tiles you could blt 50X50 at a time this would increase frame rate and you would not have to divide your large map up anyway this is just the way i would do it.

you can lead a horse through water, but you CAN make him drink.(he may or may not drown with this process)

Share this post


Link to post
Share on other sites
If you do a search on old messages from this forum, you will find a thread where we discussed just this topic... in particular, we theorized how Ultima Online accomplished their large maps. Here is my advice, in order of importance:

1) Don''t do it. If you are making a really LARGE map just for the sake of making a large map, you might need to rethink your motives. Is it really necessary for your game? What you are describing is technically quite feasible... the hard part then becomes actually filling your world with interesting geography to explore. If you can''t do that, then you shouldn''t make the map very large... if, on the other hand, you''re just doing it for a technical demo... then read on.

2) Meta-tiles. Tiles made up of other tiles. Read the old thread.

3) Dynamically load individual map sections off disk as the map scrolls. Trust me, your hard drive is plenty fast for this. Read the old thread.

4) Compress your map data. If the "Plains of Magrathea" are composed of 90% grass tiles, 5% scrub tiles, and 5% other stuff, that data will compress down very tightly. A simple RLE scheme could cut your memory usage dramatically.

Share this post


Link to post
Share on other sites
I agree with Pyabo about the geography issue, but if you still want/need obscenely large maps, here is my suggestion.

When I started I wanted to have the capabilities for two things, a world of unlimited size and I did not want to have "zones" (to use a EQ term) I wanted it to be fluid. So this is what I came up with after reading a newsgroup thread a long time ago about Ultima 5.

1) Break your UberMap into sizeable chunks, lets say 256x256... play with this number for best results. The tradeoff here is how often you go to the disk vs the ammount of memory you will need to run your program.
2) Load the map the PC is on, and all adjacent maps like so. Assume player is on map (not tile) 8,4

+-----+-----+-----+
| 7,3 | 7,4 | 7,5 |
+-----+-----+-----+
| 8,3 |(8,4)| 8,5 |
+-----+-----+-----+
| 9,3 | 9,4 | 9,5 |
+-----+-----+-----+


Now, the player roams about Map(8,4) and moves over to 8,3. If the player moves 10% of the way into 8,3, it is safe to assume that they are there to stay.

3) Unload the farthest maps from the player (in this case (7,5), (8,5), and (9,5))

4) Load the enough maps to maintain the 3x3 map (in this case (7,2), (8,2), and (9,2)). Like so:

Player is now at (8,3)
+-----+ +.....+
| | = Loaded map | | = Freed Map
+-----+ +.....+

+*****+
| | = Map about to be loaded
+*****+

+*****+-----+-----+.....+
| 7,2 | 7,3 | 7,4 | 7,5 |
+*****+-----+-----+.....+
| 8,2 |(8,3)| 8,4 | 8,5 |
+*****+-----+-----+.....+
| 9,2 | 9,3 | 9,4 | 9,5 |
+*****+-----+-----+.....+


See? This gives your program more than enough time to load (probably with a different thread) the new maps without having to have to have a brief pause between maps.

Since you don't have a 5000x5000 or even a 5,000,000x5,000,000 map in memory, you are free to use the memory saved to lower your requirements (no reason that a simple tile engine require 128MB of RAM) or put it to better use for AI, graphics, etc.

The beauty of this method is that you can thoeretically have an unlimitedly sized map.... and infinite map

Well, I hope this helps.

-OberonZ


Edited by - OberonZ on September 24, 2001 11:37:33 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Why not just use the MapViewOfFile function and let your OS page the data in and out as needed? Window''s paging algorithms work pretty well.

Just make sure you only draw the stuff that''s visible!

Share this post


Link to post
Share on other sites
An interesting idea... with some very drastic disadvantages. For one, you are suddenly limiting your game to the Windows platform. Two, you are also limited by Microsoft''s implementation of that function... what if there are bugs? What if it doesn''t behave the same on all computers?

OberonZ''s method is easily implemented by anyone with even a small amount of programming skill... what is the disadvantage over MapViewOfFile aside from a couple days of work?

Share this post


Link to post
Share on other sites
"Advanced Windows Programming" (by an author whose name eludes me since I don''t have the book at hand) other than being an excellent book I highly recommend for the serious Windows programmer, contains a lengthy explenation of Mapped Files. Unfortunately, I believe that he stated in the book that the Win9x implementation was shoddy at best and henceforth talked about Win2K and NT. Correct me if I''m wrong since I have not read that section in a long time.

Otherwise mapped files kick ass since it''s like having loaded the entire file in memory... no matter how large.

I believe Linux has mapped files as well, but I don''t know anything about them.

---
PAGE FAULT: Please insert "Swap File, Disk 2"
and press any key to continue.

Share this post


Link to post
Share on other sites
I had this problem at one time. The map was 10,000x10,000 tiles, each tile contained many floats and ints. This was for a school project and the budget for the computer was as much as we wanted, so our solution was to simply buy more ram, as the 10,000x10,000 array took up about 550megs of ram, so we loaded the computer with 768megs of ram and it ran well.

This program wouldnt work on another computer with less ram, as it would start using virtual memory and grind to a halt. So if your map array is to large to fit into ram, you will have to break it down. One thing I did notice from the project, is that speed was NOT affect by the map size as long as it ran with in memory. The program ran at the exact same speed with a map size of 256x256 or 10,000x10,000. So if you can fit your map array completely into memory, then you dont need to break it down into smaller chuncks.

Possibility

Share this post


Link to post
Share on other sites
quote:
Original post by Possibility
I had this problem at one time. The map was 10,000x10,000 tiles, each tile contained many floats and ints. This was for a school project and the budget for the computer was as much as we wanted, so our solution was to simply buy more ram, as the 10,000x10,000 array took up about 550megs of ram, so we loaded the computer with 768megs of ram and it ran well.

This program wouldnt work on another computer with less ram, as it would start using virtual memory and grind to a halt. So if your map array is to large to fit into ram, you will have to break it down. One thing I did notice from the project, is that speed was NOT affect by the map size as long as it ran with in memory. The program ran at the exact same speed with a map size of 256x256 or 10,000x10,000. So if you can fit your map array completely into memory, then you dont need to break it down into smaller chuncks.

Possibility


10,000x10,000!!? Daaaamn. Thats just nuts! However I guess
you did prove that size donen''t need to affect speed.
Just because I''m curious what ever did you need that
much space for?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
550 Megs on 10000x10000 holy crap how big were your tiles?

that''s like 5.76bytes per tile.

anyway...

The current tile engine I''m using uses 32x32 tiles (1024 pixel data) plus another 12 (Height Map, Index into tile lib, Flag mask) bytes worth of data used by the engine. So the engine scales quite well, because the tiles are generally duplicated but the data about the tile isn''t. It has a sort of tile library, and then just a load of data like:

MapData = new MapDataStruct [MapWidth*MapHeight];

The mapdata have indexes into the tile library. This doesn''t really allow for tiles that have multiple layers, however the editor that I''ve written allows you to import layers onto a tile. Memory isn''t a big issues with the tile system I''ve written due to the fact that most games nowadays chew about 100MB of memory.

This engine however generally (from statistical data I''ve looked at about the maps at the moment) uses very little.

Memory Usage = MapHeaderSize + MapWidth*MapHeight*32 + TileLibrary / 16
= 64 + MapWidth*MapHeight*12 + MapWidth*MapHeight*32*32 / 16
= 64 + MapWidth*MapHeight*12 + MapWidth*MapHeight*64

Thus for a HUGE map: (800x800 tiles 25600x25600 pixels)
= 64 + 800*800*12 + 800*800*64
= 64 + 7680000 + 40960000
= 48640064 Bytes
= 47500 KBytes
= 46.38 MBytes

For a average sized map: (250x250 tiles 8000x8000 pixels)
= 64 + 250*250*12 + 250*250*64
= 64 + 750000 + 4000000
= 4750064 Bytes
= 4638.73 KBytes
= 4.53 MBytes

Combine this with a nice resource packer (compiles multiple files into a single file with compression/encryption etc) and I can get quite a few map files onto a single cd. I''m sure that 4.53 MegaBytes of someone''s memory isn''t asking a great deal.

For your 10000x10000 Map size though:
= 64 + 10000*10000*12 + 10000*10000*64
= 7600000064 Bytes
= 7421875 KBytes
= 7247.92 MBytes

Which is a way too big to fit into memory on my pc (even if I was using a large chunk of virtual memory too lol).

I''m curious how you got 10000x10000 in 550Meg''s tho... compression + small tiles?

-Alan

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Oh yeah... my tiling system uses a palette (although the header can say whether or not to)

-Alan

Share this post


Link to post
Share on other sites
The map was for a robotic vehicle. The vehicle needed to generate a map of its surroundings using a camera and laser range finder. The map needed to cover an area of 200 yards x 200 yards with each tile being 3 inches by 3 inches. And each tile needed to store data on what was at that location, and also probability details of that tile really being what the robot thinks it is.

For the actual map, it was a while ago, the tiles hold 24bytes of data, the actual map size we used was 5000x5000, I looked up the old source code and I remeber now that we had to scale the map size down. 24bytes x 5000 x 5000 = 600 megs.

Possibility

Edited by - Possibility on September 26, 2001 4:25:41 PM

Share this post


Link to post
Share on other sites
(Forgive me if I violate any conventions here, this is my very first post)

Lunatic,

There are a number of issues raised when you only keep a portion of the total world map in memory.

First is the "granularity" or how many tiles are blocked together into a single unit that is swapped in and out. The smallest of course would be to load and discard individual tiles. In practice though, you need to block in and out larger regions.

This then leads to issues with how you handle the wrapping and the Data Structures used, and how you access them. Others here have suggested you set up a 3 by 3 (or larger) array of tile "chunks" in memory, and ''scroll'' them when the character you are tracking crosses a chunk boundary.

Before going on, I have to assume that the type of application is one where you only have a single character or unit that you control or follow, al la a RPG-type game. In an RTS-type game you would have multiple units that could go in opposite directions thus breaking the limited map area in memory because someone would need data not currently loaded.

Also, with an RGP type of game, you have the problems with updating or moving a computer AI unit when the map tile it sits on has been swapped out -> It''s hard to do pathfinding if you have reload the whole map each time.

Then you got the issue of accessing portions of the world map: When the whole thing is loaded in memory you can do a direct array access such as MapTile[Character_Y_Tile][Character_X_Tile]. It most games, you wind up doing this a lot. When the map is only partially there, every coordinate and access has to fixed up to map from the world coordinate into the loaded map space. You loose the direct 2d calculations, and you probably have to manage the address pointers for each individual map chunk as the map area may be loaded into a different memory block as the game goes on.

Then we get to the process of streaming in the data itself. You want it to be fast and transparent... which is not that easy. It might be advisable to have another thread running that can load up the chunks slightly in advance to negate the time hit from the disk. Then you may have the need to fixup data once loaded - that takes time, and if done in a thread, has to be done in a way that can''t cause problems (one thread messing with another threads data can cause you great grief in debugging)

And this so far is assuming the data is static. What if some portions of the map data can be altered.. Then you need to have a mechanism to write the modified data out instead of just discarding (reusing the memory).

Along those lines -> what if any of the map tiles have a list or other variable size data? do you then need to pad the file for each varible size item to its maximum size so you can have a consistant world map to disk file location mapping?

An aside about memory mapped files -> there is a nasty bug with them in the Win9x kernel that causes them to be copied to the swap file no matter what, even if they are read only... which can really bog a system down.

They you have to ask: what about teleporting or scrolling the view across map away from the unit you are centered on? A streaming map severely limits those options.

Finally, what about map/world creation and editing? Your editor needs to work with the map on disk instead of all in memory. Will it create problems when you need to link or relate to items that are so far apart they both wont be loaded at the same time?

So as you can see, there are a number of issues to tackle.. yet it is still very doable - you just have to understand the limitations it places on your game and live within them.

-Matt P
Developer: AoE/AoK/???

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Sounds like you''ve got alot of expereince with this The Optimizer 8^)

There is another technique as well. The use of aggressive compression to create a smaller footprint for the chunks so you can load them quicker, and store more in memory. I would think such a strategy in conjunction to what Optimizer said, would yeild the best results. Most map data is highly compressible, such as large runs of similar tiles, runs of zeros in the data set, etc.. Each chunk could be individially compressed.

Well it''s an intresting problem. I wonder how MMORPGs manage their extremly large worlds. Do they keep all the data in memory? Most likely they use their own caching and resource request schemes. Such a system, you proablly have to build an asychnrous event handler much like the windows events, I suppose. As realtime response isn''t as important as effecient resource management and network stability in those cases.

Good Luck

-ddn

Share this post


Link to post
Share on other sites
Here''s the way I would do this. My method assumes that you''ve already got what you''re currently using in memory, and also that most of the time you only ever access tiles that are next to each other. This method is good is the case of a single character (like an RPG) or if you''ve got multiple characters running around (for example, an ORPG where players can go off in their own directions, or an RTS).

Basically, it works like virtual memory. You have a bunch of frames, each one of which holds a chunk - you can have as many of these as you like, perhaps let it be configured by the user so if they have more memory, they''ll get better performance with more chunks loaded at once.

Now, instead of loading the chunks into memory on demand, you have a separate thread which looks at which chunks have been recently accessed (for example, in the last frame, or over the last second, or maybe just since the last time it checked). For every chunk that was accessed, it checks the neighboring chunks, and if any of those are not loaded, it ejects the oldest chunk (i.e. one that has not been accessed in a while) and loads the neighbors into memory.

This has the advantage that, as long as all your tile accesses are fairly contiguous, then all tiles will be in memory at all times. Also, if you have two (or more) units in separate parts of the map, then as long as you have enough frames, they''ll still have all their chunks updates automatically. Also, it''s quite fast. If you set up a TLB (Translation Lookaside Buffer - it can have as many entries as you have frames), like with normal virtual memory, then you shouldn''t notice too much of a difference. Finally, it''s completely transparent to your game. As long as all your map references are through "get" functions, you''ll have no problems.

The only problem I can see is that making dynamic maps will be a little more tricky. It shouldn''t be that hard, though - whenever you change the chunk in memory, you flag it as "dirty", and then the thread which manages the chunks will see that flag when it goes to eject the chunk, and instead of just discarding it, it writes it back to disk.


codeka.com - Just click it.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Sounds like you''ve got alot of expereince with this The Optimizer 8^)


You might say that. :-)

quote:
There is another technique as well. The use of aggressive compression to create a smaller footprint for the chunks so you can load them quicker, and store more in memory. I would think such a strategy in conjunction to what Optimizer said, would yeild the best results. Most map data is highly compressible, such as large runs of similar tiles, runs of zeros in the data set, etc.. Each chunk could be individially compressed.


This only issue with that is that the compressed size of the chunk can vary. When loading from disk, you then either need a pre-built chunk index ot you add padding to each chunk in the file. ... which reminds me, if you use memory mapped files, you are swapping in a 4K minimum granulariuty anyway, and on modern harddrives, you have the disk cluster granularity as well. Since it costs practically nothing performance wise, why not just go uncompressed? Also, you have the added overhead of having to uncompress the data to another block of RAM (where uncompressed data could be left in a read-only memory-mapped file)

Finally, the variable size of a compressed block gives other problems. Say you have a *huge* map file, made up of compressed chunks all packed together. Then you edit or the game modifys a chunk, making it more complex. You have to write that chunk back, which is now to big to fit in the portion of the file it originally occupied... time to rebuild the whole file and index :-) Unless of course you have padding after each chunk. But with all compression, your wost case scenario (very high data enthropy) is having to store it uncompressed anyway. :-)

Still, compressed map data has it uses - don''t get me wrong. You just have to know its pros and cons and how they fit into your game.

-Matt P

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
HeeHee i was thinking in terms of extremely large maps where hundreds of individual entites had to be tracked across a gigantic map (over ~50k x 50k tiles), such as be the case for say a massive isometric online RPG, or perhaps a massive online RTS . So trading off cpu for increase map coverage in memory would be worth it.

World modification would be difficult, though due to the constraints which you''ve mentioned.

I wonder if its even possible to create a massive online RTS where the map was 50k x 50k with 100+ players battling it out.

Well Good Luck!

-ddn

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Why would you think 50,000x50,000 tiles is needed for 100+ players? Ultima Online''s map is 6144x4096 tiles, and UO had (has?) over 3000 people on at the same time.

Share this post


Link to post
Share on other sites
Still, even with 6000x4000, you''d want some sort of tile-chunk cache since for every byte that your tiles require, you need an extra 22MB of memory. (that is, if each tile is 10 bytes, that''s 220MB of memory).

I still think my previous idea would suit a game with 100s of separate entities going their own way, since you''d always have only those tiles that will be needed in the immediate future in memory. I really don''t see how you''d get any better than that You''d just need to set your frame count to be a minimum of something like * 9 (since each player would require the 9 surrounding chunks to be in memory)


codeka.com - Just click it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I was envisiong an massive RTS, not RPG. In RTS, usually 2-4 players possess a much larger area for themselves, than a RPG where many players share a world. Each RTS player can posses several hundred units, so that drives the need for in memory tile storage even further.

Good Luck!

-ddn

Share this post


Link to post
Share on other sites

  • Advertisement