A Line-of-Sight Algorithm for a 2D Game

The JavaScript code below implements a (currently naive and inefficient) line-of-sight algorithm for a grid-based 2D game. To see it in action, copy it into an HTML file and open that file in a web browser that runs JavaScript.  Or, for an online version, visit https://thiscouldbebetter.neocities.org/lineofsight.html.

Use the W, A, S, and D keys to move around. The blue square represents the player’s current position. Brown squares represent walls, which block both vision and movement, while gray squares represent fog, which blocks only vision. Green squares block neither movement nor vision. Black squares are not visible from the player’s current position, either because they are obscured by obstacles or outside the maximum viewing range.

UPDATE 2014/05/17 – Hm, I’m not sure how well the fog works, as you can see in the screenshot below.  Back to the lab!  Well, maybe someday.

UPDATE 2015/03/16 – Finally got a chance to look at this again, and it turns out that even at the time of my previous update I had already fixed it in another post on this site, specifically this one. The problem was in the RangeSet.subtract() method, and it looks like the fix involved adding and/or subtracting things from i and adding some more splice statements. That method is a little hard to parse, even for me, and could still use some cleanup, but everything seems to work now.

UPDATE 2015/03/26 – I made some more slight changes. Before, if the player was standing in the middle of a rectangular room, he couldn’t see the corner squares of that room, because it was blocked by the neighboring wall squares. While this might be physically valid, it wasn’t very pleasing aesthetically. The updated version allows the player to see through a “hairline crack” in the corner to see the corner square itself. I added some wall squares to the northwest corner to illustrate this, but I didn’t update the screenshot.

UPDATE 2017/02/13 – I have refactored this code to draw the map to an HTML5 canvas rather than as a DOM table. I also optimized a bit to prevent unnecessary reallocation of temporary variables every time the field of view gets recalculated.

LineOfSight


<html>
<body>
<script type="text/javascript">
 
function main()
{
	var mapTerrains = MapTerrain.Instances._All;

	var map = new Map
	(
		mapTerrains,
		[
			"xx..............",
			"x...............",
			"................",
			"........x.......",
			"..?........?....",
			"..??............",
			"........x.......",
			".....x..........",
			".........x......",
			"...?............",
			"...?.......xx?..",
			"....xxxxx.......",
			"......??.....x..",
			"................",
			"........x.......",
			"................",
		]
	);
 
	var fieldOfView = new FieldOfView
	(
		map, 
		8, // distanceFromEyeMax
		new Coords(8, 8) // eyePos
	);

	var display = new Display(new Coords(256, 256));
 
	Globals.Instance.initialize(display, fieldOfView);

	Globals.Instance.update();
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.addLookups = function(keyName)
	{
		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var key = element[keyName];
			this[key] = element;
		}
		return this;
	}
}

 
// classes
 
function Constants()
{
	// static class
}
{
	Constants.RadiansPerCycle = Math.PI * 2;
}
 
function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}
 
	Coords.prototype.clone = function(other)
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}
 
	Coords.prototype.isInRange = function(rangeMax)
	{
		var returnValue = 
		(
			this.x >= 0
			&& this.x <= rangeMax.x
			&& this.y >= 0
			&& this.y <= rangeMax.y
		);
 
		return returnValue;
	}
 
	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}
 
	Coords.prototype.overwriteWithXY = function(x, y)
	{
		this.x = x;
		this.y = y;
		return this;
	}
 
	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function Display(sizeInPixels)
{
	this.sizeInPixels = sizeInPixels;
	this.colorBack = "Black";
	this.colorFore = "Gray";
}
{
	Display.prototype.initialize = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.sizeInPixels.x;
		canvas.height = this.sizeInPixels.y;

		this.graphics = canvas.getContext("2d");

		document.body.appendChild(canvas);
	}

	// drawing

	Display.prototype.drawRectangle = function(pos, size, colorFill, colorBorder)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect(pos.x, pos.y, size.x, size.y);
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect(pos.x, pos.y, size.x, size.y);
		}
	}
}
 
function FieldOfView(map, distanceFromEyeMax, eyePos)
{
	this.map = map;
	this.distanceFromEyeMax = distanceFromEyeMax;
	this.eyePos = eyePos;

	this.cellPositionsVisible = [];

	// helper variables

	this.directionsForSides = 
	[
		new Coords(-1, 1),
		new Coords(-1, -1),
		new Coords(1, -1),
		new Coords(1, 1),
	];

	this.cornerAddendsForSides = 
	[
		new Coords(0, 0),
		new Coords(0, -1),
		new Coords(1, 0),
		new Coords(0, 1),
	];

	this.cellPos = new Coords();
	this.cellPosRelative = new Coords();
	this.vertexPosRelative0 = new Coords();
	this.vertexPosRelative1 = new Coords();
}
{
	// methods

	FieldOfView.prototype.calculate = function()
	{
		var radiansPerCycle = Constants.RadiansPerCycle;
 
		var eyePosCentered = this.eyePos.clone().add(new Coords(.5, .5));

		this.cellPositionsVisible.length = 0;

		var angleRangeSetNotYetBlocked = new RangeSet
		([
			new Range(0, 1)
		]);
		 
		for (var r = 1; r <= this.distanceFromEyeMax; r++)
		{
			this.cellPosRelative.overwriteWithXY(r, 0);
 
			this.vertexPosRelative0.overwriteWithXY(r - .5, -.5);		  
			this.vertexPosRelative1.overwriteWithXY(r - .5, .5);
 
			for (var s = 0; s < this.directionsForSides.length; s++)
			{
				this.calculate_RadiusAndSide
				(
					r, s, angleRangeSetNotYetBlocked
				);
			}
		}
	}

	FieldOfView.prototype.calculate_RadiusAndSide = function
	(
		r, s, angleRangeSetNotYetBlocked
	)
	{
		var cellPosRelative = this.cellPosRelative;
		var cellPos = this.cellPos;
		var vertexPosRelative0 = this.vertexPosRelative0;
		var vertexPosRelative1 = this.vertexPosRelative1;

		var direction = this.directionsForSides[s];
 
		var cornerAddend = 
			this.cornerAddendsForSides[s];
		vertexPosRelative1.add(cornerAddend);
 
		for (var d = 0; d < r; d++)
		{
			cellPos.overwriteWith
			(
				this.eyePos
			).add
			(
				cellPosRelative
			);
 
			var isCellInMapBounds = cellPos.isInRange
			(
				this.map.sizeInCellsMinusOnes
			);

			if (isCellInMapBounds == true)
			{
				var cellSpan = new Range
				(
					NumberHelper.atan3(vertexPosRelative0),
					NumberHelper.atan3(vertexPosRelative1)
				);
 
				var cellSpanAsSet = new RangeSet( [ cellSpan ] );

				cellSpanAsSet.splitRangesThatSpanPeriod(1);

				var isCellVisible = cellSpanAsSet.overlaps
				(
					angleRangeSetNotYetBlocked
				);

				if (isCellVisible == true)
				{
					this.cellPositionsVisible.push
					(
						cellPos.clone()
					);
 
					var cellAtPos = this.map.cellAtPos
					(
						cellPos
					);

					var cellTerrain = cellAtPos.terrain;

					var cellBlocksVision = cellTerrain.blocksVision;
				
					if (cellBlocksVision == true)
					{
						angleRangeSetNotYetBlocked.subtract
						(
							cellSpanAsSet
						);
					}
				}
			}

			cellPosRelative.add(direction);
			vertexPosRelative0.overwriteWith(vertexPosRelative1);
			vertexPosRelative1.add(direction);
		}
	}

	// drawable


	FieldOfView.prototype.drawToDisplay = function(display)
	{
		var fieldOfView = this;

 		var map = fieldOfView.map;
		var mapSizeInCells = map.sizeInCells;
		var mapCellSizeInPixels = display.sizeInPixels.clone().divide
		(
			mapSizeInCells
		);
 
		var cellPosInCells = new Coords();
		var cellPosInPixels = new Coords();
 
		for (var y = 0; y < mapSizeInCells.y; y++)
		{
			cellPosInCells.y = y;
 
			for (var x = 0; x < mapSizeInCells.x; x++)
			{
				cellPosInCells.x = x;

				cellPosInPixels.overwriteWith
				(
					cellPosInCells
				).multiply
				(
					mapCellSizeInPixels
				);
 
				display.drawRectangle
				(
					cellPosInPixels, 
					mapCellSizeInPixels,
					display.colorBack, // colorFill
					display.colorFore // colorBorder
				);				
			}   
		}
 
		var map = fieldOfView.map;
		var cellPositionsVisible = fieldOfView.cellPositionsVisible;

		for (var i = 0; i < cellPositionsVisible.length; i++)
		{
			cellPosInCells = cellPositionsVisible[i];
 
			var cell = map.cellAtPos(cellPosInCells);
 
			cellPosInPixels.overwriteWith
			(
				cellPosInCells
			).multiply
			(
				mapCellSizeInPixels
			);
 
			display.drawRectangle
			(
				cellPosInPixels, 
				mapCellSizeInPixels,
				cell.terrain.color,
				display.colorFore // colorBorder
			);
		}

		var eyePosInCells = fieldOfView.eyePos;
		cellPosInPixels.overwriteWith
		(
			eyePosInCells
		).multiply
		(
			mapCellSizeInPixels
		);

		display.drawRectangle
		(
			cellPosInPixels, mapCellSizeInPixels, 
			"Blue", display.colorFore
		);
	}
}
 
function Globals()
{
	// do nothing
}
{
	Globals.Instance = new Globals();
 
	Globals.prototype.initialize = function(display, fieldOfView)
	{
		this.display = display;
		this.fieldOfView = fieldOfView;

		this.display.initialize();

		this.inputHelper = new InputHelper();
		this.inputHelper.initialize();  
	}

	Globals.prototype.update = function()
	{
		this.fieldOfView.calculate();   
 		this.fieldOfView.drawToDisplay(this.display);
	}
}
 
function InputHelper()
{}
{
	InputHelper.prototype.initialize = function()
	{
		document.body.onkeydown = InputHelper.processKeyDownEvent;
 
		this.keyNameToDirectionLookup = [];
		this.keyNameToDirectionLookup["a"] = new Coords(-1, 0);
		this.keyNameToDirectionLookup["d"] = new Coords(1, 0);
		this.keyNameToDirectionLookup["s"] = new Coords(0, 1);
		this.keyNameToDirectionLookup["w"] = new Coords(0, -1);
	}   
 
	InputHelper.processKeyDownEvent = function(event)
	{
		var inputHelper = Globals.Instance.inputHelper;
 
		var keyPressed = event.key;
 
		var directionToMove = inputHelper.keyNameToDirectionLookup[keyPressed];
 
		if (directionToMove != null)
		{
			var fieldOfView = Globals.Instance.fieldOfView;
			var eyePosNext = fieldOfView.eyePos.clone().add
			(
				directionToMove
			);
 
			var map = fieldOfView.map;
 
			if (eyePosNext.isInRange(map.sizeInCellsMinusOnes) == true)
			{
				var cellAtPos = map.cellAtPos(eyePosNext);
 
				if (cellAtPos.terrain.blocksMovement == false)
				{
					fieldOfView.eyePos.overwriteWith(eyePosNext);
					Globals.Instance.update();
				}
			}
		}
	}
 
}
 
function Map(terrains, cellsAsStrings)
{
	this.terrains = terrains;
	this.cellsAsStrings = cellsAsStrings;
	this.sizeInCells = new Coords
	(
		this.cellsAsStrings[0].length, 
		this.cellsAsStrings.length
	);
 
	this.sizeInCellsMinusOnes = this.sizeInCells.clone().subtract
	(
		new Coords(1, 1)
	);
}
{
	Map.prototype.cellAtPos = function(cellPos)
	{
		var codeCharForCell = this.cellsAsStrings[cellPos.y][cellPos.x];
 
		var terrainForCell = this.terrains[codeCharForCell];
 
		var returnValue = new MapCell
		(
			terrainForCell  
		);  
 
		return returnValue;
	}
}
 
function MapCell(terrain)
{
	this.terrain = terrain;
}
 
function MapTerrain(name, codeChar, blocksVision, blocksMovement, color)
{
	this.name = name;
	this.codeChar = codeChar;
	this.blocksVision = blocksVision;
	this.blocksMovement = blocksMovement;
	this.color = color;
}
{
	function MapTerrain_Instances()
	{
		if (MapTerrain.Instances != null)
		{
			return MapTerrain.Instances;
		}
 
		MapTerrain.Instances = this;		
 
		this.Wall = new MapTerrain("Wall", "x", true, true, "Brown");
		this.Open = new MapTerrain("Open", ".", false, false, "Green");
		this.Fog = new MapTerrain("Fog", "?", true, false, "Gray");
 
		this._All = 
		[
			this.Fog,
			this.Open,
			this.Wall,
		].addLookups("codeChar");
 	}
 
	MapTerrain.Instances = new MapTerrain_Instances();
}
 
function NumberHelper()
{
	// static class
}
{
	NumberHelper.atan3 = function(coordsToFind)
	{
		var returnValue = Math.atan2(coordsToFind.y, coordsToFind.x);
 
		if (returnValue < 0)
		{
			returnValue += Constants.RadiansPerCycle;
		}
 
		returnValue /= Constants.RadiansPerCycle;
 
		return returnValue;
	}
}
 
function Range(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Range.prototype.clone = function()
	{
		return new Range(this.min, this.max);
	}
 
	Range.prototype.overlaps = function(other)
	{
		var returnValue =
		(
			this.min < other.max
			&& this.max > other.min
		);
 
		return returnValue;
	}
 
	Range.prototype.subtract = function(other)
	{	   
		var returnValues = [];
 
		if (this.overlaps(other) == true)
		{
			if (this.min <= other.min)
			{
				var segment = new Range(this.min, other.min);
				returnValues.push(segment);
			}
			 
			if (this.max >= other.max)
			{
				var segment = new Range(other.max, this.max);
				returnValues.push(segment);
			}
		}
		else
		{
			returnValues.push(this);
		}
 
		return returnValues;
	}
 
	 
}
 
function RangeSet(ranges)
{
	this.ranges = ranges;
}
{
	RangeSet.prototype.overlaps = function(other)
	{
		var returnValue = false;
 
		for (var i = 0; i < this.ranges.length; i++)
		{
			var rangeThis = this.ranges[i];
 
			for (var j = 0; j < other.ranges.length; j++)
			{
				var rangeOther = other.ranges[j];
 
				if (rangeThis.overlaps(rangeOther) == true)
				{
					returnValue = true;
					i = this.ranges.length;
					break;
				}
			}
		}	   
 
		return returnValue;
	}
 
	RangeSet.prototype.splitRangesThatSpanPeriod = function(period)
	{
		for (var i = 0; i < this.ranges.length; i++)
		{
			var range = this.ranges[i];
 
			if (range.min > range.max)
			{
				var rangePart0 = new Range(0, range.max);
				var rangePart1 = new Range(range.min, period);
 
				this.ranges.splice(i, 1, rangePart0, rangePart1);   
				i++;
			}
		}
	}
 
	RangeSet.prototype.subtract = function(other)
	{
		var rangesCurrent = this.ranges;
 
		var doAnyRangesOverlap = true;
 
		while (doAnyRangesOverlap == true)
		{
			doAnyRangesOverlap = false;
 
			for (var i = 0; i < rangesCurrent.length; i++)
			{
				var rangeThis = rangesCurrent[i];
	 
				for (var j = 0; j < other.ranges.length; j++)
				{
					var rangeOther = other.ranges[j];
	 
					if (rangeThis.overlaps(rangeOther) == true)
					{
						doAnyRangesOverlap = true;
						var rangesSubtracted = rangeThis.subtract
						(
							rangeOther
						);
						rangesCurrent.splice(i, 1);
						for (var k = rangesSubtracted.length - 1; k >= 0; k--)
						{
							rangesCurrent.splice(i, 0, rangesSubtracted[k]);
						}
						break;
					}
				}
			}
		}
 
		this.ranges = rangesCurrent;
	}
}
 
// run
 
main();
 
</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s