razziel89 / astar Goto Github PK

Add such a workflow to simplify contributions.

Close these first:

• #20
• #19
• #21

Possibly even implement these, but they can also be moved to the next release:

• #22

Test coverage is not all too high yet. Add more unit tests.

Creating regular graphs is not too easy right now. It would be cool to be able to create graphs from regular grids with minimal commands.

Features:

• Provide grid size in all dimensions
• Provide metric function used to determine whether two nodes are neighbours (requires iteration over entire grid for every point, which is inefficient)
• Provide list of displacements to reach neighbours (remember to track node positions in the creation algorithm, this is very similar to the example in the readme)
• Take function that retrieves cost for each node, allow nil, in which case the cost will have to be set manually
• Take name creator function
• Make sure to add position as payload

Every project needs a logo these days having one would be cool! Should be a vector graphics in an open format such as svg.

Close these first:

• #4
• #6
• #7
• #8
• #12

The current implementation that simply iterates over a graph is not as efficient as using a binary heap. Implement a binary heap. To keep the number of dependencies low, implement it here as a sub-package.

The current implementation that simply iterates over a graph is not as efficient as using a binary heap. Assess speed up by using a heap structure.

Greatly improve speed up by making nodes aware of which graph they are in. That way, a node can only be in one graph, but that's OK as it greatly improves performance. We will get rid of the map entirely.

Release 0.1.0, which will no longer be an alpha version.

Close these first:

• #1
• #2
• #3
• #11

Moved to next release:

• #4

In order to support different types of nodes, they should be replaced by an interface. That interface needs at least the following:

• getters (and possibly setters) for currently public members
• a getter for connecting nodes (required for on-demand creation of nodes based on some algorithm)

There are cases when the approach of first creating all nodes and then finding a path through them is not ideal, e.g. when the possible number of nodes is so large that they do not all fit in memory. Instead, nodes can be created programmatically. That is, a new type of node implementing the node interfaces (cf. #19) can be created whose Connections method then provides all nodes. There is one major challenge here: currently, nodes are identified uniquely via pointers to them. When programmatically creating neighbouring nodes, some other means of uniquely ID'ing nodes is required. Suggestion: require unique names that follow some scheme, or require some hashing function that generates an ID based on a node. Implementing this without generics can be tricky. With generics, the ID type can be specified by the user as long as the ID method returns data of that type. Maybe wait until go 1.18 has been released to employ generics.

Requires these:

• #19
• #20

The README currently provides one example but not a lot of details about the different parts of the code base and what they do. That should be changed. The details could even be put into a separate file linked to from within the README.

All code is documented and there is a README. But all that documentation does not yet live within HTML documents accessible via GitHub pages. That should be changed.

The implementation supports one way connections, but the feature is not yet tested in any way. Test it.

Requires Go 1.18 and its generics, which has not yet been released. Convert the 2-D graph creator into one suitable for any dimensionality. Cf. #6.

Currently, traversing both directions is always equally expensive. For some cases, e.g. when moving uphill or downhill, this is not the case. Permit connections that cannot easily be traversed both ways.

Currently, the algorithm modifies nodes during path finding. That can be avoided by storing as many of the private members as possible in the graph in some form. That way, nodes don't have to be reset after path finding and they can be used in multiple graphs at the same time, allowing multiple paths to be found simultaneously. This will require some major modifications to both the Graph, the HeapedGraph, and the path-finding algorithm itself. Quite possibly, the GraphOps interface will have to be extended or modified. The interfaces recommended to users should stay in tact, though.

Actually check whether an update of the tracked cost has happened:

See astar_test.go.

Goroutines can be used to speed up the algorithm. Try that.

To check that the code always works, leave concrete examples in place. Also add one large example that can be used as a performance measure.