Giter VIP home page Giter VIP logo

Comments (12)

roy-t avatar roy-t commented on July 28, 2024

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

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.

from astar.

roy-t avatar roy-t commented on July 28, 2024

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:
astar

from astar.

mhughson avatar mhughson commented on July 28, 2024

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. 😄

from astar.

roy-t avatar roy-t commented on July 28, 2024

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.

from astar.

roy-t avatar roy-t commented on July 28, 2024

@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 :).

from astar.

mhughson avatar mhughson commented on July 28, 2024

Is it possible to try via NuGet?

from astar.

roy-t avatar roy-t commented on July 28, 2024

@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 :).

from astar.

mhughson avatar mhughson commented on July 28, 2024

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

from astar.

roy-t avatar roy-t commented on July 28, 2024

@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!

from astar.

Maxoper avatar Maxoper commented on July 28, 2024

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

from astar.

mhughson avatar mhughson commented on July 28, 2024

Seems to work!

from astar.

roy-t avatar roy-t commented on July 28, 2024

@Maxoper its truly appreciated :)

from astar.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.