Freesteel Blog » A* routing on a flexibly subdivided weave

A* routing on a flexibly subdivided weave

Friday, January 24th, 2014 at 6:07 pm Written by:

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.

The additional sample rate system is the more obvious way to do it, because it tackles the problem as it presents itself. One simply samples for collisions with the stock along the connecting path at several intermediate points within each wide square weavecell, and then code up some kind of side-ways deviation around the obstructions, including smooth linking and so forth.

The problem with this approach is that eventually you wind up coding the stock collision avoidance system two times in two different ways. The first way is on the underlying weave structure, and the second way is for paths that cross a single weave cell. Invariably, you’d code this second way as trivially as possible by making the assumption that what happens within a cell is going to be quite simple, so that it is probably sufficient to displace points of the path sideways and perpendicular to the underlying line across the cell.

This isn’t going to be completely easy, but it could be done, and it would be good for 99.95% of cases, until you encounter examples where the shape of the stock within the cell has a little more complexity. Now what are you going to do? Most likely, you’re going to abandon them, because it would be a whole lot of extra shoddy work to handle that 0.05% of annoying cases, and since they’re rare it would be reasonable to fudge the issue — setting aside the fact that even a 0.05% failure rate will seem to happen all the time.

Alternatively, I’ve programmed a way to overlay an additional subdividing structure onto the already subdivided weave, where each cell is binary chopped down in either direction in a not-very-efficient set of code, but which at least works.

In the image above, the white lines are the boundaries of the weave cells, the green lines are the boundaries of extra subdivided cells (done arbitrarily for now), the yellow is part of the final connecting path, and the red lines are parts of the A* search tree.

Here are the underlying structures all thrown in to the current 1700 line file that does everything:

struct astarcellside;   // side of a single (subdivided) cell

struct astarcell;       // single cell (subdivided) structure
  // contains astarcellside acs[4]

struct astarcellhead : astarcell;   // single cell associated with weavecell
  // contains vector<astarcell> splitsubcells

struct astarcelllink;   // path across a single cell
  // contains reference to a weavecell and an index into splitsubcells

struct cellgoend; 	// element of prority queue
  // contains reference to a weavecell, an index into splitsubcells, 
  // and a reference to one of the astarcellside four sides of the cell
  // priority on (dist+distremain) where distremain respects the girth line

There are probably loads of bugs in the code. I’m going to have to handle subdivisions hitting exactly on contour points, or running coincident with contour lines. I hope there are enough ASSERTs and debug code there to direct the corrections efficiently. In theory, there is nothing to stop this method from achieving 100% of the result because it is not limited by any assumption about the level of geometric complexity within a single given weavecell.

On we go. Next up, adaptively target the subdivisions of the cells along the path until it achieves the appropriate sample rate.

Leave a comment

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