How to create highly scalable worlds

Miscellaneous Topics
#1

Introduction:

Well, I think it is time for me to put up a tutorial, and seeing that there are none on ‘almost’ infinite worlds, I have decided that I would make one.

IMPORTANT: READ THIS SECOND (after the introduction):

  • This code may not be perfect, as I am not typing this into Eclipse and compiling it. If anyone points out an error, I will fix it as soon as possible.
  • Also, this code may not be the best practice. It works, but it may not work well.
  • There will be some parts missing, as I have not completely worked out how to do some of these things, but if anyone could give me help, I would be very thankful.

Now, for the tutorial

Firstly, you will need a Utility class:

Vector2Long (or course, you may use another implementation as long as it has all the required functions!)

(if you happen to not want the biggest world possible, just change everything into an Integer)


public class Vector2Long
{
	public long x, y;
	
	public Vector2Long()
	{
		x = y = 0L;
	}
	
	public Vector2Long(long x, long y)
	{
		this.x = x;
		this.y = y;
	}
	
	public Vector2Long(Vector2Long vec)
	{
		this.x = vec.x;
		this.y = vec.y;
	}
	
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(obj == this)
			return true;
		if(obj.getClass() != this.getClass())
			return false;
		Vector2Long other = (Vector2Long) obj;
		if(this.x == other.x && this.y == other.y)
			return true;
		return false;
	}
	
	public int hashCode()
	{
		final int prime = 31;
		int hashcode = 1;
		hashcode = prime*hashcode + x;
		hashcode = prime*hashcode + y;
		
		return hashcode;
	}
	
	public String toString()
	{
		return x + "," + y;
	}
}

Make sure that your implementation overrides hashcode and equals in a similar way to the above, otherwise this will fail!

Secondly, you will need 3 classes: (Rename them if you wish)

  • World.java
  • Chunk.java
  • Tile.java

Firstly, set up a ‘Tile’:


public class Tile()
{
	public Tile()
	{
	
	}
}

The Tile class can be given functions as needed, but all you need is that (and a function to get Texture Coords if using OpenGL)

Now, for the Chunk:


public class Chunk()
{
	private static final int size = World.chunksize;

	private Vector2Long chunkPos;
	
	private HashMap<Vector2Long, Tile> tiles = new HashMap<Vector2Long, Tile>();

	public Chunk(Vector2Long pos)
	{
		this.chunkPos = pos;
	}
}

This stores a hashmap of tiles that can be retrieved with a Vector2Int.
It also stores it’s position in the world and it’s size (which is static anyway).

Finally, the World:


public class World
{
	public static final int chunksize = 16; // I use 16 because it's an easier size to work with
	public final long worldsize;
	
	private HashMap<Vector2Long, Chunk> chunks = new HashMap<Vector2Long, Chunk>();
	
	public World()
	{
		this.worldsize = Long.MAX_VALUE;
	}
	
	public World(long size)
	{
		this.worldsize = size;
	}
}

The world just stores a bunch of chunks. Dynamically loading/unloading chunks is up to you depending on what you world/game is like.

So there, You now have the framework for an (almost) infinite world!

(Coming Soon: How to change Tiles in the world, how to render with LWJGL (per Chunk or full World), 3D Worlds, and Entities)

But now I have to go back to work on The Gift/Curse of Evolution…

#2

This is pretty good. I have myself written a game somehow similar to minecraft or something like that and this is also propably the way minecraft does it.

So: Awesome work! :slight_smile:
(Never thought about storing the chunks inside a hasmap… I always thought about linked chunks… so every chunk knows his neighbours… but hashmap is better!)

#3

Since it’s a WIP, then I can’t judge what the rest of the tutorial might be. Using longs for coordinates is a little disappointing. It might be interesting to have BigInteger, Strings, byte arrays, or something else could be interesting. Though, realistically, you probably won’t visit 16 * 2 ^ 63 tiles in one sitting. Linked list style structures are interesting, too. You could use a graph instead of a square grid then. Square grids might not need them (unless you had teleportation or something, then it would help a lot), but it would make it easier to “forget” chunks to save memory since it would automatically handle reachability tests and garbage collect the chunks.

#4

The Article & tutorials board is not a place for WIPs. As mentioned in the board listing, this sub-forum is moderated more intensely than others. That you have other things to do is, fine, but until then this topic is moved to Misc.

#5

Ok, sorry.

I was hoping to finish it yesterday, but then other stuff happened…

As for BigDecimals, I didn’t even think about that, I will change it when I have enough time.

I will have a look into LinkedLists, but I an used to using Hashmaps, so unless there is a huge benefit, I will stick to what I know.

#6

No, linked lists, not LinkedList. :slight_smile: Here’s an example.


public class Zone
{
  private Zone north, south, east, west;
  private Zone portals[];
  // ...
}

I was just thinking aloud about it, though.

#7

Yes this was the idea… but you would need to have a root-zone (in my case I name them “chunks” (like minecraft)), and what should you do if that one gets unloaded? Which zone will be the next? and how do you want to save it?

#8

I would just keep a reference to whatever zone the player is in. Or the camera and player if they’re separable.

#9

What if the player falls into an not-loaded chunk (happens often in minecraft :D:D)

#10

That’s a problem that has to be solved by preloading. It does not matter how neighboring nodes are accessed.