roy-t / astar Goto Github PK

Hello,

first of all thanks for sharing your AStar implementation on github. Can you answer me why you also have a
IList Incoming { get; }
in your INode interface, maybe i missing something in the Code?
From your implementation of the AStar i see you only use the Outgoing List for the algorithm, which is self explained.

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);

If PathFinder.FindPath returns null, Grid.GetPath doesn't check for it and throws an exception.

In some cases, two nodes are connected with two directional arcs that have different costs (i.e uphill / downhill).
Can this scenario be configured in your library?

Hello thank you for your work.
I've been using an old version but now moved to 3.01.
Can you explain how to do the same functionality that existed with BlockCell and UnblockCell ?

I have been using those functions to make grid nodes walkable/non walkable in my game but in the new version these functions are not there. Only can find DisconnectNode. How to reconnect?

Is this pathfinding library deterministic? I'm making a multiplayer game and I run this both on the client (for instant response feel) and server (to validate). My plan is to pass the starting row/col and the path that the client instance of this pathfinding found to the server and have the server use the same starting row/col and the map itself (which should be the exact same on both client/server) and run to get the path and compare it against the path the client send to make sure it 100% matches, but just curious given the map is setup and same starting row/col will I get the exact same path on the server that the client code came up with?

I don't just use the client path because I have to check for cheating (this is really the only reason for doing this check on the server) and the exact path is important as things along the path can cause harm.

With MovementPatterns.Full, the edge of the bolck can only go straight. eg. if (x,y) is block, can't move (x-1, y) to (x+1, y-1) . What should I do?

As long as the weights in the grid haven't changed a path you've previously computed is still valid. It might be a good idea to add caching.

Requirements

• Caching should be separated from the main algorithm to keep everything simple
• The API for the CachedGrid (??) should be compatible with the Grid api.
• This feature should be compatible with adding multi-threading/tasks.

I noticed in your previous versions of this library that it supported 3D pathing.
Is that something you are considering for this version?

If not, I'm wondering if it's something I could 'fake' by connecting 2D grids in layers and adding sensible costings between them. But not sure how best to achieve that?

Just a question, would like to know how to convert the edges to a position like a coordinate system (X, Y). I am working on a game that uses angles as a direction (the map is like a graph) that my player uses to move. Having the position of the edges would be really helpful.
Should I create more nodes to store my obstacles?
Sample code usage of this library would be really helpful.

Hello, this library is awesome! I'm having some weird issue with getting consistent paths with the error being IndexOutOfRangeException: Index was outside the bounds of the array. from Unity.

Grid grid = new Grid(gridWidth, gridLength, 1.0f);
for (int row = 0; row < gridLength; row++)
{
  for (int column = 0; column < gridWidth; column++)
  {  
    if (IsWall(column, row))
    {
      grid.BlockCell(new Position(column, row));
    }
  }
}

Parallel.ForEach(positions, position =>
{
  Position[] path = CreatePath(grid, position, endPosition);
});

This will throw an error about every 10 runs and I'm almost certain it has to do with the threading. I know #4 was an issue when it comes to threading a single find path call but I was wondering it is possible to do it the above way.

Here is the full Unity output if that helps. Thanks again for this library!

IndexOutOfRangeException: Index was outside the bounds of the array.
(wrapper stelemref) System.Object.virt_stelemref_class_small_idepth(intptr,object)
System.Collections.Generic.List`1[T].Add (T item) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
RoyT.AStar.PathFinder.MessageCurrent (RoyT.AStar.Position position, System.Collections.Generic.IReadOnlyList`1[T] path) (at Assets/Scripts/Roy-T.AStar/PathFinder.Debug.cs:17)
RoyT.AStar.PathFinder.FindPath (RoyT.AStar.Grid grid, RoyT.AStar.Position start, RoyT.AStar.Position end, RoyT.AStar.Offset[] movementPattern, System.Int32 iterationLimit) (at Assets/Scripts/Roy-T.AStar/PathFinder.cs:68)
RoyT.AStar.Grid.GetPath (RoyT.AStar.Position start, RoyT.AStar.Position end, RoyT.AStar.Offset[] movementPattern, System.Int32 iterationLimit) (at Assets/Scripts/Roy-T.AStar/Grid.cs:152)
BetterDungeons.CreatePath (RoyT.AStar.Grid grid, BetterDungeons+Cell cell, BetterDungeons+Cell mainCell) (at Assets/Scripts/BetterDungeons.cs:265)
BetterDungeons+<>c__DisplayClass14_0.<CreateDungeon>b__0 (BetterDungeons+Room room) (at Assets/Scripts/BetterDungeons.cs:104)
System.Threading.Tasks.Parallel+<>c__DisplayClass31_0`2[TSource,TLocal].<ForEachWorker>b__0 (System.Int32 i) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Parallel+<>c__DisplayClass17_0`1[TLocal].<ForWorker>b__1 () (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Task.InnerInvoke () (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Task.InnerInvokeWithArg (System.Threading.Tasks.Task childTask) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Task+<>c__DisplayClass178_0.<ExecuteSelfReplicating>b__0 (System.Object <p0>) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
Rethrow as AggregateException: One or more errors occurred.
System.Threading.Tasks.Task.ThrowIfExceptional (System.Boolean includeTaskCanceledExceptions) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Task.Wait (System.Int32 millisecondsTimeout, System.Threading.CancellationToken cancellationToken) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Task.Wait () (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Parallel.ForWorker[TLocal] (System.Int32 fromInclusive, System.Int32 toExclusive, System.Threading.Tasks.ParallelOptions parallelOptions, System.Action`1[T] body, System.Action`2[T1,T2] bodyWithState, System.Func`4[T1,T2,T3,TResult] bodyWithLocal, System.Func`1[TResult] localInit, System.Action`1[T] localFinally) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Parallel.ForEachWorker[TSource,TLocal] (System.Collections.Generic.IList`1[T] list, System.Threading.Tasks.ParallelOptions parallelOptions, System.Action`1[T] body, System.Action`2[T1,T2] bodyWithState, System.Action`3[T1,T2,T3] bodyWithStateAndIndex, System.Func`4[T1,T2,T3,TResult] bodyWithStateAndLocal, System.Func`5[T1,T2,T3,T4,TResult] bodyWithEverything, System.Func`1[TResult] localInit, System.Action`1[T] localFinally) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Parallel.ForEachWorker[TSource,TLocal] (System.Collections.Generic.IEnumerable`1[T] source, System.Threading.Tasks.ParallelOptions parallelOptions, System.Action`1[T] body, System.Action`2[T1,T2] bodyWithState, System.Action`3[T1,T2,T3] bodyWithStateAndIndex, System.Func`4[T1,T2,T3,TResult] bodyWithStateAndLocal, System.Func`5[T1,T2,T3,T4,TResult] bodyWithEverything, System.Func`1[TResult] localInit, System.Action`1[T] localFinally) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
System.Threading.Tasks.Parallel.ForEach[TSource] (System.Collections.Generic.IEnumerable`1[T] source, System.Action`1[T] body) (at <d7ac571ca2d04b2f981d0d886fa067cf>:0)
BetterDungeons.CreateDungeon () (at Assets/Scripts/BetterDungeons.cs:101)
BetterDungeons..ctor (System.Int32 gridLength, System.Int32 gridWidth, System.Int32 minRoomLength, System.Int32 minRoomWidth, System.Double percentWalls, System.Int32 passes, System.Int32 seed) (at Assets/Scripts/BetterDungeons.cs:40)
DrawDungeon.Start () (at Assets/Scripts/DrawDungeon.cs:25)

The viewer was really just hacked together. It would be nice to give it some UI love and features.

• Remove performance info (its unreliable and causes confusion, performance should be tested using the benchmark.net project we have)
• Create custom controls for the cells that act like this
  • Scroll: change the cost
  • Middle click: block the cell
  • Left click: set as start node
  • Right click: set as end node
• Visualize the decision process of the algorithm without impacting the performance of the NuGet package
• Be able to load/store grids

I am probably not fully understanding how this is working, but why is there not a closed list of some sort? For example, on a grid that is 32x32 from close to each corners with only a few high weighted positions but is mostly empty, the iteration count is getting to 1800+ before finding the path? It's running super quick, however shouldn't it only evaluate each position only once?

A WIP version of v2 is now on master. It includes

• Graph based path finding
• Partial paths

It also uses actual numbers to feed the algorithm. So a node has a position, and an edge has a max speed at which you can traverse it. So if two nodes are connected by an edge and are 120km a part, and the edge has a speed limit of 60km/h, the cost of traveling between these two nodes is 2 hours. This will hopefully make it easier for the end-user to construct graphs that work well for the real world.

As of yet the v2 version only supports graphs, while v1 only supports grids. I'm thinking of clever and fast ways to marry the two, with an interface that looks similar to v1. But in the end it might be simpler to have two different approaches. Who knows :).

V2 also contains a brand new viewer, which is also very much WIP:

Hey @roy-t,

this library looks quite interesting, but I find it hard to get started with the current state of documentation.

Your blog article seems to be outdated (or at least the examples are). The README examples work for me, but there are some parts I don't understand.

I want to use it for a roguelike-y game, so the Grid looks like the right starting point. It looks like the cellSize and traversalVelocity are used to measure some sort of "real" distance. Can I omit them somehow? Can I use some default values without affecting the path calculations?

Thanks in advance.

Hello,

This is probably a stupid question, but I have a project I'm working on where the grid obstacles change often and the grid map is shared with multiple agents. I don't want my agents to be able to walk through each other, so I need to be able to update my grid easily. I see there is an option to disconnect a node, which seems to make the position on the grid unusable, but is there anyway to add the same node back after you remove it?

Hello, thank you very much for the code, the current algorithm is exceptionally fast to compute, but after referring to it I realized that the algorithm has some differences from the actual AStar algorithm. For example, the cost function of the AStar algorithm calculates the sum of the distances between the starting point and the target point preferentially, which is indeed fine without considering obstacles, but if obstacles are added, it is more similar to the (Greedy Best First Search) algorithm if you use the minimum heap, here is my actual test, is it designed this way on purpose?

I'm using no walls for my pathfinding, instead I have to use high cost for very unlikely positions.
I use a cost value of 5-200 for those.
Targeting the pathfinding to those will make the DLL loop endless.
Nothing urgent though :)

I like the code overall, but it's not usable in games as is because it's so heavy with allocations.

Lots of games have a zero heap allocation policy for pathfinding.

If there are two parallel equal cost paths the path finding process will keep switching between the two paths because they have an equal expected cost. We can traverse faster if we sort the MinHeap by the lowest ExpectedCost first and then the highest CostSoFar. This way we keep trying one possible solution instead of continuously switching between all possible solutions.

This isn't really an issue, it's more of a feature. I was having a problem in that the path will cut corners instead of finding the way around. This is probably standard A* behaviour but I needed it to work a bit differently for a game I'm working on. I forked the code and made the change.
https://github.com/EnderYoss/AStar/commit/c1633de8f2315c581e2005ab0e994151cecaf661

I just thought I'd let you know in case you wanted to use it or adapt it. The difference can be seen here-

If we add path finding for Directed Acyclic Graphs, and also add an option to convert a grid to such a graph. We can make path finding a lot more flexible as this gives more control over what tiles are reachable from another tiles.

This could fix #16 by removing links between tiles that would cause cutting a corner.
This could fix #17 by giving links between tiles a direction.

Its still unclear what the performance impact would be. Do we need both algorithms or is path finding equally fast on a DAG?

In the usage examples for graphs, node connections are added like this:

nodeA.Connect(nodeB, traversalVelocity);

However, since commit 1daf2de the Connect method is internal. How are node connections to be added now?

Use cases

• Compute one path without stalling the game loop (ordering a unit)
• Compute a large number of paths in succession (ordering a squad, all AIs, etc..

I'd like to make this approach compatible with a typical Game Loop. Meaning that you should be able to check every frame if a given path query was completed. Maybe we can use a producer/consumer like scheme.

Another option is to use the async/await pattern. I think that would work great for computing a single path, but I'm not sure if its the best fit for a Game Loop. For complex environments it might take more than one frame to compute a path and this shouldn't stall paths.

Challenges

• How to make sure the cell costs are not changed while calculating a path without locking (copy the array?)

#39 was merged but I need to give it one quick test before I'll release a new nuget package. Planning to this next Wednesday (06-08-2020)

We need to be able to verify new changes automatically. But the API might need to be changed (be more open) to make effective unit tests.

Is there a good way to handle unreachable points? It appears that there is no way to early out of your path search, so an unreachable point will be very, very, expensive.

I would like a way to tell the GetPath function to exit early after either visiting N number of nodes, or after spending N amount of time. This way I can avoid huge hangs when an invalid search is requested.

This may have some overlap with #10

Is it posible to use GPS coordinates as position values since i wasnt able to make my example work.
Also is it posible to assign some ids to the nodes so that later on i can find out which node coresponds to my information about that node.

Thanks for an awsome library saved me a lot of time.

Hi there,

Thanks for your very nice library! It is very easy to use, although I modified Grid to use my underlying data structure directly.

I was wondering if you could add a version (e.g., GetPathToClosest() or an option to GetPath) that would return a path to the closest point to the destination, if the destination itself could not be reached, please. This would be useful, for example, when using it for pathfinding for monsters who are extremely numerous and are "mobbing" the player, assuming of course that only one monster can be in a cell and hence would BlockCell their locations.

The shortest path, if multiple end up equidistant, would be preferred, of course.

(Yes, I know a non-infinite cell cost could be used as well.)

Thanks,

Doug

I've been using this library for a small prototype I've been working on and it's working very well, kudos.

I've been thinking about the movement patterns though, and while it's nice to be able to specify that something can't move down for example, I found that what I need is to be able to tell the path finder not how it can move generally, but on a tile to tile basis. For example, I might have a tile that you can only walk over from north to south.

It seems like that's not currently possible. A way to do it might be to let Grid/PathFinder take a function that can be called to get the available movement options instead of an array of offsets. I feel like that would make the system a whole lot more flexible, as you get full control over the options.

grid.GetPath(tile1, tile2, GetMovementOptions);

private IEnumerable<Offset> GetMovementOptions(Position position, int dimX, int dimY)
{
	return MovementPatterns.LateralOnly.Where(
		m =>
		{
			var target = position + m;
			if (!(target.X >= 0 && target.X < dimX && target.Y >= 0 && target.Y < dimY))
				return false;

			if ((this.GetTile(position).NorthToSouth() || this.GetTile(target).NorthToSouth()) && m != new Offset(0, 1))
				return false;

			return true;
		}
	);
}

This would be a nice feature to be have in my opinion.

Done some more random testing, then tried some repeated path testing and seeing some inconsistencies.

Attached a quick video to demonstrate.

Showing times for the same path, resolved repeatedly.

Times range from 0.11 to 2.0 for repeatedly checking the same path. Should possibly have some caching or checks. However, the spikes are a slight concern.

Not sure if it's an issue or not, or just scope for improvement.

Just an observation for now.

Thank you. Your code is very useful
I am interested in Different agent sizes
how can i use that in your before branch 'feature/improve_string_pulling'?

Hello!

There is an excessive amount of allocations and I'm surprised the author is saying there are no allocations and even closing the issue without any explanation #9...
Basically, any request to find a path results in at least a single List, single Stack, and single Array allocations (effectively multiplying the amount of memory traffic and GC pressure).
I cannot see any collection pools used to reduce the number of allocations, and in some cases, there are excessive collections allocated and data is copied, which could be easily avoided.

For example:

Why not use Array.Empty here?

Here a Stack is created just to reverse the List, then it's converted to an Array. I find this code extremely confusing as there are obvious approaches how to reverse-copy list content into an Array without using an intermediate Stack object, or avoiding allocating both Stack and Array altogether as the List entries could be reversed in a single for loop right inside the List and then the List object itself could be returned (though the result type should be IReadOnlyList<Position> in that case which is usually fine):

And that just a few obvious cases which I've found on the highest API level by quickly reading the code of the Grid and Pathfinding classes.

I hope the author is willing to improve these moments (especially the most obvious ones). I found that the author is using BenchmarkDotNet to measure performance but I'm really surprised the allocations aspect is neglected...

It's a general rule that allocations should be minimized for games even if the game is shipped for modern .NET Framework/.NET Core instead of outdated Mono. Any GC implementation is taking precious time in the main thread and could result in noticeable hiccups for the players. Considering that pathfinding is often one of the heaviest sections of the code (which could be invoked thousands of times per second for some games such as strategy or MMOs) such amount of allocations should be avoided. Especially as modern .NET has all sorts of pooled collection approaches to ensure the best performance and often avoid the allocations altogether.

Regards!

Floats seem overkill for many scenarios so it would be nice to be able to use int's, too.

Great library and love the lack of dependencies. However, it doesn't seem to sort on best path, or could just be the viewer maybe?

As you can see, it's clearly marking a path which is not "best".

Any thoughts?

It would be nice if the end cell is unreachable that the algorithm still provides path to the closest reachable cell. Like this:

It doesn't choose straight paths etc. The path it calculates is good though it's ugly. When Lateral or Diagonal it's prefect and is super easy to setup. Though when Full, let's say you're going to walk in a straight line. It can choose to go diagonal on some steps. The path it calculates has the same cost though it's ugly. Do u have any idea or solutions?

So if I follow the most basic explanation of A*, it usually talks about finding a path from A to B on some grid/graph G.

I am completely lost where the velocity comes in here, how I should use it, and what I should set it to for the basic case of simply finding a path.

I assume it has something todo with declaring the cost of moving from P1 to P2, so that you optimise the path with the lowest cost (fastest path, etc), but what does that mean for finding a path, what does setting maximumVelocity actually do?

Would it be possible to extend the library to also load & save graphs? Would be very useful for testing purposes!
Of course the saving should also be possible from code and viewer, such that it's easy to dump a graph and load it up in the viewer

Hi,

Is there any possibility that I could find missing paths by using some condition?

For example, I want to use the grid for an online game, as I am working with udp, so in this case there may be packet loss and I am also using interpolations. The grid can have walls and so on, so sometimes the interpolation can end up taking a path in which it is blocked, so my idea is to try to "recover" by calculating some points from packet losses. As each movement works with sequences or timestamp, then the idea of filling in, would be being able to limit the searches of the path, to find such a path, it needs to go through amount of time or sequence. He does not need to find the slowest or the fastest, but the necessary condition.

Thanks,
Regards.

Hi, is it possible to take the size of the agent into account? For actually making sure the object which follows the path gets through the narrow gaps. For simplicity the object could be considered as circle with radius in cells (default 1, but 2, 3, 4, etc. also possible).