- Home /

**Question**by InappropriateFeelings · Apr 28, 2016 at 05:14 AM · c#rotationvector3directionpathfinding

# Checking vector3 gameObject is about to move to (pathfinding collision detection)

I've been implementing an A* algorithm, and have been trying to add basic collision detection, and am failing very badly and just getting frustrated. Basically, the unit's update class checks if the unit has any vectors in the movement vector list. If so, it goes through a number of steps to decide what to do.

First, it rotates to face the target vector, then it creates a forward vector, which is meant to be based off the gameObject's position and takes rotation into account. So this can be used to check if there is anything in the node closest to that vector which would obstruct movement.

```
// unit MUST rotate before moving (otherwise forward node checks ruined)
transform.LookAt(listMovePos[0]);
// normalise the X and Z axis (only Y axis must change)
transform.eulerAngles = new Vector3(0, transform.eulerAngles.y, 0);
// forward checks node ahead of current node
Vector3 forward = transform.position;
forward += transform.forward * 0.6f;
Node forwardNode = Map.mapNodes[(int)forward.x, (int)forward.z];
```

That works in straight lines, but if the unit is trying to move diagonally past a stationary unit in an adjacent node, it sometimes freaks out and thinks that the occupied node is the one it's trying to enter... which it is not, since the other unit is sitting stationary for the duration of the unit moving along its path of vectors.

I'm just fed up and don't know what to do. Any suggestions greatly appreciated! Is there a specific piece of code I need to use to take any direction into account, instead of the above? Is there something else likely logically wrong, like the distance being too short for diagonals (in which case any suggestions)? Or is it possibly something else entirely?

In the above you can see a visualisation of the pathfinding. Blue tiles are open list, green are closed list. Cyan is start, red is end. Yellow is created upon the node the unit thinks is obstructed. As you can see, that node is indeed occupied by a sphere; but the unit's path successfully navigates around it diagonally, and yet gets confused and detects that node incorrectly.

The sphere is moving along the green tiles from cyan to red, and attempts to move around the other sphere by moving outwards and then inwards diagonally; moving outwards is fine regardless of the direction of travel, but moving inwards then always glitches the system and detects a false positive obstruction.

**EDIT:**

I have been following Glurth's advice, and investigating further, and there must be something simple wrong with the vector, as upon using more visualisation aides, it appears that the vector3 it is checking is ALWAYS off consistently.

In this photo the magenta tiles show the vector3s the movement is checking. They should be aligned almost exactly with the green path tiles, but they are not; they are completely off (in this case by about +0.8f, I am really confused now) So I'm just going to dump the whole code here and see if anyone can spot what is causing the unit to be checking a vector3 which is clearly not straight ahead of where it is looking? Any other improvements appreciated too, but this particular issue is crippling.

```
void Update ()
{
// refresh node this unit is occupying
node = Map.mapNodes[(int) transform.position.x, (int) transform.position.z];
if (listMovePos.Count > 0) // unit is moving
{
node.occupiedByMover = true;
// unit MUST rotate before moving (otherwise forward node checks buggered)
transform.LookAt(listMovePos[0]);
transform.eulerAngles = new Vector3(0, transform.eulerAngles.y, 0); // set X and Z axis (only Y axis must change)
// forward checks node ahead of current node
Vector3 forward = transform.position;
Vector3 normal = transform.position;
normal.Normalize();
forward += normal;
Node forwardNode = Map.mapNodes[(int)forward.x, (int)forward.z];
Map.Instance.CreateThing(new Vector3(forward.x, forward.y + 0.7f, forward.z), forwardNode, Color.magenta); // test
// refresh old node when this unit moves into new node
if (node != lastNode)
{
lastNode.occupiedByMover = false;
lastNode.occupied = false;
}
// then update old node
lastNode = node;
// assuming unit size 1, remove first index (that has been reached)
if (Vector3.Distance(transform.position, listMovePos[0]) < 0.1)
{
listMovePos.RemoveAt(0);
node.occupiedByMover = false;
node.occupied = true;
}
else // movement logic...
{
// this unit is about to move into a new node
if (forwardNode != null && forwardNode != node)
{
// this unit must wait if another unit is moving in forward node
if (forwardNode.occupiedByMover)
{
Debug.Log(" //NODE OCCUPIED BY MOVER");
Map.Instance.CreateThing(new Vector3(forwardNode.getVectorX(), forwardNode.getVectorY() + 0.7f, forwardNode.getVectorZ()), forwardNode, Color.yellow); // test
}
// this unit must repath around forward node occupied by a stationary unit
else if (forwardNode.occupied)
{
//move = false;
Debug.Log(" //NODE OCCUPIED");
Map.Instance.CreateThing(new Vector3(forwardNode.getVectorX(), forwardNode.getVectorY() + 0.7f, forwardNode.getVectorZ()), forwardNode, Color.yellow); // test
}
else // move normally
{
transform.Translate(Vector3.forward * speed * Time.deltaTime);
}
}
else // move normally
{
transform.Translate(Vector3.forward * speed * Time.deltaTime);
}
}
}
else // unit is stationary
{
node.occupied = true;
}
}
```

**Answer** by Glurth
·
Apr 28, 2016 at 07:17 PM

lf we assume the parameter you are passing in `movelist[0]`

, is know to be only 1 tile away, straight or diagonally: can't you skip a whole bunch of that stuff?

```
Node forwardNode = Map.mapNodes[(int)movelist[0].x, (int)movelist[0].z];
```

if NOT know to be one unit away.. I'd do it with the difference in positions.

```
Vector3 moveDir= movelist[0]-transform.position;
moveDir = moveDir.normalized;
if(moveDir.x==0.0f || moveDir.y==0.0f)
{//straight
//already normalized- nothing to do
}
else
{//diagonal
moveDir *= Math.Sqrt(2.0f); //1.4142... the length of the hypotenuse of a right triangle with the other 2 edges having length 1. (a diagonal in your grid)
}
Vector3 moveLoc = transform.position + moveDir;
Node forwardNode = Map.mapNodes[(int)moveLoc .x, (int)moveLoc .z];
```

Thank you for your reply! You make good points, but ask an even better question. :D In my case, the nodes will always be 1 away from each other. But, two things are at work. Firstly, the pathfinding already optimises the path by removing the nodes between the start and end of a straight line, and secondly I want to implement varying node density in future to reduce the number of nodes over long distance paths. So the future low density nodes may indeed not be 1 unit away. But high density (default) are.

So, though the first code you'd suggested would be the most sensible without changing the system, some version of the second might be the ideal solution? Regardless of whether the unit is using high or low density pathfinding, or whether the path has been optimised to reduce the number of vectors it contains, the unit will ALWAYS check 1 ahead to see if that high density node is occupied, and thus repath or wait or something. That's the problem. I hope that helps us find the solution?

P.S. moveDir doesn't need to be *= Math.Sqrt(2) if it could be 1.4? Sqrt computationally expensive, or is there a specific reason for doing that? Thanks! :)

You comments about the density, or more specifically distance between he nodes, is actually the answer to your question about the sqrt(2). I used sqrt(2), because of Pythagoras: c^2 = a^2 +b^2. If a and b are both 1, we get c^2=1+1=2 or c = sqrt(2). If your distance between adjacent is NOT equal to one, you will need to feed that distance value into Pythagoras' equation, as values for a and b.. c = Sqrt( dist^2 + dist^2) or c= sqrt(dist*dist*2). Also note that where the code says "already normalized" you would ALSO need to multiply by this dist between tiles value e.g. `moveDir*=dist;`

Edit: Forgot to finish answering, lol: Note that sqrt(ab)= sqrt(a)*sqrt(b) so, sqrt(dist*dist*2)= sqrt(dist*dist) *sqrt(2)= dist*sqrt(2). YES, you CAN just use the constant value sqrt(2). Then simply multiply the result by the distance between tiles to account for low density.

All that being said (because Glurth likes math) if always checking one unit away, AND we assume the movelist[0] parameter always represents the location of that tile, the first, single-line code should be sufficient. (exception: if your titles are LESS than one unit apart, you are going to run into issues with the mapNodes array indexing.)

Only if we need to **reduce** the distance from transform.position to movelist[0], such that we make sure we move only one tile away, would we need the other stuff.

Thank you for that reply! :D The point about 1.4 * distance is good!

Also yeah, so the unit's update class is checking per tick if the exact vector it is going to move to (via transform.translate) is a new node, by trying to find that vector, other than the one it is in, and consequently that node it may be going into may not be movelist[o], it may not be in movelist at all. I need to be sure that the unit is checking the right node it might be moving into, dependant on its move speed per tick. Which must be simpler than I am thinking. But I'm not sure how it should work. :(

So... long story short: how do I make sure the vector a unit will translate into is the same / is that node it is moving into (which is why I use casting to int in the code to fetch the correct node).

So as it turns out your very first comment works almost perfectly, at the time I simply didn't read/understand. Thank you SO MUCH!!

Technical notes however on implementation: The direction had to be acquired from a comparison of the target node vector AND the current node vector (NOT the current game object vector!) as although this may effectively have been 1 or 0, in reality it was 0.99999 or 0.000023422 etc. Since I had made nodes placed on *exact* vectors, they needed called for the XZ (not XY) checks to work. They also needed to be told explicitly to check for 0.0f instead of 0. And the straight/diagonal distances were 0.4f and 1.0f instead of what you might have thought (1.0f and 1.414f), BECAUSE if straight was 1.0f it'd trip up and accidentally think it was moving into a tile ahead that wasn't the next one on the list, so 0.4f was necessary to make sure that if the unit was just about to move to the centre of the next node, it wouldn't accidentally check ahead in the wrong one! :)

```
// forward checks node ahead of current node
Vector3 forward = transform.position;
Vector3 direction = (listMovePos[0] - node.getVector()).normalized; // make direction
float mod = 0.4f;
// direction is NOT in a straight line
if (direction.x != 0.0f && direction.z != 0.0f) { mod = 1.0f; }
forward += (direction * mod); // apply direction to unit's vector
Node forwardNode = Map.mapNodes[(int)forward.x, (int)forward.z]; // find node unit is about to move into
```

Great! Glad it worked out! I'll edit the answer to use 0.0f, good catch. Your last sentence sent my head spinning though, lol. Not quite clear why you used 0.4 and 1.0... I would have though .707(=1/sqrt(2)) and 1.0.. because: 1/sqrt(2) is to 1 AS 1 is to sqrt(2)

But on that point, I'd also like to throw one more vector-thing out there. I didn't mention it initially, so as to stay more on track with your question about directions, but: lets say, just for a moment, that you DID want your tiles aligned on a 1.0 x 1.0 basis.

In this case you would NOT need to normalize, check for diagonal, then multiply by a the pre-computed/hardcoded distance.

```
Vector3 travel = (listMovePos[0] - node.getVector());
```

Instead, the original result of the subtraction is ALREADY the proper length (with diagonals between tiles being appropriately longer than straight) If you instead, wanted your tiles evenly spaced at 0.4x0.4, then you can simply multiply the "travel" vector by that amount.

```
scale=0.4f;
forward += travel * scale;
```

You can "scale" the length of ANY vector this way. Normalize is really only of use when you don't WANT to know how long a vector is, you want ONLY it's direction.

(I'm NOT sure why I didn't mention this stuff in my initial answer. If it helps simplify your code, let me know and I'll edit the Ans.)

Informative as always! Thanks! :) The reason for 0.4 and 1.0 is because this is used in update (will have to refactor to reduce the number of times its called). But because of this, the distance need to be less than the distance between the centre of one node and the edge of another. 0.5 would be the limit, but I put it as 0.4 just to simplify things. That way a unit doesn't accidentally think it's going into the wrong node. Hopefully that adds some context?

### Your answer

### Welcome to Unity Answers

The best place to ask and answer questions about development with Unity.

To help users navigate the site we have posted a site navigation guide.

If you are a new user to Unity Answers, check out our FAQ for more information.

Make sure to check out our Knowledge Base for commonly asked Unity questions.

If you are a moderator, see our Moderator Guidelines page.

We are making improvements to UA, see the list of changes.