cast some shadows already

assumptions:

all cells have a diameter of 1, this works for a classic rogue grid and a hexagonal tiling

transform positions of all cells such that the player is at (0,0). iterate over cells in ascending distance from the player, i just calculated distance to each cell, added it to the list if distance was less than vision radius, and sorted an array. the array sort ended up being slower than the shadowcasting algorithm itself, but u could breadth-first get cell neighbours or use some other kind of graph traversal method depending on the coordinate system.

we need one more helper function, getting the points that two tangent lines intersect a circle with radius 0.5 from (0,0). i called this function tshape: desmos graph

function tshape(p, r=0.5, _left=array_create(2), _right=array_create(2)) {
	var d = point_distance(0, 0, p[0], p[1]);
	
	var a = r * r / d;
	var b = sqrt(r * r - a * a);
	a = d-a;
	
	// get unit vectors
	var ux = p[0] / d;
	var uy = p[1] / d;
	var vx = -uy;
	var vy = ux;
	
	// au ± bv
	_left[0] = a*ux+b*vx;
	_left[1] = a*uy+b*vy;
	
	_right[0] = a*ux-b*vx;
	_right[1] = a*uy-b*vy;
	
	return {
		left: _left,
		right: _right,
	};
}

i tried simply using a tangent of length 0.5 to the vector p, however in hexagonal grids this left a small gap in adjacent cells

pseudocode for the shadowcasting algorithm:

let shadows = empty list of Sectors
for each c in cells: (ascending distance from (0,0))
	if vision engulfed: break
	if dist to c > vision radius: break
	
	let reveal = true
	let sect = new Sector using tshape of cell
	let sect_original = copy of sect
	for each s in shadows:
		if sect overlaps s:
			sect = difference(sect, s)
			if sect empty:
				# tile is not visible
				reveal = false;
				break
	
	if reveal:
		reveal cell c
		if c opaque:
			merge sect_original into shadows
			if merge detects an engulfed sector:
				# no more cells are visible
				break

implementation:

	var shadows = [];
	
	var engulf = false;
	var tsleft = [ 0, 0 ];
	var tsright = [ 0, 0 ];
	for (var i = 0; i < array_length(dat); i++) {
		var next = dat[i];
		
		if (next.r == 0) {
			revealTile(next);
			continue;
		}
		
		if (engulf || next.r > visionRadius) {
			break;
		}
		
		var reveal = true;
		
		tshape(next.vec, , tsleft, tsright);
		var sect = new Sector(tsleft, tsright);
		var __sect_orig = sect;
		
		for (var j = 0; j < array_length(shadows); j++) {
			var overlap = sect.sectorOverlaps(shadows[j]);
			if (overlap != SECTOR.NONE && overlap != SECTOR.COVERING) {
				var sect2 = sect.sectorDifference(shadows[j]);
				if (sect2 == undefined) {
					reveal = false;
					break;
				}
				else {
					sect = sect2;
				}
			}
		}
		
		if (reveal) {
			revealTile(next);
			if (next.opaque) {
				// insert the original sector for this cell
				// at the beginning of the list
				// for O(n) merge
				array_insert(shadows, 0, __sect_orig);
				if (mergeSectorListFast(shadows) == 1) {
					engulf = true;
				}
			}
		}
	}

if merging the list of sectors on insertion, we only need to check the newest sector against the others. for each union found, replace the two smaller sectors with the new one. if the union covers all 360 degrees, return a different value so we know to stop the shadowcasting early

function mergeSectorListFast(list) {
	var i = 0;
	for (var j = i+1; j < array_length(list); j++) {
		var next = list[i].sectorUnion(list[j]);
		if (next != undefined) {
			if (next.engulfed) {
				return 1;
			}
			array_delete(list, j, 1);
			j--;
			list[i] = next;
		}
	}
	return 0;
}