using System.Collections.Generic;
using Math = System.Math;
using UnityEngine;
#if UNITY_5_5_OR_NEWER
using UnityEngine.Profiling;
#endif
namespace Pathfinding {
using Pathfinding.Serialization;
using Pathfinding.Util;
///
/// Generates a grid of nodes.
/// The GridGraph does exactly what the name implies, generates nodes in a grid pattern.\n
/// Grid graphs suit well to when you already have a grid based world.
/// Features:
/// - You can update the graph during runtime (good for e.g Tower Defence or RTS games)
/// - Throw any scene at it, with minimal configurations you can get a good graph from it.
/// - Supports raycast and the funnel algorithm
/// - Predictable pattern
/// - Can apply penalty and walkability values from a supplied image
/// - Perfect for terrain worlds since it can make areas unwalkable depending on the slope
///
/// [Open online documentation to see images]
/// [Open online documentation to see images]
///
/// The The Snap Size button snaps the internal size of the graph to exactly contain the current number of nodes, i.e not contain 100.3 nodes but exactly 100 nodes.\n
/// This will make the "center" coordinate more accurate.\n
///
/// Updating the graph during runtime\n
/// Any graph which implements the IUpdatableGraph interface can be updated during runtime.\n
/// For grid graphs this is a great feature since you can update only a small part of the grid without causing any lag like a complete rescan would.\n
/// If you for example just have instantiated a sphere obstacle in the scene and you want to update the grid where that sphere was instantiated, you can do this:\n
/// AstarPath.active.UpdateGraphs (ob.collider.bounds);
/// Where ob is the obstacle you just instantiated (a GameObject).\n
/// As you can see, the UpdateGraphs function takes a Bounds parameter and it will send an update call to all updateable graphs.\n
/// A grid graph will update that area and a small margin around it equal to \link Pathfinding.GraphCollision.diameter collision testing diameter/2 \endlink
/// See: graph-updates (view in online documentation for working links) for more info about updating graphs during runtime
///
/// Hexagon graphs\n
/// The graph can be configured to work like a hexagon graph with some simple settings. Since 4.1.x the grid graph has a 'Shape' dropdown.
/// If you set it to 'Hexagonal' the graph will behave as a hexagon graph.
/// Often you may want to rotate the graph +45 or -45 degrees.
/// [Open online documentation to see images]
///
/// Note however that the snapping to the closest node is not exactly as you would expect in a real hexagon graph,
/// but it is close enough that you will likely not notice.
///
/// Configure using code\n
///
/// // This holds all graph data
/// AstarData data = AstarPath.active.data;
///
/// // This creates a Grid Graph
/// GridGraph gg = data.AddGraph(typeof(GridGraph)) as GridGraph;
///
/// // Setup a grid graph with some values
/// int width = 50;
/// int depth = 50;
/// float nodeSize = 1;
///
/// gg.center = new Vector3(10, 0, 0);
///
/// // Updates internal size from the above values
/// gg.SetDimensions(width, depth, nodeSize);
///
/// // Scans all graphs
/// AstarPath.active.Scan();
///
///
/// \ingroup graphs
/// \nosubgrouping
///
/// Tree colliders\n
/// It seems that Unity will only generate tree colliders at runtime when the game is started.
/// For this reason, the grid graph will not pick up tree colliders when outside of play mode
/// but it will pick them up once the game starts. If it still does not pick them up
/// make sure that the trees actually have colliders attached to them and that the tree prefabs are
/// in the correct layer (the layer should be included in the 'Collision Testing' mask).
///
/// See: for documentation on the 'Height Testing' and 'Collision Testing' sections
/// of the grid graph settings.
///
[JsonOptIn]
[Pathfinding.Util.Preserve]
public class GridGraph : NavGraph, IUpdatableGraph, ITransformedGraph {
/// This function will be called when this graph is destroyed
protected override void OnDestroy () {
base.OnDestroy();
// Clean up a reference in a static variable which otherwise should point to this graph forever and stop the GC from collecting it
RemoveGridGraphFromStatic();
}
protected override void DestroyAllNodes () {
GetNodes(node => {
// If the grid data happens to be invalid (e.g we had to abort a graph update while it was running) using 'false' as
// the parameter will prevent the Destroy method from potentially throwing IndexOutOfRange exceptions due to trying
// to access nodes outside the graph. It is safe to do this because we are destroying all nodes in the graph anyway.
// We do however need to clear custom connections in both directions
(node as GridNodeBase).ClearCustomConnections(true);
node.ClearConnections(false);
node.Destroy();
});
}
void RemoveGridGraphFromStatic () {
var graphIndex = active.data.GetGraphIndex(this);
GridNode.ClearGridGraph(graphIndex, this);
}
///
/// This is placed here so generators inheriting from this one can override it and set it to false.
/// If it is true, it means that the nodes array's length will always be equal to width*depth
/// It is used mainly in the editor to do auto-scanning calls, setting it to false for a non-uniform grid will reduce the number of scans
///
public virtual bool uniformWidthDepthGrid {
get {
return true;
}
}
///
/// Number of layers in the graph.
/// For grid graphs this is always 1, for layered grid graphs it can be higher.
/// The nodes array has the size width*depth*layerCount.
///
public virtual int LayerCount {
get {
return 1;
}
}
public override int CountNodes () {
return nodes != null ? nodes.Length : 0;
}
public override void GetNodes (System.Action action) {
if (nodes == null) return;
for (int i = 0; i < nodes.Length; i++) action(nodes[i]);
}
///
/// \name Inspector - Settings
/// \{
///
///
/// Determines the layout of the grid graph inspector in the Unity Editor.
/// This field is only used in the editor, it has no effect on the rest of the game whatsoever.
///
/// If you want to change the grid shape like in the inspector you can use the method.
///
[JsonMember]
public InspectorGridMode inspectorGridMode = InspectorGridMode.Grid;
///
/// Determines how the size of each hexagon is set in the inspector.
/// For hexagons the normal nodeSize field doesn't really correspond to anything specific on the hexagon's geometry, so this enum is used to give the user the opportunity to adjust more concrete dimensions of the hexagons
/// without having to pull out a calculator to calculate all the square roots and complicated conversion factors.
///
/// This field is only used in the graph inspector, the field will always use the same internal units.
/// If you want to set the node size through code then you can use .
///
/// [Open online documentation to see images]
///
/// See:
/// See:
/// See:
///
[JsonMember]
public InspectorGridHexagonNodeSize inspectorHexagonSizeMode = InspectorGridHexagonNodeSize.Width;
/// Width of the grid in nodes. See: SetDimensions
public int width;
/// Depth (height) of the grid in nodes. See: SetDimensions
public int depth;
///
/// Scaling of the graph along the X axis.
/// This should be used if you want different scales on the X and Y axis of the grid
///
[JsonMember]
public float aspectRatio = 1F;
///
/// Angle to use for the isometric projection.
/// If you are making a 2D isometric game, you may want to use this parameter to adjust the layout of the graph to match your game.
/// This will essentially scale the graph along one of its diagonals to produce something like this:
///
/// A perspective view of an isometric graph.
/// [Open online documentation to see images]
///
/// A top down view of an isometric graph. Note that the graph is entirely 2D, there is no perspective in this image.
/// [Open online documentation to see images]
///
/// For commonly used values see and .
///
/// Usually the angle that you want to use is either 30 degrees (alternatively 90-30 = 60 degrees) or atan(1/sqrt(2)) which is approximately 35.264 degrees (alternatively 90 - 35.264 = 54.736 degrees).
/// You might also want to rotate the graph plus or minus 45 degrees around the Y axis to get the oritientation required for your game.
///
/// You can read more about it on the wikipedia page linked below.
///
/// See: http://en.wikipedia.org/wiki/Isometric_projection
/// See: https://en.wikipedia.org/wiki/Isometric_graphics_in_video_games_and_pixel_art
/// See: rotation
///
[JsonMember]
public float isometricAngle;
/// Commonly used value for
public static readonly float StandardIsometricAngle = 90-Mathf.Atan(1/Mathf.Sqrt(2))*Mathf.Rad2Deg;
/// Commonly used value for
public static readonly float StandardDimetricAngle = Mathf.Acos(1/2f)*Mathf.Rad2Deg;
///
/// If true, all edge costs will be set to the same value.
/// If false, diagonals will cost more.
/// This is useful for a hexagon graph where the diagonals are actually the same length as the
/// normal edges (since the graph has been skewed)
///
[JsonMember]
public bool uniformEdgeCosts;
/// Rotation of the grid in degrees
[JsonMember]
public Vector3 rotation;
/// Center point of the grid
[JsonMember]
public Vector3 center;
/// Size of the grid. Might be negative or smaller than
[JsonMember]
public Vector2 unclampedSize;
///
/// Size of one node in world units.
/// See:
///
[JsonMember]
public float nodeSize = 1;
/* Collision and stuff */
/// Settings on how to check for walkability and height
[JsonMember]
public GraphCollision collision;
///
/// The max position difference between two nodes to enable a connection.
/// Set to 0 to ignore the value.
///
[JsonMember]
public float maxClimb = 0.4F;
/// The max slope in degrees for a node to be walkable.
[JsonMember]
public float maxSlope = 90;
///
/// Use heigh raycasting normal for max slope calculation.
/// True if is less than 90 degrees.
///
protected bool useRaycastNormal { get { return Math.Abs(90-maxSlope) > float.Epsilon; } }
///
/// Erosion of the graph.
/// The graph can be eroded after calculation.
/// This means a margin is put around unwalkable nodes or other unwalkable connections.
/// It is really good if your graph contains ledges where the nodes without erosion are walkable too close to the edge.
///
/// Below is an image showing a graph with erode iterations 0, 1 and 2
/// [Open online documentation to see images]
///
/// Note: A high number of erode iterations can seriously slow down graph updates during runtime (GraphUpdateObject)
/// and should be kept as low as possible.
/// See: erosionUseTags
///
[JsonMember]
public int erodeIterations;
///
/// Use tags instead of walkability for erosion.
/// Tags will be used for erosion instead of marking nodes as unwalkable. The nodes will be marked with tags in an increasing order starting with the tag .
/// Debug with the Tags mode to see the effect. With this enabled you can in effect set how close different AIs are allowed to get to walls using the Valid Tags field on the Seeker component.
/// [Open online documentation to see images]
/// [Open online documentation to see images]
/// See: erosionFirstTag
///
[JsonMember]
public bool erosionUseTags;
///
/// Tag to start from when using tags for erosion.
/// See:
/// See:
///
[JsonMember]
public int erosionFirstTag = 1;
///
/// Number of neighbours for each node.
/// Either four, six, eight connections per node.
///
/// Six connections is primarily for emulating hexagon graphs.
///
[JsonMember]
public NumNeighbours neighbours = NumNeighbours.Eight;
///
/// If disabled, will not cut corners on obstacles.
/// If \link connections \endlink is Eight, obstacle corners might be cut by a connection,
/// setting this to false disables that. \image html images/cutCorners.png
///
[JsonMember]
public bool cutCorners = true;
///
/// Offset for the position when calculating penalty.
/// See: penaltyPosition
///
[JsonMember]
public float penaltyPositionOffset;
/// Use position (y-coordinate) to calculate penalty
[JsonMember]
public bool penaltyPosition;
///
/// Scale factor for penalty when calculating from position.
/// See: penaltyPosition
///
[JsonMember]
public float penaltyPositionFactor = 1F;
[JsonMember]
public bool penaltyAngle;
///
/// How much penalty is applied depending on the slope of the terrain.
/// At a 90 degree slope (not that exactly 90 degree slopes can occur, but almost 90 degree), this penalty is applied.
/// At a 45 degree slope, half of this is applied and so on.
/// Note that you may require very large values, a value of 1000 is equivalent to the cost of moving 1 world unit.
///
[JsonMember]
public float penaltyAngleFactor = 100F;
/// How much extra to penalize very steep angles
[JsonMember]
public float penaltyAnglePower = 1;
/// Show an outline of the grid nodes in the Unity Editor
[JsonMember]
public bool showMeshOutline = true;
/// Show the connections between the grid nodes in the Unity Editor
[JsonMember]
public bool showNodeConnections;
/// Show the surface of the graph. Each node will be drawn as a square (unless e.g hexagon graph mode has been enabled).
[JsonMember]
public bool showMeshSurface = true;
/// \}
///
/// Size of the grid. Will always be positive and larger than .
/// See:
///
public Vector2 size { get; protected set; }
/* End collision and stuff */
///
/// Index offset to get neighbour nodes. Added to a node's index to get a neighbour node index.
///
///
/// Z
/// |
/// |
///
/// 6 2 5
/// \ | /
/// -- 3 - X - 1 ----- X
/// / | \
/// 7 0 4
///
/// |
/// |
///
///
[System.NonSerialized]
public readonly int[] neighbourOffsets = new int[8];
/// Costs to neighbour nodes
[System.NonSerialized]
public readonly uint[] neighbourCosts = new uint[8];
/// Offsets in the X direction for neighbour nodes. Only 1, 0 or -1
[System.NonSerialized]
public readonly int[] neighbourXOffsets = new int[8];
/// Offsets in the Z direction for neighbour nodes. Only 1, 0 or -1
[System.NonSerialized]
public readonly int[] neighbourZOffsets = new int[8];
/// Which neighbours are going to be used when =6
internal static readonly int[] hexagonNeighbourIndices = { 0, 1, 5, 2, 3, 7 };
/// In GetNearestForce, determines how far to search after a valid node has been found
public const int getNearestForceOverlap = 2;
///
/// All nodes in this graph.
/// Nodes are laid out row by row.
///
/// The first node has grid coordinates X=0, Z=0, the second one X=1, Z=0\n
/// the last one has grid coordinates X=width-1, Z=depth-1.
///
///
/// var gg = AstarPath.active.data.gridGraph;
/// int x = 5;
/// int z = 8;
/// GridNode node = gg.nodes[z*gg.width + x];
///
///
/// See:
/// See:
///
public GridNode[] nodes;
///
/// Determines how the graph transforms graph space to world space.
/// See:
///
public GraphTransform transform { get; private set; }
///
/// Get or set if the graph should be in 2D mode.
///
/// Note: This is just a convenience property, this property will actually read/modify the of the graph. A rotation aligned with the 2D plane is what determines if the graph is 2D or not.
///
/// See: You can also set if the graph should use 2D physics using `this.collision.use2D` (\reflink{GraphCollision.use2D}).
///
public bool is2D {
get {
return Quaternion.Euler(this.rotation) * Vector3.up == -Vector3.forward;
}
set {
if (value != is2D) {
this.rotation = value ? new Vector3(this.rotation.y - 90, 270, 90) : new Vector3(0, this.rotation.x + 90, 0);
}
}
}
public GridGraph () {
unclampedSize = new Vector2(10, 10);
nodeSize = 1F;
collision = new GraphCollision();
transform = new GraphTransform(Matrix4x4.identity);
}
public override void RelocateNodes (Matrix4x4 deltaMatrix) {
// It just makes a lot more sense to use the other overload and for that case we don't have to serialize the matrix
throw new System.Exception("This method cannot be used for Grid Graphs. Please use the other overload of RelocateNodes instead");
}
///
/// Relocate the grid graph using new settings.
/// This will move all nodes in the graph to new positions which matches the new settings.
///
public void RelocateNodes (Vector3 center, Quaternion rotation, float nodeSize, float aspectRatio = 1, float isometricAngle = 0) {
var previousTransform = transform;
this.center = center;
this.rotation = rotation.eulerAngles;
this.aspectRatio = aspectRatio;
this.isometricAngle = isometricAngle;
SetDimensions(width, depth, nodeSize);
GetNodes(node => {
var gnode = node as GridNodeBase;
var height = previousTransform.InverseTransform((Vector3)node.position).y;
node.position = GraphPointToWorld(gnode.XCoordinateInGrid, gnode.ZCoordinateInGrid, height);
});
}
///
/// Transform a point in graph space to world space.
/// This will give you the node position for the node at the given x and z coordinate
/// if it is at the specified height above the base of the graph.
///
public Int3 GraphPointToWorld (int x, int z, float height) {
return (Int3)transform.Transform(new Vector3(x+0.5f, height, z+0.5f));
}
public static float ConvertHexagonSizeToNodeSize (InspectorGridHexagonNodeSize mode, float value) {
if (mode == InspectorGridHexagonNodeSize.Diameter) value *= 1.5f/(float)System.Math.Sqrt(2.0f);
else if (mode == InspectorGridHexagonNodeSize.Width) value *= (float)System.Math.Sqrt(3.0f/2.0f);
return value;
}
public static float ConvertNodeSizeToHexagonSize (InspectorGridHexagonNodeSize mode, float value) {
if (mode == InspectorGridHexagonNodeSize.Diameter) value *= (float)System.Math.Sqrt(2.0f)/1.5f;
else if (mode == InspectorGridHexagonNodeSize.Width) value *= (float)System.Math.Sqrt(2.0f/3.0f);
return value;
}
public int Width {
get {
return width;
}
set {
width = value;
}
}
public int Depth {
get {
return depth;
}
set {
depth = value;
}
}
public uint GetConnectionCost (int dir) {
return neighbourCosts[dir];
}
public GridNode GetNodeConnection (GridNode node, int dir) {
if (!node.HasConnectionInDirection(dir)) return null;
if (!node.EdgeNode) {
return nodes[node.NodeInGridIndex + neighbourOffsets[dir]];
} else {
int index = node.NodeInGridIndex;
//int z = Math.DivRem (index,Width, out x);
int z = index/Width;
int x = index - z*Width;
return GetNodeConnection(index, x, z, dir);
}
}
public bool HasNodeConnection (GridNode node, int dir) {
if (!node.HasConnectionInDirection(dir)) return false;
if (!node.EdgeNode) {
return true;
} else {
int index = node.NodeInGridIndex;
int z = index/Width;
int x = index - z*Width;
return HasNodeConnection(index, x, z, dir);
}
}
public void SetNodeConnection (GridNode node, int dir, bool value) {
int index = node.NodeInGridIndex;
int z = index/Width;
int x = index - z*Width;
SetNodeConnection(index, x, z, dir, value);
}
///
/// Get the connecting node from the node at (x,z) in the specified direction.
/// Returns: A GridNode if the node has a connection to that node. Null if no connection in that direction exists
///
/// See: GridNode
///
private GridNode GetNodeConnection (int index, int x, int z, int dir) {
if (!nodes[index].HasConnectionInDirection(dir)) return null;
/// TODO: Mark edge nodes and only do bounds checking for them
int nx = x + neighbourXOffsets[dir];
if (nx < 0 || nx >= Width) return null; /// TODO: Modify to get adjacent grid graph here
int nz = z + neighbourZOffsets[dir];
if (nz < 0 || nz >= Depth) return null;
int nindex = index + neighbourOffsets[dir];
return nodes[nindex];
}
///
/// Set if connection in the specified direction should be enabled.
/// Note that bounds checking will still be done when getting the connection value again,
/// so it is not necessarily true that HasNodeConnection will return true just because you used
/// SetNodeConnection on a node to set a connection to true.
///
/// Note: This is identical to Pathfinding.Node.SetConnectionInternal
///
/// Deprecated:
///
/// Index of the node
/// X coordinate of the node
/// Z coordinate of the node
/// Direction from 0 up to but excluding 8.
/// Enable or disable the connection
public void SetNodeConnection (int index, int x, int z, int dir, bool value) {
nodes[index].SetConnectionInternal(dir, value);
}
public bool HasNodeConnection (int index, int x, int z, int dir) {
if (!nodes[index].HasConnectionInDirection(dir)) return false;
/// TODO: Mark edge nodes and only do bounds checking for them
int nx = x + neighbourXOffsets[dir];
if (nx < 0 || nx >= Width) return false; /// TODO: Modify to get adjacent grid graph here
int nz = z + neighbourZOffsets[dir];
if (nz < 0 || nz >= Depth) return false;
return true;
}
///
/// Changes the grid shape.
/// This is equivalent to changing the 'shape' dropdown in the grid graph inspector.
///
/// Calling this method will set , , and
/// to appropriate values for that shape.
///
/// Note: Setting the shape to does not do anything except set the field.
///
/// See:
///
public void SetGridShape (InspectorGridMode shape) {
switch (shape) {
case InspectorGridMode.Grid:
isometricAngle = 0;
aspectRatio = 1;
uniformEdgeCosts = false;
if (neighbours == NumNeighbours.Six) neighbours = NumNeighbours.Eight;
break;
case InspectorGridMode.Hexagonal:
isometricAngle = StandardIsometricAngle;
aspectRatio = 1;
uniformEdgeCosts = true;
neighbours = NumNeighbours.Six;
break;
case InspectorGridMode.IsometricGrid:
uniformEdgeCosts = false;
if (neighbours == NumNeighbours.Six) neighbours = NumNeighbours.Eight;
isometricAngle = StandardIsometricAngle;
break;
case InspectorGridMode.Advanced:
default:
break;
}
inspectorGridMode = shape;
}
///
/// Updates from , and values.
/// Also \link UpdateTransform generates a new matrix \endlink.
/// Note: This does not rescan the graph, that must be done with Scan
///
/// You should use this method instead of setting the and fields
/// as the grid dimensions are not defined by the and variables but by
/// the and variables.
///
///
/// var gg = AstarPath.active.data.gridGraph;
/// var width = 80;
/// var depth = 60;
/// var nodeSize = 1.0f;
///
/// gg.SetDimensions(width, depth, nodeSize);
///
/// // Recalculate the graph
/// AstarPath.active.Scan();
///
///
public void SetDimensions (int width, int depth, float nodeSize) {
unclampedSize = new Vector2(width, depth)*nodeSize;
this.nodeSize = nodeSize;
UpdateTransform();
}
/// Updates from , and values. Deprecated: Use instead
[System.Obsolete("Use SetDimensions instead")]
public void UpdateSizeFromWidthDepth () {
SetDimensions(width, depth, nodeSize);
}
///
/// Generates the matrix used for translating nodes from grid coordinates to world coordinates.
/// Deprecated: This method has been renamed to
///
[System.Obsolete("This method has been renamed to UpdateTransform")]
public void GenerateMatrix () {
UpdateTransform();
}
///
/// Updates the field which transforms graph space to world space.
/// In graph space all nodes are laid out in the XZ plane with the first node having a corner in the origin.
/// One unit in graph space is one node so the first node in the graph is at (0.5,0) the second one at (1.5,0) etc.
///
/// This takes the current values of the parameters such as position and rotation into account.
/// The transform that was used the last time the graph was scanned is stored in the field.
///
/// The field is calculated using this method when the graph is scanned.
/// The width, depth variables are also updated based on the field.
///
public void UpdateTransform () {
CalculateDimensions(out width, out depth, out nodeSize);
transform = CalculateTransform();
}
///
/// Returns a new transform which transforms graph space to world space.
/// Does not update the field.
/// See:
///
public GraphTransform CalculateTransform () {
int newWidth, newDepth;
float newNodeSize;
CalculateDimensions(out newWidth, out newDepth, out newNodeSize);
// Generate a matrix which shrinks the graph along one of the diagonals
// corresponding to the isometricAngle
var isometricMatrix = Matrix4x4.TRS(Vector3.zero, Quaternion.Euler(0, 45, 0), Vector3.one);
isometricMatrix = Matrix4x4.Scale(new Vector3(Mathf.Cos(Mathf.Deg2Rad*isometricAngle), 1, 1)) * isometricMatrix;
isometricMatrix = Matrix4x4.TRS(Vector3.zero, Quaternion.Euler(0, -45, 0), Vector3.one) * isometricMatrix;
// Generate a matrix for the bounds of the graph
// This moves a point to the correct offset in the world and the correct rotation and the aspect ratio and isometric angle is taken into account
// The unit is still world units however
var boundsMatrix = Matrix4x4.TRS(center, Quaternion.Euler(rotation), new Vector3(aspectRatio, 1, 1)) * isometricMatrix;
// Generate a matrix where Vector3.zero is the corner of the graph instead of the center
// The unit is nodes here (so (0.5,0,0.5) is the position of the first node and (1.5,0,0.5) is the position of the second node)
// 0.5 is added since this is the node center, not its corner. In graph space a node has a size of 1
var m = Matrix4x4.TRS(boundsMatrix.MultiplyPoint3x4(-new Vector3(newWidth*newNodeSize, 0, newDepth*newNodeSize)*0.5F), Quaternion.Euler(rotation), new Vector3(newNodeSize*aspectRatio, 1, newNodeSize)) * isometricMatrix;
// Set the matrix of the graph
// This will also set inverseMatrix
return new GraphTransform(m);
}
///
/// Calculates the width/depth of the graph from and .
/// The node size may be changed due to constraints that the width/depth is not
/// allowed to be larger than 1024 (artificial limit).
///
void CalculateDimensions (out int width, out int depth, out float nodeSize) {
var newSize = unclampedSize;
// Make sure size is positive
newSize.x *= Mathf.Sign(newSize.x);
newSize.y *= Mathf.Sign(newSize.y);
// Clamp the nodeSize so that the graph is never larger than 1024*1024
nodeSize = Mathf.Max(this.nodeSize, newSize.x/1024F);
nodeSize = Mathf.Max(this.nodeSize, newSize.y/1024F);
// Prevent the graph to become smaller than a single node
newSize.x = newSize.x < nodeSize ? nodeSize : newSize.x;
newSize.y = newSize.y < nodeSize ? nodeSize : newSize.y;
size = newSize;
// Calculate the number of nodes along each side
width = Mathf.FloorToInt(size.x / nodeSize);
depth = Mathf.FloorToInt(size.y / nodeSize);
// Take care of numerical edge cases
if (Mathf.Approximately(size.x / nodeSize, Mathf.CeilToInt(size.x / nodeSize))) {
width = Mathf.CeilToInt(size.x / nodeSize);
}
if (Mathf.Approximately(size.y / nodeSize, Mathf.CeilToInt(size.y / nodeSize))) {
depth = Mathf.CeilToInt(size.y / nodeSize);
}
}
public override NNInfoInternal GetNearest (Vector3 position, NNConstraint constraint, GraphNode hint) {
if (nodes == null || depth*width != nodes.Length) {
return new NNInfoInternal();
}
// Calculate the closest node and the closest point on that node
position = transform.InverseTransform(position);
float xf = position.x;
float zf = position.z;
int x = Mathf.Clamp((int)xf, 0, width-1);
int z = Mathf.Clamp((int)zf, 0, depth-1);
var nn = new NNInfoInternal(nodes[z*width+x]);
float y = transform.InverseTransform((Vector3)nodes[z*width+x].position).y;
nn.clampedPosition = transform.Transform(new Vector3(Mathf.Clamp(xf, x, x+1f), y, Mathf.Clamp(zf, z, z+1f)));
return nn;
}
public override NNInfoInternal GetNearestForce (Vector3 position, NNConstraint constraint) {
if (nodes == null || depth*width != nodes.Length) {
return new NNInfoInternal();
}
// Position in global space
Vector3 globalPosition = position;
// Position in graph space
position = transform.InverseTransform(position);
// Find the coordinates of the closest node
float xf = position.x;
float zf = position.z;
int x = Mathf.Clamp((int)xf, 0, width-1);
int z = Mathf.Clamp((int)zf, 0, depth-1);
// Closest node
GridNode node = nodes[x+z*width];
GridNode minNode = null;
float minDist = float.PositiveInfinity;
int overlap = getNearestForceOverlap;
Vector3 clampedPosition = Vector3.zero;
var nn = new NNInfoInternal(null);
// If the closest node was suitable
if (constraint == null || constraint.Suitable(node)) {
minNode = node;
minDist = ((Vector3)minNode.position-globalPosition).sqrMagnitude;
float y = transform.InverseTransform((Vector3)node.position).y;
clampedPosition = transform.Transform(new Vector3(Mathf.Clamp(xf, x, x+1f), y, Mathf.Clamp(zf, z, z+1f)));
}
if (minNode != null) {
nn.node = minNode;
nn.clampedPosition = clampedPosition;
// We have a node, and we don't need to search more, so just return
if (overlap == 0) return nn;
overlap--;
}
// Search up to this distance
float maxDist = constraint == null || constraint.constrainDistance ? AstarPath.active.maxNearestNodeDistance : float.PositiveInfinity;
float maxDistSqr = maxDist*maxDist;
// Search a square/spiral pattern around the point
for (int w = 1;; w++) {
//Check if the nodes are within distance limit
if (nodeSize*w > maxDist) {
break;
}
bool anyInside = false;
int nx;
int nz = z+w;
int nz2 = nz*width;
// Side 1 on the square
for (nx = x-w; nx <= x+w; nx++) {
if (nx < 0 || nz < 0 || nx >= width || nz >= depth) continue;
anyInside = true;
if (constraint == null || constraint.Suitable(nodes[nx+nz2])) {
float dist = ((Vector3)nodes[nx+nz2].position-globalPosition).sqrMagnitude;
if (dist < minDist && dist < maxDistSqr) {
// Minimum distance so far
minDist = dist;
minNode = nodes[nx+nz2];
// Closest point on the node if the node is treated as a square
clampedPosition = transform.Transform(new Vector3(Mathf.Clamp(xf, nx, nx+1f), transform.InverseTransform((Vector3)minNode.position).y, Mathf.Clamp(zf, nz, nz+1f)));
}
}
}
nz = z-w;
nz2 = nz*width;
// Side 2 on the square
for (nx = x-w; nx <= x+w; nx++) {
if (nx < 0 || nz < 0 || nx >= width || nz >= depth) continue;
anyInside = true;
if (constraint == null || constraint.Suitable(nodes[nx+nz2])) {
float dist = ((Vector3)nodes[nx+nz2].position-globalPosition).sqrMagnitude;
if (dist < minDist && dist < maxDistSqr) {
minDist = dist;
minNode = nodes[nx+nz2];
clampedPosition = transform.Transform(new Vector3(Mathf.Clamp(xf, nx, nx+1f), transform.InverseTransform((Vector3)minNode.position).y, Mathf.Clamp(zf, nz, nz+1f)));
}
}
}
nx = x-w;
// Side 3 on the square
for (nz = z-w+1; nz <= z+w-1; nz++) {
if (nx < 0 || nz < 0 || nx >= width || nz >= depth) continue;
anyInside = true;
if (constraint == null || constraint.Suitable(nodes[nx+nz*width])) {
float dist = ((Vector3)nodes[nx+nz*width].position-globalPosition).sqrMagnitude;
if (dist < minDist && dist < maxDistSqr) {
minDist = dist;
minNode = nodes[nx+nz*width];
clampedPosition = transform.Transform(new Vector3(Mathf.Clamp(xf, nx, nx+1f), transform.InverseTransform((Vector3)minNode.position).y, Mathf.Clamp(zf, nz, nz+1f)));
}
}
}
nx = x+w;
// Side 4 on the square
for (nz = z-w+1; nz <= z+w-1; nz++) {
if (nx < 0 || nz < 0 || nx >= width || nz >= depth) continue;
anyInside = true;
if (constraint == null || constraint.Suitable(nodes[nx+nz*width])) {
float dist = ((Vector3)nodes[nx+nz*width].position-globalPosition).sqrMagnitude;
if (dist < minDist && dist < maxDistSqr) {
minDist = dist;
minNode = nodes[nx+nz*width];
clampedPosition = transform.Transform(new Vector3(Mathf.Clamp(xf, nx, nx+1f), transform.InverseTransform((Vector3)minNode.position).y, Mathf.Clamp(zf, nz, nz+1f)));
}
}
}
// We found a suitable node
if (minNode != null) {
// If we don't need to search more, just return
// Otherwise search for 'overlap' iterations more
if (overlap == 0) {
break;
}
overlap--;
}
// No nodes were inside grid bounds
// We will not be able to find any more valid nodes
// so just return
if (!anyInside) {
break;
}
}
// Copy fields to the NNInfo struct and return
nn.node = minNode;
nn.clampedPosition = clampedPosition;
return nn;
}
///
/// Sets up with the current settings. , , and are set up.\n
/// The cost for a non-diagonal movement between two adjacent nodes is RoundToInt ( * Int3.Precision)\n
/// The cost for a diagonal movement between two adjacent nodes is RoundToInt ( * Sqrt (2) * Int3.Precision)
///
public virtual void SetUpOffsetsAndCosts () {
//First 4 are for the four directly adjacent nodes the last 4 are for the diagonals
neighbourOffsets[0] = -width;
neighbourOffsets[1] = 1;
neighbourOffsets[2] = width;
neighbourOffsets[3] = -1;
neighbourOffsets[4] = -width+1;
neighbourOffsets[5] = width+1;
neighbourOffsets[6] = width-1;
neighbourOffsets[7] = -width-1;
uint straightCost = (uint)Mathf.RoundToInt(nodeSize*Int3.Precision);
// Diagonals normally cost sqrt(2) (approx 1.41) times more
uint diagonalCost = uniformEdgeCosts ? straightCost : (uint)Mathf.RoundToInt(nodeSize*Mathf.Sqrt(2F)*Int3.Precision);
neighbourCosts[0] = straightCost;
neighbourCosts[1] = straightCost;
neighbourCosts[2] = straightCost;
neighbourCosts[3] = straightCost;
neighbourCosts[4] = diagonalCost;
neighbourCosts[5] = diagonalCost;
neighbourCosts[6] = diagonalCost;
neighbourCosts[7] = diagonalCost;
/* Z
* |
* |
*
* 6 2 5
* \ | /
* -- 3 - X - 1 ----- X
* / | \
* 7 0 4
*
* |
* |
*/
neighbourXOffsets[0] = 0;
neighbourXOffsets[1] = 1;
neighbourXOffsets[2] = 0;
neighbourXOffsets[3] = -1;
neighbourXOffsets[4] = 1;
neighbourXOffsets[5] = 1;
neighbourXOffsets[6] = -1;
neighbourXOffsets[7] = -1;
neighbourZOffsets[0] = -1;
neighbourZOffsets[1] = 0;
neighbourZOffsets[2] = 1;
neighbourZOffsets[3] = 0;
neighbourZOffsets[4] = -1;
neighbourZOffsets[5] = 1;
neighbourZOffsets[6] = 1;
neighbourZOffsets[7] = -1;
}
protected override IEnumerable