update_consumers.worker.js

/* eslint-disable */

/*

Webworker to update the consumer network.

Recieves workload messages from the main thread and responds once a solution
has been found.

*/


// Verbose level, set via api from main thread
var VERBOSE = false

// Cached node net & entities
var globalNodeNet = null
var globalEntities = null

// Constants duplicated from Config
var transporterRadius = 3.5 * 1.01
var resourceSpeedTilesPerSecond = 1

var transporterRadiusSquared = transporterRadius * transporterRadius;

// Jobs in queue
var jobQueue = []

// Serialization, must match update_possible_consumers.js!
const KEY_TRANSPORTER = "0"
const KEY_EMITTER = "1"
const KEY_CONSUMER = "2"
const CP_BIAS = 256
const CP_MULTIPLIER = 200 // == Config.numTilesX
const DATA_DIVISOR = "_"

// Message handler
self.onmessage = function (msg) {
	const cmd = msg.data.cmd
	const payload = msg.data.payload
	const jobId = msg.data.jobId
	
	if (cmd === "setVerboseLevel") {
		// Set verbosity level
		VERBOSE = payload;
		if (VERBOSE) {
			console.log("[WEBWORKER] Verbose =", VERBOSE)
		}
	} else if (cmd === "onNewNodeNet") {
		// New network recieved
		if (VERBOSE) {
			console.log("[WEBWORKER] Recieved node net")
		}
		
		jobQueue.push({
			cmd: "onNewNodeNet",
			jobId: jobId,
			payload: payload
		});
	} else if (cmd === "computeEntity") {
		// Workload for entity recieved
		if (VERBOSE) {
			console.log("[WEBWORKER] Request entity computation", payload)
		}
		
		jobQueue.push({
			cmd: "computeEntity",
			jobId: jobId,
			payload: payload
		})
	} else if (cmd === "cancelAll") {
		// Net outdated, cancel all
		jobQueue = [];
		
		if (VERBOSE) {
			console.log("[WEBWORKER] Recieved cancel all")
		}
		self.postMessage({
			jobId: jobId,
			sourceCommand: cmd,
			result: null
		});
	}
}

// Recurring job handler
function processJobs() {
	while (jobQueue.length > 0) {
		// Always take first job, FIFO queue
		const job = jobQueue.shift();
		
		if (VERBOSE) {
			console.log("Processing", job);
		}
		
		const cmd = job.cmd;
		const jobId = job.jobId;
		const payload = job.payload;
		
		let result = null;
		
		if (cmd === "onNewNodeNet") {
			// Deserialize node net and store it
			if (VERBOSE) {
				console.log("Storing new node net")
			}
			globalNodeNet = deserializeNodeNet(payload.nodeNet);
			globalEntities = deserializeEntities(payload.entities);
		} else if (cmd === "computeEntity") {
			// Compute entity
			if (VERBOSE) {
				console.log("computing entity")
			}
			
			const uid = payload.ui;
			const hash = payload.hash;
			result = computeEntity(uid, hash);
		}
		
		// Post job done message to notify main thread that work has been done
		self.postMessage({
			jobId: jobId,
			sourceCommand: cmd,
			result: result
		});
	}
}

// Poll for new job each N ms
setInterval(processJobs, 50);

// Deserializes a float from an utf16 codepoint
function deserializeFloat(str, index) {
	return (str.codePointAt(index) - CP_BIAS) / 100.0;
}

// Deserializes an integer from an utf16 codepoint
function deserializeInt(str, index) {
	return str.codePointAt(index) - CP_BIAS;
}

// Deserializes the node net from an binary encoded utf16 string
function deserializeNodeNet(binaryStr) {
	// Format: [fromEntityHash] ([toEntityHash] [toEntityDistance])+ DATA_DIVISOR
	let index = 0;
	let result = {};
	
	if (VERBOSE) {
		console.log("[WEBWORKER] Parsing nodenet of length", binaryStr.length);
	}
	while (index < binaryStr.length) {
		if (binaryStr[index] === DATA_DIVISOR) {
			index += 1;
			continue;
		}
		let startNodeId = binaryStr[index++];
		let distances = {};
		while (binaryStr[index] !== DATA_DIVISOR && index < binaryStr.length) {
			let connectedNode = binaryStr[index++];
			const distance = deserializeFloat(binaryStr, index++);
			distances[connectedNode] = distance;
		}
		result[startNodeId] = distances;
	}
	
	if (VERBOSE) {
		console.log("[WEBWORKER] Parsed net:", result);
	}
	return result;
}

// Decodes tile space position from an entity hash (utf16 codepoint)
function decodePositionFromHash(str, index) {
	const code = str.codePointAt(index) - CP_BIAS;
	const tileX = code % CP_MULTIPLIER;
	const tileY = Math.floor(code / CP_MULTIPLIER);
	return { x: tileX, y: tileY };
}

// Deserializes the entity list
function deserializeEntities(binaryStr) {
	// Format: [entityHash] ([component] [copmonentData]+)+ DATA_DIVISOR
	const result = {};
	
	let index = 0;
	
	// Read in entities
	while (index < binaryStr.length) {
		if (binaryStr[index] === DATA_DIVISOR) {
			index += 1;
			continue;
		}
		
		// Get hash & position from hash
		const hash = binaryStr[index];
		const entityData = decodePositionFromHash(binaryStr, index++);
		
		// Read in components
		while (binaryStr[index] !== DATA_DIVISOR) {
			const componentId = binaryStr[index++];
			
			if (componentId === KEY_TRANSPORTER) {
				// Read transporter component
				
				const speed = deserializeFloat(binaryStr, index++);
				entityData.transporter = { speed: speed };
			} else if (componentId === KEY_CONSUMER) {
				// Read consumer component
				
				const resources = [];
				const numResources = deserializeInt(binaryStr, index++);
				for (let i = 0; i < numResources; ++i) {
					resources.push(binaryStr[index++]);
				}
				entityData.consumer = { resources: resources };
			} else if (componentId === KEY_EMITTER) {
				// Read emitter component
				
				const resource = binaryStr[index++];
				const maxRadius = deserializeFloat(binaryStr, index++);
				entityData.emitter = { resource: resource, spawnMaxRadius: maxRadius };
			} else {
				// Unkown
				throw new Error("Invalid component id: " + componentId);
			}
		}
		result[hash] = entityData;
	}
	return result;
}

// Helper method copied from utils.js
function newEmptyMap() {
	return Object.create(null);
}

// Converts from an entity hash to the entity handle by looking up in the global dict
function hashToEntity(hash) {
	if (!globalEntities[hash]) {
		if (VERBOSE) {
			console.log("NODENET:", globalEntities, "REQUESTED:", hash);
		}
		throw new Error("Invalid hash: " + hash);
	}
	return globalEntities[hash];
}

// Gets tile space distance between two entities
function distanceBetweenEntities(entityA, entityB) {
	return Math.hypot(entityA.x - entityB.x, entityA.y - entityB.y);
}

// Gets squared tile space distance between two entities
function distanceBetweenEntitiesSquared(entityA, entityB) {
	var delta_x = entityA.x - entityB.x;
	var delta_y = entityA.y - entityB.y;
	return delta_x * delta_x + delta_y * delta_y;
}

// Returns whether the entity consumes the given resource
function entityConsumesResource(entity, resourceId) {
	return entity.consumer.resources.indexOf(resourceId) >= 0;
}

// Checks if the transport between two entities is possible
function transportIsPossible(startEntity, consumerEntity, targetResourceId) {
	// Dont emit to ourself
	if (startEntity === consumerEntity) {
		return false;
	}
	
	const startEmitterComponent = startEntity.emitter;
	const distance_squared = distanceBetweenEntitiesSquared(startEntity, consumerEntity);
	
	if (startEmitterComponent && (false
		|| consumerEntity.transporter
		|| consumerEntity.consumer
	)) {
		if (distance_squared <= startEmitterComponent.spawnMaxRadius * startEmitterComponent.spawnMaxRadius) {
			// Check for emitter -> transporter
			if (consumerEntity.transporter) {
				// Check for same resource
				if (!targetResourceId || startEmitterComponent.resource === targetResourceId) {
					return true;
				}
			}
			
			// Check for emitter -> consumer
			if (consumerEntity.consumer) {
				// Check for same resource
				if (entityConsumesResource(consumerEntity, startEmitterComponent.resource)) {
					return true;
				}
			}
		}
	}
	
	// Check for transporter -> consumer (don't care about resource type here, too)
	const startTransporterComponent = startEntity.transporter;
	if (startTransporterComponent && consumerEntity.consumer) {
		if (!targetResourceId || entityConsumesResource(consumerEntity, targetResourceId)) {
			if (distance_squared <= transporterRadiusSquared) {
				return true;
			}
		}
	}
	
	// Check for transporter -> transporter
	if (startTransporterComponent && consumerEntity.transporter) {
		if (distance_squared <= transporterRadiusSquared) {
			return true;
		}
	}
	
	return false;
}

// Checks if the direct consume between both entities would be fine, while
// ignoring transporters. This behaves like transportIsPossible for the only
// case Emitter -> Consumer
function isEndConsumerFor(emitterEntity, targetEntity) {
	// Dont emit to ourself
	if (emitterEntity === targetEntity) {
		return false;
	}
	
	// Check for a consumer component
	const consumerComp = targetEntity.consumer;
	if (!consumerComp) {
		return false;
	}
	
	// Check if the consumer component accepts the emitters component resources
	const emitterComp = emitterEntity.emitter;
	const resourceId = emitterComp.resource;
	if (entityConsumesResource(targetEntity, resourceId)) {
		return true;
	}
	return false;
}

// Travels the node net to compute the distances (dijkstra)
function travelNodeNet(entity, travelDistancesInOut, endNodesInOut, start, targetResourceId) {
	// Use a stack instead of recursion (faster)
	const stack = [
		[start, 0]
	];
	
	// While there are nodes to visit ...
	while (stack.length > 0) {
		// ... pop next node
		const [currentNode, currentPathLength] = stack.pop();
		
		const children = globalNodeNet[currentNode];
		const currentStartEntity = hashToEntity(currentNode);
		
		// Look at all children
		for (/* const */ childHash in children) {
			const distanceToChild = currentPathLength + children[childHash];
			
			// Check if the current path is better, either it is shorter or there
			// was no path so far
			if (false
				|| travelDistancesInOut[childHash] === undefined // eslint-disable-line no-undefined
				|| travelDistancesInOut[childHash] > distanceToChild
			) {
				const childEntity = hashToEntity(childHash);
				// Only visit the child if a transport is actually possible
				if (transportIsPossible(currentStartEntity, childEntity, targetResourceId)) {
					// Store new best way
					travelDistancesInOut[childHash] = distanceToChild;
					
					// Visit children of transporters
					if (childEntity.transporter) {
						stack.push([childHash, distanceToChild]);
					}
					
					// If we found a consumer, store that if its compatible
					if (isEndConsumerFor(entity, childEntity)) {
						endNodesInOut[childHash] = distanceToChild;
					}
				}
			}
		}
	}
}

// Computes the traveling distances inside the node net, starting at the entities position
// Mainly a starter for travelNodeNet()
function computeTravelDistances(entity, startHash) {
	// Start has a distance of 0
	const travelDistances = newEmptyMap();
	travelDistances[startHash] = 0;
	
	const endNodes = newEmptyMap();
	const targetResourceId = entity.emitter.resource;
	travelNodeNet(entity, travelDistances, endNodes, startHash, targetResourceId);
	return { travelDistances: travelDistances, endNodes: endNodes };
}

// Determines the transport speed of a given entity
function determineTransportSpeed(entity) {
	if (entity.transporter) {
		return entity.transporter.speed;
	}
	return resourceSpeedTilesPerSecond;
}

// Determines the transport speed between two entities
// IMPORTANT: Must be bidirectional, e.g. speed(a, b) === speed(b, a)
function determineTransportSpeedBetween(start, end) {
	// Get individual speed
	const startSpeed = determineTransportSpeed(start);
	const endSpeed = determineTransportSpeed(end);
	
	// If either start or end is a transporter, use that speed
	// So consumer ---> transporter is already fast (otherwise looks weird)
	if (start.transporter) {
		if (end.consumer || end.emitter) {
			return startSpeed;
		}
	}
	if (end.transporter) {
		if (start.consumer || start.emitter) {
			return endSpeed;
		}
	}
	
	// Otherwise just take the average
	return (startSpeed + endSpeed) / 2;
}

// Find a path by simply going the path of the least weights
function findPathToConsumer(start, end, travelDistances, targetResourceId) {
	let currentPosition = end;
	let maxIterations = 999;
	const path = [];
	
	// As long as we don't meet our starting point, iterate
	while (currentPosition !== start && maxIterations-- > 0) {
		// We are now at <currentPosition>
		const connections = globalNodeNet[currentPosition];
		
		let bestNext = null;
		let bestNextLength = 1e20;
		const currentEntity = hashToEntity(currentPosition);
		
		// Find the children with the least distance
		for (/* const */ connectedHash in connections) {
			// Take the speed into account which we need to travel the given
			// distance. Longer ways might actually be faster when the transport speed
			// is faster
			const connectedEntity = hashToEntity(connectedHash);
			const tileSpaceDistance = distanceBetweenEntities(currentEntity, connectedEntity);
			const speed = determineTransportSpeedBetween(currentEntity, connectedEntity);
			const weight = tileSpaceDistance / speed;
			
			const nodeWeight = travelDistances[connectedHash] + weight;
			
			if (nodeWeight < bestNextLength) {
				// Found a theoretically better children than the current one
				// - however, check if transport is actually possible
				if (transportIsPossible(connectedEntity, currentEntity, targetResourceId)) {
					bestNextLength = nodeWeight;
					bestNext = connectedHash;
				}
			}
		}
		
		// When no child was found, something must be very wrong, since we
		// can not find a way, although there must be one
		if (bestNext === null) {
			// Debug output to figure out whats going on
			console.error("Invalid node net, for ", currentPosition, "there are no valid children");
			console.error("- Started from =", globalEntities[start]);
			console.error("- Target end =", globalEntities[end]);
			console.error("- Path so far =", path.map((entry), " => ", globalEntities[entry]));
			console.error("- Current Entity =", globalEntities[currentPosition]);
			return null;
		}
		
		// Don't push start and end to the path
		if (bestNext !== end && bestNext !== start) {
			path.push(bestNext);
		}
		
		// Go to the children
		currentPosition = bestNext;
	}
	
	// Since we traverse from end -> start, reverse the path
	return path.reverse();
}

// Updates the paths of a given entity
function computeEntity(uid, startHash) {
	const entity = globalEntities[startHash];
	
	// Store the distances so far
	const { travelDistances, endNodes } = computeTravelDistances(entity, startHash);
	const targetResourceId = entity.emitter.resource;
	const result = [];
	
	// Find paths to all consumers
	for (/* const */ hash in endNodes) {
		const path = findPathToConsumer(startHash, hash, travelDistances, targetResourceId);
		if (path) {
			result.push({
				entity: hash,
				stops: path
			});
		}
	}
	
	return {
		uid: uid,
		hash: startHash,
		result: result,
	};
}