'proc' has the right idea, but CP+<./\ CD does not take into account all
the P values between the minimum point found by <./\CD and the point
that the minimum value is being propagated to. It adds in only the last
P. [Also it doesn't prevent a value from affecting results on the other
side of a blockage, but I reckon you were going to deal with that in a
later version.]
The data structure is a rectangular table representing the display.
Think of each point as representing a pixel (actually the gridpoints are
bigger than pixels, but the idea would be the same).
The program starts with a set of block locations and desired wires.
Routing the wires involves allocating 'pixels' to the wires. The
algorithm starts at the source of the net, probing pixel-by-pixel until
it reaches the goal. At each pixel-step there are several different
moves (straight, bend, jog), and there are penalties for each, as well
as penalties for crossing a wire or getting too close to another wire or
to a block. The algorithm proceeds until the best route is found.
[I don't want to consider here any major changes in approach. The
method works, looks OK, and fits in with a larger design goal of using
the result of the wiring phase to detect areas of congestion and change
the placement accordingly.]
The main point in the implementation is to keep from wasting time
following paths that are not part of a best path. My code uses several
techniques to score paths as they are created and put unpromising ones
on the shelf while the most promising ones are continued to a conclusion.
But a problem arises in certain complicated situations where the
position has so many blockages that it is impossible to get a good idea
of what the final route will be. Then, even (or especially) when the
algorithm is routing over a large empty area, it tries all the different
ways to cross the area with two turns, and there are a lot of those
ways, all with the same score, and the route bogs down trying to keep
them all active.
You could think of several ways to respond to this problem, but the
easiest and best that I can see is to zip across straight areas with one
long leap rather than pixel-by-pixel - best, that is, provided it can be
implemented efficiently. That is where the current problem comes from.
The list D represents one row (or column) of pixels: at certain pixels
there is a new source-to-pixel distance, coming from all the bends and
jogs that cross the row; at other pixels there is an old distance left
over from previous routes. The goal is to calculate the best
source-to-pixel distances for each pixel in the row, all in one go.
This whole-grid processing will be slower than pixel-by-pixel processing
much of the time, but I think I can detect when those times will be and
use the whole-grid method only when it will be worthwhile.
Henry Rich
On 2/23/2016 12:30 AM, Raul Miller wrote:
So, ok, maybe we can talk a bit more about the system this fits into,
in dissect? Please forgive me for being slow, I'm not thinking about
this very well at the moment.
My first attempt at an implementation looked like this:
H =. 1e6
L =. _1
D =: H, H, 1, H, 5, H, 8, H, 11, L, L, H, H, 20,3
P =: 1, 1, 1, 2, 4, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2
proc=: dyad define
P=. x
D=. y
C=. notblocked=. _1 ~: D
CP=. C#P
CD=. C#D
C #inv!._1 CD<.CP+<./\ CD
)
Here, I was thinking that D would represent the shortest distance from
any node to the left. But, clearly, that's not what you have asked
for. Instead, you're going for "nearest left neighbor", and apparently
there tend to be a lot of these, and you run a lot of tries.
So, taking a step back, just a little - for dissect I imagine you have
a rectangle size that you need to support (and presumably you're
clamping these sizes for large arrays, with interior scrolling within
the rectangle though... hmm... a quick test (10+i.1e3 1e3) suggests
that you are also handing the entire inner rectangles off to Qt to
manage - perhaps out of necessity, given the current jQt
implementation?).
Anyways... I imagine your data structure is some kind of a directed
acyclic graph describing which rectangles connect to which rectangles
and you're trying to approximate a "minimum total distance for the
connections" algorithm.
So... all of this sort of suggests that D represents a specific path
from the start of the expression down through the various rectangles
representing intermediate results and down to a specific
[intermediate] result.
But that path contains several aspects: left-to-right position and
where you introduce the bends. So, anyways, presumably this
represents... the location of those bends? And the total horizontal
distance traveled?
(As you can see, I'm having trouble understanding the spec itself, and
not just the algorithm it fits into... )
Going back to the algorithm I described above - it might represent
something like an A* approach if you slapped a ^:_ onto it. But
limiting us to the immediate left neighbor? That... doesn't actually
seem to me to be an a star algorithm.
Anyways, if you feel comfortable spelling this out in more detail, I
think that could help me understand what you're asking for.
Thanks,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
