Bresenham’s Algorithm in a Turn Based Tile Game — Vanilla Javascript

Thomas Oh

Published in

The Startup

6 min readAug 12, 2020

Screenshot of ‘Alien Hunt’, turn based tile game coded in Vanilla Javascript

Game and Github Links

Inspiration for the Idea

The inspiration and general idea behind this project was XCOM! For the uninitiated (straight from the wiki):

X-COM (sometimes stylized as X-Com or XCOM) is a science fiction video game franchise featuring an elite international organization tasked with countering alien invasions of Earth.

The basic mechanics of the game were that you had an army, the aliens had an army, and both sides took turns trying to attack each other on a two-dimensional tile board. It was honestly one of the most fun games I had ever played (and I usually find turn based games rather dull).

There were of course far more complexities in the actual XCOM produced by 2k Games. My project is a simplified, mini version, but I nevertheless had a blast building it!

Basic Technical Components

I created a HTML representation of the board (a 10x10 grid), a 2d array that would store the game state, a global variable to save the current position of the user, and another 2-d array to save the location of all the aliens.

let gameState = [];
let gameBoard = document.getElementById(‘game-board’);
let userPositionRow = 0;
let userPositionColumn = 0;let alienLocations = [] // array of arrays containing all the alien locations

If the player or the alien have line of sight on each other, depending on how close they are to each other, the likelihood of attack success increases.

if (lineOfSight()){        
    attackButton.id = "attack-button";        
    attackButton.innerText = "Attack!";        
    attackProbability = 100 - (lineOfSightArray.length * 10);
    ...       
}

The main technical challenge then, apart from figuring out all the game logic, was determining when “line of sight” shall exist. As I implemented ‘walls’ into the game that allowed the player to hide from the aliens (and vice versa), this was a critical component.

Exploring Bresenham’s Line Algorithm

I realised I had two main options to determine when line of sight is available:

There must be a perfectly horizontal, vertical or 45 degree line between the alien and the player. This would be easy to code, but pretty lame.
If an imaginary line drawn between two squares did not intersect any walls, line of sight would exist. More challenging, but much more cool.

I naturally went with the second option, and my research first took me to Bresenham’s Line Algorithm. In plain english (at least in the way I understood it), the algorithm rasterizes a line between two squares on a 2-d grid. It turns a theoretical straight line into a bunch of squares.

Picture taken from https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Basically, I would imagine the player at the upper leftmost square of the picture above, and the alien at the bottom rightmost square. An implementation of the algorithm chooses which squares to shade grey — therefore, the idea was that if none of these grey squares were a ‘wall’ on my game board, there would be line of sight!

I used the following resources when learning. The last article in particular was really helpful.

So this was the implementation of the algorithm in my game. The “line of sight array” basically contained the squares which were part of the rasterized line, and the function checks if any of these squares were considered a wall (based on my pre-set game state).

let lineOfSight = () => {    
    lineOfSightArray = [];    
    let x0 = userPositionColumn;
    let y0 = userPositionRow;    
    let x1 = alienPositionColumn;    
    let y1 = alienPositionRow;    let dx = Math.abs(x1 - x0);    
    let dy = Math.abs(y1 - y0);    
    let sx = x0 < x1 ? 1 : -1;    
    let sy = y0 < y1 ? 1 : -1;        let err = (dx > dy ? dx : -dy) / 2; 
    while (true) {        
       lineOfSightArray.push(gameState[y0][x0]);        
       if (x0 === x1 && y0 === y1) {            
          break;        
       }        
       if (err > -dx) {            
          err -= dy;            
          x0 += sx;        
       }        
       if (x0 === x1 && y0 === y1) {
          break;        
       }        
       if (err < dy) {            
          err += dx;            
          y0 += sy;        
       }        
       if (x0 === x1 && y0 === y1) {
          break;        
       }    
    }    
   console.log(lineOfSightArray)    
   if (lineOfSightArray.includes("wall")){        
      return false;    
   }    
   return true;    
}

All credit goes to JsTut. I more or less adapted his Javascript version of the algorithm, to be used in my game. His article on the algorithm can be found here (link).

Note —the code shown above is for level 1 of the game. Level 2 and the subsequent levels builds on the same ideas of level 1, but allows for multiple aliens and slightly more complex logic.

Note — I spoke to a gamedev friend of mine after working on this and he mentioned that ray-casting is the way most developers do line of sight these days. I understand that it’s a really complex area, but one worth really exploring for those who are interested.

Planning the Game

I’ve included some of my scribblings on my notebook (like, a book with paper in it). Its probably impossible to read and make sense of my writing here, but these were really important in helping me (a) understand Bresenham’s algorithm a bit better, and (b) planning out the logic sequences in the game (e.g. player turn, player choices, alien turn, randomizing alien movement, etc.).

Conclusion

Working on this project, I had a few key takeaways:

Pen and Paper — Using pen and paper to plan and break down complex problems can really help! Being able to quickly sketch out ideas, draw arrows, and make rough ugly plans on pen and paper can sometimes be better than typing it out. In this project, pen and paper allowed me think through problems a lot faster.
Have confidence in your ability to learn things — When I first realised that implementing line of sight functionality in the game would require me to learn and understand an algorithm (including the math behind it), it was quite daunting. However, as I researched the algo further I realise that my GCE A-Level math would be sufficient to carry me through, and I really should give implementing it a go.

It is important to try and demystify seemingly difficult problems with research, and properly assess whether one has the capacity to figure it out ~ you might be surprised with the results!

Power of plain ol’ Javascript — Last of all, in a world full of web frameworks and fancy libraries, it’s pretty crazy how much plain ol’ Javascript, without any backend servers or database, can do!

Thanks for reading! Feel free to ask me any questions about the code or my process :)