Tag/Penalties applied to Connections instead of Nodes?


We’ve been using the A* Pathfinding Project to create a custom point graph for our 2.5D platformer. So far, it’s been working pretty well, but as we’re adding new enemy types, we’re realizing that the connections between nodes in the graph need to have more data for our purposes: All the nodes in the scene are equally valid for all characters (so far, at least), but the issue is that not all connections are equally valid for all characters. Some AI characters can jump/move in a way that allows them to move between two nodes that other AI characters are incapable of doing.

We thought of adding a separate graph for each type of enemy, but this seems like such a waste, since all the nodes (and there are a fairly large number in the scene) would be unnecessarily duplicated a bunch of times (and we’re targeting mobile!). We think it would make so much more sense to just tag the connections between nodes instead of the nodes themselves, but we haven’t been able to find any documentation or discussion about such an approach.

Is there any way tag the connections and have the pathfinding account for those tags, similar to how it accounts for tags on nodes? Or maybe there’s another, better approach to the problem of the different behaviors of our AI?



Sorry, there is no way to tag them directly (for memory and performance reasons, it creates a very large overhead for larger graphs). I am not sure what graph type you are using, but if you want to tag the connection between A and B, you add a node C in between them and tag that node instead. Would that work for you?

You could of course also extend the node classes and create a new node type with the data you want. But that requires some code.

Hi Aron,

First off, thank you for A) Having such a great product and B) Being so responsive and helpful.

We’re using our own custom graph that extends your NavGraph class, and it is very similar to your PointGraph class. It looks like our best bet (and what we’re going forward with) is extending your PointNode class with our own CustomPointNode class that also keeps track of connection tags with public uint[] connectionTags. Truthfully, this is what we were considering doing, but we wanted to make sure that we weren’t re-inventing the wheel here. We’ll continue to look through your documentation and code to find out how to make the A* search account for these tags we define.

Thanks again!

Ok, sounds great!

The method you should be looking for is the “Open” method, override that and provide some filtering on which connections can be taken.