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.


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.


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*

Grab Bag Release: Rapidly-Exploring Random Trees

Almost there! I’ve finished the implementation of Rapidly-Exploring Random Trees, and added the Random Number Generator implemented by Denis Vaz Alves to the Grab Bag.

Next up are algorithms for the computation of Shortest Paths, and I’m done!

Rapidly-Exploring Random Trees

Rapidly-Exploring Random Trees are a randomized data structure designed by Steven M. LaValle for a broad class of path planning problems.

Rapidly-Exploring Random TreeEach tree lives in a configuration space that allows making motions from one configuration towards another, and has a distance function imposed on. Given a configuration space and an initial configuration, the tree can grow around that configuration until it is unable to make any further motions.

Grab Bag Release: Minimum Spanning Trees

Okay, the last weeks have been full of work, my apologies for the delay. This weekend, I finally managed to finish my implementation of the algorithm for finding minimum spanning trees by Fredman and Tarjan, here we go.

Minimum Spanning Trees

Let G = (V, E) be a connected, undirected graph with |V| = n vertices and |E| = m edges (v, w) with non-negative edge weights c(v, w). A minimum spanning tree of G is a spanning tree of G with minimum total edge weight.

Minimum Spanning Tree

The algorithm presented in “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms” by Michael L. Fredman and Robert Endre Tarjan in 1985 finds a minimum spanning tree of an input graph in O(m ß(m,n)), where

ß(m,n) = min{ i | log(i) n ≤ (m/n)}

and log(i) n is defined inductively by

  • log(0) n = n
  • log(i + 1) n = log log(i) n

Grab Bag Release: Graphs

Last week, I’ve been to Munich with my girlfriend, celebrating indie comics and her winning the Kurt Schalker Award! 🙂 AND I’ve found some time for working on my graph implementation.


Graphs are pairs G = (V, E) where V denotes some set of vertices and E some set of edges between these vertices.

My implementation stores the set of edges of the graph as adjacency list, making it fast at enumerating vertex neighbors, but slows at accessing specific edges for dense graphs (which have many edges between each pair of vertices. It allows adding multiple edges between two vertices, thus being feasible for modeling multi-graphs. Also, it allows creating loops, edges whose source and target vertex are identical.