My game gives the player the ability to lay down a custom road network; like simcity. The code for this is all custom of course, but I am exploring the possibility of using a* Pathfinding Project to pathfind along them.
The way I have it set up, each intersection is a gameobject, and they connection to eachother via the roads themselves. Since all of this is placed in realtime by the player, I do not think I can us any scanning functionality. In addition, since they are already connected via the roads themselves, I fear a scan would find the incorrect links, since a road is in no way guaranteed to be the shortest path between nodes (and two close nodes may not even be connected at all!)
As such, I would like to forgo scanning altogether, and maintain the pointgraph myself. How would I go about this?
I am thinking that each time I want to add a node, I would need to do something like this:
PointGraph graph = AstarPath.active.astarData.pointGraph;
PointNode intersectionPointNode = graph.AddNode((int3)transform.position);
To add connection to it:
// unsure what I should set for cost, is it ok to just set to 0 for everything?
uint cost = ?'
intersectionPointNode.AddConnection(otherIntersection.intersectionPointNode, cost);
Do I have the right idea? Is there anything else I would have to do for the system to pathfind along these nodes? Sorry in advance if this is too general a question; I am just trying to get an idea of if this library is going to be a good solution to this, or if I am better off writing something myself that is more specialized. Thanks in advance!
Hi
Check out this tutorial: http://arongranberg.com/astar/docs/writing-graph-generators.php
You can use a point graph to do it, however currently there is no API to delete nodes, but as a workaround you can just make the nodes unwalkable if you want to remove them.
The cost should usually be the distance between the nodes multiplied by 1000 (since it is stored as an integer) or easier
var cost = Mathf.RoundToInt(((Int3)pointA - (Int3)pointB).magnitude);
If you set the cost to zero, that will essentially mean that the player can teleport any distance in no time, which is likely not what you want.
Hey Aron, Thanks for the quick reply!
So if I understand, what you are suggesting is that I write my own graph, and override the methods i’ll need. I read the tutorial, and I am wondering if I need to override scan() at all? I’ll never need to scan over the entire network, as I’ll know every node that needs to be created/updated at the time of creation (I plan to store a reference to the intersection’s PointNode in the intersections’ script).
Also, If I override it and create the necessary editor script as defined in the tutorial, will all of this just work as if it came out of the box? Basically, will I be able to follow the tutorial for pathfinding between point A and point B without any extra intervention? I only ask because this seems really easy to extend. If that is really all there is to it, then bravo sir, this is amazing. haha
Well, you are probably better off using the point graph. Potentially you can override some methods that you need. I mostly linked to that tutorial so that you would get a better idea of how it all works behind the scenes.
Yeah, it will work. All graphs included with the system are written as add-ons to the system, so anything the built-in graphs can do, a custom graph can do.
The custom graph that is constructed in the tutorial has some drawbacks however. For example the point graph has a few options for speeding up the search for the closest node in the graph (to find the start and end nodes of the path), but the custom graph will just fall back to a linear search through all nodes (which may or may not be fast enough, depending on the game and the graph complexity).
Ahhh I see. Ok then. Awesome! I’ll extend from PointGraph just so I have some wiggle room to extend later. I’m not too concerned about speed atm because believe it or not, this path won’t be used at the moment for an object to move across; it is to be used to assist with the procedural generation of a mesh funny enough (for now). It won’t be called too often.
It looks like this is going to work beautifully. Seems simple enough that I can test it out today. I’ll let ya know how it goes! Thanks!!! This was extremely helpful!
I have this very close to being ready to test, but I am having a problem with updating the graph. Consider the following code snippet:
// ensure the pathfinder is aware of the road
AstarPath.RegisterSafeUpdate (() => {
RoadGraph graph = (RoadGraph)AstarPath.active.astarData.FindGraphOfType(typeof(RoadGraph));
// NOTE: because this is queued, we lose reference to the road. we need to use
// a reference that will not be lost
graph.AddRoad(currentRoad.gameObject.GetComponent<Road>());
AstarPath.active.FloodFill();
});
currentRoad = null;
This is giving me strange nullreferenceexception issues. At first it was somewhat clear because I am setting currentRoad to null. But, after I explicitly pass a reference I KNOW will(should) not be null, I get the following runtime error:
NullReferenceException: Object reference not set to an instance of an object
RoadNet.RoadPlacement.<Update>m__9 () (at Assets/Scripts/Roads/RoadPlacement.cs:191)
AstarPath.PerformBlockingActions (Boolean force, Boolean unblockOnComplete) (at Assets/ThirdParty/AstarPathfindingProject/Core/AstarPath.cs:896)
AstarPath.Update () (at Assets/ThirdParty/AstarPathfindingProject/Core/AstarPath.cs:857)
191 is my AddRoad() call in the code above. 'm a little confused by this.
N/M, I figured it out; I must be tired…
Hi
When you register a delegate with RegisterSafeUpdate it will not be executed immediately, instead it will wait until the pathfinding system (which could be running in other threads) have finished calculating their paths, and then it will run the delegate. So your line which sets currentRoad to null will be called before the delegate is executed.
1 Like