- Home /
Moving only if straight path dijkstra
Hello everyone, I'm having a little bit of trouble with a pathfiding system which I saw in a tutorial. So far I have achieved that my player builds a path and even follow it. Everything seems to work just fine while the player is able to move in all directions as soon as the connections of these paths are enabled. The problem I have is, I'd like my player to move only either horizontal or vertically. In this sense if I click in a position which is diagonal to the player (in the grid he would move creating a "L") I'd like the player to ignore it and only move if the clicked position is either in a straight line (in front or back) or perpendicular to the player (sort of like a rook in chess).
Here is the code I hope I can get some help:
public class AnotherPlayerController : MonoBehaviour { public bool walking = false;
[Space]
public Transform currentCube;
public Transform clickedCube;
public Transform indicator;
[Space]
public List<Transform> finalPath = new List<Transform>();
private int targetIndex;
IEnumerator currentRoutine;
void Start()
{
RayCastDown();
}
void Update()
{
//GET CURRENT CUBE (UNDER PLAYER)
RayCastDown();
// CLICK ON CUBE
if(walking != true)
{
if (Input.GetMouseButtonDown(0))
{
Ray mouseRay = Camera.main.ScreenPointToRay(Input.mousePosition); RaycastHit mouseHit;
if (Physics.Raycast(mouseRay, out mouseHit))
{
if (mouseHit.transform.GetComponent<Walkable>() != null)
{
clickedCube = mouseHit.transform;
finalPath.Clear();
FindPath();
}
}
}
}
}
void FindPath()
{
List<Transform> nextCubes = new List<Transform>();
List<Transform> pastCubes = new List<Transform>();
foreach (WalkPath path in currentCube.GetComponent<Walkable>().possiblePaths)
{
if (path.active)
{
nextCubes.Add(path.target);
path.target.GetComponent<Walkable>().previousBlock = currentCube;
}
}
pastCubes.Add(currentCube);
ExploreCube(nextCubes, pastCubes);
BuildPath();
}
void ExploreCube(List<Transform> nextCubes, List<Transform> visitedCubes)
{
Transform current = nextCubes.First();
nextCubes.Remove(current);
if (current == clickedCube)
{
return;
}
foreach (WalkPath path in current.GetComponent<Walkable>().possiblePaths)
{
if (!visitedCubes.Contains(path.target) && path.active)
{
nextCubes.Add(path.target);
path.target.GetComponent<Walkable>().previousBlock = current;
}
}
visitedCubes.Add(current);
if (nextCubes.Any())
{
ExploreCube(nextCubes, visitedCubes);
}
}
void BuildPath()
{
Transform cube = clickedCube;
while (cube != currentCube)
{
finalPath.Add(cube);
if (cube.GetComponent<Walkable>().previousBlock != null)
cube = cube.GetComponent<Walkable>().previousBlock;
else
return;
}
finalPath.Insert(0, clickedCube);
finalPath.Reverse();
if(currentRoutine != null)
{
StopCoroutine(currentRoutine);
}
currentRoutine = FollowPath();
StartCoroutine(currentRoutine);
}
IEnumerator FollowPath()
{
walking = true;
while (true)
{
if (Vector3.Distance(finalPath[targetIndex].GetComponent<Walkable>().GetWalkPoint() + transform.up / 2f, transform.position) < 0.1f)
{
targetIndex++;
if (targetIndex >= finalPath.Count - 1)
{
targetIndex = 0;
Clear();
yield break;
}
}
transform.position = Vector3.MoveTowards(transform.position, finalPath[targetIndex].GetComponent<Walkable>().GetWalkPoint() + transform.up / 2f, 3f * Time.deltaTime);
yield return null;
}
}
public void Clear()
{
foreach (Transform t in finalPath)
{
t.GetComponent<Walkable>().previousBlock = null;
}
finalPath.Clear();
walking = false;
}
public void RayCastDown()
{
Ray playerRay = new Ray(transform.position, -transform.up);
RaycastHit playerHit;
if (Physics.Raycast(playerRay, out playerHit))
{
if (playerHit.transform.GetComponent<Walkable>() != null)
{
currentCube = playerHit.transform;
}
}
}
private void OnDrawGizmos()
{
Gizmos.color = Color.blue;
Ray ray = new Ray(transform.position, -transform.up);
Gizmos.DrawRay(ray);
}
}
Answer by unity_ek98vnTRplGj8Q · Jan 08, 2021 at 05:43 PM
You have 3 options in my opinion.
You can make 2 separate node connection graphs, 1 that is only connected vertically and 1 that is only connected horizontally, then search them 1 at a time.
You can use 1 graph, but add a condition that before you add a node to the list you need to make sure that it is in the same direction as the node that added it. That means that you will have to pair information about the direction you are looking in with each node that is added to your list, so that later nodes that you search can determine which direction you are searching in. This is probably the most complicated solution.
You can simply look at the complete path after it is created and discard it if it is not straight. This will only work if the shortest path between any two nodes in a line in your graph is always straight.
I hope that I understood your problem correctly.
First of all thanks a lot for answering.
To be honest I understand how the elements are added to my list and then how the path is created. However I don't seem to visualize how I could possibly check if all nodes are in a straight line since they are individual objects that are not really aware of each other's position. Each of the nodes just have an array from possible target paths which are added manually (ex one node 2 possible paths) which I access through the playerController and then I build the path.
Your first suggestion seems interesting, however since I'm still new in all of this I don't clearly see how I could apply it. Does it mean I have to set some bools (ex. isHorizontal and isVertical) for each of the nodes and then from my playerController just build the path if all elements in the list return either isHorizontal true or isVertical?
2 and 3. Brings me to the same problem earlier, how can I make the nodes aware of each others position and check if they are effectively on a straight lane. How would I be able to check they are in the same axis relative to each other?
I myself implemented something that is partially working, but I do not understand 100%. Right before the FollowPath() function I did the following. It's working however I don't know if its the most efficient way and its giving me troubles at a certain point in my game that I have to rotate my player's transform.up:
Vector3 dir = (clickedCube.GetComponent().GetWalkPoint() + transform.up / 2f - transform.position).normalized; Debug.Log("direction normalized: " + dir); float direction = Vector3.Dot(dir, transform.forward); Debug.Log("dot products: " + direction);
if (direction == 0 || $$anonymous$$athf.Abs(direction) >= 0.95f) { FollowPath(); }
If you are building the connections manually then separating the 1 graph into 2 graphs shouldn't be too difficult, but if you are doing it programatically you may have to tinker with it it a bit more. But the general idea is for each node, instead of having 1 list called possiblePaths on each node you would have 2 lists, called something like possiblePathsVert and possiblePathsHori, then only put vertical connections in the vertical path list and horizontal connections in the horizontal path list. Then you can just copy the same code you are using now but do it once for the horizontal path and once for the vertical path.
The downside to this is you have to manually re-assemble your whole graph, which is a pain. If you wanted to use option 2 I could help you with how to feed information about the previous node into your node list, but like I said this is probably the most complicated.
I think the 3rd option is still good so that's what I'll help you with here. To check if a built path is straight, use this code ->
bool IsPathStraight(List<Transform> path){
//Some of this code assumes flat ground and that nothing too weird geometrically is going on with your path
//If your ground is far from just a checkerboard pattern of walkable nodes then we will have to improve this code a little
//This code also assumes that the STARTING NODE is part of the path. If not we will have to tweak
//Assu$$anonymous$$g the starting node is part of the path, a path of length 2 must be straight
if(path.Count <= 2) return true;
//Get the first direction that we walk in. We will use this to compare the direction for the rest of the nodes
Vector3 startingDir = path[1].position - path[0].position;
//Get the direction to each node from its previous node, then compare it to the direction of our starting position
for(int i = 2; i < path.Count; i++){
Vector3 dir = path[i].position - path[i-1].position;
float dotProduct = $$anonymous$$athf.Abs(Vector3.Dot(startingDir, dir));
if(dotProduct < 0.95) return false; //This means the path is not straight
}
return true;
}
This is nice because it a) doesn't depend on the rotation of your character and b) checks the whole path. This is similar to the code that you were using with the Dot product, but ONLY looks at the nodes in the path.
If you have any questions about what this code is doing, or if you need to tweak it let me know
Wow, thanks a lot for such a detailed answer, that way I can properly learn.
I've applied your solution and its partially working however I'm having my player moving still in a "L" shape when it comes to small corners. I'll attach a pic from the basic layout from the level to give an idea. It's not a checkerboard style board and I think that might complicate things a little. Also I'm constantly having to change the player's transform.up since it is one of the main requirements for my game mechanics to work, which I have already tried with your solution and its working well.
as you can see in the pic I set cubes as possible paths to follow for my player. The intention is that the player can only move when in a straight line. In this sense while the player starts in that position and I click in the yellow circle he shouldn't move. I've have to click in the blue circle and then when the player reaches that pos then click again in the yellow circle. That is working with your solution. However by having the player back in his starting pos and clicking in the red circle he shouldn't be able to move and he stills does. I've checked and the reason why is because the dot value of that command is 1. Nevertheless if I raise the value for our function to return true (say <= 1 return false) some other movements stop working.
The green area is just to illustrate areas where the player would change plane (change his transform.up to match the one from the path).
Thanks again for all the help.
Your answer
Follow this Question
Related Questions
Convert WASD to local rotation 1 Answer
MoveTowards is moveing my object to random position when i click it is already on a way 1 Answer
Script click to move not working, MoveTowards always move forward 3 Answers
MoveTowards inside Coroutine 2 Answers
Move Character to touched Position 2D (Without RigidBody and Animated Movement) 1 Answer