15 replies to this topic

[sliders_alpha]

Hi, I want to make a minecraft clone but I don't know if I'm going in the right way or not.
having never took any game programming courses I might be re-invented the wheel^^

first thing first, my world is stored in a 2D sectors array.
I give the illusion of movement by drawing the world backward when the player wants to go forward.



and here is my Idea for infinite world generation.


(in reality I have a bigger array called cache which contains the world sectors and the sourrounding ones, this cache object is managing hard disk access on it's own to always give to the world quick access to new sectors)

what do you think?

thanks

Attached Thumbnails

• 
• 

[Waterlimon]

So basically you have a square grid which holds the visible chunks of the world, where it moves them around trying to keep the player in the center cell? k.

You could make it not-square but something similiar to a circle (leave some corner cells not pointing anywhere) as theyre not really useful in the corners as you cant see that far in all of the directions...

[sliders_alpha]

yeah but I'm using java, Since i'm declaring an array of chunk.
I think that even If I put nothing inside a cell the memory for it is still allocated.

I just thought about something, it's all ok if the player start a 0,0.

but how to move it back to where he was last time?
my current thought is to store the chunk name and the coordinate on the chunk.

[Waterlimon]

But if theyre kind of references the memory usage will be a lot lower without those extra chunks as youre just storing something that can point to chunks, not the chunks themselves.

[Krohm]

I see no problem in line of theory. Keep in mind however that wrapping the world to reset it around the origin might be more problematic than expected. I can tell for sure Bullet (a physics API I'm using) wouldn't allow you to do so. If you're going to write your own physics, keep in mind the periodic "re-centering" operation will likely have to be supported somehow.

It is possible to do something like what you have drawn in the first two images, let the camera move forward for a few chunks (say 1024*16 units) and keep streaming (letting the model "grow", without changing camera position). Then, wrap to the origin only when a certain rationale is met, such as distance from the origin > 1024*16. This is fairly easy: just subtract a constant such as 1024*16 along a certain axis.

How to move back where it was last time? It's not like we are talking about something we don't know. We know exactly how big a chunk is. Think at it. As long as FP precision allows, the operation will be perfect.

What's the deal with chunk names and coordinates? It appears to me this information is not required.

But if theyre kind of references the memory usage will be a lot lower without those extra chunks as youre just storing something that can point to chunks, not the chunks themselves.

I don't completely agree for two reasons.

• Nobody says chunks will be reused. In the case of minecraft, they are mostly unique - this means the difference will be close to zero but anyway..
• Java does not really create a array of objects. It creates arrays of references to objects. Java does not really deal with the objects themselves like C/C++ does, it deals with the references only.
• I hardly believe the chunk structure itself will take much space. It's data will.

[sliders_alpha]

you were both right, making an array of reference to chunk does not allocate anything it just creates reference.
then I have to instanciate a class and link it to this reference.

I see no problem in line of theory. Keep in mind however that wrapping the world to reset it around the origin might be more problematic than expected. I can tell for sure Bullet (a physics API I'm using) wouldn't allow you to do so. If you're going to write your own physics, keep in mind the periodic "re-centering" operation will likely have to be supported somehow.

well I'm planning on coding everything, i'm doing this for fun^^
what kind of other type of infinite world algorythm is there out there? I searched the first 10 pages of google and each camera implementation is the same.

the camera never moves, the world does.
therefore I don't see any other way to do it.

It is possible to do something like what you have drawn in the first two images, let the camera move forward for a few chunks (say 1024*16 units) and keep streaming (letting the model "grow", without changing camera position). Then, wrap to the origin only when a certain rationale is met, such as distance from the origin > 1024*16. This is fairly easy: just subtract a constant such as 1024*16 along a certain axis.

why? basically you are asking me to do exactly the same thing but to increase the "reset" distance from 1 chunk to 1024 chunk.

what will it changes?

Edited by sliders_alpha, 30 April 2012 - 10:50 AM.

[Ravyne]

That's more or less sound, what you're doing is generally called "streaming" -- However, you probably don't want to decide which "chunks" of the world to cache based on direction the player is facing, since the player can turn quite rapidly. I would cache chunks based on distance to the player, and perhaps use direction of travel as a secondary influence -- so basically, cache concentric rings around the player from the inside out, and on those rings start with the chunks directly in front of the player, going around the ring in either direction until they meet behind the player.

Within that set you might use a heat-map to identify commonly-traveled areas, so that you know to get updates for those more-frequently, if it matters for your game. For example, most of the time when I play Minecraft I'm at my home, or in a nearby area where I hunt mobs.

[sliders_alpha]

well I'm not choosing wich chunk to cache, I'm caching EVERY chunk around the player.



for now I'm only working with 49 Chunk but storing 600-900 chunk on RAM is more than acceptable.
it would take around 400Mb and today's computer have at least 4GB of ram, why shouldn't I use it?

Attached Thumbnails

• 

Edited by sliders_alpha, 30 April 2012 - 01:40 PM.

[Acharis]

I would do it like this:

Assuming the visibility range is 10 units.
- Load all chunks within 12 units range. Do not use any separate threading, just load chunks one by one without hurry, you are loading these before these are needed (since you have 2 chunks buffer).
- Unload all chunks that are farther than 30 units range (much bigger than visibility range and the load range). Players frequently go back and forth so unloading prematurely is a big waste.

Do not forget the bottleneck is CPU, not memory nowadays. You should waste some memory to in order to give CPU some break.

[sliders_alpha]

It's true that by expanding the cache size from radius+1 to radius*radius would allow me to load chunks in a unique thread.

however are you sure that it changes anything for when a player is going back and forth?
look at this, if the player is going back and forth, the red lines keeps getting loaded/unloaded.

but not having to be in a hurry to load chunk is quite nice^^

Attached Thumbnails

• 

[Ravyne]

Do not forget the bottleneck is CPU, not memory nowadays. You should waste some memory to in order to give CPU some break.

Your reasoning is actually exactly the opposite of reality. CPUs are *highly* sensitive to memory latency and cache misses. The CPU can't do any useful work at all if its waiting for the data it needs to operate on.

You're conclusion is, however, on the mark. The reason you'd "waste" memory by pre-caching information you're not actively using is to move the data closer to the CPU within the memory hierarchy (Typically: CPU -> CPU registers, L1$, L2$, L3$, RAM, HDD). The nearer you are to the CPU, the greater the bandwidth and less latency involved. Bandwidth across SATA is more than an order of magnitude slower than typical bandwidth to main memory. Mechanical storage like traditional HDDs or optical discs aren't usually able to saturate the available bandwidth and introduce seek latencies in addition.

Edited by Ravyne, 30 April 2012 - 03:12 PM.

[Krohm]

basically you are asking me to do exactly the same thing but to increase the "reset" distance from 1 chunk to 1024 chunk.

what will it changes?

If the re-centering operation is perfect, it will change almost nothing. If not, this reduces the chance to hiccup at a fraction. It also involves slightly less transform matrix uploading - but I'd expect the benefit to be not measurable. In general, the camera should be allowed to somehow move as expected or at least, some system must keep track of the "real" position. But if you just want to do minecraft, I suppose there will be no problems anyway.

[DrMadolite]

Minecraft isn't infinite *grrrr*

but how to move it back to where he was last time?

With one big-ass text-file. (jk, I got no idea)

Edited by DrMadolite, 01 May 2012 - 04:35 AM.

[Waterlimon]

It's true that by expanding the cache size from radius+1 to radius*radius would allow me to load chunks in a unique thread.

however are you sure that it changes anything for when a player is going back and forth?
look at this, if the player is going back and forth, the red lines keeps getting loaded/unloaded.

but not having to be in a hurry to load chunk is quite nice^^

I think he meant that you unload chunks if you go far away from them, but you only load them if they get in the original cache area. So that you dont unload already loaded chunks until you need to because you might come back soon.

[noizex]

It's true that by expanding the cache size from radius+1 to radius*radius would allow me to load chunks in a unique thread.

however are you sure that it changes anything for when a player is going back and forth?
look at this, if the player is going back and forth, the red lines keeps getting loaded/unloaded.

but not having to be in a hurry to load chunk is quite nice^^

I think he meant that you unload chunks if you go far away from them, but you only load them if they get in the original cache area. So that you dont unload already loaded chunks until you need to because you might come back soon.

Yeah, this would allow you to unload not needed chunks and not fall into this load/unload loop if player moves back and forth. If he does, closest chunks will always be in cache so you can just fetch the reference and do whatever you want (render etc.)

But I'd make decision about unloading chunks not distance based - I suggest making a limited "list" or "deque" that will hold references to chunk data and it will act as cache that can store for example 500 chunks. You set the limit or allow user to choose based on his available memory. Whenever you hit the limit, you remove oldest chunk from it when you're inserting new one. Whenever you reference chunk for rendering you push that chunk on top of that "deque", this gives you chunks ordered by last access time. This way you can freely remove chunk from the bottom of the list because those are the oldest chunks and are not used anymore.

There is of course problem of quickly accessing required chunk (based on its coordinates?) but you can keep two lists - one linked list or some kind of deque to keep information about chunks last access time (this will be used to unload unused chunks) and another storage for fast chunk access (hash or dictionary kind) so you can quickly ask for a chunk at (x, y, z) and if its in cache it will fetch the reference - I assume that asking for a chunk by rendering engine would always return cached chunk because we ensure that chunks in some distance around player will be prefetched even if they're not needed right now.

Edit: Added diagram so it explains better what I had in mind. As you can see it gives us some sort of 'inertia' where chunk loading doesn't take place immediately when player moves (forward or back and forth) but only when we have to load completly new chunks.

Edited by noizex, 01 May 2012 - 06:05 AM.

[sliders_alpha]

Minecraft isn't infinite *grrrr*

a VERY BIG procedural world then

thanks for the pic noizec, it really helped =D
however erasing according to the last access time sounds quite tricky to implement So I made a simplier version (used your graph, hope you don't mind) :

http://www.youtube.com/watch?v=OLnb8NRqAuM

Edited by sliders_alpha, 01 May 2012 - 09:07 AM.