GetSmoothPath along straight lines returns diagonal movement

[mhughson]

I have some really simple test cases that seem appear to return invalid smoothed paths.

In these screenshots, the light blue boxes are the path returned from GetSmoothPath. The agent is attempting to walk to each corner of the darker blue square.

The grid has no solid objects and a consistent cost (1.0f) across all cells in the grid.

With GetSmoothPath I would have expected all diagonal movement to be removed from the path.

Here is the same test but with GetPath(..., MovementPatterns.LateralOnly);

[roy-t]

Hey @mhughson, I've been able to reproduce this bug:
.

It seems that if there are 3 or more tiles between the start and finish, and no obstructions, and enough space. The string pulling algorithm is only able to pull a small part of the path straight (without smoothing its a true triangle, now the top is pulled off). I will investigate more, but I think I will need to run the string pulling algorithm recursively, or make another small adjustment.

Interesting that I never saw this happen before because my test application starts in the top left corner of a grid, and due to ordering of neighbours the errors are only to the top-left direction.

[roy-t]

I've found the problem, the string pulling is too simplistic, I've worked out a better solution on my whiteboard and I only have one programming problem to solve before I can show something, but a few quick tests showed it solved these problems :).

(What I need now is to find all the cells that are on a line from one cell to another cell, but due to floating point inaccuracies this is proving slightly more difficult than I thought and I want to keep the code as simple as possible).

I'm probably going to need to implement this: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm :)

Sneak preview:

[mhughson]

Does it make sense that a diagonal move costs the same as a lateral one? They are not the same distance. In implementations I've done in the past, I believe I made a diagonal cost slightly more than a lateral move, but cheaper than 2 lateral moves. Basically I made the cost of movement equal to the distance between the 2 points.

I believe that would solve this issue without smoothing being needed, but perhaps it would introduce other oddities.

I'm probably going to need to implement this: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

That's actually the algorithm I used to draw the blue lines in my examples above, so we've come full circle. 😄

[roy-t]

Originally I wanted the heuristic and cost calculations to be as simple as possible. So I used Chebyshev distance for the heuristic and equal costs for the diagonal and horizontal/vertical movement. Then using the string pulling algorithm to create nicer looking paths. My reasoning for this was that the string pulling only needs to consider the cells on the path, so that doing a little extra work afterwards would speed up things, compare to making all the costSoFar and stepCost calculations more difficult.

I had quite a few samples in which the string pulling algorithm worked really well. So I thought this was the right decision. But if I see now how much more complex (its >O(n^2) in the test branch) I have to make the string pulling algorithm to smooth out this case it might have been the wrong approach.

I hope I have time this weekend to experiment a bit, and hopefully release a better version that solves your problems.

[roy-t]

@mhughson I've used your feedback to create a v2 version of the package, that does penalize diagonal movement, and I'm happy to say that it looks like it no longer needs any string pulling or other methods to make the paths look good. Please try it out and let me know how you like it, so I can close this issue :).

[mhughson]

Is it possible to try via NuGet?

[roy-t]

@mhughson yes! Its the 2.0.0 version I uploaded to last night to nuget: https://www.nuget.org/packages/RoyT.AStar/ if you already have the package you should be able to see there is an update in VS :).

[mhughson]

Getting a crash after after a short period:

 	mscorlib.dll!System.Collections.Generic.List<RoyT.AStar.Position>.Capacity.set(int value) Line 123	C#
 	mscorlib.dll!System.Collections.Generic.List<RoyT.AStar.Position>.EnsureCapacity(int min) Line 414	C#
 	mscorlib.dll!System.Collections.Generic.List<RoyT.AStar.Position>.Add(RoyT.AStar.Position item) Line 222	C#
 	RoyT.AStar.dll!RoyT.AStar.PathFinder.ReconstructPath(RoyT.AStar.Grid grid, RoyT.AStar.Position start, RoyT.AStar.Position end, RoyT.AStar.Position[] cameFrom)	Unknown
 	RoyT.AStar.dll!RoyT.AStar.PathFinder.FindPath(RoyT.AStar.Grid grid, RoyT.AStar.Position start, RoyT.AStar.Position end, RoyT.AStar.Offset[] movementPattern)	Unknown
 	RoyT.AStar.dll!RoyT.AStar.Grid.GetPath(RoyT.AStar.Position start, RoyT.AStar.Position end, RoyT.AStar.Offset[] movementPattern)	Unknown
>	mono8samples.exe!Mono8Samples.TopDown.simple_ai.move_to_pos(float dest_x, float dest_y) Line 232	C#

Exception (the internal list you are using has 100 million + entries...

System.OutOfMemoryException was unhandled
  HResult=-2147024882
  Message=Array dimensions exceeded supported range.
  StackTrace:
       at System.Collections.Generic.List`1.set_Capacity(Int32 value) in f:\dd\ndp\clr\src\BCL\system\collections\generic\list.cs:line 123
       at System.Collections.Generic.List`1.EnsureCapacity(Int32 min) in f:\dd\ndp\clr\src\BCL\system\collections\generic\list.cs:line 414
       at System.Collections.Generic.List`1.Add(T item) in f:\dd\ndp\clr\src\BCL\system\collections\generic\list.cs:line 222
       at RoyT.AStar.PathFinder.ReconstructPath(Grid grid, Position start, Position end, Position[] cameFrom)
       at RoyT.AStar.PathFinder.FindPath(Grid grid, Position start, Position end, Offset[] movementPattern)
       at RoyT.AStar.Grid.GetPath(Position start, Position end, Offset[] movementPattern)
       at Mono8Samples.TopDown.simple_ai.move_to_pos(Single dest_x, Single dest_y) in C:\Users\Matt\Documents\Dev\Game\mono8\Mono8Samples\TopDown\simple_ai.cs:line 232
       at Mono8Samples.TopDown.simple_ai.update() in C:\Users\Matt\Documents\Dev\Game\mono8\Mono8Samples\TopDown\simple_ai.cs:line 94
       at Mono8Samples.TopDown.TopDown._update60() in C:\Users\Matt\Documents\Dev\Game\mono8\Mono8Samples\TopDown\TopDown.cs:line 302
       at Mono8.Mono8Game`1.Update(GameTime gameTime) in C:\Users\Matt\Documents\Dev\Game\mono8\Mono8\Mono8Game.cs:line 456
       at Microsoft.Xna.Framework.Game.DoUpdate(GameTime gameTime)
       at Microsoft.Xna.Framework.Game.Tick()
       at MonoGame.Framework.WinFormsGameWindow.RunLoop()
       at Microsoft.Xna.Framework.Game.Run(GameRunBehavior runBehavior)
       at Mono8Samples.Program.Main() in C:\Users\Matt\Documents\Dev\Game\mono8\Mono8Samples\Program.cs:line 19
       at System.AppDomain._nExecuteAssembly(RuntimeAssembly assembly, String[] args)
       at System.AppDomain.ExecuteAssembly(String assemblyFile, Evidence assemblySecurity, String[] args) in f:\dd\ndp\clr\src\BCL\system\appdomain.cs:line 1966
       at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
       at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx) in f:\dd\ndp\clr\src\BCL\system\threading\executioncontext.cs:line 954
       at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx) in f:\dd\ndp\clr\src\BCL\system\threading\executioncontext.cs:line 902
       at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state) in f:\dd\ndp\clr\src\BCL\system\threading\executioncontext.cs:line 891
       at System.Threading.ThreadHelper.ThreadStart() in f:\dd\ndp\clr\src\BCL\system\threading\thread.cs:line 111
  InnerException: 

Here's the call that crashes and some of the values:

Position[] path = Game.map_grid.GetPath(new Position((int)(x / 8), (int)(y / 8)), new Position((int)(dest_x / 8), (int)(dest_y / 8)));

-		Game.map_grid	{RoyT.AStar.Grid}	RoyT.AStar.Grid
		DefaultCost	1	float
		DimX	128	int
		DimY	128	int
+		Weights	{float[16384]}	float[]
		dest_x	36	float
		dest_y	4	float
		path	null	RoyT.AStar.Position[]
+		this	{Mono8Samples.TopDown.simple_ai}	Mono8Samples.TopDown.simple_ai
		x	36	float
		y	7.75	float

[roy-t]

@mhughson ah, I figured it out. It happens when the start and end position are the same but are not (0,0). This is something that can never happen in the Viewer, but is of course something that can happen when the library is used. I'll update the Nuget package in a few minutes! (It might take a few hours before you can see the update). Sorry about this!

[Maxoper]

@roy-t great work Roy ! Using this library since more than 2 months.
Wanna say thank you this way :)

[mhughson]

Seems to work!

[roy-t]

@Maxoper its truly appreciated :)