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.

One Does Not Simply

I gave a talk about Entity Systems and how to use them in Unity3D at the SAE Institute Hamburg last Friday. Feel free to check out the slides at Slideshare!

One Does Not Simply

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.