Freesteel Blog » Homing in on an A* structure

Homing in on an A* structure

Tuesday, December 10th, 2013 at 6:40 pm Written by:

Of course, I could be going down another blind channel. But for the moment it looks like it is getting closer as I progressively fiddle with the search algorithm and allow it to pick the exit points from each cell and not stick to the mid-point of each edge.




I hacked the function over and over again, trying to make sure each version still worked, and ignored any optimization. This is now the fourth complete rewrite.

The most important change was to alter the structure from paths being defined by a sequence of points, to paths being defined as a sequence of edges.

Specifically, when you have a piecewise linear path, you can represent it either as a sequence of points

[p0, p1, p2,..., pn]

or as a sequence of edges

[ {p0,p1}, {p1,p2},... {pn-1,pn} ]

Obviously you always go for the points representation first, because it looks the simplest and you don’t have redundant information of duplicate points. The redundancy is not so much a waste of memory, so much as that the points can get out of sync. What happens if your sequence goes:

[ ..., {a,b}, {b',c},...]

and then later b != b’? You’re leaving yourself open to inconsistencies.

The problem with the pointwise representation is it doesn’t represent the whole of the geometry.

What happens when you get a intersection that hits on the edge between two points? How do you reference it?

One could establish the convention that any particular point (except the first one) represents the edge immediately preceding it.

Often the edge contains more associated data than the point, such as its length and direction and cell in which it is embedded within. Do these also by convention get associated to that same end point? Pretty soon you’ve got a sequence of what, for all intents, looks exactly like bloated structures representing edges, and the only thing they’re missing which prevents them from being conveniently self-contained is the start point of each edge which you have to iterate one step back in the list to obtain. So why not include that in the structure as well, and complete this evolution?

And then each one structure has to handle a single cell — the one that the edge is embedded within.


Well, anyway, this was working pretty well, until I tried it on something huge and it took 5 minutes to calculate the A* route.

Zoomed in:

Eventually I got it right (after two false starts and hundreds of lines of deleted code) and used a priority_queue — the first one I’ve used in C++.

Next up there’s pulling the connecting path tight, then taking account of stock engagement, and finally making it move smoothly with as few sharp corners as possible — including the first and last where it is meant to be tangent to the incoming and outgoing toolpaths.

Someone did point out today that if the incoming toolpath had a sharp corner just before its endpoint, then one could be permitted to follow through with a tighter corner at the start of the linking path on the assumption that the machine tool would anyway be running at a slower feedrate when it got there. You can have a tight corner at the start of the entrance ramp to a highway because you are not yet up to speed.

Maybe this super-duper linking algorithm ought to allow for variable cornering rads along its length, even though this feature won’t be exposed for many years.

Leave a comment

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