Pathfinder & Grab Bag API

Ho ho ho, that’s almost like Christmas! I haven’t got one, I haven’t got three, no, I’ve got exactly two things for you:

First, I’ve uploaded the API Documentation of my Grab Bag of Useful Stuff! This one is especially useful if you’re working with the libraries instead of the plain source code.

Second, I’ve finished my pathfinder tool, which illustrates different shortest path algorithms for you.

Pathfinder

The top left shows a map of 300 x 300 tiles. Use the Unwalkable brush to the right to block parts of the map for the pathfinding algorithm. When you’re finished, set the start and finish points of the path to find.

Pathfinder

The tool offers three different pathfinding algorithms: Dijkstra, A* and growing a rapidly-exploring random tree.

Click on Find Path to make the tool try to find a path from start to finish. All visited tiles will be painted yellow, and the resulting path will be painted green.

Grab Bag Release: Shortest Paths

It is done. I’ve completed the rework of my Grab Bag of Useful Stuff, organizing all of my reusable code as a collection of .NET libraries. Feel free to use anything you want, either parts of the source code or the libraries in whole!

Shortest path algorithms were added last, especially the A* might be of use for you.

This week, I’m going to add the API documentation to my website. Additionally, I’ll clean up the code of my Pathfinder tool, a nice Windows Forms application that illustrates the different shortest paths algorithms and serves as showcase for the Grab Bag. This tool will be open-source as well, of course.

Shortest Paths

Let G = (V,E) be an undirected, connected graph with |V| = n vertices and |E| = m edges. We call w: V × V → N the positive edge weight function of G and define w(u,v) = ∞ if (u,v) is not in E. The task is to find the distance d(v) = dist(v,s) from a distinguished source vertex s ∈ V to all other vertices v ∈ V. This classic problem in algorithmic graph theory is called the single-source shortest paths problem.

Finding the shortest path using A*