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.

LineOfSight


<html>
<body>
<script type="text/javascript">

function main()
{
	var map = new Map
	(
		[
			"xx..............",
			"x...............",
			"................",
			"........x.......",
			"..?........?....",
			"..??............",
			"........x.......",
			".....x..........",
			".........x......",
			"...?............",
			"...?.......xx?..",
			"....xxxxx.......",
			"......??.....x..",
			"................",
			"........x.......",
			"................",
		]
	);

	var distanceFromEyeMax = 8;

	var eyePos = new Coords(8, 8);

	var fieldOfView = new FieldOfView(map, distanceFromEyeMax, eyePos);

	Globals.Instance.initialize(fieldOfView);
}

// classes

function Constants()
{}
{
	Constants.Tau = 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.isWithinRange = function(rangeMax)
	{
		var returnValue = 
		(
			this.x >= 0
			&& this.x <= rangeMax.x
			&& this.y >= 0
			&& this.y <= rangeMax.y
		);

		return returnValue;
	}

	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 FieldOfView(map, distanceFromEyeMax, eyePos)
{
	this.map = map;
	this.distanceFromEyeMax = distanceFromEyeMax;
	this.eyePos = eyePos;
}
{
	FieldOfView.prototype.calculate = function()
	{
		var tau = Constants.Tau;

		var eyePosCentered = this.eyePos.clone().add(new Coords(.5, .5));

		this.cellPositionsVisible = [];

		var angleRangeSetNotYetBlocked = new RangeSet
		([
			new Range(0, 1)
		]);

		var displacementFromEyeToCell = new Coords(0, 0);	

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

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

		var cellPos = new Coords(0, 0);
		var cellPosRelative = new Coords(0, 0);
		var vertexPositionsRelative = [ new Coords(0, 0), new Coords(0, 0) ];

		for (var r = 1; r <= this.distanceFromEyeMax; r++)
		{
			cellPosRelative.overwriteWithXY(r, 0);

			vertexPositionsRelative[0].overwriteWith(new Coords(r - .5, -.5));			
			vertexPositionsRelative[1].overwriteWith(new Coords(r - .5, .5));

			for (var s = 0; s < directionsForSides.length; s++)
			{
				var direction = directionsForSides[s];

				vertexPositionsRelative[1].add(cornerAddendsForSides[s]);

				for (var d = 0; d < r; d++)
				{
					cellPos.overwriteWith(this.eyePos).add(cellPosRelative);

					if (cellPos.isWithinRange(this.map.sizeInCellsMinusOnes) == true)
					{
						var cellSpan = new Range
						(
							NumberHelper.atan3(vertexPositionsRelative[0]),
							NumberHelper.atan3(vertexPositionsRelative[1])
						);

						var cellSpanAsSet = new RangeSet( [ cellSpan ] );

						cellSpanAsSet.splitRangesThatSpanPeriod(1);

						if (cellSpanAsSet.overlaps(angleRangeSetNotYetBlocked) == true)
						{
							this.cellPositionsVisible.push
							(
								cellPos.clone()
							);

							var cellAtPos = this.map.cellAtPos(cellPos);
							if (cellAtPos.terrain.blocksVision == true)
							{
								angleRangeSetNotYetBlocked.subtract(cellSpanAsSet);
							}
						}
					}

					cellPosRelative.add(direction);
					vertexPositionsRelative[0].overwriteWith(vertexPositionsRelative[1]);
					vertexPositionsRelative[1].add(direction);
				}
			}
		}
	}

	FieldOfView.prototype.htmlElementBuild = function()
	{
		var returnValue = document.createElement("table");

		var cellSizeInPixels = new Coords(16, 16);

		returnValue.cellPadding = "0px";
		returnValue.cellSpacing = "1px";

		for (var y = 0; y < this.map.sizeInCells.y; y++)
		{
			var tr = document.createElement("tr");

			for (var x = 0; x < this.map.sizeInCells.x; x++)
			{
				var td = document.createElement("td");
				td.style.width = cellSizeInPixels.x + "px";
				td.style.height = cellSizeInPixels.y + "px";
				tr.appendChild(td);
			}	

			returnValue.appendChild(tr);
		}

		this.htmlElement = returnValue;

		this.htmlElementUpdate();

		return returnValue;
	}

	FieldOfView.prototype.htmlElementUpdate = function()
	{
		var cellPos = new Coords(0, 0);

		for (var y = 0; y < this.map.sizeInCells.y; y++)
		{
			cellPos.y = y;

			for (var x = 0; x < this.map.sizeInCells.x; x++)
			{
				cellPos.x = x;

				var cell = this.map.cellAtPos(cellPos);

				this.htmlElement.children[cellPos.y].children[cellPos.x].style.backgroundColor = "#000000";
			}	
		}

		this.htmlElement.children[this.eyePos.y].children[this.eyePos.x].style.backgroundColor = "#0000ff";

		for (var i = 0; i < this.cellPositionsVisible.length; i++)
		{
			var cellPosVisible = this.cellPositionsVisible[i];

			var cellVisible = this.map.cellAtPos(cellPosVisible);

			var htmlElementForCellVisible = this.htmlElement.children[cellPosVisible.y].children[cellPosVisible.x];

			htmlElementForCellVisible.style.backgroundColor = cellVisible.terrain.color;
		}

	}
}

function Globals()
{}
{
	Globals.Instance = new Globals();

	Globals.prototype.initialize = function(fieldOfView)
	{
		this.inputHelper = new InputHelper();
		this.inputHelper.initialize();

		this.fieldOfView = fieldOfView;

		this.fieldOfView.calculate();	

		this.fieldOfView.htmlElementBuild();

		document.body.appendChild(fieldOfView.htmlElement);
	}
}

function InputHelper()
{}
{
	InputHelper.prototype.initialize = function()
	{
		document.body.onkeydown = InputHelper.processKeyDownEvent;

		this.keyCodeToDirectionLookup = [];
		this.keyCodeToDirectionLookup["_65"] = new Coords(-1, 0);
		this.keyCodeToDirectionLookup["_68"] = new Coords(1, 0);
		this.keyCodeToDirectionLookup["_83"] = new Coords(0, 1);
		this.keyCodeToDirectionLookup["_87"] = new Coords(0, -1);
	}	

	InputHelper.processKeyDownEvent = function(event)
	{
		var inputHelper = Globals.Instance.inputHelper;

		var keyCodePressed = "_" + event.keyCode;

		var directionToMove = inputHelper.keyCodeToDirectionLookup[keyCodePressed];

		if (directionToMove != null)
		{
			var fieldOfView = Globals.Instance.fieldOfView;
			var eyePosNext = fieldOfView.eyePos.clone().add
			(
				directionToMove
			);

			var map = fieldOfView.map;

			if (eyePosNext.isWithinRange(map.sizeInCellsMinusOnes) == true)
			{
				var cellAtPos = map.cellAtPos(eyePosNext);

				if (cellAtPos.terrain.blocksMovement == false)
				{
					fieldOfView.eyePos.overwriteWith(eyePosNext);
					fieldOfView.calculate();
					fieldOfView.htmlElementUpdate();
				}
			}
		}
	}

}

function Map(cellsAsStrings)
{
	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 = MapTerrain.Instances._All[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, "#808000");
		this.Open = new MapTerrain("Open", ".", false, false, "#00ff00");
		this.Fog = new MapTerrain("Fog", "?", true, false, "#cccccc");

		this._All = 
		[
			this.Fog,
			this.Open,
			this.Wall,
		];

		for (var i = 0; i < this._All.length; i++)
		{
			var terrain = this._All[i];
			this._All[terrain.codeChar] = terrain;
		}
	}

	new MapTerrain_Instances();
}

function NumberHelper()
{}
{
	NumberHelper.atan3 = function(coordsToFind)
	{
		var returnValue = Math.atan2(coordsToFind.y, coordsToFind.x);

		if (returnValue < 0)
		{
			returnValue += Constants.Tau;
		}

		returnValue /= Constants.Tau;

		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>

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