Efficient object culling

Unity Engine
1

Hey gang! I’m working on a top-down 2D game that has a very large tile-based map. Without paying for Unity Pro, I’ve been trying to implement my own “occlusion culling” algorithm and was wondering if any of the devs out there had any tips.

What I’ve implemented so far is quick and dirty: Each tile is a quad with a texture. I’ve split the map in chunks of 16x16 (the whole map is 128x128 chunks). At the moment, the game instantiates the tile GameObjects for the chunk the player character is in, and the tiles for the 8 chunks that surround it. When the player moves around the map, any tiles belonging to a chunk that is no longer near the player are destroyed (so there are only ever 9 active chunks).

	private Hashtable chunkCache;

	....

	void Update () {
		CheckForNewChunk();
		CheckChunksToRemove();
	}

	private void CheckForNewChunk(){
		//Get current chunk
		int xChunk = Mathf.FloorToInt(transform.position.x / Config.CHUNK_FACTOR_X); //CHUNK_FACTOR_X = TILES_PER_CHUNK_X*TILE_SIZE
		int yChunk = Mathf.FloorToInt(transform.position.y / Config.CHUNK_FACTOR_Y);//CHUNK_FACTOR_Y = TILES_PER_CHUNK_Y*TILE_SIZE

		for(int y = yChunk - 1; y < yChunk + 2; y++){
			for(int x = xChunk - 1; x < xChunk + 2; x++){
				// Check if current chunk is cached
				if(!chunkCache.ContainsKey(Utils.HashPair(x, y))){
					if(x >= 0  y >= 0  x < Config.CHUNKS_X  y < Config.CHUNKS_Y){
						GameObject[] chunkTiles = new GameObject[Config.TILES_PER_CHUNK];
						float chunkXOffset = x * (Config.CHUNK_FACTOR_X);
						float chunkYOffset = y * (Config.CHUNK_FACTOR_Y);
						
						//Add tiles
						for(int i = 0; i < Config.TILES_PER_CHUNK; i++){
							
							GameObject tile = (GameObject)Instantiate(tile,transform.position,transform.rotation);
							tile.transform.position = new Vector3(chunkXOffset+(i%Config.TILES_PER_CHUNK_X)*0.5f, chunkYOffset+Mathf.FloorToInt(i/Config.TILES_PER_CHUNK_Y)*0.5f, 0);
							chunkTiles[i] = tile;
						}
						
						//Add chunk to scenes and cache
						chunkCache.Add(Utils.HashPair(x, y), chunkTiles);
					}
				}
			}
		}
	}
	
	private void CheckChunksToRemove(){

		ArrayList chunksToRemove = new ArrayList();
		//Get current chunk
		int xChunk = Mathf.FloorToInt(transform.position.x / Config.CHUNK_FACTOR_X);
		int yChunk = Mathf.FloorToInt(transform.position.y / Config.CHUNK_FACTOR_Y);


		foreach (DictionaryEntry chunkEntry in chunkCache){
			bool isActive = false;
			for(int y = yChunk - 1; y < yChunk + 2; y++){
				for(int x = xChunk - 1; x < xChunk + 2; x++){
					if((int)chunkEntry.Key == Utils.HashPair(x, y)){
						isActive = true;
					}
				}
			}

			if(!isActive){
				GameObject[] chunkTiles = (GameObject[])chunkEntry.Value;
				
				for(int i = 0; i < chunkTiles.Length; i++){
					Destroy((GameObject)chunkTiles[i]);
				}
				
				chunksToRemove.Add(chunkEntry.Key);
			}
		}

		foreach(int chunkHash in chunksToRemove){
			chunkCache.Remove(chunkHash);
		}
	}

This works alright, but there is definitely a bottleneck when new chunks are created and destroyed that causes an annoying jitter.

Here are some of the ideas I have had to address it that I hope you guys have an opinion on (I’m still fairly new to Unity, so I’m not sure what’s effective yet).

  • Hide and Show the tile GameObjects instead of Creating and Destroying (keeping in mind this is a giant map that’s 2048x2048 tiles across
  • Re-position quads and change their material instead of destroying them and creating new ones (is changing the material on an object faster than destroying one and creating a new one?)
  • Create an object pool
  • Some other thing I haven’t thought of…

Thanks in advance for the help.

Edit: The code I posted only creates one type of tile at the moment, just in case anyone is confused.

2

Never worked with tiles, but having 2 double for loops every update is never a good idea(in my experience). Even if the entire codeblock is not executed.

I would further separate the world into collision triggers, only when you enter a new collision trigger will objects be created/destroyed/manipulated. Which gets rid of that nasty update.

An object pool may be a solution to further optimise, if your level is finite, otherwise you could run into problems.

3

Thanks for the reply. The update loops were just something I threw in to quickly get a proof of concept. As it is at the moment, they don’t seem to hurt anything until I need to create and destroy objects. You might be on to something with the collision triggers. I’ll try implementing it when I get home from work. The level isn’t infinite, but it is pretty huge.

Another thought I had was that I might be to reuse the same tiles and instead of changing their materials, I can change the offset of the materials texture (and have all the different tiles in the same texture)

4

The trick is finding ways to do less work, or find ways to do some of the work ahead of time.

If collision triggers will work for you, that’s solid.

If you want to learn more about algorithms and data structures, this is an excellent use case for a “quadtree”. You can create a data structure that keeps track of your objects based on where they are, then allows you to check or skip them on that basis.

In fact, the collision system is more than likely using something like a quadtree, internally!

5

Thanks rutter! This might very well be what I’m looking for. I implemented a quadtree for collisions in a flash project a few years ago (based on a chapter in Keith Peter’s excellent book “AdvancED ActionScript 3.0 Animation”), I’ll post my final results after I implement it.