## Freesteel Blog » 2014 » January

Friday, January 24th, 2014 at 6:07 pm - Adaptive

## A* routing on a flexibly subdivided weave

Sometimes it’s a relief to be certain that I’m doing something which is exactly what I am paid to do. All the rest of the mouthing off comes for free. Though maybe it’s important to always question what you are paid to do, so you don’t wind up wasting everyone’s time doing something that’s actually pointless.

After having got the A* routing through the weave structure to work based on my unpatented subdividing model of a 2D area that forms the geometric basis of the adaptive clearing non-gouging motion algorithm, I noticed that it did not give enough sample points for a linking pass to be within tolerance. The route, which must avoid uncut stock, requires a greater sample rate than the basic weave cells. These cells were sampled to a resolution along the boundary contour so that it would be within tolerance, but it is insufficient to handle the uncut stock structures that exist in the interior space of this area partway through the clearing cycle.

There are two options to deal with this insufficiency of sampling. Either add in an additional sample rate system, or improve the basic underlying weave sampling structure.

Tuesday, January 14th, 2014 at 6:47 pm - Adaptive

## Multi-threading progress object

A quick day’s work to make a multi-threading percentage progress handling object in Python that handles residuals.

Let’s start with the test code (which I wrote after the working code — take that TDD!):

```class ACProgress:
def __init__(self):
self.sumprogress = 0
def ReportProgress(self, lprogress):
self.sumprogress += lprogress
print "The progress is at:", (self.sumprogress *100), "percent"

for i in range(n):
acprogress.ReportProgress(a/n)
time.sleep(0.05)

acprogress = ACProgress()
```

This prints numbers up to 100% in steps of 4%.

Now we want to do this in threads.

Friday, January 10th, 2014 at 4:22 pm - Adaptive 1 Comment »

## A minor A* improvement

The stay-down linking code relies on an implementation of the A* search algorithm to quickly find a connecting path between the start point and end point by spreading a network of paths in an optimal way.

There’s a couple of nice animations from Wikipedia showing what they look like.

Suppose we have a network of paths, like so:

The path from Start to A and the path from Start to B rank the same in the priority queue because:

length(Start, B) + distance(B, End) < length(Start, A) + distance(A, End)

(The length function is the length of the green path, while the distance function is the length of the yellow path.)

According to the A* algorithm, the next step should extend outwards from the point B before we go from A on the basis that there could potentially be a direct path that takes us all the way from B to the End point that is shorter than the best one we are going to get by extending A.

But this is impossible, because the theoretical best direct path cuts through many paths (including the Start to A one) before it reaches End, and any one of these paths could be substituted up to the point of intersection into that StartBEnd path to make it shorter, which is illogical, captain.

Therefore, if there is going to be a shorter path from Start that passes through B, then it will have avoid at the very least the girth of the search tree, defined as a line connected two extreme points, like so:

And when you use this to increase the value of distance(B, End) in the formula above to the length of the two segments required to get round the girth line on either side (whichever is shorter), you don’t get quite so much unnecessary sprawl near the Start point. You can add more girth lines if you like.

It’s a small improvement, but practically for free, and may make a big difference for a lot of realistic cases where there is one major obstruction.

Friday, January 3rd, 2014 at 5:26 pm - Weekends

## Avoiding Nadilog by Walking in Wales

Well, it was a plan. Xmas is a drag, what with either having to go away on holiday or spend days overeating with the family feeling inadequate because you didn’t bring any presents. My thoughts of a flying holiday in Lanzarote had been deemed impractical, and Becka’s plans for a week XC skiing with friends in Norway looked equally difficult due to the lack of passenger ferries.

I’d had this walk in Wales on my mind for ages. Let’s do it, I said.

“But the weather will be crap.”

Exactly. It’s only a walk, and we wouldn’t be wasting good weather on something that doesn’t depend on good weather. In fact the worse it is, the more adventurous it will be. It’s only Wales. It’s not like the Pacific Crest Trail. How bad can it be?
(more…)