Navigating through a list of points

#1

Hi,

I’m wondering if anyone can help me here, I’m working on a project to run a simulation. This simulation requires that my enitities navigate along a series of points i.e. list of Vector3’s. I’ve been trying to find help online but there’s nothing out there that tackles the issue of AI type navigation.

Does anybody know how I could do this? This is what I have at the moment:

var nextPoint = _routes.First(x => x.Key == drone.Key).Value.First();
var speed = _speeds.First(x => x.Key == drone.Key).Value;
drone.Value.Transform.Position += Vector3.TransformCoordinate(nextPoint,Matrix.LookAtLH(drone.Value.Transform.Position,nextPoint,Vector3.One))*speed;

Not too sure what this is doing but it doesn’t seem to be working.

Any help would be greatly appreciated.

Thanks,
Jack

#2

Not too sure what this is doing but it doesn’t seem to be working.

So let’s start by breaking this down! n_n Sorry if I go too far as I’m not sure what parts exactly you’re unsure of, but hopefully this can help others too!

Since there isn’t much to go off of here, I’m going to assume some things. I’m assuming that drone is a Key/Value pair from some iterator? And the routes and speeds are also Key/Value pairs

_routes.First(x => x.Key == drone.Key) [..]

We start by getting the first route with a key that matches drone’s using the LINQ extension First() and the lambda expression x => x.Key == drone.Key, where x represents a route Key/Value pair

[...] .Value.First()

Since _routes is a collection of Key/Value pairs we only need the Value from it- which should be a collection of vectors, and we call First again to get the first Vector3 in this route.

_speeds.First(x => x.Key == drone.Key).Value

Same thing here, only we’re getting the first speed that shares a Key with our drone.

#So far no problems!
Except that this will only ever get the first point in the first route for all of your drones- unless you’re altering the route elsewhere; e.g. popping the first Vector from a Queue when you reach it.

.

#Here’s Where Things Get Weird

drone.Value.Transform.Position += Vector3.TransformCoordinate(nextPoint,Matrix.LookAtLH(drone.Value.Transform.Position,nextPoint,Vector3.One))*speed;

Ok, so…

Matrix.LookAtLH(drone.Value.Transform.Position,nextPoint,Vector3.One)

Here we create a Left-Handed Look At transformation matrix. The first parameter is our origin, the second is the look-at target, and the third is our Up direction. In most cases, the third parameter should be Vector3.UnitY (0,1,0) in left-handed coordinates, whereas here we’re passing in Vector3.One (1,1,1). Though this might not help anything, as…

[...] Vector3.TransformCoordinate(nextPoint, [LookAtMatrix])*speed;

… I’m not entirely sure what the point of this bit is. IIRC a LookAt Matrix is used to project other positions into local coordinates relative to a view and position. So I believe the result of this will always be (0, 0, d) where d is the distance from the drone to the next point. I’m a bit fuzzy on this, however, so I may be wrong.

Perhaps what you’d want to do here is get the direction from the drone to the nextPoint, then multiply that by speed? It could be something like Vector3.Normalize(Target - Origin) * speed, where Target is the nextPoint, and Origin is our current position (the drone’s Position)

drone.Value.Transform.Position += Vector3.Normalize(nextPoint - drone.Value.Transform.Position) * speed;

Not sure if this is the most efficient way, but it’s easy to understand imo.

.

To be honest though, I don’t have the editor open in front of me! Haha, so hopefully this all compiles fine. n_n’ I at least double checked the API docs, so it seems fine.

#TL;DR

I’d recommend using the direction equation above instead of the LookAt matrix transform, if for nothing else because it’s simpler.

If you haven’t already, look into either popping the first vector from your route when you reach it, OR store off the index of which point in the route each drone is on, otherwise they will only go to the first point. In either case, since their speeds are constant, you may need to check if their distance to the target is less than their speed or they’ll vibrate around it.

Sorry for the ramble. Hope this helps!

2 Likes
#3

Hi,
Thank you for your response, I’ll give this a try now.

I’m ok with the whole LINQ and iteration part. The part I’m struggling to understand really was the TransformCoordinate method, I was thinking that it was similar to the MoveTowards method in Unity but I could be mistaken. Do you know of any good resources that would explain these methods? I had a look through the object browser and this gave the best explanation but it was still a bit ambiguous.

Thanks again,
Jack.

#4

Gotcha!
Well, then, yeah the Position + Direction * Speed above works like Unity’s MoveTowards, except you’ll have to cap it yourself when the distance is less than speed.

Here’s something more encapsulated:

public static Vector3 MoveTowards(Vector3 origin, Vector3 target, float speed)
{
    Vector3 difference = target - origin;
    float distance = difference.Length();

    if(distance < speed || distance == 0.0f) // Avoid divide by zero issues
        return target;

    // Same as normalizing and multiplying speed, but reusing our length since it's expensive to calculate
    return origin + difference  * (speed / distance); 
}

TransformCoordinate applies the transformation matrix to the coordinate without taking it out of coordinate space (ignoring perspective distortion / assuming it’s 1). It’s very generic, but also super handy

At the moment, the best resources I’ve been able to find have been the API Docs here and comparing against similar APIs and Linear Algebra algorithms. Some things mirror managed DirectX, so a bit of the information on Microsoft’s website has been helpful.

Sorry I can’t be much help with resources n_n’

1 Like
#5

Ah perfect, thank you for your help.

I’ll try this solution and see how I get on.

Thanks,
Jack.