Hi Aron,
I’m wondering what you use to hold your node/cell data in. Do you use a class, or a struct, or something else?
Also, when you iterate through your nodes, are you using a built-in array or a list or, again, something else?
The reason I’m asking is because I’m trying to learn how to do fast node searches for a different pathfinding algorithm (not astar), and since your algorithm rocks I figured I’d ask you what you do 
I use classes. Structs would mean a lot of copying and also then I could not use references for node connectivity. Barely any node iteration is done when pathfinding, then only the node connections are traversed. But nodes are stored in built-in arrays in the current versions. I have other versions which store it a bit differently for each graph type and use a function with a callback to iterate through them, that also works, but it is a bit slower. Node connections are stored in a built-in array for most graph types. The exception is grid graphs where the node connections are simple offsets in the node array.
When doing pathfinding, you gain most from having a good complexity, so for example using a binary heap for getting the node with the lowest F score (which the A* algortihm must do every step) will gain one much more than simply optimizing a linear search to run 10 times as fast because a binary heap does it in O(log n) time, while a linear search does it in O(n) time. Check out big O notation on wikipedia if you do not already know about it.
What other pathfinding algorithm are you thinking about?
Wow that was a quick reply thanks.
Well I’m being overly ambitious and wanting to implement hybrid flow field pathfinding in my game. Which, honestly, is probably way above my current programming knowledge-set.
Currently I have your excellent A* pathfinding working in my game (using a grid graph). But since from what I’ve read on these forums local avoidance doesn’t work with grid graph’s yet, I desparately need some form of accurate local avoidance.
Realistically I’ll probably have to find some local avoidance solution that integrates with your A* pathfinding (since I already have your system set up and working). For instance, how can I have a unit following the A* path go around a slower unit as they’re traversing the path? That’s just one example problem among several.
Flow field pathfinding looks amazing for rts games. But it’s relatively new, and more importantly, very complicated for a beginner programmer like myself.
So my two options right now are:
A: Use A*, but somehow integrate it with local avoidance (on a gridgraph)
B: Use flow field pathfinding
Whoa, flow field pathfinding. That’s something I haven’t attempted (though it does look cool I must say).
Local avoidance does not work with grid graphs in the sense that units will not dynamically avoid grid obstacles, but it works just fine following a path and avoiding other units.
I think you could program some flow field pathfinding Aron. I’d be willing to pay upwards of $200 (possibly more) if you made a flow field package for Unity, hint hint, nudge nudge lol
I’m a little confused though now on what you mean about your local avoidance. Do you mean that if, for example, (on a gridgraph) that if a unit is traveling east, and another unit is traveling west, and they’re about to collide, that with your local avoidance they will go around each other – and it will work on a gridgraph?
Because when you say “units will not dynamically avoid grid obstacles”, do you mean static grid obstacles, or do you mean moving ones? I guess I’m thinking that units are simply a type of moving grid obstacle themselves. Am I mistaken?
Sorry, I’m thoroughly confused now.
The local avoidance works with two types of objects. Agents (moving units) and obstacles (static polygons obstacles, though their position can be updated quite quickly and efficiently, they are still considered static). Agents can avoid each other at all times. However for navmesh graphs, it is also possible to build a static obstacle representing the navmesh edges to make sure the agents also avoid to go outside the navmesh. For grid graphs this would also be possible, to avoid unwalkable nodes, but I haven’t implemented that yet.
Heh, nice monty python reference
I will see, but I don’t think I will implement flow field in the near future.
Ok, so even on gridgraphs, agents will avoid other agents when they’re set up to use your local avoidance. If that’s the case, that is fantastic.
I’ve been reading how to set up agents, and I know that you use a character controller with your local avoidance. Is it possible to get it to work if I have my agents simply using a rigidbody and a collider (without a character controller)?
When I first started programming, the character controller seemed to be causing performance issues – so I avoided using them. But perhaps if I implement them now, there will be no issues. Or, better yet, maybe I can get your local avoidance system to work without a character controller?
Thanks Aron.
The local avoidance system itself is almost completely separate from Unity (except using a bit of its API, like Vector3). There are some wrapper classes like RVOController. The RVOController does not actually use a character controller, only a simple raycast for finding the ground. When using A LOT of agents however, more even lightweight approaches are desirable (that’s the scale when creating a gameobject for each agent is too much, so you are talking > 400 agents at least). The RVO example scenes contains an example where all agents are rendered as squares which is very lightweight.