I need help configuring the A* Pathfinding Project to suit my level. Is it even possible?

Hi, I bought the Pro version of the package, thinking it would be easy to set up. But I’m having trouble figuring out which option would be best for me.

I’ve read through the documentation, particularly the section on Spherical Worlds, and it seems like my case. In my game, there’s a space station where players can move without gravity, grabbing onto walls, ceilings, and floors. There’s no real horizon, top, or bottom in the game. And I have NPCs, spiders, that roam the station and attack the player when spotted.

My idea is for the spiders to move on all surfaces—floor, walls, ceiling—building a path across them and jumping at the player when they get close. According to the documentation, NavMesh Variant seems suitable for spherical worlds.

I have two questions:

  1. Can I achieve this behavior through automatic mesh generation using raycasts or points?
  2. I’ll attach a screenshot of my level. I manually added NavMesh graphs to all surfaces, and they rendered fine. But when there are many, my NPC spider can’t compute a path; it takes too long, and it just stands still without moving.

Can you advise me on how to solve my problems? Or perhaps suggest a simpler way to achieve the effect I need?

Thanks!

Hello everyone, again. I tried to merge my level into a single mesh, and it turned out very well; I’ll continue using it. However, for some reason, with A*, all agents behave a bit differently. They reach the edge of the room and don’t want to leave it, as if they can’t walk through walls and can’t climb to a hole in the wall because of a threshold. I’ll try to illustrate the problem with screenshots.

I’ve used all types of AI agents; some don’t move at all, while others get stuck like this or tumble around. But none perceive this mesh as a surface for pathfinding.

I’m not asking for a ready-made solution or answers to all questions. I’ve been studying the documentation for the second day and can’t understand or decide which direction to move in. Which type of graphs is better to choose, and which pathfinding agent to use? Or is it impossible and everything needs to be written from scratch?









Hi

This seems doable, assuming that the spiders only have to crawl on walls, and that you switch to a separate system when they jump to attack the player (pathfinding will not help you there).

You can visualize the graph using the Area option (A* Inspector → Settings → Graph Coloring). If it’s possible for the agents to move from one part of the navmesh to another, they will have the same color.

For a navmesh to be connected, the triangle vertices must line up perfectly. You can’t have gaps in it, as then the agents will not realize that they can move over it.

Also. You cannot use the RichAI movement script for this. You’ll need to use the AIPathAlignedToSurface component (or a custom movement script). The FollowerEntity movement script also works, but it currently doesn’t have as good normal smoothing, so the AIPath script might be preferable at the moment.

1 Like

Thank you for your quick response. In the meantime, I have also made some changes.
I have reviewed examples and also read the documentation. Here’s what I’ve understood for myself:

  1. I have a graph of NavMesh type with a large mesh of my space station.
  2. I added an RVO Simulator to it and selected the parameter MovementPlane = non-plane.
  3. I added a Funnel Modifier and set its parameter Split At Every Portal = true. This resulted in my entire station being covered with a NavMesh grid, the connections are perfect, but for some reason, each object is a different color, even though they are all part of one large mesh. However, they are divided into layers within this mesh, and these layers were also transferred here, which I did not want.

For my agent, I configured it as follows:

  1. Added the AI Path Align to Surface script to my spider with the parameter Constrain Inside Graph = false.
  2. Added the AIDestinationSetter script to my spider (set it to my player).
  3. Added an RVO Controller to my spider.
  4. Added a box collider to my spider.

Agents move well within one room but refuse to step over the threshold and exit the room because there is a NavMesh of a different color. I don’t understand what I am doing wrong and how to connect it. Is the issue specifically with the mesh of my station?

I would be grateful for any recommendations on configuration and advice.

I am attaching a couple of screenshots with the settings and view of the station.






Hi

This, to me, sure doesn’t look like the vertices are aligning perfectly between the rooms.

1 Like

Hello Aron.
I completely rebuilt my mesh in Blender, greatly simplifying the polygons and combining them into one object.

The A* system has significantly improved in tracking the surface of the navmesh.
Now all areas are of the same color.
Agents correctly build paths along the surface and start moving in the right direction.
But for some reason, they cannot overcome the passage in my room.
It seems like they don’t see it at all and don’t perceive it as a passage, even though there is nothing obstructing it. Perhaps you need to mark it with some additional object? Like a portal or a hole?
Thank you in advance.

I attach a couple more screenshots of the issue.







Hi

The paths look correct, so pathfinding seems to be working.
You could try to make the transition a bit smoother. The movement script is not great at handling sharp 90 degree changes in the surface normal. Just a small bevel should do it, I think.

1 Like

Is there a way to cut out this threshold from the nav mesh grid? So that they simply step over it without paying attention to it? Perhaps some kind of hole modifier or manually laying out the path in this area?

Is it possible to somehow change the size of the agent itself?

Thank you for your assistance and prompt response.

You control the navmesh completely, since you are using a navmesh graph. So you can do whatever you want with it.
However, in this case, I think it is the physics part that might be problematic. Essentially, close to the ledge, they will try to follow a path directly downwards, from the spiders’ point of view, and then they either move really slowly, or come to a complete stop.

1 Like

Got it, thank you. Unfortunately, I can’t add a bevel, it’s dictated by the level design, sharp angles are required. And unfortunately, I couldn’t handle this threshold with the standard scripts that come with the package. I’ll try to write my own script. In fact, what I need is everything that is in the standard package plus the ability to specify the step height of the agent so that they can ignore such thresholds.

In any case, thank you very much, you are making an amazing product.



Alright.
Keep in mind that the collision mesh need not be the same as the rendered mesh.

1 Like

Hi Aron, Hello everyone.
Guys, I’m really struggling to set up my level with spiders properly. I’ve tried all the settings options available, but nothing seems to help.

The main issue is that the spider completely ignores the pathway. I’ve tried smoothing out the angles on the pathway and even making the mesh more complex but uniform, but nothing changes. The spider’s behavior remains more or less the same.

What’s interesting is that it seems to completely disregard the pathway as if it doesn’t exist, even though the path is clearly defined, and sometimes there are no obstacles at all along the way. I’m still using AIPathAlignedToSurface and NavMesh as the graph type constructed from my level’s mesh.

Below, I will attach two video recordings of my spider’s behavior. The first one features a simple mesh, while the second one involves a more complex mesh. Please take a look; I would greatly appreciate it.

Would appreciate any help or advice. Thanks!

I understand that the issue lies in the raycast casting directly downwards from the character, whereas they should also extend slightly at an angle. However, I’m struggling to decipher the library code to write a modifier correctly to address this. Has anyone encountered something similar? Or perhaps there’s an example of another task involving modifying raycast behavior? Any guidance would be appreciated; I’m at a loss. :slightly_frowning_face:

I tried to write my own AIPathAlignedToSurface, but it seems I completely misunderstood something. It looks terrible, although I like how the path laid out looks. But the spider has stopped reacting to walls altogether and just walks through them without turning. I need a nudge or any help.

using Pathfinding;
using UnityEngine;

namespace Vetal.Scripts
{
    public class AIPathAlignedToSurfaceExtremeDegrees : AIPathAlignedToSurface
    {
        protected override Vector3 RaycastPosition(Vector3 position, float lastElevation) {
            var rayLength = tr.localScale.y * height * 0.5f + lastElevation;
            var rayDirection = -movementPlane.ToWorld(Vector3.forward, rayLength);
            var rayOrigin = position + movementPlane.ToWorld(Vector3.forward, rayLength) * rayLength;

            var hits = new RaycastHit[10];
            var hitCount = Physics.RaycastNonAlloc(rayOrigin, rayDirection, hits, rayLength, groundMask, QueryTriggerInteraction.Ignore);

            for (int i = 0; i < hitCount; i++) {
                if (!hits[i].collider.isTrigger) {
                    verticalVelocity = 0;
                    return hits[i].point;
                }
            }

            return position;
        }
    }
}

Hello everyone!

I want to share the results of my work with A*.

I managed to make my character search for the ground around itself, and when it found it, change the direction of movement. Additionally, I redesigned the mesh of my level and regenerated the navmesh, which significantly improved the situation, but it’s still far from perfect. What bothers me the most is why my character sometimes detaches from the ground and starts moving in the air. Shouldn’t it always stay grounded?

I have questions regarding ray optimization. Perhaps someone has recommendations for optimization? Because right now, I’m doing it rather blindly.

Here’s an example of my code for the character and a small video of what I’ve achieved. I like the result, it looks cool. What do you think?

using System.Collections.Generic;
using UnityEngine;

namespace Pathfinding {
    public class AIPathAlignedToSurfaceExtremeDegrees : AIPathAlignedToSurface {
        [SerializeField]
        private float additionalRayDistance = 1f;
        
        [SerializeField]
        private float horizontalRaysCount = 10f;        
        
        [SerializeField]
        private float verticalRaysCount = 10f;
             
        [SerializeField]
        private float maxVerticalAngle = 10f;

        protected override void UpdateMovementPlane() {
            base.UpdateMovementPlane();

            var lAverageNormal = lastRaycastHit.normal;
            var lValidHits = 1;

            foreach (var aRayDirection in GetRayDirections())
            {
                if (!TryGetSurfaceNormalAtDirection(aRayDirection, out var aNormal)) continue;
                lAverageNormal += aNormal;
                lValidHits++;
            }

            if (lValidHits > 1) {
                SetInterpolatedNormal(lAverageNormal / lValidHits);
            }
        }

        private bool TryGetSurfaceNormalAtDirection(Vector3 aDirection, out Vector3 aNormal) {
            var lRayOrigin = transform.position;
            var lHitSomething = Physics.Raycast(lRayOrigin, aDirection, out var aHit, additionalRayDistance);

            aNormal = lHitSomething ? aHit.normal : Vector3.zero;
            
            return lHitSomething;
        }

        private IEnumerable<Vector3> GetRayDirections() {
            for (var i = 0; i < horizontalRaysCount; i++) {
                var lHorizontalAngle = (i / horizontalRaysCount) * 360f;

                for (var j = 0; j < verticalRaysCount; j++) {
                    var lVerticalAngle = -maxVerticalAngle + (j / (verticalRaysCount - 1)) * (2 * maxVerticalAngle);
                    var lHorizontalRotation = Quaternion.Euler(0, lHorizontalAngle, 0);
                    var lVerticalRotation = Quaternion.Euler(lVerticalAngle, 0, 0);
                    var lRayDirection = lHorizontalRotation * lVerticalRotation * Vector3.forward;
                    
                    yield return lRayDirection;
                }
            }
        }

        protected override void OnDrawGizmosSelected() {
            foreach (var aRayDirection in GetRayDirections()) {
                Gizmos.color = Color.red;
                Gizmos.DrawRay(transform.position, aRayDirection * additionalRayDistance);
            }
        }
    }
}





Useful links on the forum that can help. Thank you to all the authors, I found useful information.

1 Like

Hello, Aron,

I wanted to inquire about the ConnectTiles function that generates connections between nodes. I’m trying to figure out how it’s set up because it’s quite complex. I’m particularly interested in the part that creates connections between the tiles because, as it stands, they don’t always line up perfectly. My approach with raycasts works, but it seems a bit excessive and makeshift for my taste. I’d like to explore other possibilities. One active issue I’ve noticed, as you mentioned, is that 90-degree angles are poorly handled.

For tiles that are adjacent, their shared edge is checked, and if one exists, a connection between their centers is created. However, this does not take into account the angle at which the meshes are positioned relative to each other. As a result, connections are made through invisible parts of the mesh at corners.

I want to address and process this in the construction of connections, but I’m not sure if I’m looking in the right place. Is there perhaps a modifier that affects this? Or has someone already tackled this issue?






									if (maxalt > minalt2 && minalt < maxalt2) {
										// The two nodes seem to be adjacent

										// Test shortest distance between the segments (first test if they are equal since that is much faster and pretty common)
										bool identical = (aVertex1 == bVertex1 && aVertex2 == bVertex2) || (aVertex1 == bVertex2 && aVertex2 == bVertex1);
										if (maxalt > minalt2 && minalt < maxalt2 && (identical || VectorMath.SqrDistanceSegmentSegment((Vector3)aVertex1, (Vector3)aVertex2, (Vector3)bVertex1, (Vector3)bVertex2) < maxTileConnectionEdgeDistance*maxTileConnectionEdgeDistance)) {
											Vector3 normalA = CalculateSurfaceNormal(
												(Vector3)nodeA.GetVertex(0),
												(Vector3)nodeA.GetVertex(1),
												(Vector3)nodeA.GetVertex(2)
											);

											Vector3 normalB = CalculateSurfaceNormal(
												(Vector3)nodeB.GetVertex(0),
												(Vector3)nodeB.GetVertex(1),
												(Vector3)nodeB.GetVertex(2)
											);

											float angle = Vector3.Angle(normalA, normalB);

											if (angle > 140) {
												uint cost = (uint)(nodeA.position - nodeB.position).costMagnitude;
												nodeA.AddPartialConnection(nodeB, cost, Connection.PackShapeEdgeInfo((byte)a, (byte)b, identical, true, true));
												nodeB.AddPartialConnection(nodeA, cost, Connection.PackShapeEdgeInfo((byte)b, (byte)a, identical, true, true));
											}
										}
									}

		public static Vector3 CalculateSurfaceNormal(Vector3 vertex1, Vector3 vertex2, Vector3 vertex3) {
			Vector3 side1 = vertex2 - vertex1;
			Vector3 side2 = vertex3 - vertex1;
			return Vector3.Cross(side1, side2).normalized;
		}

Hello everyone, and a special shout-out to Aron,

I’ve found myself deep into the lengthy process of manually retopologizing an entire level again. The outcome is precise and satisfactory. I’ve tried importing various versions of models, both low poly and high poly, and the results are more or less the same. However, I’m still facing significant challenges with getting any sort of reasonable behavior from the pathfinding algorithm. Whenever a path goes around a corner or over a threshold, the AI starts to act erratically, wandering in circles and often failing to find the ground.

I suspect this issue might be related to how navigation paths between tiles are constructed, connecting their centers, which seems to cause a strange effect. And don’t get me started on AI walking on walls. The NavMesh variant of the graph seems extremely limited in capabilities.

Why is this happening, and what can be done to address it? At this point, I’ve invested a lot of time into this library but haven’t been able to obtain a clear result or find an answer on forums, unfortunately.

Any insights or suggestions would be greatly appreciated. Thank you in advance for your help.

Additionally, I’m attaching a couple of screenshots below to illustrate the issue more clearly. For some reason, spiders in the game are attempting to navigate through walls, even though there’s a perfectly viable path on the floor right next to them. It’s baffling. I’ve disabled my custom scripts to ensure there’s no interference, and I’m using the standard setup recommended in the documentation for a NavMesh graph in a spherical world.

This persistent issue has left me puzzled, and I’m eager to hear if anyone has encountered something similar or has insights on how to resolve it. Your feedback would be invaluable to me as I try to navigate these challenges.






As there are no answers since a few posts, I’ll try my best guess:
The path isn’t the problem. The problem is the Agent.
The agent always walks to the next path node, respecting physic colliders (as it seems, maybe it just respects the NavMesh, but from your Video, I doubt that).
So it tries to go after the path-points - and once it reaches a corner, the next path point isn’t on the corner but actually “inside” the corner, so it’s now behind the agent, so the agent turns around, while still not having passed the corner.

How to prevent that? If you have the normal vector of the next path point, then you can interpolate between your Agent & Agent Normal to your NextPathPoint & NextPathPointNormal. Then shoot rays downwards to see the actual physical Geometry. BUT all of this is just neccessary because of the custom NavMeshGeometry that’s behind the colliders. If you go back to the previous version of yours, there’s a much simpler way.

The path in this video is almost correct, you still have to turn off smoothing.
So what you have to do here is to remove all (navigation and physics related) components from your spider-agent. And then write a clean one without any kind of smoothing or steering. Just follow the path as if it was a spline. No physics, no anything. And then the Agents will absolutely reach their destination because there is absolutely nothing that could stop them, no physics, no steering, nothing.
And from there, you have a starting point and you can begin making it more pretty with some acceleration and deceleration along the path - and then you can think about ways to make spiders avoid intersecting with one another.
But you should definitely start with a version where your agents reach their destination.

1 Like

Hi leorid, thank you for your attention and response; it means a lot to me, especially since I was starting to feel a bit ignored here :slight_smile:

I tried the approach you mentioned. I removed all the physics related to navigation. Added a purely bare component with a single nav mesh graph. I uploaded there the simplest version of my graph (I have about a hundred different versions, from low poly to high poly). I added an agent to a 3D sphere, also just the basic one. And most importantly, I turned off gravity entirely for it. Then everything starts working perfectly, and I’ve attached the result in the first video.

The path construction and movement along it indeed work well. But as you can see in the video, it ignores everything and flies straight, even though it follows a path laid out nearby. I don’t understand why the agent detaches from the green line of the path. It seems like all settings have been reset to zero.

In the second video, however, I only turn on the gravity setting in the standard controller recommended for a spherical world. And immediately, all the problems that exist with walls and passages arise. You can check out the problem in the second video.

If you have a minute, please take a look and give your recommendations. Your opinion is very valuable and important to me. Thanks in advance, Vitaly

And here’s another piece.

As for the third option and what I’ve managed to achieve at this point. If you’re interested and have the time, you might want to check it out in the adjacent thread. Foolishly, I created a duplicate, and now the information is a bit scattered. In the last comment, I attach a rather long video and describe the problems that exist at the moment. Plus, there’s an example script there. With some research and my own modest efforts, I was able to adapt it for my case. It’s a pity that the situation is still far from ideal.
https://forum.arongranberg.com/t/seeking-help-with-navmesh-and-a-pathfinding-issues/15910/3?u=vitaliy.jafarov