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

// 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)
}

// 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 = null) {

    // Dont emit to ourself
    if (startEntity === consumerEntity) {
        return false
    }

    const startEmitterComponent = startEntity.emitter
    const distance = distanceBetweenEntities(startEntity, consumerEntity)

    // Check for emitter -> transporter
    if (startEmitterComponent && consumerEntity.transporter) {
        // Check for same resource
        if (!targetResourceId || startEmitterComponent.resource === targetResourceId) {
            if (distance <= startEmitterComponent.spawnMaxRadius) {
                return true
            }
        }
    }

    // Check for emitter -> consumer
    if (startEmitterComponent && consumerEntity.consumer) {
        // Check for same resource
        if (entityConsumesResource(consumerEntity, startEmitterComponent.resource)) {
            if (distance <= startEmitterComponent.spawnMaxRadius) {
                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 <= transporterRadius) {
                return true
            }
        }
    }

    // Check for transporter -> transporter
    if (startTransporterComponent && consumerEntity.transporter) {
        if (distance <= transporterRadius) {
            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 = null) {

    // 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 ((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,
    }
}