Freesteel Blog » Rolling A-star linking

Rolling A-star linking

Tuesday, February 11th, 2014 at 5:43 pm Written by:

Taking a break from all my other mindful notions to do some proper work on this stay-down linking job.

I have an A-star function that works on the underlying weave structure. The white zones refer to the weave which defines the interior of the contour, and the red zones are the places where it’s safe to go without colliding with the uncut stock.

astart0area
Most A-star algorithms involve one start point in each tile which spreads out to all sides of the tile. But in my implementation the paths from the sides of the tile are pulled from the receiving end, so it’s possible to have two start points in the same tile with two paths going through, as shown above.

astartoparea2crossing
One slight change to this algorithm resulted in paths crossing each other in the cell, which shouldn’t be possible. (The yellow paths are all the elements of the A-star tree, and the green path is the final chosen shortest route.)

astartoparea
I spent a long time gazing at this “bug” wondering why it didn’t choose the shortest path in the direction of the yellow arrow, but instead went round the bottom to point a and round the top to point b. Turns out that, while my model can handle more than one path in the same tile, it can’t handle more than one path claiming the same side of a tile. When the growth of the A-star tree reaches point a, that claims that side of the tile (from the other side), which means the only way forward from the start is into the upper tile and back round.

So, my function DirectWeaveAstarConnecting(ptfrom, ptto) is not perfect, but it’s qualitatively good enough to work with, because it has the property that if it’s possible to fit straight line between the end points, you get that straight line.

The next thing is finding the shortest path. I do this recursively (using an array rather than the call-stack).

Here are the structs in C++

struct astarcelllink
{
    tilereference cpi;
    P2 ptback; 
    P2 ptfore;
};

struct chainstackelem
{
    list<astarcelllink>::iterator it0; 
    list<astarcelllink>::iterator it1;
    bool btoremap; 
}

double Length(list<astarcelllink>::iterator it0, list<astarcelllink>::iterator it1)
{
    double length = (it0->ptfore - it0->ptback).Len(); 
    while (it0 != it1)
    {
        ASSERT(it0->ptfore == (it0+1)->ptback); // points match in sequence
        ++it0; 
        length += (it0->ptfore - it0->ptback).Len(); 
    }
    return length; 
}

You can’t actually apply +1 or -1 to a Bidirectional Iterator, which is what you get with a list (there’s only ++ and –), but you know what it means.

Here’s the function that actually does the work:

void PullChainTight(list<astarcelllink>& astarcellchain)
{
    tlist<chainstackelem> chainstack;
    chainstack.push_back(chainstackelem(astarcellchain.begin(), astarcellchain.final(), false));

    while (!chainstack.empty())
    {
        chainstackelem cse = chainstack.pop_back();
        if (cse.it0 == cse.it1)
            continue;

        list<astarcelllink>::iterator itextreme = FindExtremumLink(astarcellchain, cse.it0, cse.it1);
        if (Line(cse.it0->ptback, cse.it1->ptfore).SideDistance(itextreme.ptfore) < 0.001)
            continue
            
        if (cse.btoremap)
        {
            list<astarcelllink> lastarcellchain;
            DirectWeaveAstarConnecting(lastarcellchain, cse.it0->ptback, cse.it1->ptfore);
            if (Length(lastarcellchain.begin(), lastarcellchain.final()) < Length(cse.it0, cse.it1))
            {
                // splice in the new sequence
                list<astarcelllink>::iterator it1n = it1+1;
                list<astarcelllink>::iterator it10p = (it0 != astarcellchain.begin() ? it0-1 : astarcellchain.end()); 
                astarcellchain.erase(it0, it1n);
                astarcellchain.splice(it1n, lastarcellchain);

                // btoremap=false to enable split in next loop, but no new path
                chainstack.push_back(chainstackelem((it10p != astarcellchain.end() ? it10p+1 : astarcellchain.begin()), it1n-1, false));
                continue;
            }
        }

        // cut chain into two and recursively set up the subpaths
        chainstack.push_back(chainstackelem(it0, itm0, true));
        chainstack.push_back(chainstackelem(itm0+1, it1, true));
    }
}

I’m glossing over one of the extra stages here, which is that, after creating the linking motion, I add in some extra obstructions in the form of these circles at key turning points and splice the connecting path to go round them.

astart0areasplice

Then we pull the result tight within the area defined by (a) the contour slice, (b) the stock engagement calculated along each weave fibre, and (c) a set of additional circles.

Finally, we insert further subdivisions within each of the cells the path passes through to bring it up to the appropriate sample tolerance, and get a nifty routing path like so:

astartareaf
The tight green mesh represents the un-cut stock.

The code is about 2300 lines all in one vast file with 8 struct definitions. It’s got vast inefficiencies and duplicate calculations (for example, it recalculates the stock engagement on every single side of every single cell that we enter, which is a factor of 2 out right there since you should be able to copy the engagement across). But we don’t need it to be perfect for now.

The next job is to drop it into place and apply it to real linking examples and watch how the whole thing fails because I’ve only developed and debugged it against this one example.

This is, in essence, my software development process. (1) Create a test case that’s reasonably challenging, (2) Invent a general-purpose algorithm works against that test case using the failures on that test case to learn more about the problem, (3) Drop your function into the real world and see how it performs.

This is not the same as Test Driven Development, because I’m not writing test cases for every single add-statement in the whole algorithm like I know what I’m doing. I can pretty much count on my initial designs totally not working (a reasonably good assumption). I’ve probably deleted another 2000 lines beyond the ones that are here.

Any of this makes sense? Probably not. Too early to say.

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>