Blocking Movement & Lighting

This was a fun update!

The first thing I needed to do was not allowing the character to walk anywhere. He has to respect walls, trees, and other “blocking” stuff.

Flags appear here for the first time. Each tile in the sprites has some flags associated to it. For blocking, we have “NonWalkable” (to block walking into a cell at all, for things like water), and “BlockWalkFromXX”, with XX representing the 4 iso directions (NE, NW, SW, SE). When the character changes cells, we check the flags of the 2 cells he moved between to see if they block movement.

This is straightforward for the 4 diagonal directions. For N, S, E, W, which happen if he’s just walking xactly through the vertex of a cell, we simply do 2 double diagonal checks. If one of those is permitted, it’s fine. For example, if going E, we try doing SE-NE, or NE-SE. If either of those work, we let him through.

// Check whether a character can actually change cells
Character.prototype.ValidateChangeToCell = function(curCell, newCell) {
	if (newCell.equals(curCell)) { return true; } // this shouldn't happen, but you can always walk within a cell
	if (newCell.x < 0 || newCell.x >= map.width || newCell.y < 0 || newCell.y >= map.height) { return false; } // If we're walking off-map, don't go there
	if (map.Cells[newCell.x][newCell.y].flags & CellFlags.NonWalkable) { return false; } // If the destination cell is not walkable, we just can't go there
	if (curCell.CircleDistance(newCell) > 1) { console.log("Non-adjacent!"); return true; } // I can't really validate if cells are non-adjacent
	var curCellFlags = map.Cells[curCell.x][curCell.y].flags;
	var newCellFlags = map.Cells[newCell.x][newCell.y].flags;
	switch (curCell.DirectionTo(newCell)) {
		case Direction.NE: if (curCellFlags & CellFlags.NonWalkFromNE || newCellFlags & CellFlags.NonWalkFromSW) { return false; }; break;
		case Direction.SW: if (curCellFlags & CellFlags.NonWalkFromSW || newCellFlags & CellFlags.NonWalkFromNE) { return false; }; break;
		case Direction.SE: if (curCellFlags & CellFlags.NonWalkFromSE || newCellFlags & CellFlags.NonWalkFromNW) { return false; }; break;
		case Direction.NW: if (curCellFlags & CellFlags.NonWalkFromNW || newCellFlags & CellFlags.NonWalkFromSE) { return false; }; break;
		// For non-diagonals, we test both possible diagonal paths. If neither works, return false
		case Direction.N:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.NE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NE, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.NW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NW, true), newCell))) {				
			} else { return false; }
		case Direction.S:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.SE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SE, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.SW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SW, true), newCell))) {
			} else { return false; }
		case Direction.E:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.NE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NE, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.SE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SE, true), newCell))) {
			} else { return false; }
		case Direction.W:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.NW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NW, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.SW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SW, true), newCell))) {
			} else { return false; }
	return true;

This was relatively straightforward, now for the fun part.


One fun thing we can do, which is really simple and pays off greatly, is darken the sprite sheets by processing them pixel-by-pixel and multiplying each color value by a ratio < 1.
If we progressively darken them and store the different "light levels", we can then pick, for each cell, from which of these levels to draw, and draw each individual cell darker or lighter.
Simply picking the light level through proximity to a light, we have some nice lighting.

The direct problem with this is, if for each cell we start trying to find the closest of all the lights in the map, drawing slows down considerably. To be fair, it was way less than I expected, it went from 61 FPS to 55 in my simple test, but still, that’s a lot of lost frames, and we can do better. Also, this doesn’t allow one of the best effects.

The position of the lights doesn’t change too often (the big exception is if the character himself holds a light, but still, it only changes when we change cells), so we can pre-calculate a “light map”, which just stores the pre-calculated light level for each cell in the map, and then simply refer to it when drawing.
The lightmap also lets us do something very cool, which i’ll get to in a sec.

To calculate the lightmap, we need to “project light” from each of the lights in the map. I want to do this by starting from the light, and “creeping outward” cell by cell, reducing the amount of light given in each step.
Processing a square centered on the light, and sized according to the “power” of the light is way faster, but it doesn’t let me do the cool thing I want to do.
So, starting from the light, I move in the 8 directions and put all those cells in a queue, which I process and for each of those cells, I put the 8 surrouding ones (that I haven’t already visited) in the queue too.

The result is that I’m always going from the center to the edges, the code is simple, and while the most efficient, still fast enough.
Calculating the whole lightmap for a 100×100 map with 12 lights takes about 0.6 ms.
That’s perfect.

And now for the cool part. Just like I have flags to block walking, I can have equivalent flags to block light passing through from cell to cell (for example, for the sprite of a tall wall). When spilling light from one cell to the next, I first check whether light “can walk” between those 2 cells, and if not, I don’t add that new cell to the queue.

The result is what I call “dungeon mode”. When you’re in a room, and there’s a narrow door leading to another room, only a sliver of your light passes through that door, giving a very realistic effect of holding a torch

And this is esentially the reason to do lighting by spilling from cell to cell, instead of the faster methods. This lets me very easily check for walls at each step, allowing this extra-cool effect almost for free.
Well, not free, the lightmap calculation jumps from 0.6 to 1.5ms, but it’s still more than fast enough. And if this becomes a problem, I can definitely make it better by only calculating the part that I need, instead of the whole map.

One caveat though… This doesn’t scale to huge maps and enormous amounts of lights…
I tried this in a 1,000 x 1,000 map with 10,000 lights, and it takes a full second to run.
Granted, you won’t have 10k lights, like, ever, but 1 second is very dire. If I ever need huge maps or too many lights, i’ll have to do something about this.

CalculateLightMap: function() {
	// Initialize the whole surface
	Drawing.LightMap = {};
	for (var x=0; x < map.width; x++) {
		Drawing.LightMap[x] = {};
		for (var y=0; y < map.height; y++) {
			Drawing.LightMap[x][y] = map.globalLightLevel;
	// Project light from each light
	for (var l=0; l < map.Lights.length; l++) {
		if (map.Lights[l].power > 0) {
			Drawing._ProjectLight(map.Lights[l].pos, map.Lights[l].power);
_ProjectLight: function(pos, power) {
	var alreadyProcessed = {}; alreadyProcessed[pos.x * 100000 + pos.y] = 1; // Store which cells I've been to already with this light
	var toProcess = [[pos, power]]; // And store which cells I need to light. This holds: cell, power to add
	while (toProcess.length > 0) {
		var c = toProcess.shift();
		var cp = c[0]; // cellPos
		Drawing.LightMap[cp.x][cp.y] = Math.min(Drawing.LightMap[cp.x][cp.y] + c[1], Map.Constants.LightingLevels);
		if (c[1] > 1) {
			for (var d = 0; d < 8; d++) {
				var newPos = cp.Move(d, true); // cp.Move takes a direction and moves in that direction. Directions are an enum from 0 to 7.
				if (Viewport.ValidateChangeToCell(cp, newPos, "Light")) {
					if (!alreadyProcessed[newPos.x * 100000 + newPos.y]) {
						alreadyProcessed[newPos.x * 100000 + newPos.y] = 1;
						toProcess.push([newPos, c[1] - 1]);
			} // go each of 8 directions
		} // If we have power to spill
	} // while (queue)

Final tip: When darkening the canvas, if instead of just multiplying for a ratio < 1, you make the pixels “tend” to some color that’s not black, you can create cool “fog” effects (white), or weird hellish environments (orange-red). It looks pretty good.

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">