Struct ScyllaGraphSearchState

Per-node state record used by graph traversal algorithms such as Dijkstra and A*. Tracks the best-known path cost from the source, the back-pointer used for path reconstruction, and the node's current position in the search frontier.

Implements

IEquatable<ScyllaGraphSearchState>

Inherited Members

object.Equals(object, object)

object.GetType()

object.ReferenceEquals(object, object)

Namespace: Scylla.Core.Structures

Assembly: ScyllaCore.dll

Syntax

public struct ScyllaGraphSearchState : IEquatable<ScyllaGraphSearchState>

Remarks

Search lifecycle: every node starts as STATUS_UNVISITED. When a node is first discovered (added to the open list / priority queue), its status advances to STATUS_OPEN and GCost is set to the tentative cost. When the node is dequeued and its cost is finalised, status advances to STATUS_CLOSED. Closed nodes are never re-processed.

Path reconstruction: after the search completes, follow the chain of ParentID values from the target node back to the source to recover the optimal path. The source node's ParentID will be NO_PARENT (-1). Use Reverse() after collecting the IDs to obtain the canonical source-to-target order.

Layout and DOTS compatibility: the struct uses Sequential and is 12 bytes (4-byte float, 4-byte int, 1-byte status + 3 bytes implicit padding). It is fully unmanaged and can be stored in a NativeArray<ScyllaGraphSearchState> for Unity DOTS or Burst-compiled path-finding jobs.

Initialisation: call CreateDefault() to obtain a state with GCost set to PositiveInfinity and Status set to STATUS_UNVISITED. This sentinel pattern allows algorithms to detect unvisited nodes without a separate visited array.

Fields

GCost

The best-known accumulated edge-weight cost from the search source to this node. Initialised to PositiveInfinity by CreateDefault() to indicate that no path has been found yet. The algorithm updates this value whenever a cheaper path is discovered. In A* terminology this is the g-cost (actual path cost), as distinct from the heuristic estimate h-cost.

Declaration

public float GCost

Field Value

Type	Description
float

NO_PARENT

Sentinel value stored in ParentID when a node has no predecessor in the search tree - i.e., when the node is the search source or has not yet been reached. Value is -1, which is guaranteed to be an invalid node ID in all IScyllaGraph implementations (node IDs are non-negative integers).

Declaration

public const int NO_PARENT = -1

Field Value

Type	Description
int

ParentID

The node ID of the predecessor through which the cheapest known path to this node passes. After the search completes, follow the chain of ParentID links starting from the target node back to the source to reconstruct the optimal path. A value of NO_PARENT (-1) indicates either the source node itself or a node that has not yet been discovered.

Declaration

public int ParentID

Field Value

Type	Description
int

STATUS_CLOSED

Status value for a node that has been removed from the open list and whose shortest path from the source is now final. Once closed, a node will not be processed again (guaranteed optimal for non-negative edge weights).

Declaration

public const byte STATUS_CLOSED = 2

Field Value

Type	Description
byte

STATUS_OPEN

Status value for a node that has been discovered and added to the search frontier (open list / priority queue) but whose shortest path has not yet been finalised. The node's GCost represents the current best-known tentative cost; it may be improved by a cheaper path found later.

Declaration

public const byte STATUS_OPEN = 1

Field Value

Type	Description
byte

STATUS_UNVISITED

Status value for a node that has not yet been reached by the search. The initial value assigned by CreateDefault(). An unvisited node's GCost is PositiveInfinity and its ParentID is NO_PARENT.

Declaration

public const byte STATUS_UNVISITED = 0

Field Value

Type	Description
byte

Status

The current position of this node in the search lifecycle. Valid values are STATUS_UNVISITED (0), STATUS_OPEN (1), and STATUS_CLOSED (2). Stored as a raw byte to keep the struct at 12 bytes and to ensure compatibility with DOTS NativeArray and Burst-compiled code. Prefer the helper methods IsUnvisited(), IsOpen(), and IsClosed() over direct field access for readable and forward-compatible status checks.

Declaration

public byte Status

Field Value

Type	Description
byte

Methods

CreateDefault()

Returns an initial ScyllaGraphSearchState suitable for use at the start of a search. The returned state has GCost set to PositiveInfinity (indicating no path yet), ParentID set to NO_PARENT (-1), and Status set to STATUS_UNVISITED (0). Populate a state table by calling this for every node before running a search algorithm.

Declaration

public static ScyllaGraphSearchState CreateDefault()

Returns

Type	Description
ScyllaGraphSearchState	A default-initialised, unvisited search state with infinite cost.

Equals(ScyllaGraphSearchState)

Determines whether this search state equals other by comparing all three fields: GCost (approximately), ParentID (exact), and Status (exact). Because GCost uses approximate comparison via NumberUtil.Approximately, the GetHashCode() implementation intentionally excludes GCost to preserve the Equals/GetHashCode contract.

Declaration

public bool Equals(ScyllaGraphSearchState other)

Parameters

Type	Name	Description
ScyllaGraphSearchState	other	The search state to compare against.

Returns

Type	Description
bool	true if all fields compare equal (with approximate float comparison for GCost); false otherwise.

Equals(object)

Declaration

public override bool Equals(object obj)

Parameters

Type	Name	Description
object	obj

Returns

Type	Description
bool

Overrides

ValueType.Equals(object)

GetHashCode()

Declaration

public override int GetHashCode()

Returns

Type	Description
int

Overrides

ValueType.GetHashCode()

IsClosed()

Returns true if this node has been removed from the open list and its shortest path from the source has been finalised. A closed node will not be re-processed by the search algorithm.

Declaration

public bool IsClosed()

Returns

Type	Description
bool	true when Status equals STATUS_CLOSED.

IsOpen()

Returns true if this node has been discovered and placed in the search frontier (open list / priority queue) but whose shortest path has not yet been finalised. The node's GCost represents the current best tentative cost.

Declaration

public bool IsOpen()

Returns

Type	Description
bool	true when Status equals STATUS_OPEN.

IsUnvisited()

Returns true if this node has not yet been reached by the search algorithm. An unvisited node has GCost equal to PositiveInfinity and ParentID equal to NO_PARENT.

Declaration

public bool IsUnvisited()

Returns

Type	Description
bool	true when Status equals STATUS_UNVISITED.

ToString()

Declaration

public override string ToString()

Returns

Type	Description
string

Overrides

ValueType.ToString()

Operators

operator ==(ScyllaGraphSearchState, ScyllaGraphSearchState)

Returns true if left and right are equal as defined by Equals(ScyllaGraphSearchState) - all three fields match (with approximate comparison for GCost).

Declaration

public static bool operator ==(ScyllaGraphSearchState left, ScyllaGraphSearchState right)

Parameters

Type	Name	Description
ScyllaGraphSearchState	left
ScyllaGraphSearchState	right

Returns

Type	Description
bool

operator !=(ScyllaGraphSearchState, ScyllaGraphSearchState)

Returns true if left and right differ in any field as defined by Equals(ScyllaGraphSearchState).

Declaration

public static bool operator !=(ScyllaGraphSearchState left, ScyllaGraphSearchState right)

Parameters

Type	Name	Description
ScyllaGraphSearchState	left
ScyllaGraphSearchState	right

Returns

Type	Description
bool

Implements

IEquatable<T>

See Also

ScyllaGraphPath

ScyllaGraphAlgorithms