Jump to content
  • Advertisement
kensarto

C# A* Pathfinding Misallignment

Recommended Posts

Getting a bit desperate, not knowing what to do as this is a topic I've only just dipped my feet into and so far attempts at getting assistance directly on the Unity Scripting forum has proved fruitless and attempting the gamedev reddit failed because of my decisions in how I tried to share the project while it was on the first page of results. 

https://drive.google.com/drive/folders/1so24aSUCRWSRynpEo8ZLGNdKHkncQ589?usp=sharing

Above is a link to my unity project. It is a bit muddled up as I have been messing around with it for a while now, but amongst the assets are a series of scripts which should produce a path finding effect. Essentially a Seeker finds the most efficient route, while avoiding obstacles to the target and then follows the nodes to reach the target.

The issue I am having is that while for the most part it sticks to the grid, after a short time it will move itself from the centre of each tile/node and will deviate to the point where it doesn't even reach the target before it stops completely.

The goal is to have a Runescape style of movement, click on the tile walk to that tile and stop, and development of anything resembling a game can't begin until I can safely move a player around accurately.

If someone could tell me what is wrong with the scripts (I suspect the unit.cs script personally but can't confirm) and how to fix it so that it works as intended that would be great. So far the only advice I've been given is to use Debug.Log on different values to make sure they look right, which I already did to check the waypoints are being represented correctly (which they are) among other things.

https://www.youtube.com/watch?v=HtdQOSfpRc8&feature=youtu.be

I have also attached a youtube video showing how it will arbitrarily sit perfectly on the target in the centre of the tile and not do that under different conditions.

Share this post


Link to post
Share on other sites
Advertisement

I didn't look at the code, but (and I suppose this is obvious) it seems to be a path following problem rather than a pathfinding problem.

So I suppose the question would be, what are the mechanics of the path following? In your video it looks like the agent 'wanders' a bit as it travels rather than simply moving in a straight line. I'm guessing this has to do trying to follow the specific grid cells in the path. And since it doesn't move strictly from cell to cell, I'm guessing there's some kind of smoothing or approximation going on that could result in inaccuracy.

Another question would be what criteria are used to determine when the agent has reached the goal, and what steps, if any, are taken to ensure the agent arrives exactly at the goal (which it of course isn't doing reliably at the moment).

As for the code, it might be easier if you could post some of the relevant bits (such as the path-following code) here.

Share this post


Link to post
Share on other sites
IEnumerator FollowPath() {
		Vector3 currentWaypoint = path[0];
		//Debug.Log (currentWaypoint.x + ", " + currentWaypoint.y);
		//Debug.Log (transform.position.x + ", " + transform.position.y);

		while (true) {
			if (transform.position == currentWaypoint) {
				targetIndex ++;
				if (targetIndex >= path.Length) {
					yield break;
				}
				currentWaypoint = path[targetIndex];
			}

			transform.position = Vector3.MoveTowards(transform.position,currentWaypoint,speed * Time.deltaTime);
			yield return null;

		}
	}

This is the code for following the waypoints grid to grid. as previously mentioned i've checked each waypoint as you can see with the commented debug.logs as well as another that im currently using elsewhere in the code.

the most relevant line is "transform.position = vector3.movetowards(transform.position, current waypoint, speed*time.deltatime)" which literally and assumably simply moves the players transform position towards the position of the waypoint, and each iteration of the while loop it changes to the next waypoint and moves towards it again and again until it reaches the final waypoint in the list of waypoints.

This should show off the path following, the lack of approximation or smoothing, and the method it determines if it has reached the target.

Share this post


Link to post
Share on other sites

I looked at the documentation for MoveTowards(). As you probably already know, it claims that if the move would overshoot the target, the target position is returned. It's probably reasonable to take the documentation at its word here, although it might be informative to test that empirically, since documentation isn't always correct. For example, one way of implementing such a function might involve clamping the delta to the remaining distance and then moving as usual, which could result in the returned value being approximately equal to the target, but not necessarily exactly equal. (It's also worth noting that Unity's vector '==' function uses an epsilon, which could be enough to compensate for any inaccuracy in MoveTowards(), although I certainly wouldn't recommend relying on that.)

I don't think this is the explanation (because there are other behavioral anomalies), but in the video I notice that on the first path-follow, the red square stops more or less in the center of the upper-left cell, but the white square is off-center. I don't know why the white square is off-center, but that could give the mistaken impression that the red square 'missed' when it actually didn't. That was the only case I saw though of the white square being noticeably off-center, and obviously the red square is missing by quite a bit in other cases.

Do you know for a fact that the waypoint positions all lie at the exact centers of cells?

I also see you're getting an 'array index out of range' error at the end of each path-follow, so it may be that all the preceding discussion about positions, epsilons, etc. is irrelevant and it's just a simple logic error. I don't see where/how targetIndex is initialized, but in any case, I think a good next step would probably be to determine the cause of the range error.

Share this post


Link to post
Share on other sites

I believe the range error is coming from the fact i have the pathing being requested every update, and when the player thinks it is at the target position, the number of waypoints is 0, thus the list has 0 entries and my code still attempts to access it at least once, a poor programming practice stemming for sure, but im assuming unrelated to the problems that occur when the program is actually doing something.

The white square is off centre for the very very first attempt purely and simply because its placed poorly, i fixed that just now by changing its transform. When i left click it sets it to the centre of the square i click on but the scene itself it was placed wrong. (-3.99, 4.08 instead of -4,4)

i do know for a fact that the waypoint positions all lie at the exact centers of cells. I can prove this with the following: 
first the centre of each tile is at an exact X,Y coordinate where x and y are whole integers, either negative or positive. They were all placed manually and it took some time so i know i didnt miss any.
the waypoints use the world coordinates starting at 0,0 and spreading outwards a total distance of 1 unit per node, this is because the node radius is 1, something i can change if i desire smaller nodes etc. I will attach an image of the nodes in the scene view showing how they sit directly above the tiles.
finally in my code i have tested what unity thinks the coordinates of the waypoitns are with debug.log in a few places, it is one of the first things i checked.

unfortunately your statements in the first paragraph go over my head a certain degree when you talk about epsilons, but for the former part of that paragraph where you mention overshooting the target position, all I will say is that the program only ever undershoots, so unless I'm missing something (and do tell me if I am, i'm still a rather new unity developer) a chance for overshooting a position shouldn't result in undershooting it instead.

I can attempt to fix the arrayindex out of range issue now, it will be as simple as making sure the list has at least 1 entry before beginning the loop, if it fixes the issue I will update this thread immediately.

Capture.JPG

Share this post


Link to post
Share on other sites
Quote

unfortunately your statements in the first paragraph go over my head a certain degree when you talk about epsilons, but for the former part of that paragraph where you mention overshooting the target position, all I will say is that the program only ever undershoots, so unless I'm missing something (and do tell me if I am, i'm still a rather new unity developer) a chance for overshooting a position shouldn't result in undershooting it instead.

I was just saying that MoveTowards() prevents overshooting and eventually returns the target position (according to the documentation at least), and that vector == uses an epsilon, and that those two things together suggest that the problem isn't with MoveTowards() or the vector comparison.

Assuming transform.position and targetIndex are initialized appropriately, it's not immediately obvious to me why the code you posted would be producing the results in your video. (I'm not that familiar with Unity coroutines though, so there may be factors I'm missing.)

If it were I, I'd use a debugger or log output to record the following things: the transform position at every step of the process; when the transform position tests as == to the current waypoint position and what the values are at that point; when the process terminates with 'yield break' and what the values are at that point; and anything else that seems relevant. Presumably at 'yield break', the current waypoint should be equal to the last waypoint in the path, and the transform position should be equal or nearly equal to the waypoint. If the agent is stopping significantly short of the target (as it appears to be doing), presumably the debug information will reflect that, and perhaps offer some clues as to why. (Logging every position could result in a lot of log output of course, but I'm assuming the logging system can handle it.)

Share this post


Link to post
Share on other sites
Posted (edited)

I am happy to try this, logging the transform positions vs the waypoint position and the values etc, before I do however I would like to ask, what am I suppose to be looking for when I do. I'm going to assume that the values for transform will be wrong eventually as that is visibly the case, but I'm unsure as to how that can then lead me to a clue. It seems like all that would do is provide written evidence of what is already visually apparent. So I guess I'm asking, what should I be looking for when I do this to find out what is actually wrong.

I will start it now and get some values to look at in the mean time.

Edited by kensarto

Share this post


Link to post
Share on other sites

Fortune favors me it seems as I did notice something by pure accident. I placed my Debug.Log for both current wyapoint and transform position inside the if statement that checks if the transform is equal to the waypoint and it never fired. After relocating it and with that knowledge in mind i realised that the transform never reached the waypoint yet the waypoint was still changing. I realise now this was due to the fact that the co-routine was being stopped and started and recalculated each update. 

I believe a potential fix to my problem is to only sop and start the coroutine each time the target is moved i.e. each time the player left clicks to move. As once i changed the method call from update to start (i.e. only once) the player moved exactly to each waypoint and stopped exactly on the tile.

Thank you for suggesting this as it led to what I believe may be the solution.

Share this post


Link to post
Share on other sites
Quote

It seems like all that would do is provide written evidence of what is already visually apparent. So I guess I'm asking, what should I be looking for when I do this to find out what is actually wrong.

Your follow-up post basically provides the answer, which is that even when it seems like debugging will only tell us what we already know, it often reveals more than that (which is of course the point).

As I mentioned earlier I'm not up to speed on Unity coroutines at the moment, so I can't comment on the specifics of your fix, but it sounds like you were able to identify at least part of the problem :)

Just to be thorough I'll point out that (as you probably already know) you don't have to use coroutines for this. I'm not saying you shouldn't use them (you may have compelling practical or conceptual reasons for doing so). I'm just pointing out that there are other ways you could accomplish the same thing.

Share this post


Link to post
Share on other sites

You're probably correct, and shortly after my next undertaking which is to apply a model and animation to this instead of a cube, I might rewrite this code in ways I am more comfortable with, including the removal of the coroutine if possible.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!