barsonax / pathfindax Goto Github PK

Summary

Even though the MinHeap is called MinHeap the first element does not actually have the smallest value but instead has the largest value. Because of this rename the MinHeap to MaxHeap.

Summary

There should be a getting started guide for making your own Pathfinder and using it in duality

Summary

Cleanup the nodenetwork interfaces and make it clearer that there is a source node network and a node network for each thread:

• Remove properties from node networks that simply return their value by looking at the source node network. The source node network itself should be used for this. This should make some interfaces quite a bit smaller.

• In the Pathfinder it should be clear what is a source node network and what not.

• Interface structure should be consistent

Summary

This applies to the Pathfindax.Duality project.

In order to integrate pathfindax with duality it needs to be easily accessible from other components. The following steps have to be done to achieve this:

• Create a PathfinderComponent component which implements a IPathfinder interface. The completed paths should be checked in the before update of the core plugin.
• Create a PathfinderManagerComponent will find all IPathfinderComponents in the scene and store this in a public static property.
• Since the way the pathfinder is accessed might be changed in the future and static properties do not give you this flexibily there needs to be a layer of abstraction between the static property. A Proxy class which sits between these systems is suited for this.

Analysis

This makes it possible for other classes to easily request a path.

Summary

In some of the refactorings in #35 the logic that created the request in the pathfindproxies has been moved to the pathfindalgorithms. So currently the pathfindproxies do nothing but get a reference to a pathfinder.

This could be done alternatively by getting a reference to a pathfindcomponent (with GetComponent or just setting it in the duality editor) so there is no longer a need for pathfindproxies.

Analysis

• Use the standard way of getting a reference to a object instead of a custom way.
• Less duplicate code.

Summary

Currently the MouseClickPathfinder has implementations for both grid and non grid pathfinding. A OnGrid Boolean controls which implementation is active. These should be separated in 2 different components as they most likely wont be used at the same time in real scenarios.

While at it provide additional comments explaining what each property/method does.

As this is not included in the nuget package there is no need to make a new release.

Analysis

• Less confusion about what is needed for the pathfinding and what is needed to support these 2 implementations.
• Shorter component code that's straight to the point and ready to be pasted in without additional configuration.

Summary

Add support for await to PathRequest. This can be done by implementing a GetAwaiter method that returns a class that implements INotifyCompletion, a GetResult method and a Status property.

Awaiting a pathrequest will symantically be the same as adding a callback to a pathrequest and therefore should also call AddCallback behind the scenes.

Analysis

• Shorter syntax for adding a callback to a PathRequest, especially for nested callbacks.
• Will not play well when used in a winform/wpf/asp.net project as the logic will bypass the SynchronizationContext. However adding a callback currently doesnt support this either and this could be fixed in a later issue. Currently I don't think ppl will use this library in such a project either.

Summary

Add a astar pathfinder that works on non grid maps

Summary

Duality tilemaps can have multiple collision layers. The pathfinding has to support this aswell.

Implementation

-There will be a new enum called 'PathfindaxCollisionCategory'. This is a flag enum that is a copy of the duality 'CollisionCategory' flag enum.
-The path request class should have a extra variable added for this new enum.
-There will be a new object called 'NodeConnection' which will have a node object and a variable of type 'PathfindaxCollisionCategory' called CollidesWith for the collisions.
-The pathfinding algorithm has to be modified to take this into account. This can be done by checking for any intersection between the PathfindaxCollisionCategory of the request and the CollidesWith flag enum in the NodeConnection object.
-The visualization of the nodes should be changed too to reflect this.
-This also means that the ISourceNodeNetworkProvider interface will no longer be returning a list of nodenetworks but just a single one.

Summary

Currently there is a PathRequest object to request a path and a pathcompleted object for when a path is completed. These could be merged into a single object which would also make it easier to provide a Status property for a user who would like to poll if a path is finished already or not.

Analysis [Feature Requests]

• The ability to poll if a path is completed
• Less objects and generic arguments

Summary

Add hierarchical pathfinding to the framework. This will be a optional feature that is not required. A more detailed description can be found here: http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/. This would be implemented in the Pathfinder.Process method.

Analysis

A huge performance boost can be achieved at the cost of losing path optimality.

Implementation

The source node network will be responsible for creating the less detailed node arrays. The Pathprocesser has to be modified to support this aswell and implement the hierarchical algorithm. These should all be optional.

Summary

Currently every time a new path has been solved amongst other objects a new maxheap is created and allocated. It might be better to reuse a already created object here to avoid having to reallocate memory every time and reduce the GC pressure.

Summary

Separate the code to visualize paths and node networks into separate components

Summary

The current tilemap node generation code is quite messy and hard to read. While rewriting this the following functionality could be added:

• An option to exclude diagonal neighbours
• An option to allow crossing corners

Summary

Instead of using references consider using a int to reference a item in an array in the maxheap.

Analysis

• This will work with structs
• This removes the need to have a HeapIndex property on the object
• Possibly better performance

Summary

Nodes should have a flat cost that will make it 'costlier' to traverse by adding it to the GCost.

The pathfinding algorithm should take this into account when finding the shortest path.

Analysis

This will allow agents to avoid parts of the map that will be hard to traverse (like a swamp area, jungle etc) and try stick to parts of the map that are easier to traverse (like roads).

Summary

The hashset can be replaced with an array lookup. Use a byte here so it can be easily cleared by upping a 'generation' variable instead of zeroing the entire array. This will be much faster than a hashset and use less memory.

Summary

Implement flow and potential field pathfinding. The flowfield should be created by using the potential field.

Analysis

Both:

• Efficient multi agent pathfinding.
• Robust in the sense that if a unit somehow gets pushed from the path it will find its way back without problems.
• The naïve implementation that will calculate the field for the entire map will use up more cpu and memory than necessary. This could be made more efficient by only doing a high level hierarchical astar search to determine which parts of the map are needed. Caching fields will also be more complex as you could have a incomplete field. However this requires a lot more work as no such nodenetwork or algorithm has been implemented yet in pathfindax. For now stick to the simple implementation.
• Can and should be cached based on the targetnode, clearance and agentsize (the startnode does not matter). This will reduce memory usage and increase performance.

PotentiaField:

• Less performant than flowfields since the actual heading at a position has to be calculated by checking all neighbours and picking the one with the highest potential. Still this are just a couple of array lookups so its still quite fast. The difference might even be unnoticeable in many cases.
• Dynamic pathfinding if agents can emit their own potential field that's added to the potential field values when figuring out the heading.

FlowField:

• Highly performant once the field has been calculated. Getting the heading for a particular agent at a particular position is basically an array lookup.
• if you constrain the directions to 248 different directions and 1 for the Vector.Zero then it will only take 1 byte per node to store a flowfield if you use a separate lookup array for these values.
• Basically what you would get if you asked the heading of every node in a potential field and store this in an array.

Summary

There are several private fields used in pathfindax duality components that are currently being serialized. This is not needed and can even cause nasty bugs. Add a [DontSerialize] attribute to these fields.

Summary

Change the node classes to structs and use the new maxheap as the old one did not supported structs. This will use less memory and can lead to better performance due to better memory locality.

Summary

It should be possible to convert a duality tilemap to a node grid that can be used for pathfinding

Analysis

This will make it much easier to use the Pathfinder with tilemap based games

Summary

Add overloads for float, Vector2 and Vector3 as start and end position.

Summary

Change NodeConnection to use a int index to point to the node instead of a reference to the node.

There is no need to store a reference to the node itself as you could look this up in the nodearray if you have the index. This index is the same for both sourcenodes and the nodes that are used on each thread.

Analysis

• No need to duplicate NodeConnections between the source node networks and the node networks for each thread. The int index can be reused without problems. So each thread will only use extra memory for the extra nodes instead of nodes + nodeconnections. Even for just 1 thread the savings will be quite big.
• Less memory per NodeConnection on 64 bit systems (for 32 bit it would be the same as a reference is also 32 bit there) .
• NodeConnection doesn't have to be a generic type anymore as it no longer cares about the type of node.

Summary

By using rectangular symmetry reduction one can achieve a speedup of a order of magnitude without sacrificing path optimality. This requires some preprocessing and some memory overhead in order to generate and store the 'rectangular node groups'. However the memory overhead could be offset by the fact its possible to move the clearances to these groups so its no longer needed to store them per node.

The basic idea is to group nodes which have the same clearances (and later on weights) together in a group. We know this group has a rectangular shape and thus we only need to expand from the nodes at the border of the rectangle. This is the part that gives a huge speed boost since alot of nodes are pruned and do not have to be inserted into the heap during the search. Especially in maps with large open areas the speed boost could be more than a order of magnitude.

https://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/#4

Summary

Nodenetworks shouldnt be serialized by default by duality due to the amount of data involved and the fact they are currently generated from other data. Add surrogates that will prevent serializing them.

Summary

Currently there is a clearance float for this but it's unused. The Pathfinder should be able to take the agents size into account.

This could be implemented by adding a list of clearances per node with a clearance value and a collisionmask. The clearance will be the true clearance which can be found here: https://aigamedev.com/open/tutorials/clearance-based-pathfinding/. This will all be precalculated.

The exact clearance will be calculated at runtime by getting all the clearances that have a collision with the collisionlayer provided and then taking the smallest one.

This should provide a balance between memory usage and cpu usage as its not practical to store all possible combinations of clearances and collisionlayers beforehand.

Summary

There are cases in which you want to wait synchronously till the path is completed. Currently the PathRequest class does not support this out of the box. Exposing a WaitHandle which is set when the path is finished would make this a lot easier and even make it possible to wait for multiple PathRequests.

Analysis [Feature Requests]

-Usually unit tests have to wait till the PathRequest is finished
-There can be cases in which a user desires to wait till a PathRequest is finished

Summary

Visual studio 2017 seems to have broken the sandcastle documentation. This might be because visual studio 2017 targets v75 instead of v111 for PCL's and something weird is going on here atm.

How to reproduce

Documentation project does not build

Summary

Replace the current imperative way of rendering with a model based way. This should allow most logic to be moved to the core library and make it easier to test while at the same time reducing code duplication.

Summary

Currently its possible to specify a agent size. This is then used in the pathfinder to prevent calculating a path that goes through nodes with not enough clearance.

However currently its up to the end user to supply the correct offset. The pathfinder itself should manage this.

Summary

There should be a tutorial how to use pathfindax with the duality tilemaps

Summary

The MaxHeap plays a major role in the performance of the pathfinding algorithms as its used as a priority queue. Some micro benchmarking has shown that storing the result of a property in a local variable can significantly increase performance of the MaxHeap. The compiler probably cannot guarantee the values of the properties do not change and thus cannot optimize them properly.

See if there are any redundant property accesses and optimize these away. Microbenchmarks already have shown significant improvement so measure the result by measuring the performance gains in the pathfind algorithms.

Summary

Currently pathfinding uses the same nodenetwork to do the pathfinding for all collision layers. Change this to a separate nodenetwork for each collision layer.

Analysis [Feature Requests]

• Makes it possible to implement stuff like hierarchical pathfinding.
• Nodes themselves won't have to know if they are in a grid or not. This leads to less code duplication.
• More memory usage. Though in practice only a few collision layers will be used and the fact that nodes themselves are simpler might offset this a bit.

Summary

Add a benchmark project that can run benchmarks with benchmarkdotnet

Summary

Add a unit test that checks if a zeroed out potential field returns zero vectors. If this is not the case fix this.

Summary

Currently version 2.9.8.0 of duality is used but the latest version is 2.13.3 already. Other packages can be updated as well.

Summary

It should be possible to add multiple callbacks to the PathRequest which will all be called when the PathRequest is finished. If its already finished the callback can be called immediately.

Analysis

-Allows users to call multiple methods

Summary

Add unit tests for the following functionality:

• RemoveFirst
  • add some items to the heap and check if RemoveFirst returns these in the correct order.
• Contains
  • Add some items and check if contains returns true.
  • Add some items and create new items and check if it now returns false for these new items.

Summary

The following things need better error messages:

• TilemapNodeGridGenerator needs to provide a proper warning when it cannot find a tilemap.

• PathfinderProxy needs to provide a warning if it cannot find a pathfinder.

Summary

The functionality of the GridTransformer class should be splitted into 2 classes:
-A Transformer class that simply transforms a position to local or world space
-A GridTransformer class that inherits from Transformer and adds grid related transformations to this.

Lastly add unit tests that check if these classes behave properly.

Analysis

• Non grid networks can use the Transformer class and grid networks can use the GridTransformer.
• Preparation to add proper transformer support that will make it possible to move the network after it has been created. Possibly also rotations in the future (might be needed for iso grids?). Currently the positions in the nodes are not local but worldpositions.

Summary

The compiler does not use generic type inference in constructors. When using a normal method the compiler will try to use inference to figure out the generic types. Create a factory class with a static method to create the following types:
-NodeConnection
-MultithreadedPathfinder

Summary

Currently the offset and scale is not properly calculated for the tilemap

Summary

Currently there is a foreach loop in which the workers are checked if they are busy or not. If not it will give them new work to do. When the queue is empty the thread will already wait for new work.

However when there is work and all workers are busy it will keep checking them constantly which eats alot of cpu. The thread should also wait if all workers are busy.

Summary

There is no check if the provided x is valid on the 2 dimensional indexer.

Also add unit tests for this.

How to reproduce [Bugs]

• Define a 2x2 array
• Access the array with x = 2 and y = 0.
• This will cause the actual coordinates to turn into x = 0 and y = 1.

Summary

Currently when no path is found the pathrequest status is set to Solved while this should be NoPathFound. This is because the dijkstra algorithm that runs over the graph always succeeds unless the target node is not traversible. A additional check is needed that checks if the potential field has a non zero heading for the startposition.

Summary

This class is no longer used

Summary

Add a example of using pathfindax in a console application. The goal is to help make ppl understand better what pathfindax is doing.
While at it this would also be a opportunity to see if there are any easy usability improvements.

Summary

Currently DynamicPotentialField is updated completely on the mainthread. This is done in the following way:

• Set all values to 0f in the potential array.
• Calculate new values using the stored PotentialFunctions and add these values to the array.

So currently the work that has to be done scales both with gridsize and the amount of agents/complexity of the PotentialFunctions. Without separate threads this could be improved in the following ways:

• Make it possible for the user to provide a boolean that will make the PotentialFunction precalculate its values and put it in a array. This array will then be used in further calculations.

If this is not enough a final change would be doing most of the work in a separate thread. This way there is no longer a hard 16ms frametime restriction. Broadly speaking this could be achieved in the following way:

1. Initialize 2 arrays of the same size. One for the potential field itself and one for the worker thread thats going to update it. These will be called potential array and worker array.
2. The mainthread will first get the positions and store the potentials that will be added in separate arrays.
3. A separate thread will reset all values to 0f in the worker array.
4. A separate thread will calculate the new potentials in the worker array
5. Once finished signal the mainthread to swap the references to the potential array and the worker array. So now the old potential array is the worker array and the old worker array is the potentail array. This approach avoids the LOH issue with big array as there is nothing that has to be cleaned.

Using this approach the work on the mainthread will only scale with the amount of agents and most of that work might already be done in a precalculation.

Summary

Tilemapnodemapgenerator currently only looks at children gameobjects when searching for tilemaps. Make it also look at the current gameobject so that it will work with single layer tilemaps as well without having to add another parent gameobject.

Summary

Currently the node model is not compatible with the duality tilemap. It should be possible to manually define the neighbours.

The INode interface will expose a IList of INode called Neighbours so it can be modified. These must also be generic so it's possible to use different kind of nodes. This is needed for the duality tilemap integration.

While we are modifying the node model anyway. There will also be a new interface called IGridNode. This interface implements the INode interface and the GridX and GridY variables will move to this interface. This will make the base INode interface not have a dependency on the concept of a grid.