Something went wrong. Try again.
[READ-ONLY] Mirror of https://github.com/excaliburjs/Excalibur. 🎮 Your friendly TypeScript 2D game engine for the web 🗡️ excaliburjs.com
excalibur excaliburjs game-development game-engine game-framework gamedev games html5-canvas typescript
Something went wrong. Try again.
TypeScript
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774import { Random } from './random';import type { Vector } from './vector';
/** * A unique identifier for a graph node or edge. */export type G_UUID = string & { readonly __brand: unique symbol };
/** * Interface to define data with a custom id */export interface DataWithId { id: G_UUID;}
/** * Return true if obj implement DataWithId interface * @param obj value to test * @returns true if obj implement DataWithId */const isDataWithId = (obj: unknown): obj is DataWithId => { return (obj as DataWithId)?.id !== undefined && typeof (obj as DataWithId).id === 'string';};
interface EdgeOptionsWithWeight { weight: number; useEuclidean?: false; /** * Whether the edge is directed. * @default false */ directed?: boolean;}
interface EdgeOptionsWeightless { weight?: undefined; useEuclidean?: false | undefined; /** * Whether the edge is directed. * @default false */ directed?: boolean;}
interface EdgeOptionsWithEuclidean { weight?: undefined; useEuclidean: true; /** * Whether the edge is directed. * @default false */ directed?: boolean;}
/** * Options for creating a new edge in the graph. */type EdgeOptions = EdgeOptionsWithWeight | EdgeOptionsWithEuclidean | EdgeOptionsWeightless;
/** * A weighted graph data structure. * @template T The type of data stored in each node. */export class Graph<T> { private _nodes: Map<G_UUID, Node<T>>; private _edges: Set<Edge<T>>; adjacencyList: Map<G_UUID, Set<G_UUID>>; id: G_UUID = GraphUUId.generateUUID();
/** * Constructs a new graph data structure. * * This constructor initializes an empty graph with no nodes or edges. */ constructor() { this._nodes = new Map(); this._edges = new Set(); this.adjacencyList = new Map(); }
/** * Adds a new node to the graph with the given data. * @returns The newly created node. */ addNode(data: T, position?: Vector): Node<T> | PositionNode<T> { let newNode; if (position) { newNode = new PositionNode(data, position); } else { newNode = new Node(data); } this._nodes.set(newNode.id, newNode); this.adjacencyList.set(newNode.id, new Set()); return newNode; }
/** * Adds multiple new nodes to the graph with the given data. * @returns A map of all nodes in the graph, including the newly created ones. */ addNodes(nodes: T[]): Map<G_UUID, Node<T>> { for (const node of nodes) { this.addNode(node); } return this._nodes; }
/** * Deletes a node from the graph along with all its associated edges. * This method removes the specified node and any edges connected to it * from the graph. It updates the internal structures to reflect these * changes. * @param node - The node to be deleted from the graph. * @returns A map of all remaining nodes in the graph. */ deleteNode(node: Node<T>): Map<G_UUID, Node<T>> { //delete any edges tied to node const nodeEdges = node.edges; for (const edge of nodeEdges) { this.deleteEdge(edge); }
this.adjacencyList.forEach((value, key) => { value.delete(node.id); });
this._nodes.delete(node.id); this.adjacencyList.delete(node.id); return this._nodes; }
/** * Adds a new edge between two nodes in the graph. If the edge already exists, it does not add a duplicate. * The function allows specifying edge options such as weight and directionality. For undirected edges, * it creates a duplicate edge in the reverse direction and links both edges as partners. * @param from - The source node of the edge. * @param to - The target node of the edge. * @param options - Optional settings for the edge, including weight and directionality. * @returns An array containing the created edge(s). If the edge is directed, the array contains one edge; * if undirected, it contains both the original and the duplicate edge. */
addEdge(from: Node<T>, to: Node<T>, options?: EdgeOptions): Edge<T>[] { //gaurd clauses const existingEdges = Array.from(this._edges).find((edge) => edge.source.id === from.id && edge.target.id === to.id); if (existingEdges) { return []; }
let directed;
if (options) { directed = 'directed' in options ? options.directed : false; } else { directed = false; }
const newEdge = new Edge(from, to, options);
this._edges.add(newEdge); from.registerNewEdge(newEdge); to.registerNewEdge(newEdge); this.adjacencyList.get(from.id)?.add(to.id);
if (!directed) { const duplicateEdge = new Edge(to, from, options); this.adjacencyList.get(to.id)?.add(from.id); this._edges.add(duplicateEdge); to.registerNewEdge(duplicateEdge); from.registerNewEdge(duplicateEdge); //link the two edges together newEdge.linkWithPartner(duplicateEdge); duplicateEdge.linkWithPartner(newEdge); return [newEdge, duplicateEdge]; } return [newEdge]; }
/** * Deletes an edge from the graph. * * This method removes the specified edge and its partner edge (if any) from the graph. * It updates the internal edge set and edge list accordingly. The source and target * nodes of the edge are also updated to reflect the removal of the edge. * @param edge - The edge to be deleted from the graph. */
deleteEdge(edge: Edge<T>) { edge.source.breakEdge(edge); edge.target.breakEdge(edge); this._edges.delete(edge);
const partnerEdge = edge.partnerEdge; if (partnerEdge) { partnerEdge.source.breakEdge(partnerEdge); partnerEdge.target.breakEdge(partnerEdge); this._edges.delete(partnerEdge); } }
/** * The set of nodes in the graph, keyed by their UUID. * * The map returned by this property is a shallow copy of the internal map. * The nodes in this map are not frozen, and may be modified by the caller. * @returns A shallow copy of the graph's internal node map. */ get nodes(): Map<G_UUID, Node<T>> { return this._nodes; }
/** * Gets a node by its UUID. * @param id - The UUID of the node to be retrieved. * @returns The node with the specified UUID, or undefined if no such node exists. */ getNode(id: G_UUID): Node<T> { return this._nodes.get(id)!; }
/** * Retrieves the set of edges in the graph. * * The returned set is a shallow copy of the internal edge set. * Modifications to this set do not affect the graph's internal state. * @returns A set containing all edges in the graph. */ get edges(): Set<Edge<T>> { return this._edges; }
/** * Gets the neighbors of the given node. * * The returned array contains all of the nodes that are directly connected to the given node. * @param node - The node whose neighbors should be retrieved. * @returns An array of nodes that are directly connected to the given node. */ getNeighbors(node: Node<T>): Node<T>[] { return Array.from(this.adjacencyList.get(node.id) ?? []).map((nid) => this.nodes.get(nid)!); }
/** * Checks if two nodes are connected by an edge. * @param node1 - The first node to check. * @param node2 - The second node to check. * @returns true if the nodes are connected, false if not. */ areNodesConnected(node1: Node<T>, node2: Node<T>): boolean { return this.adjacencyList.get(node1.id)?.has(node2.id) ?? false; }
/** * Reset the graph * * Clear all nodes and edges from the graph. */ reset(): void { this._nodes.clear(); this._edges.clear(); this.adjacencyList.clear(); }
/** * Performs a breadth-first search (BFS) on the graph starting from the given node. * * This method explores the graph layer by layer, starting from the specified node. * It visits all nodes that are directly connected to the start node before moving * on to the nodes at the next level of the graph. * @param startNode - The node to start the BFS from. * @returns An array of UUIDs representing the nodes that were visited during the search. * The order of the nodes in the array corresponds to the order in which they * were visited. */ bfs(startNode: Node<T>): G_UUID[] { // Verify the start node exists in the graph if (!this._nodes.has(startNode.id)) { return []; }
const queue: G_UUID[] = [startNode.id]; const visited: Set<G_UUID> = new Set([startNode.id]);
while (queue.length > 0) { const nodeId = queue.shift()!; const neighbors = this.adjacencyList.get(nodeId) || new Set(); for (const neighborId of neighbors) { if (!visited.has(neighborId)) { visited.add(neighborId); queue.push(neighborId); } } } return Array.from(visited); }
/** * Performs a depth-first search (DFS) on the graph starting from the given node. * * This method explores the graph by traversing as far as possible along each * branch before backtracking. It visits all nodes that are reachable from the * start node. * @param startNode - The node to start the DFS from. * @param [visited] - A set of node IDs that have already been visited during * the search. This parameter is optional, and defaults to an * empty set. * @returns An array of UUIDs representing the nodes that were visited during the * search. The order of the nodes in the array corresponds to the order * in which they were visited. */ dfs(startNode: Node<T>, visited: Set<string> = new Set()): G_UUID[] { const startId: G_UUID = startNode.id; if (!this._nodes.has(startId)) { return []; } // Invalid start node
visited.add(startId); let result: G_UUID[] = [startId];
for (const neighbor of this.adjacencyList.get(startId) ?? []) { if (!visited.has(neighbor)) { result = result.concat(this.dfs(this._nodes.get(neighbor)!, visited)); } } return result; }
/** * Creates a new graph from an array of nodes, and adds them all to the graph. * @param nodes - The array of nodes to add to the graph. * @returns The newly created graph. */ static createGraphFromNodes<T>(nodes: T[]): Graph<T> { const graph = new Graph<T>(); graph.addNodes(nodes); return graph; }
/** * Finds the shortest path between two nodes in the graph using Dijkstra's algorithm. * * This method calculates the shortest path from the specified start node to the * specified end node in the graph. It returns an object containing the path and * the total distance of the path. * @param sourcenode - The node from which the search for the shortest path begins. * @returns An object containing: * - `path`: An array of nodes representing the shortest path from startNode to endNode. * If no path is found, this will be `null`. * - `distance`: The total distance of the shortest path. If no path is found, this will * be `Infinity`. */
dijkstra(sourcenode: Node<T>): Array<{ node: Node<T>; distance: number; previous: Node<T> | null }> { const visited: Node<T>[] = []; const unvisited: Node<T>[] = []; const resultArray: Array<{ node: Node<T>; distance: number; previous: Node<T> | null }> = [];
//fill unvisited and resultArray this.nodes.forEach((node) => { unvisited.push(node); resultArray.push({ node, distance: Infinity, previous: null }); });
//start with starting node //add startingnode to result array const startingNodeIndex = resultArray.findIndex((node) => node.node === sourcenode); if (startingNodeIndex === -1) { return []; } resultArray[startingNodeIndex].distance = 0;
visited.push(sourcenode); unvisited.splice(unvisited.indexOf(sourcenode), 1);
let current = sourcenode; const currentEdges = current.edges; const filteredCurrentEdges: Edge<T>[] = Array.from(currentEdges).filter((edge: Edge<T>) => edge.target !== current);
//update result array with distances, which is edge values
for (const edge of filteredCurrentEdges) { const index = resultArray.findIndex((node) => node.node === edge.target);
if (index === -1) { return []; } resultArray[index].distance = edge.weight as number; resultArray[index].previous = current; }
while (unvisited.length > 0) { //get list of unvisited available nodes let listOfAvailableNodes: Node<T>[] = []; let listofAvailableEntries: Array<{ node: Node<T>; distance: number; previous: Node<T> | null }> = []; listofAvailableEntries = resultArray.filter((node) => unvisited.includes(node.node)); listOfAvailableNodes = listofAvailableEntries.map((node) => node.node);
//loop through available nodes and find lowest distance to sourcenode let lowestDistance = Infinity; let lowestDistanceIndex = -1;
if (listOfAvailableNodes.length > 0) { for (let i = 0; i < listOfAvailableNodes.length; i++) { const unVisitiedNode = listOfAvailableNodes[i];
const index = resultArray.findIndex((node) => node.node === unVisitiedNode); if (resultArray[index].distance < lowestDistance) { lowestDistance = resultArray[index].distance; lowestDistanceIndex = index; } } } else { //manage exception //choose node from unvisited list that has lowest distance to source node
lowestDistance = Infinity; lowestDistanceIndex = -1; for (let i = 0; i < unvisited.length; i++) { const unVisitiedNode = unvisited[i]; const index = resultArray.findIndex((node) => node.node === unVisitiedNode); if (resultArray[index].distance < lowestDistance) { lowestDistance = resultArray[index].distance; lowestDistanceIndex = index; } } }
// add test for -1 index representing unreachable node if (lowestDistanceIndex === -1) { break; }
current = resultArray[lowestDistanceIndex].node; let currentEdgesArray = Array.from(current.edges);
//remove visited from currentEdges currentEdgesArray = currentEdgesArray.filter((edge: Edge<T>) => { return !visited.includes(edge.source) && !visited.includes(edge.target) && edge.target !== current; });
visited.push(current); unvisited.splice(unvisited.indexOf(current), 1);
//update result array with distances, which is edge values for (let i = 0; i < currentEdgesArray.length; i++) { const edge = currentEdgesArray[i]; const index = resultArray.findIndex((node) => node.node === edge.target);
//update cumulative distances const previousIndex = resultArray.findIndex((node) => node.node === edge.source);
const previousDistance = resultArray[previousIndex].distance; const cumDistance = (previousDistance + edge.weight!) as number;
if (cumDistance < resultArray[index].distance) { resultArray[index].distance = cumDistance; resultArray[index].previous = current; } } }
return resultArray; }
/** * Finds the shortest path between two nodes in the graph using the Dijkstra method * * This method calculates the shortest path from the specified start node to the * specified end node in the graph. It returns an object containing the path and * the total distance of the path. * @param startingNode - The node from which the search for the shortest path begins. * @param endNode - The node where the search for the shortest path ends. * @returns An object containing: * - `path`: An array of nodes representing the shortest path from startNode to endNode. * If no path is found, this will be `null`. * - `distance`: The total distance of the shortest path. If no path is found, this will * be `Infinity`. */ shortestPathDijkstra(startingNode: Node<T>, endNode: Node<T>): { path: Node<T>[]; distance: number } { const dAnalysis = this.dijkstra(startingNode);
if (dAnalysis.length === 0) { return { path: [], distance: Infinity }; } //iterate through dAnalysis to plot shortest path to endnode const path: Node<T>[] = []; let current: Node<T> | null | undefined = endNode; const distance = dAnalysis.find((node) => node.node === endNode)?.distance as number; if (distance === Infinity) { return { path: [], distance: Infinity }; } while (current != null) { path.push(current);
current = dAnalysis.find((node) => node.node === current)?.previous;
if (current == null) { break; } } path.reverse(); return { path, distance }; }
/** * Finds the shortest path between two nodes in the graph using the A* algorithm. * * This method calculates the shortest path from the specified start node to the * specified end node in the graph. It returns an object containing the path and * the total distance of the path. * @param startNode - The node from which the search for the shortest path begins. * @param endNode - The node where the search for the shortest path ends. * @returns An object containing: * - `path`: An array of nodes representing the shortest path from startNode to endNode. * If no path is found, this will be `null`. * - `distance`: The total distance of the shortest path. If no path is found, this will * be `Infinity`. * - `skippedNodes`: A set of all nodes that were skipped during the search (because they * were not `PositionNode`s). */ aStar( startNode: PositionNode<T>, endNode: PositionNode<T> ): { path: PositionNode<T>[] | null; pathSteps: number; distance: number; skippedNodes: Set<G_UUID>; } { // Make sure we're working with PositionNodes if (!('pos' in startNode) || !('pos' in endNode)) { throw new Error('A* algorithm requires PositionNode with position vectors'); }
// Initialize data structures const openSet: Set<G_UUID> = new Set([startNode.id]); const closedSet: Set<G_UUID> = new Set(); const skippedNodes: Set<G_UUID> = new Set();
// Track g scores (distance from start) and f scores (estimated total cost) const gScore: Map<G_UUID, number> = new Map(); const hScore: Map<G_UUID, number> = new Map(); const fScore: Map<G_UUID, number> = new Map();
// Track the path const cameFrom: Map<G_UUID, G_UUID | null> = new Map();
// Initialize scores
//remap positionNodes from this._nodes where node is type of PositionNode const positionNodes: Map<G_UUID, PositionNode<T>> = new Map(); for (const [nodeId, node] of this._nodes) { if ('pos' in node) { positionNodes.set(nodeId, node as PositionNode<T>); } else { skippedNodes.add(nodeId); } }
for (const [nodeId] of positionNodes) { gScore.set(nodeId, this._euclideanDistance(positionNodes.get(nodeId)!, startNode)); hScore.set(nodeId, this._euclideanDistance(positionNodes.get(nodeId)!, endNode)); fScore.set(nodeId, gScore.get(nodeId)! + hScore.get(nodeId)!); cameFrom.set(nodeId, null); }
// Continue until we've visited all nodes or found the target while (openSet.size > 0) { // Find node with lowest fScore let currentId: G_UUID | null = null; let lowestFScore = Infinity;
for (const nodeId of openSet) { const score = fScore.get(nodeId) || Infinity; if (score < lowestFScore) { lowestFScore = score; currentId = nodeId; } }
// If we can't find a node, there's no path if (currentId === null) { break; }
// If we found the target, we're done if (currentId === endNode.id) { // Reconstruct path const path: PositionNode<T>[] = []; let current: G_UUID | null = endNode.id;
while (current !== null) { const node = this._nodes.get(current)! as PositionNode<T>; path.unshift(node); current = cameFrom.get(current)!; }
return { path, pathSteps: path.length - 1, distance: gScore.get(endNode.id) || Infinity, skippedNodes }; }
// Move from open to closed set openSet.delete(currentId); closedSet.add(currentId);
// Get current node const currentNode = this._nodes.get(currentId)! as PositionNode<T>;
// Check all neighbors const neighbors = this.getNeighbors(currentNode);
for (const neighbor of neighbors) { const neighborId = neighbor.id;
// Skip if neighbor has been processed if (closedSet.has(neighborId)) { continue; }
// Ensure neighbor is a PositionNode const positionNeighbor = neighbor as PositionNode<T>; if (!('pos' in positionNeighbor)) { continue; }
// Find the edge connecting current to neighbor const edge: Edge<T> = Array.from(currentNode.edges).find((e: Edge<T>) => e.source.id === currentId && e.target.id === neighborId)!;
if (!edge) { continue; }
cameFrom.set(neighborId, currentId); // Add to open set if not already there if (!openSet.has(neighborId)) { openSet.add(neighborId); } } }
// No path found return { path: [], pathSteps: 0, distance: Infinity, skippedNodes }; }
private _euclideanDistance(currentNode: PositionNode<T>, testNode: PositionNode<T>): number { const a = currentNode.pos; const b = testNode.pos; return Math.sqrt((b.x - a.x) ** 2 + (b.y - a.y) ** 2); }}
/** * Represents an edge in a graph, connecting two nodes. * @template T The type of data stored in the nodes connected by this edge. */export class Edge<T> { private _id: G_UUID = GraphUUId.generateUUID(); private _source: Node<T>; private _target: Node<T>; private _weight: number = 0; private _partnerEdge: Edge<T> | null = null; // Reference to the opposite direction edge
constructor(source: Node<T>, target: Node<T>, config?: EdgeOptions) { this._source = source; this._target = target; if (config && config.weight) { this._weight = config.weight; } else if (config && config.useEuclidean) { this._weight = (source as PositionNode<T>).pos.distance((target as PositionNode<T>).pos); //calc weight } else { this._weight = 0; } }
linkWithPartner(partnerEdge: Edge<T>): void { this._partnerEdge = partnerEdge; }
get id() { return this._id; }
get source() { return this._source; }
get target() { return this._target; }
get weight() { return this._weight; }
get partnerEdge() { return this._partnerEdge; }}
/** * Represents a node in a graph, with a unique identifier and optional data. * @template T The type of data stored in this node. */export class Node<T> { private _id: G_UUID; private _data: T; private _edges: Set<Edge<T>>;
constructor(data: T) { this._id = isDataWithId(data) ? data.id : GraphUUId.generateUUID(); this._data = data; this._edges = new Set(); }
get id(): G_UUID { return this._id; }
get data() { return this._data; }
get edges() { return this._edges; }
registerNewEdge(newEdge: Edge<T>) { this._edges.add(newEdge); }
breakEdge(edge: Edge<T>) { this._edges.delete(edge); }
getConnectedNodes(): Node<T>[] { return Array.from(this._edges).map((edge) => edge.target); }}
/** * Represents a node in a graph with a unique identifier, optional data, and a position in space. * @template T The type of data stored in this node. * @augments {Node<T>} */export class PositionNode<T> extends Node<T> { pos: Vector;
constructor(data: T, pos: Vector) { super(data); this.pos = pos; }}
class GraphUUId { static rng: Random = new Random();
static generateUUID(): G_UUID { const uuid = 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx';
const generatedUuid = uuid.replace(/[xy]/g, function (c) { const r = (GraphUUId.rng.next() * 16) | 0; const v = c === 'x' ? r : (r & 0x3) | 0x8; return v.toString(16); });
// Type assertion to convert string to branded type return generatedUuid as G_UUID; }}