Hello Community,
i´m currently using the free version of astar, but i will upgrade to the pro version if the features i´m aiming for are only available in the pro version.
I want diffrent kinds of units in my gamne, which find their path with diffrent preferences. Let me give some examples:
-Unit1 is following the shortest path through a maze to a set destination, avoiding obstacles. Pretty straight forward, no problems here.
-Unit2 is following also the shortest path, but has a diffrent destination. I also know how to implement this feature.
-Unit3 is following the shortest path, but objects which are obstacles for unit 1+2, should be walkable for this unit. So the workaround here would be to set up a new graph with other collision and height masks setup. i´m guessing that there is a way to let this kind of unit calculate their path with diffrent masks settings, without the need of a second independent graph. But i don´t know how do this.
-unit4 should follow the LONGEST availabe path in the maze without backtracking. I have no idea of a workaround here, but i´m shure that there is a way doing this with astar.
Another question which has come to my mind while thinking about my pathfinding-issues is: How can i calculate the remaining length of the path from the current position of the unit to the destination? i assume, that somehow i have to get all the remaining nodes to the target and sum all the vector magnitudes from nod to nod.
Hi
Sorry for the late answer.
For Unit3, that is easy. You can use tags to mark some regions as only being passable by some units.
Take a look a the “Penalties” example scene and this page: http://arongranberg.com/astar/docs_dev/tags.php
For Unit4. I’m sorry, that is unfortunately an NP-complete. NP-complete means roughly that there is no “efficient” way of calculating it, so for even moderately large graphs, you could have a computer churn at the problem for thousands of years (or possibly longer than the universe has existed) and still not come up with a solution.
See https://en.wikipedia.org/wiki/Hamiltonian_path_problem
The last thing depends on the movement script used so I cannot give you the exact code. But all of the included movement scripts use a currentIndex variable (or some variant of that name), that refers to the node in the path, they also store the path (vectorPath), so you can simply sum the lengths of the distances between the points from currentIndex to the end of the path array.
Hey Aron,
thx for the answer, i was off the pathfinding issue, taking care of the camera controll, so my answer is also late 
Anyways, thx for help with Unit3. I will build this in very soon.
Also thx for the length-method. I´m using the unity character controller up to this point.
I was also thinking about Unit4 and i read the wiki-page, even if i didn´t understood the details, i kinda got it. But i think i may have found a solution, at least for my kind of problem.
So i can totally see, why this is not working for open areas, my maps will be more like mazes, with connections between the paths.
So i think i have a method, which will work this kind of maps in a acceptable time, but till now its just on paper and not in code, and it will take time for me, cause much of the stuff i have to do, is quite new for me.
Anron, if you are interested in the method i´m aiming for, write me a pm, you might like it (or laugh, because i forgot something obvious). I will anyways answer here, IF i got it working.
Thx again for your help!
Hi
If it is a maze, then it might be a tree (graph terminology), if that is the case, then it is easier.
See http://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work that might give you some ideas. Note that this only works if it is a tree, i.e no cycles.
Hey Aron,
it´s me finally having pathfinding on my schedule again.
So i´m currently working on Unit 3 from the first post and i´m havin a bit trouble setting up my Astar environment propperly to fit my needs.
Goal:
- Unit 1 finding the shortest path through an environment of premade obstacles and player-builded-obstacles (walls) while runtime. Player can build those walls during runtime.
- Unit 2 finding the shortest path, getting blocked by premade-obstacle, but not affected by walls from the player.
- a checking-routine which prevents the player from blocking of Unit 1 completely.
Setup:
-
I´m using a Gridgraph
-
Collisiontest is on and set to all Layers of premade obstacle objects, obstacle-nods get successfully marked red
-
no heighttest yet, since the actual test-map is flat.
-
for the walls i used also a collsiontest-layer and used this to check for pathblock:
GraphUpdateObject guo = new GraphUpdateObject (structure.GetComponent().bounds)
bool blocked = GraphUpdateUtilities.UpdateGraphsNoBlock(guo, startNode, endNode, true);
This is working so far, but i see no way to make this node walkable again for unit 2.
It seems that nodes marked by a collisiontest are kinda out, even if you change the tag. How are they treated internaly? Do they get a special tag/property or do they get deleted out of the nodes available for pathcalculations?
So i got into the tag system you recommended and changed the setup a bit.
- only premade obstacles get collisiontested.
- walls get a GraphUpdateScene component and set their nod to tag “wall”, which will checked off in unit 2´s tagmask. The Checkbox on the GUS for physicsupdate seems to be needed to be checked, to effect colliders, right?
In this case the units act like they should (with a tiny bummer, cause i didn´t yet managed to get the update during runtime done).
The mainissue here is atm, that i also don´t know how to setup the UpdateGraphsNoBlock method, to check for a blocked path, taking in concideration that we can´t walk tag “walls”.
This function seems to just take nodes blocked by collision test in concideration.
So if it´s possible to make nodes blocked by collisiontesting walkable again for certain units, or to take a certain seeker.tag setup in concideration for the noBlockTest i would be very happy 
Im well aware that i might got the whole setup a bit wrong, cause having a GUS on every wall just for changing a tag of that very node the wall is standing on, seems a bit overheaded 
So i´m really curious now how to get this done proper.
Hi
There is no out of the box support for that currently. However you can with relatively simple modifications make sure UpdateGraphsNoBlock work for you.
The line you want to change is
worked = worked && PathUtilities.IsPathPossible (nodes);
That checks if all nodes still have valid paths to each other. What you want to do is to create a new method which takes a tagMask. For the first node you would call PathUtilities.GetReachableNodes with the tag mask, for the rest you would make sure that the first node can reach them.
Something like this
/** Returns if there are walkable paths between all nodes.
* If you are making changes to the graph, areas should first be recaculated using FloodFill()
*
* This method will actually only check if the first node can reach all other nodes. However this is
* equivalent in 99% of the cases since almost always the graph connections are bidirectional.
* If you are not aware of any cases where you explicitly create unidirectional connections
* this method can be used without worries.
*
* \warning This method is significantly slower than the IsPathPossible method which does not take a tagMask
*
* \see AstarPath.GetNearest
*/
public static bool IsPathPossible (List<GraphNode> nodes, int tagMask) {
// Fast check first
if (!IsPathPossible(nodes)) return false;
// Make sure that the first node can reach all other nodes
var reachable = GetReachableNodes(nodes[0], tagMask);
bool result = true;
for (int i=1;i<nodes.Count;i++) {
if (!reachable.Contains(nodes[i])) {
result = false;
break;
}
}
// Pool the temporary list
Pathfinding.Util.ListPool<GraphNode>.Release(reachable);
return true;
}
Hey Aron,
first of all: Thanks for your great support here. Providing help on unfeatured requests is ace!
Concerning your function. Currently i´m struggeling in getting the right integer input for the custom IsPathPossible method. Since you are not using Unitys LayerMask (which provides a .value function) i can´t figure out how to convert your TagMask-Class into an int value.
I can see in inspector on my unit with the tagMask that it should be: 11111111111111111111111111111101
TagMask mask = GetComponent().traversableTags;
Debug.Log("Mask: " + mask); gives me this:
Mask: 11111111111111111111111111111101
11111111111111111111111111111111
Which is confusing because of the extra digits…
I tried something like this for the int property, but it seems to have a diffrent value in your class:
int mask = ~(1 << 31); //everything on, except the second tag
Is it possible to remove a GridNode from a GridGraph with out placing a GUO and scanning the graph around it? since the nodes are uniquely identifiable by their .position value for example, it should be possible to remove a specific node?
Hi
Sorry for the confusing fields. Only the “tagsChange” field on the TagMask should be used. I had to use two fields in previous versions of Unity because I had to work around a limiting API. In Unity 4.6 (I think) they lifted this restriction but I have not yet refactored the code.
I will likely change this in the next update so that there is only a single field.
You can make a single node unwalkable easily.
// Only update the graph inside safe update callbacks
// Otherwise we might update it at the same time as pathfinding is executed
// in another thread, which could cause all kinds of issues
AstarPath.RegisterSafeUpdate (() => {
// Get the closest node
var node = AstarPath.active.GetNearest (somePosition).node as GridNode;
node.Walkable = false;
// Update the connections of all neighbour nodes
node.GetConnections ((node) => GridGraph.CalculateConnections(node as GridNode));
// Makes sure that pathfinding area data is up to date
AstarPath.active.FloodFill ();
}
Hey Aron,
i made some significant progress with using your Pathfinding tool for my Enemy-Features. It was really a hard travel up so far, hitting a lot of walls, while trying diffrent approaches, but i found solutions for 6 out of 7 enemys so far.
For my last Enemy i have some ideas and i´m currently making a possibility check research through your docs, if i can get i hooked up with you design pattern.
Some questions i couldn´t answer myself.
-
is it possible to let the seeker pull a path out of another source then Graphscollection stored in AstarPath. The idea is to use mainGraph = (GridGraph)AstarPath.active.astarData.graphs[0]; to make a copy of a graph, make some Nodes unwalkable and then calculate a path for a specific unit out of this graph.
-
with the custom isPathPossible method i couldn´t get it to work. I did some Attempt to include it in you classes, but i was unsure where exactly and was afraid of breaking something. I had a version, wich seemed to be right, but UpdateGraphsNoBlock didn´t work as expected. i guess somewhere i missunderstood something. as i get it right it´s just another overloaded method of isPathPossible… Is it maybe possible to include this in the next Update, since it might be in general a useful feature to be able to make pathchecks concidering tagrestrictions.
---- Both approaches aim for a unity which marks parts of the graph unwalkable for just him and have important methods available like isPathPossible and the seeker to search on this graph for the shortest path concidering those unwalkable nodes. isPathPossible is needed for deadend-checks while placing those individual tags/unwalkables.
- what also be a very handy feature, if it were possible to set the settings for each graph individually, not global. especially something like maxNearestNodeDistance would be awesome to have seperate for diffrent graphs. Or better let it be a variable set in the seeker, so the bot decides what maxdistance is appropriate.
If something like this is allready there it would help me to fix a still unsolved issue with one of my units. since it´s a range unit it doesn´t have get as close to a target point as the others, to get a valid path. If it´s possible to set this value in the unit, i could let it exist in the same graph as the others. If could make this setting individual for serperate graphs, i could give unit another graph.
Right now the only possibility i see is is giving this unit a new astar instance, which i don´t know how to handle and also seems a bit off 
- last but not least just a question helping me better understand what your intention here was: GraphUpdateScene is a Component i can use at gameobjects. GraphUpdateObject is for constructing the class in a class, having less features like inScene drag and drop for making areas.
So basically they are doing similar things like setting nodestuff and so on.
Why can´t i use the gus in functions like UpdateActiveGraph(GraphUpdateObject guo)?
Hi
If you really want control over what nodes are walkable and which ones are not you should subclass ABPath and override the CanTraverse method (just noticed it is not virtual, but that’s easy to fix).
class MyPath : ABPath {
public override bool CanTraverse (GraphNode node) {
return ....;
}
// Required for pooling
protected override void Recycle () {
PathPool<MyPath>.Recycle (this);
}
}
You should know that IsPathPossible which takes a tag mask is a lot slower than the IsPathPossible which does not. The one which does not take a tag mask can calculate the result in constant time (quickly) but when using a tag mask it actually needs to search the graph.
UpdateGraphsNoBlock is not just an overload of IsPathPossible. It is kinda similar, but by default it will change the graph if it would not block.
Hej Aron!
I think I’m having a similar problem, where separate units need individual criteria for what nodes they can traverse. In my game, I want villagers to pathfind through a village without crossing through each others houses. I could tag all houses and exclude that tag from pathfinding, but each unit must still be able to pathfind inside its own house (and its destination house). I guess I’d then have to set up some weird, unit-specific tags and update the graph every time a unit needs to do pathfinding, and that seems super-clunky.
It would be more convenient to override ABPath, as you described above. Do I understand correctly that the “easy fix” is to edit the AstarPathfindingProject source code? I have tried making Path.CanTraverse virtual so I can inject my custom code in a subclass. (I also had to override ABPath.Construct and create an empty constructor for my subclass to make it compile.)
My CanTraverse-function is now being called, but I’m not sure how to handle the GridNode parameter I get. How do I convert the int3 position member to world space? And is there an easier way to get the result I’m after? I have a feeling I’m making this way too complicated
Thanks for an awesome library!
for the int3 position you can use (vector3) before it to convert it into a vector3, wich should be in world position. Other then that you could use path.vectorpath to get the vector directly
