Calculating dynamic light and shadows in tile based roguelike games – part 1: Bresenham’s line algorithm

Read all posts about "" game
I love roguelike games. From the simple ASCII games to more complex turn based games like Sproggiwood. I also made some blog posts about roguelike games. One of the features a good roguelike game should have is dynamic light and shadows, as well as a “fog of war” effect. Although it may seem complex, I’ll show you this feature in a way you will find it a lot easier than it seems. I will use a logic similar to the one used in the creation of a survival horror game, but this time we are dealing with tiles. In this first step, we’ll see the algorithm which will be the core of dynamic lights in tile based environments: Bresenham’s line algorithm. From Wikipedia: Bresenham’s line algorithm is an algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. To create a demo with Bresenham algorithm I am going to use the JavaScript code found on RosettaCode together with the magic of Phaser. This is what we are going to create:
We have two draggable tiles, the white ones, a green straight line connecting the tiles, and the result of Bresenham algorithm made of grey tiles. Try to drag white tiles and see what happens. This will be our ray of light. The source code is very basic at the moment, let’s have a look:
var game;
var gridWidth = 40;
var gridHeight = 40;
var tileSize = 16;

window.onload = function() {	
	game = new Phaser.Game(640, 640, Phaser.AUTO, "");
     game.state.add("PlayGame", playGame);
     game.state.start("PlayGame");
}

var playGame = function(game){};

playGame.prototype = {
     preload: function(){
           game.load.image("tile", "tile.png");
     },
     create: function(){
          var startCol = game.rnd.between(0, gridWidth - 1);
          var startRow = game.rnd.between(0, gridHeight - 1);
          this.startPoint = game.add.sprite(startCol * tileSize, startRow * tileSize, "tile");
          this.startPoint.inputEnabled = true;
          this.startPoint.input.enableDrag();
          this.startPoint.input.boundsRect = new Phaser.Rectangle(0, 0, game.width, game.height);
          this.startPoint.input.enableSnap(tileSize, tileSize, true, true);
          do{
               var endCol = game.rnd.between(0, gridWidth - 1);
               var endRow = game.rnd.between(0, gridHeight - 1);     
          } while (startRow == endRow && startCol == endCol);
          this.endPoint = game.add.sprite(endCol * tileSize, endRow * tileSize, "tile");
          this.endPoint.inputEnabled = true;
          this.endPoint.input.enableDrag();
          this.endPoint.input.boundsRect = new Phaser.Rectangle(0, 0, game.width, game.height);
          this.endPoint.input.enableSnap(tileSize, tileSize, true, true);
          this.lineGroup = game.add.group();
          this.lineGraphics = game.add.graphics(0, 0);
     },
     update: function(){
          this.lineGroup.removeAll(true);
          this.lineGraphics.clear();
          this.lineGraphics.lineStyle(3, 0x00ff00);
          this.lineGraphics.moveTo(this.startPoint.x + tileSize / 2, this.startPoint.y + tileSize / 2);
          this.lineGraphics.lineTo(this.endPoint.x + tileSize / 2, this.endPoint.y + tileSize / 2);
          var x0 = this.startPoint.x / tileSize;
          var x1 = this.endPoint.x / tileSize;
          var y0 = this.startPoint.y / tileSize;
          var y1 = this.endPoint.y / tileSize;
          var dx = Math.abs(x1 - x0);
          var sx = -1;
          if(x0 < x1){
               var sx = 1
          }
          var dy = Math.abs(y1 - y0);
          var sy = -1;
          if(y0 < y1){
               var sy = 1;
          }
          var err = -dy / 2;
          if(dx &gt; dy){
               err = dx / 2;
          }
          do{
               var tile = game.add.sprite(x0 * tileSize, y0 * tileSize, "tile");
               tile.alpha = 0.5;
               this.lineGroup.add(tile);
               var e2 = err;
               if(e2 &gt; -dx){
                    err -= dy;
                    x0 += sx;
               }
               if(e2 < dy){
                    err += dx;
                    y0 += sy;
               }
          } while(x0 != x1 || y0 != y1)   
     }
}
It’s just the management of draggable sprites which snaps on a grid and the rendering of Bresenham algorithm itself, which runs from line 44 to line 75. The reason I am leaving this script uncommented is most of it will be discarded in the final version as it’s only a demo to show you how Bresenham algorithm works. Next time I am going to show you how to use this algorithm to create dynamic light and shadows, meanwhile if you already have some idea, you can download the source code and start from here.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

214 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers