Archive for July, 2009
Topological all shortest paths automatique’ (TASPA) v1.0
I’ve been writing a paper on the theory behind this project, and in the preliminaries, I derived what it means for a curve to locally concave. Through this definition, I realized my code, as it was, had two major flaws:
(1) I didn’t need to partition the map to find the minimum set of vertices required for path-finding.
(2) Using the set I was getting from convex partitioning, I would need a more sophisticated straight-line algorithm to deal with cases when source or destination lands on or near the boundary of an obstacle, at a crux of a step.
In (1), while I was at the Numenta conference last Thursday, a spark of inspiration came to me. This will be fully disclosed in my paper and so I won’t discuss it fully here. Suffice it to say, I came up with a fully word-combinatorial approach to finding the minimum set and it takes a very short linear time with respect to obstacle boundary length to fully compute. What took version 0.5 about an hour to compute takes version 1.0 about 1/10 of a second.
Because convex partitioning was no longer required for finding the minimum set, I was a little crest-fallen. I’ve spent many hours writing my convex partitioning engine from scratch, optimizing it for speed, and determining how to use it for path-finding. As most would do under such circumstances, I tried to come up with some justification, ex post facto, for having put so much of my recent life into this algorithm, and I think I’ve done it!
It occurred to me that for the same reasons as (2) but with the new combinatorial algorithm, I needed to slightly modify the path-finding wrapper to handle nitch cases where the source point is in the crux of a down-step and needs to travel along the boundary of the obstacle to reach its destination. My solution was to check for source/dest being against a boundary, store passible neighboring pixels, do the appropriate table lookup for each pair of source/dest neighbors, and use the shortest (and thus, possible) path. Mind you, after determining all-pairs shortest paths, this is a fast transaction.
But then I thought to myself, if I can do this for this slightly larger set (the true minimum set via combinatorics is typically larger than that got by shared vertices of convex partitions), its not much of a stretch to do it for the case of partitions. This is not implemented in taspa yet, but I already have code written for a text-based game I’ve been working on for some years now (_very_ part time) that does a simple heuristic for shortest path-finding, which, when given strict limits, can do a good job of circumventing a lot of irregularities in terrain, including bumpy digital lines!
Since, for many practical purposes, this is asking a lot of the end-developer that would use these algorithms for something like robotics or even video games, I have decided to split my project in two. Below are links to Taspa v1.0, including an implementation of Thorup’s algorithm, a linear time SSSP algorithm (thanks Joe Crobak!), my new word combinatorial algorithm for the minimum set, and my new bug-fix for the nitch situation, and to CVX_part v1.0, a convex partitioner for bitmaps, including all the old code, minus the path-finding.
If I hear of some interest in CVX_part as a path-finding preprocessor, I will consider putting the line heuristic and Thorup’s algorithm into it, but for now, the more clinical, provable, and elegant solution is contained in Taspa. Oh! I almost forgot to mention, I added a method to save/load path matrices to/from disk, so paths found with Taspa can be used in other programs without incorporating more than a few of its headers.
Here is the tarball. There was lots of code reuse, so only one tarball is necessary for both utilities.
TASPA/CVX_PART v1.0.1 — Source tarball (GPL v3)
TASPA/CVX_PART v1.0 — Source tarball (GPL v3)
Unlike last time, I not only expect this will be the last update on this project for a while (not counting binaries for Windows and some of the major Linux distros), I have someone to hold me to it. My friend and colleague, Alex Tsui are going to begin work on a video analytics project.
Below are a list of regressions that version 1.0.1 fixed. If you downloaded 1.0.0 and are having problems, try 1.0.1 before commenting.
Version 1.0.0 regressions If you have trouble compiling with g++ > 3.3, < 4.3, replace the following lines of code:
src/taspa.cc:423 &
src/cvx_part.cc:513
if (reportFile.tellp() == 0) {
should read:
std::streampos begin = 0;
if (reportFile.tellp() == begin) {
Version 1.0.0 regressionsIf you have trouble compiling with g++ > 4.3, add the following line of code:
src/user_interface/ui.cpp:39, add
#include <stdlib.h>