Jump to content

  • Log In with Google      Sign In   
  • Create Account


Handling a 2D procedural world


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 02 October 2012 - 11:57 AM

So I am still on my long journey to create a 2D tile based side scroller. Today I jumped into the part where I save my world to the harddisk instead of keeping it in the memory.
Currently what I do is, serialize the 2D Tile array that I've made. The size I test on is 10240 * 512. Now I know I can optimize the file size further, but currently this gives me a file size of roughly 305MB.(I am planning to have worlds much bigger than this one) My problem occurs when I try to deserialize the array. The game freezes, and rapidly swallows more and more memory, and after a while (5-10 mins) it will throw an out of memory exception. Is this due to the huge size of the file? Or are there other factors I should consider. My code for serializing and deserializing is here:

		public void SerializeWorld(string fileName)
		{
			using (Stream stream = File.Open(fileName, FileMode.Create))
			{
				BinaryFormatter bf = new BinaryFormatter();
				bf.Serialize(stream, world);
			}
		}
		public static void DeserializeWorld(string filename)
		{
			using (Stream stream = File.Open(filename, FileMode.Open))
			{
				BinaryFormatter bf = new BinaryFormatter();
				world = (Tile[,])bf.Deserialize(stream);
			}
		}

In the above code world is the array where I keep my tiles. I've tested this in two ways:
On both tests I create the world as I usually do, and then serialize it into a file right after the creation. The difference is when I load it. First I tried loading it while the game was running, to see if It would be able to load the world without having to leave the game session. Failing this I tried simply loading the world when I start the game, but with the same results- Game freezes for 5-10 mins, swallows memory and ends up with Out of memory exception.

Now the way I believe I should do this is divide the world into chunks, and only keep 9 chunks loaded at any one time. (Normally it would be 3, but I need to consider up and down as well). This would also require me to keep each chunk in its own file, giving me tons of smaller files. This is sort of okay with me as long as this does not cause any other issues? I would then load those 9 chunks into my in memory world array, and release the ones out of range. Currently I'm not quite sure how to do this effectively.
Maybe keeping it in small files, might fix the problem with deserialization?

So to sum it up:
- Am I right to assume that the 305MB file, is the cause of the freeze and out of memory exception when I deserialize?
- How should I correctly handle chunks?
- Will it be an issue to have multiple smaller files, where each file represents one chunk?
- Are there anything wrong with the way I de- and serialize right now, and should I consider other methods?

Thank you for reading. Posted Image

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


Sponsor:

#2 slicksk8te   Members   -  Reputation: 190

Like
1Likes
Like

Posted 02 October 2012 - 01:28 PM

I highly doubt that it fails due to the size of the file because it is only 305MB. How much memory does it peak at before it throws the out of memory error?

Chunks are always a good way to go.
You say your world size is 10240 * 512 which is about 5 million tiles. This does not need to be loaded or saved all at once and should be streamed.
All of these chunks can be in the same file(file seeking) or different files, whichever is better for your needs but does not seem to be the bottleneck here.

The issue may be because the objects are not correctly serialized. Check here under 'Making an Object Serializable'.

I am still trying to determine what data you are serializing because 305MB seems rather high for tile based, even for 5 million tiles. So, what exactly are you serializing?

#3 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 02 October 2012 - 01:54 PM

The following is the current state of my Tile class.
[Serializable]
	/// <summary>
	/// Stores the appearance and collision behavior of a tile.
	/// </summary>
	public class Tile
	{
		public TileType Type;
		public TileType BackgroundType;
		public TileOrientation Orientation;
		protected short _directLightLevel;
		protected short _ambientLightLevel;
		protected ushort _flickerTimer;
		protected bool _lightCalculated;
		protected byte _variant;
		/// <summary>
		/// Constructs a new tile.
		/// </summary>
		public Tile(TileType type, TileType backgroundType)
		{
			Type = type;
			BackgroundType = backgroundType;
			Orientation = TileOrientation.None;
			_variant = 0;
			_lightCalculated = false;
			if (type == TileType.None)
			{
				if (backgroundType == TileType.None)
					_ambientLightLevel = Light.AmbientLight;
				else
					_ambientLightLevel = 0;
				_directLightLevel = 0;
				_flickerTimer = 0;
			}
			else if (type == TileType.Torch)
			{
				_directLightLevel = 255;
				_ambientLightLevel = 0;
				_flickerTimer = 1;
			}
			else
			{
				_directLightLevel = 0;
				_ambientLightLevel = 0;
				_flickerTimer = 0;
			}
		}
		public virtual TileCollision Collision
		{
			get { return Terrain.TerrainGenerator.tileInfo[(int)Type].Collision; }
		}
		public virtual ToolType Tool
		{
			get { return Terrain.TerrainGenerator.tileInfo[(int)Type].Tool; }
		}
		public byte Variant
		{
			get { return _variant; }
			set { _variant = value; }
		}
		public bool LightCalculated
		{
			get { return _lightCalculated; }
			set { _lightCalculated = value; }
		}
		public short AmbientLightLevel
		{
			get { return _ambientLightLevel; }
			set { _ambientLightLevel = value; }
		}
		public short DirectLightLevel
		{
			get { return _directLightLevel; }
			set { _directLightLevel = value; }
		}
		public short LightLevel
		{
			get
			{
				if (_directLightLevel + _ambientLightLevel > 255)
					return 255;
				if (_directLightLevel + _ambientLightLevel < 0)
					return 0;
				return (short)(_directLightLevel + _ambientLightLevel);
			}
		}
		public ushort FlickerTimer
		{
			get { return _flickerTimer; }
			set { _flickerTimer = value; }
		}
	}

I recently removed a lot of data from the tile class, and added it to a static tile class, where it keeps information based on type etc. I have already planned to remove the enumerators in the tile and replace them with bytes, I figure there's a lot more room to spare there.
I do have a specific type of Tile that inherits from this one, I call Dynamic tile. That is for tiles that span over more than one tile, and that have changing states (besides orientation).
If you have any suggestions to optimize the class above, I am all ears Posted Image - And a question for that one - Would a public variable take less memory than accessing it through a property? As you might notice I've experimented with that, but no visible results.

I will check out the link you provided and see if there are things I've overlooked there.
Thanks for your reply Posted Image

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#4 serumas   Members   -  Reputation: 712

Like
0Likes
Like

Posted 02 October 2012 - 02:15 PM

woow, >10000 tiles in x. What is the size of tile. Is level not too long. For example if tile 64X64 pixels and screen is 1280px and lets take one screen last about 5 seconds (normal scrolling speed) to fly throu it will be 64*10240*5/1280/60=42 minutes. Not too log for level?

If tiles are in most cases the same or and they have rules of connect with each other , so it could be very procedural. Tiles could be generated proceduraly.

Edited by serumas, 02 October 2012 - 02:20 PM.


#5 Mizu   Members   -  Reputation: 968

Like
1Likes
Like

Posted 02 October 2012 - 04:04 PM

I do not have an answer to all your questions, but I can say this: From my experience, serialization is quite terrible when it comes to file size. This is due to the fact that most data you serialize will need some header information so that it can be properly deserialized later. If you are concerned about file size, I would suggest that you write your own Serialize and Deserialize method for the tile class and simply use a BinaryReader/Writer to read/write the data you care about.

Seems odd to run out of memory on 305Mb... Something's wrong with the De/Serialization, but it's hard to tell what that may be. I usually get those types of crashes when I expect to read an array but read something else instead... but the serializer should make sure that doesn't happen (right..? Posted Image )

Chunks is indeed the way to go for such a large world, and having them in many small files should not be a problem at all. Then you can begin to stream new chunks directly from the files as the player gets close to them.

As for that last question: Properties makes no significant difference to the size of the class, so use them as much as you want. Posted Image

#6 uglybdavis   Members   -  Reputation: 901

Like
1Likes
Like

Posted 02 October 2012 - 07:39 PM

Maybe it's when you are allocating your new object?
[source lang="csharp"]while (stuff_to_deserialize) myObject = new MyObjectType();[/source]

Easy way to test, comment anything out of your deserialization loop that actually creates a game object, and just let it run. If that is the problem, you need to have less objects. Maybe only allocate enough tiles for the screen plus a border, then swap them?

If that did not solve your problem, try this: http://www.downloadmoreram.com

#7 jefferytitan   Crossbones+   -  Reputation: 1958

Like
0Likes
Like

Posted 02 October 2012 - 09:04 PM

I've found (no hard numbers) that during deserialisation .NET often uses much more memory than the actual objects take up. I'd go with chunks or custom serialisation. I wonder whether memory allocation may be particularly inefficient if you're serialising a generic List or similar, e.g. hard for it to know up front what memory to allocate. May be more efficient if you serialise the number and type of items (so you can allocate an array or similar in one go during deserialisation) then individual objects.

#8 phil_t   Crossbones+   -  Reputation: 3234

Like
1Likes
Like

Posted 02 October 2012 - 10:30 PM

I have already planned to remove the enumerators in the tile and replace them with bytes


You can make enums be byte-sized by doing the following:

enum TileType : byte
{
Grass,
Dirt,
// etc....
}

As for serialization, you should be using custom serialization for something like this. I don't know the details of how .net serializes classes, but I'm sure it needs a bunch of metadata along with the actual data. It may be convenient, but it doesn't seem like the right tool for a scenario like this.

It also looks like you have a bunch of runtime state in your Tile class (_flickerTimer, _lightCalculated, etc...), in addition to "static" state (_BackgroundType, etc..). You can probably avoid serializing that.

Assuming the only important "static" information is BackgroundType, Orientation, _directionLightLevel and _ambientLightLevel, then you've got 6 bytes, for a total of around 30MB for your 10240 * 512 level. Looking at your code, it may be that _directionLightLevel and _ambientLightLevel can be inferred from the tile type? If so, then you really only need 2 bytes per tile, so 10MB.

You could probably substantially reduce this with some compression algorithm, since I assume there are a lot of tiles of similar types next to each other.

#9 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 03 October 2012 - 01:39 PM

That was a lot of good responses I got there :)

woow, >10000 tiles in x. What is the size of tile. Is level not too long. For example if tile 64X64 pixels and screen is 1280px and lets take one screen last about 5 seconds (normal scrolling speed) to fly throu it will be 64*10240*5/1280/60=42 minutes. Not too log for level?

I am aiming at very large worlds like in Terraria, so the size I present is rather small. (I am doing 16X16 tiles though)

Chunks is indeed the way to go for such a large world, and having them in many small files should not be a problem at all. Then you can begin to stream new chunks directly from the files as the player gets close to them.
As for that last question: Properties makes no significant difference to the size of the class, so use them as much as you want. Posted Image

When doing chunks, do you then Deserialize small amounts on the run? Or how is it handled?
And thanks for the info on properties, just the answer I was looking for.

If that did not solve your problem, try this: http://www.downloadmoreram.com

Good one lol - But I'm pretty sure I don't need more RAM, 8GB should be plenty for this Posted Image - I will try out your suggestions.

I wonder whether memory allocation may be particularly inefficient if you're serialising a generic List or similar, e.g. hard for it to know up front what memory to allocate.

I serialize an array with a pre-determined size.

You can make enums be byte-sized by doing the following:

enum TileType : byte
{
Grass,
Dirt,
// etc....
}

As for serialization, you should be using custom serialization for something like this. I don't know the details of how .net serializes classes, but I'm sure it needs a bunch of metadata along with the actual data. It may be convenient, but it doesn't seem like the right tool for a scenario like this.

It also looks like you have a bunch of runtime state in your Tile class (_flickerTimer, _lightCalculated, etc...), in addition to "static" state (_BackgroundType, etc..). You can probably avoid serializing that.

Assuming the only important "static" information is BackgroundType, Orientation, _directionLightLevel and _ambientLightLevel, then you've got 6 bytes, for a total of around 30MB for your 10240 * 512 level. Looking at your code, it may be that _directionLightLevel and _ambientLightLevel can be inferred from the tile type? If so, then you really only need 2 bytes per tile, so 10MB.

You could probably substantially reduce this with some compression algorithm, since I assume there are a lot of tiles of similar types next to each other.

I will definetly look into this- I did not know that you could do that to enumerators, thanks a bunch for that one.

All in all it seems I've underestimated the entire topic of serialization. I am very grateful for all the responses you've given me. I think I will try to reduce the size of the tiles more, and look more into custom serialization.
Right from the beginning of this project, the two things I've "feared" the most is this, and random terrain generation.

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#10 Mizu   Members   -  Reputation: 968

Like
1Likes
Like

Posted 04 October 2012 - 05:27 AM

You can make enums be byte-sized by doing the following:

That's... brilliant. Why have I never seen this before Posted Image

When doing chunks, do you then Deserialize small amounts on the run? Or how is it handled?

Naah, the easiest way should be to load the whole chunk at once. Just make sure you don't use too large chunks and load them in the background to not freeze the game, then it should be fine Posted Image Streaming sometimes has a tendency to become a bit complicated if you're not careful though, so if you're just starting out you might want to keep it simple and, if possible, use areas instead, showing a loading screen as the player walks from one area to the next.

Good luck!

Edited by Mizu, 04 October 2012 - 05:28 AM.


#11 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 04 October 2012 - 12:53 PM

Naah, the easiest way should be to load the whole chunk at once. Just make sure you don't use too large chunks and load them in the background to not freeze the game, then it should be fine Posted Image Streaming sometimes has a tendency to become a bit complicated if you're not careful though, so if you're just starting out you might want to keep it simple and, if possible, use areas instead, showing a loading screen as the player walks from one area to the next.

Good luck!

Thanks a lot. Tomorrow I will finally have time to dive into all this so I am looking forward to it. About using areas, I don't consider that an option, that will not fit into the concept, in my opinion. But thanks a lot for all the input, I really appreciate it :D

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#12 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 05 October 2012 - 06:16 AM

So I've finally had some time to play around with this, and I've managed to get it to work... But only on very small worlds/file sizes. Now I've tried two ways of doing it, with exactly the same results. The first way is the simple way I described earlier, I did however mark a few objects as nonserializable to save additional space.
The other solution I've tried is the one posted here: http://www.codeproje...ization-using-C.
I got the exact same result with this one when deserializing- The game stays frozen for 5-10 minutes, and then throws an out of memory exception. I then tried to reduce the world to 1024*512. This actually fixed it. I still had a load time on about 1.5 minutes and a save time of maybe 15 second, but it seems to work flawlessly after that.
Just prior to posting this I then figured that it might work by doing it the "simple" way. So I commented out all the code related to the CodeProject article, and tried again, and exactly the same result.
Just now I tried with a world size of 128*128. Here the save time is like .3 seconds, and the load time is maybe around 1 second. This is close enough to be acceptable, and it might probably work if I chunk it down to 128*128 chunk pieces, but it feels wrong doing it like this, since I got the feeling I am doing something wrong.
I did get a suggestion to try and do a custom serialization, but as far as I understand, that's exactly what I am doing if I follow the CodeProject article?
I do have a few Tile classes that inherrits from the base Tile class, to handle objects that changes state, and objects that take up more than 1 tile in the world grid, but I did remember to follow these rules(when using the CodeProject article) - http://msdn.microsof...326(VS.80).aspx so I don't think that is the cause.
Below is the code I use for the CodeProject solution:

/// <summary>
		/// Constructer for deserialization
		/// </summary>
		public Tile(SerializationInfo info, StreamingContext ctxt)
		{
			Type = (TileType)info.GetValue("TileType", typeof(TileType));
			BackgroundType = (TileType)info.GetValue("BackgroundType", typeof(TileType));
			Orientation = (TileOrientation)info.GetValue("Orientation", typeof(TileOrientation));
			_variant = (byte)info.GetValue("Variant", typeof(byte));
			_lightCalculated = false;
			if (Type == TileType.None)
			{
				if (BackgroundType == TileType.None)
					_ambientLightLevel = Light.AmbientLight;
				else
					_ambientLightLevel = 0;
				_directLightLevel = 0;
				_flickerTimer = 0;
			}
			else if (Type == TileType.Torch)
			{
				_directLightLevel = 255;
				_ambientLightLevel = 0;
				_flickerTimer = 1;
			}
			else
			{
				_directLightLevel = 0;
				_ambientLightLevel = 0;
				_flickerTimer = 0;
			}  
		}
		public virtual void GetObjectData(SerializationInfo info, StreamingContext ctxt)
		{
			info.AddValue("TileType", Type);
			info.AddValue("BackgroundType", BackgroundType);
			info.AddValue("Orientation", Orientation);
			info.AddValue("Variant", _variant);
		}

Notice that GetObjectData is virtual. The child classes overrides it, add their own values in the same manner, and then calls the base method. I also remember to make the Tile class inherrit from ISerializable. I then serialize exactly the same way as before, using the methods I posted earlier.

So to sum it up:

As I understand it, when a class inherrits from ISerializable and has the GetObjectData method and the deserialization constructer, both should automatically be called when you are both de- and serializing. This seems very odd to me, but is this true?
And secondly is this what is meant by making custom serialization, or am I completely off?

I'm off to read up on all this, and I'll post here if I happen to answer some of my own questions.

Thanks for reading Posted Image

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#13 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 05 October 2012 - 03:41 PM

I did happen to answer a few of my own questions. I now know that my code is true in regards to the Serialization while inherriting from ISerializable. So I sat down and started to think out how I would handle dividing my world up into chunks, and I figured I'd check out how Terraria does this.
I tried to make a world of the largest terraria size, which, to my suprise "only" is around 8400*2400, so I figured I'd begin to test out doing that size. I also realized that Terraria increases drastically in memory usage when you load a large map. It was just above 900MBs (over 400 prior to loading). Which tells me it keeps the world in memory. When saving the game the world file is a bit over 90MBs. In my game currently, my memory usage is only about 200-250MB prior to loading, and just below 900MB when the world is loaded. This is all well and good, My game (as it is right now) consumes slightly less, but my world consumes about 200MB more. I can live with that for now. The problem is then when I try to save the file via selective serialization (I only chose TileType,BackgroundType,Orientation and variant, all of these should be the same as a byte each.) it takes several minutes... It even gave me an out of memory exception on my first try. So instead of serializing the entire world in one go, I made 2 for loops to handle it, one tile at a time. I end up with a world file on no less than 7.4GB, I do understand that using the out of the box serialization that .NET brings, is very ineffective, but this is just rediculous.
If I can dramatically decrease save/load times and file size, I am close to solving this problem- Can anyone help me out here? And maybe even explain why I experience this huge file?

I read something about that a lot of extra data was added to the stream this way. if this happens for every single tile... that's bad Posted Image

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#14 nife87   Members   -  Reputation: 516

Like
1Likes
Like

Posted 05 October 2012 - 05:20 PM

I might have missed if someone else mentioned this, but you might want to take a look at streaming (only load what you need now plus a little more, then let a background thread load more when needed) and/or compression (if you cannot minimize the tile data further), considering the amount of data you are handling. Since you only load one file sequentially, you do not need to worry about (mechanical head) seeking.
Perhaps, depending on the Type/Background/Orientation variables (whether or not they differ a lot for each tile), you can make these objects flyweights, thereby only having one to load 1 object for each different type/background/orientation and in the file reference them by some identifier (ID/GUID)?
Other than that, use as small data types as possible to describe what you need, which I see you already are in Tile, using bytes/shorts. For instance, an int X can often be reduced to short/byte X if any two X does not differ by more than 2^15/2^7 (or unsigned 2^16/2^8). For instance, if your X's are all in the range [545;668], the difference is at most 668-545=123 (making it a perfect fit for a byte), so serialized is byte bX = (int iX - 545) and deserialized is int iX = (byte bX + 545). Warning to readers, in case I just created arithmetic overflow of converted data types (do not know C# well enough to catch these).

#15 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 06 October 2012 - 03:29 AM

I might have missed if someone else mentioned this, but you might want to take a look at streaming (only load what you need now plus a little more, then let a background thread load more when needed) and/or compression (if you cannot minimize the tile data further), considering the amount of data you are handling. Since you only load one file sequentially, you do not need to worry about (mechanical head) seeking.
Perhaps, depending on the Type/Background/Orientation variables (whether or not they differ a lot for each tile), you can make these objects flyweights, thereby only having one to load 1 object for each different type/background/orientation and in the file reference them by some identifier (ID/GUID)?
Other than that, use as small data types as possible to describe what you need, which I see you already are in Tile, using bytes/shorts. For instance, an int X can often be reduced to short/byte X if any two X does not differ by more than 2^15/2^7 (or unsigned 2^16/2^8). For instance, if your X's are all in the range [545;668], the difference is at most 668-545=123 (making it a perfect fit for a byte), so serialized is byte bX = (int iX - 545) and deserialized is int iX = (byte bX + 545). Warning to readers, in case I just created arithmetic overflow of converted data types (do not know C# well enough to catch these).


Those are good ideas, I'll add them to my list of possible optimizations, thanks a lot :) I'll go read up on streaming and see if it is usable in my situation.

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#16 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 06 October 2012 - 06:21 AM

Finally I suceeded.
I was too focused on using the serialization that was build into the .net framework that I misunderstood some of the advice I got earlier.
So I spend some time away from the computer, and when I came back I reread the posts here and decided to try to do it manually by using BinaryWriter and BinaryReader. 30 minutes later (and on my first test I might add) I successfully saved my world (8400*2400 tiles). With a save time on less than 2 seconds, and a load time on about the same. The file size is also down to less than 78MB.
Basically what I do is I make two for loops that starts out at 0, 0 (x, y) and take all the values that aren't recalculated at runtime every frame, from each tile, and write them to a file stream. When I load them back in, I use two for loops again and make sure I load them in the exact same order I wrote them.

To make sure that everything worked as intended, I decided to build a small.. monument for the occasion of being able to save and load my world, I took a small screenshot. This screenshot was taken after I've sucessfully saved and then reloaded the world:

Posted Image
Although I still need to pollish the save/load algorithm, I consider this step successful. As I posted earlier I considered this step to be one of the harder ones, so I am very grateful for all the help I got from you guys- So thanks a lot :-)

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#17 Waterlimon   Crossbones+   -  Reputation: 2435

Like
1Likes
Like

Posted 06 October 2012 - 10:37 AM

You could implement some very simple RLE to get rid of all that air in the file. It wouldnt be that hard to add, instead of just copying the stuff to the file one by one, you count how many sequential blocks of the same type there are and then save it as BlockCount,BlockType, and when you read it you write the next BlockCount cells to contain a block of BlockType type.

o3o


#18 Mekuri   Members   -  Reputation: 299

Like
0Likes
Like

Posted 06 October 2012 - 01:20 PM

You could implement some very simple RLE to get rid of all that air in the file. It wouldnt be that hard to add, instead of just copying the stuff to the file one by one, you count how many sequential blocks of the same type there are and then save it as BlockCount,BlockType, and when you read it you write the next BlockCount cells to contain a block of BlockType type.

That is actually a good and simple idea. I'll keep it in mind when I start optimizing further :)

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS