Is it possible, while using A* pathfinding, to generate larger nodes in empty spaces to reduce the total number of nodes generated in the grid?
I think it could improve the performance of the calculation a lot, any thoughts on how to go about implementing such a thing?
I’ve done it, so the short answer is “yes”.
In what sense? I don’t recall there being anything special I had to do. Are you using a pre-made pathfinding system or implementing your own?
I think I set up my node graph such that each node had a radius, and there were no obstructions between any two points in connected nodes. I made a function which got me the closest node to any given point in world space, possibly with some kind of obstruction check. To calculate a path I’d get the closest nodes to the start and end points and path between them with A*. When travelling along the path, as soon as the agent is within the radius of their current target node they pick a point within the radius of the following node and move towards that, until they reach the final node and head to their actual destination point (which should now be unobstructed).
Well I’m generating my grid like this,
void CreateGrid()
{
grid = new Node[gridSizeX, gridSizeY, gridSizeZ];
Vector3 bottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward * gridWorldSize.z / 2 - Vector3.up * gridWorldSize.y / 2;
int i = 0;
for (int z = 0; z < gridSizeZ; z++)
{
for (int y = 0; y < gridSizeY; y++)
{
for (int x = 0; x < gridSizeX; x++)
{
Vector3 worldPosition = bottomLeft + Vector3.right * (x * nodeDiameter + nodeRadius) + Vector3.forward * (z * nodeDiameter + nodeRadius) + Vector3.up * (y * nodeDiameter + nodeRadius);
bool wall = true;
if (Physics.CheckSphere(worldPosition, nodeRadius, wallMask))
{
wall = false;
}
grid[x, y, z] = new Node(i, wall, worldPosition, x, y, z, false);
i++;
}
}
}
}
So I’m just not sure how I could go about making the nodes bigger because won’t that mess up my grid array?
You can do what a* already does, but just make your own nodes.
That’s pretty much what OG Unreal did.
And it’s WAY cheaper.
That’s what I’m hoping for, but I don’t think it will work within my current system because of the grid array
Then you probably don’t want to use a grid array and instead, if a grid-like structure is important to you, something like a quadtree instead.
Are you using a grid array for any particular reason?
If variable node size is important that doesn’t sound like a good fit, unless there’s some reason for it.
I was using it to optimize, but I guess if I’m optimizing away a large portion of the nodes instead then no. I probably wouldn’t need the grid anymore I guess. Though everything is based on the grid and I’m reluctant to switch it all over.
Just make it work is always the way to go.
If New Vegas can strap a train on an NPCs head to make it work, you can just use the code you already have.
My project did have a grid for other reasons, and it was used for node lookup. You could do the same thing.
I have a potential project I shelved because I realized I’d need to implement my own 3D pathfinding, but my general idea was an octree that subdivides whenever there is a potential collision. 2D example:
Each cell would contain its position, bounds, and a list of other connected cells. When a moving object detected that it would enter the same cell as another object, the cells would subdivide, updating their neighbor relationships, to a maximum of the larger object’s dimensions, until the moving object could pass through an empty cell.
The logic of subdividing would be trivially simple - pseudocode for a 2D example would be something like
public class Node
{
Vector2 pos;
Vector2 bounds;
List<Node> neighbors;
public Node(Vector2 center, Vector2 bounds)
{
this.pos = center;
this.bounds = bounds;
}
}
List<Node> nodes = new List<Node>();
...
sd = nodes[sdIndex];
var pos0 = new Vector2(sd.pos.x - (sd.bounds.x/2), sd.pos.y - (sd.bounds.y/2));
var pos1 = new Vector2(sd.pos.x - (sd.bounds.x/2), sd.pos.y + (sd.bounds.y/2));
var pos2 = new Vector2(sd.pos.x + (sd.bounds.x/2), sd.pos.y - (sd.bounds.y/2));
var pos3 = new Vector2(sd.pos.x + (sd.bounds.x/2), sd.pos.y + (sd.bounds.y/2));
var bounds = sd.bounds / 2;
List<Node> addNodes = new List<Node>
{
Node node0 = new Node(pos0, bounds),
Node node1 = new Node(pos1, bounds),
Node node2 = new Node(pos2, bounds),
Node node3 = new Node(pos3, bounds)
};
node0.neighbors.Add(node1);
node0.neighbors.Add(node2);
node1.neighbors.Add(node0);
node1.neighbors.Add(node3);
node2.neighbors.Add(node0);
node2.neighbors.Add(node3);
node3.neighbors.Add(node1);
node3.neighbors.Add(node2);
foreach(var neighbor in sd.neighbors)
{
neighbor.neighbors.Remove(sd);
List<float> distances = addNodes.Select(x => (x, Vector3.Distance(x.pos, neighbor.pos))).OrderBy(xx => xx.Item2).ToList();
neighbor.neighbors.Add(distances[0].Item1);
distances[0].Item1.neighbors.Add(neighbor);
neighbor.neighbors.Add(distances[1].Item1);
distances[1].Item1.neighbors.Add(neighbor);
}
nodes.RemoveAt(sd_index);
nodes.AddRange(addNodes);
I have no idea if this overall idea would work for pathfinding, or if there are way better solutions.