Moving Camera

 

A moving camera is an update that I've been thinking about since I first started working on Bloopworld, I put it off partly due to the complexity, and partly to consider if/how it would contribute to the overall gameplay of the world.

Eventually I decided that implementing it may be the best way to understand how it may function in the game so I started considering more in depth how a camera system for Bloopworld could work.

A bit of background. Since its creation Bloopworld gameplay has occurred from the perspective of fixed top-down cameras that can see an entire "stage" at a time. This view is reminiscent of very old school (think 1980's) video games. 

I've previously described Bloopworld as essentially the world's most over complicated typing indicator. I think this is a good demonstration of that. Each stage is like a chat room and you can see everything that happens on the stage you currently occupy, when you cross the edge - you enter a new room. This strategy is easy to implement and distinctive, but also pretty limiting. 

A camera that can move has different dynamics, and as an added constraint I wanted to leave the rest of the game world unchanged as a special case of the new system (The special case where the camera is staying still). I implemented three solutions that I will discuss in order: (A) tile/pixel approach, (B) double pointer approach, and (C) spatial hash approach.

The fundamental problem in implementing a moving camera is determining, on the server, who is able to see which things that happen:

Bloopworld is subdivided into "Stages" composed of squares called "Tiles" and with the current one camera per player per stage approach, answering this question is easy, a player on the same stage as the tile in question can see its updates, a player on a different stage can not. 

Solution A to this problem, the tile/pixel approach, is one in which our new Camera entity will work by attaching itself to a grid of tiles. Tiles, subsequently, instead of sending their updates to the stage will now send updates to the list of cameras currently attached. We can see this depicted below:

It solves the problem of who can see which tile, and each player is free to move around as much as they like within their camera box, if they cross outside the edge the camera will need to adjust by detaching from certain old tiles and attaching to other new ones. It's not hard to calculate which tiles these are, we can see an example implementation of this approach below:  

    func updateTilesA(camera *Camera, newY, newX int) {
	oldTopLeft := camera.topLeft
	camera.topLeft = oldTopLeft.stage.tiles[newY][newX]
	stage := oldTopLeft.stage
	stageH, stageW := len(oldTopLeft.stage.tiles), len(oldTopLeft.stage.tiles[0])

	oldY0, oldY1 := oldTopLeft.y, oldTopLeft.y+camera.height-1
	oldX0, oldX1 := oldTopLeft.x, oldTopLeft.x+camera.width-1
	newY0, newY1 := newY, newY+camera.height-1
	newX0, newX1 := newX, newX+camera.width-1

	// Tiles that dropped *out* of view.
	for y := oldY0; y <= oldY1; y++ {
		if y < 0 || y >= stageH {
			continue
		}
		for x := oldX0; x <= oldX1; x++ {
			if x < 0 || x >= stageW {
				continue
			}
			if y < newY0 || y > newY1 || x < newX0 || x > newX1 {
				removeCamera(stage.tiles[y][x], camera)
			}
		}
	}

	// Tiles that came *into* view.
	for y := newY0; y <= newY1; y++ {
		if y < 0 || y >= stageH {
			continue
		}
		for x := newX0; x <= newX1; x++ {
			if x < 0 || x >= stageW {
				continue
			}
			if y < oldY0 || y > oldY1 || x < oldX0 || x > oldX1 {
				attachCamera(stage.tiles[y][x], camera)
			}
		}
	}
}

The biggest problem, in my opinion, with this approach is the amount of bookkeeping that needs to occur with each camera movement. In a concurrent system this type of bookkeeping is also prone to double delete / off by one addition errors that lead to reference cloning. In this case cloned/straggling reference are particularly dangerous because not only can they lead to visual artifacts for users, after a user logs out these spare references cannot be easily detected, and, when activity occurs, they can trigger "send on closed channel" server panics. 

All of this is not to say that option A is not viable, my testing indicated it is a valid strategy, but with the downside of having a relatively heavy update loop and an ongoing cost of increasing the complexity of the codebase w.r.t concurrency. 

Option B is a slight variation on option A. It employs a coding trick that I usually consider to be bad practice, but which has a particular advantage in this situation. I will refer to (B) as the double pointer approach. The high level setup is the same as above with the critical difference being that instead of transmitting updates from Tile to a Camera directly, updates are sent through an intermediary pointer to a Camera (e.g. a *Camera pointer or a **Camera). The update code for this approach can be seen below:  

func updateTilesB(camera *Camera, newY, newX int) {
	camera.topLeft = camera.topLeft.stage.tiles[newY][newX]

	// "remove" all of the old camera
	camera.ref.Store(nil)

	newRef := &atomic.Pointer[Camera]{}
	newRef.Store(camera)

	for y := newY; y < newY+camera.height; y++ {
		for x := newX; x < newX+camera.width; x++ {
			attachCameraPtr(camera.topLeft.stage.tiles[y][x], newRef)
		}
	}
}

One advantage here is that camera revocation is now very simple. All previously placed cameras can be revoked in O(1) time with no risk of stragglers. On sign out the current camera reference is nullified. However, the mechanics of atomics end up leaving this version even more prone to "send on closed" errors during update loops: 

func (tile *Tile) updateAllB(update string) {
	updateAsBytes := []byte(update)
	tile.camerasLock.Lock()
	defer tile.camerasLock.Unlock()
	for cameraPtr := range tile.cameraPtrs {
		camera := cameraPtr.Load()
		if camera == nil {
			delete(tile.cameraPtrs, cameraPtr)
			continue
		}
                // risky - what if camera owner logs out now from another thread?
                //   and checking camera state in this critical section adds complexity 
		camera.outgoing <- updateAsBytes
	}
}

Another issue with this approach is that while we can revoke all camera attachments in a single instruction, every camera view update is now the worst case and the entire NxM (camera height x camera width) window needs to get a freshly added camera pointer. This can also require additional bookkeeping/filtering to occur with respect to the updates sent to the user. Combining these issues with the cognitive load and inherent higher complexity of the approach leads me to conclude that option B is inferior even to option A. The O(1) camera removal does feel like a magic trick, but, in this case, it does not add enough value.

Option C is the implementation that can currently be found in the infirmary region of the game. If you go visit you will see that the infirmary is now a single large stage, bigger than the viewport that forms your screen: 

Moving around we can see the desired camera tracking action: 

Option C relies on a fundamentally different approach than options A and B above. It relies on 2 key observations and a willingness to make a specific constant factor concession in order to get (arguably) simpler code. I will discuss here the theoretical approach followed (in another article) by the measured performance results.

The first observation to consider is that if we know the width and height of our camera viewport, we can uniquely identify that window using a single tile. We could choose any tile but we will pick the top left corner. 

Like before, players can move around within the camera window as much as they like. If the player exits the window (or some padding value becomes too low) the top left corner will adjust by transferring to a new tile:

When it comes time for a given tile to send out an update, we're not guaranteed that every camera that can see will have it as a top-left corner. But if we divide the stage into camera sized regions (the green/yellow previous "Stages" in these diagrams), we will find that a camera which can see a given tile is either in the same region as that tile, or in one of up to only 3 adjacent regions. See below:

This diagram is hopefully convincing of the fact that the corner of a camera that can see a given tile is limited to at most 4 possible regions. This is more limited than the players themselves who might find themselves in any one of 8 surrounding regions, or the original (for 9 total).

This is demonstrated in the above diagram with the top-most camera/player. The top player can see the tile in question (marked with a star) despite themselves being in a region that would not even be checked; this top player has a camera with top-left corner in one of the only 4 green check regions. The player beneath them is in physically in the same region, but because they are close to the top left of their camera, they cannot see the starred tile. 

Some tiles are even more restricted. For example, the bottom right corner of each camera sized region can only be seen by cameras that are in that exact same region. For larger grid sizes the average number of adjacent / visible regions approaches 4, with only the bottom row and right column <4  

Below is the code that runs for approach C when the user exits the boundary window (or padding) and the camera position needs to be updated:

func updateTiles(camera *Camera, newY, newX int) []*Tile {
	oldTopLeft := camera.topLeft
	newTopLeft := oldTopLeft.stage.tiles[newY][newX]

	if oldTopLeft.primaryZone != newTopLeft.primaryZone {
		if !oldTopLeft.primaryZone.tryRemoveCamera(camera) {
			// Camera not found section, cannot add to new section (prevents reference duplication)
			return nil
		}
		newTopLeft.primaryZone.addCamera(camera)
	}

	camera.topLeft = newTopLeft

	stage := oldTopLeft.stage
	stageH, stageW := len(oldTopLeft.stage.tiles), len(oldTopLeft.stage.tiles[0])

	oldY0, oldY1 := oldTopLeft.y, oldTopLeft.y+camera.height-1
	oldX0, oldX1 := oldTopLeft.x, oldTopLeft.x+camera.width-1
	newY0, newY1 := newY, newY+camera.height-1
	newX0, newX1 := newX, newX+camera.width-1

	// Tiles that came into view.
	newTiles := make([]*Tile, 0)
	for y := newY0; y <= newY1; y++ {
		if y < 0 || y >= stageH {
			continue
		}
		for x := newX0; x <= newX1; x++ {
			if x < 0 || x >= stageW {
				continue
			}
			if y < oldY0 || y > oldY1 || x < oldX0 || x > oldX1 {
				newTiles = append(newTiles, stage.tiles[y][x])
				camera.outgoing <- []byte(swapsForTileNoHighlight(stage.tiles[y][x]))
			}
		}
	}
	return newTiles
}

We still need to calculate the newly viewed tiles so that we can send them to the camera's screen, but these are now lightweight screen updates, the critical logic is occurring at the top of the function. We can see that instead of modifying the state of many tiles on every camera movement now we only occasionally need to transfer the camera between zones and only if after moving it would no longer agree with where it was before. 

The corresponding logic for tiles to notify their listening cameras is below:

func (tile *Tile) updateAll(update string) {
	// Send to zone containing this tile and neighboring zones (Only cameras in these zones can see this tile)
	tile.primaryZone.updateAll(update)
	for _, section := range tile.adjacentZones {
		section.updateAll(update)
	}
}

Option C was the third implementation I designed for this problem, and while it did avoid some tradeoffs regarding concurrency management one makes by following option A. It introduced a new issue that neither A nor B has. Following option C it is possible to mis-send an update. That is cameras can exist in one of the adjacent regions without the given tile being on screen. In fact, a back of the envelope estimate would seem to imply that this new update system needs to work about 4 times as hard as its predecessor. 

With option C newly implemented that performance implication is exactly what I set out next to test!

This post is already substantially longer than any of my previous posts so I think I will save that for part II. 

Thanks 🐙