A* Node Pathfinding Optimization

Unity Engine
1

Hello Unity Forums! :slight_smile:

I have created a very simple node-based pathfinding script using the A* algorithm (or more specifically, a version of the pseudo-code found on wikipedia :)). It uses nodes placed within the scene (at every corner), which have a node script attached. This node script has data on that particular node, such as linked nodes and availability. It finds a path (currently its not the shortest path, but I think I know the heuristic that will find the shortest), but the path currently has to start and end at a node.

I plan for it to be used for the character AI. Unfortunately, since the game is not based on a grid system, the characters are not going to always be on a node or moving to a node (eg. enemies may see the player and stray off the path to attack). Therefore, I do not know the nodes that are nearby the character, nor do I know the nodes that are nearby the target.

I thought perhaps to make these “dynamic” nodes, which, every so often (perhaps one raycast per frame, or all the raycasts every second), cast a ray to every node in the scene to check whether they can be linked. Then I have a dynamic node for the character and the target, that find all the neighboring nodes, so that it can find the path.

I believe this can work, but my question is: Is there a better (more efficient) method of doing this? In my scenes, there may be hundreds of nodes. If I cast a ray for every one of those nodes, per character, I would think that would be very cpu intensive. I’m not asking this on UA because there may be many answers to this and probably some personal preference. Also UF is better for conversation.

If your wondering why I’m not using a pre-made pathfinding system on the asset store, it’s because most are in C# and are appear to be overly complicated.Although I can read C# well, I don’t really feel like going in and putting in some touches in a program that I do not completely understand (especially in this case). Also, I don’t like the interface ;).

Thanks for reading and for all responses and comments! :smile:

2

Welcome to the rich world of problems when using a node-based path representation.

It is correct that you usually let the actor be a dynamic node, run the algorithm with this node as the starting node and your target position as the ending node. To efficiently connect this starting node to your path system you should subdivide your path nodes into subareas such that both sides of a bridge are separate subareas. That way you just have to find the appropriate subarea your actor node belongs to. However, you may already notice that this is a lot of overhead to work around the fact that nodes are not the right tool for the job. It looks like what you’re looking for is actually a mesh, not a net of nodes that essentially does the same thing, just worse.

My rule of thumb is: If you are not navigating on a grid, use navigation meshes instead of nodes. For more information on the difference between a navigation mesh and navigation nodes you might want to read this article: ai-blog.net - ai blog Resources and Information.

3

Ah, very nice link. Do you know of any tutorials or just general information on NavMesh? If not, I guess I’ll go and buy one in the Asset Store. Thanks it very useful! :slight_smile:

4

If you are willing to create the navigation mesh by hand it shouldn’t be too hard to think of a way of doing it. Automatic navigation mesh generation is a difficult topic though, there are commercial packages out there that cost thousands or even hundreds of thousands of dollars. As far as I know Unity 3.5 Pro came with an algorithm for this, but I don’t know whether or not you can use the resulting mesh for your own path finding algorithm.

If you want to prototype your own implementation you might want to organize the mesh in quads or n-gons instead of triangles and you can even store the nodes of these polygons as GameObject instances if you prefer to do so - it would simplify dragging the nodes around to adjust to the world geometry. However, you have to be aware that this is a few weeks worth of work. For tutorials Google shouldn’t be the worst place to start, but the article I linked also has a lot of links in it that discuss navigation mesh generation. Just scroll all the way to the bottom, the articles are linked right above the comments section.

5

Yes, I plan on making it by hand. My geometry isn’t very complicated. Thanks again, you’ve convinced me to use a NavMesh. But how exactly does NavMesh pathfinding find dynamic (Instantiated/Moved during runtime) objects? Perhaps I will find a tutorial out there that will tell me, but if you would, or at least how you think it may work, I would very grateful. :slight_smile:

6

I’m not entirely sure if I understand your question correctly.

Your pathfinding should consist of two parts:

  • A* pathfinding
  • Dynamic obstacle avoidance

In case of a navigation mesh you guarantee that within one mesh polygon an actor can move around freely, with the exception of a few other dynamic obstacles (like other actors) that are being avoided dynamically. An additional condition for the polygons could be that they have to be convex, e.g. any point within a polygon has a direct line of view to any other point in this polygon without the view ray leaving the polygon at any point. This greatly simplifies navigating on the navigation mesh as you can guarantee that you can just move “in the direction of the next polygon of my path” and will not leave the valid moving area.

The workflow could be as follows:

  • Find the polygon of the actor (start point)
  • Find the polygon of the target (end point)
  • Find the list of polygons the actor has to move through in order to reach the target (A*)
  • Until the target is reached: Move the actor to the next polygon while avoiding dynamic obstacles by the means of your dynamic obstacle avoidance

The dynamic obstacle avoidance should only avoid other moving objects, all static objects are being handled by your navigation mesh. This can for example be implemented using raycasts.

7

A mesh solution will indeed be neat, but with that said it is not that easy to create and as plzdiekthxbye says then you will likely have a few weeks of work in front of you.

He did touch something you could do (not the best solution), but that is to save an array with all nodes (class or struct), which contains all connections to other nodes and position in the game world. Then chunk them in some matter like all nodes between 0-10 x and 0-10 z and further.

Create a method that will search through the chunks first and then the chunks nodes to find the nearest. Do this for both start and end point.

Even with 1000s nodes it wont really be slow. It is just important that you use the right data structures for the A* (priorty queues is one thing to look at)

8

@plzdiekthxbye
Ah, I see how it works. Thanks for clarifying! :smile: Sorry if I wasn’t clear, I’m not very experienced with this sort of thing.

@BFGames
I get what your saying, I’ll make sure to do that if I decide to go for nodes (which I may). I’ll look up priority queues aswell.

Thanks, you’ve both helped a lot! :smile: