Clever Geek Handbook

Modification of AStar algorithm for connecting gates in a logic circuit

I have been working on a logic circuit simulator for some time now. This all pretty much works, but there is a problem that I can't seem to solve.

Logic connections must be vertical and horizontal. They should avoid logic gates and have as few turns as possible (avoiding the staircase effect). Joints can also overlap, but they can never overlap.

I used AStar's algorithm to find the shortest and most enjoyable path between two logic gates. The heuristic for pathfinding is the distance in Manhattan, and the cost between two nodes is the dimension of one square on the canvas.

The whole problem arises between two conditions. "Min. Turns" and "no overlap". I solved the "minute turns" problem by punishing the algorithm with double its normal cost when it tries to turn. This forces the algorithm to defer all rotations until the last possible moment, which my next image calls.

The issue!

My no-overlap condition prevents the second input from connecting to the second free input of the AND gate (note: the simulator is made for Android, and the number of inputs is variable, so the inputs are close to each other). A similar situation will inevitably happen sooner or later, but I would like to do it as late as possible.

I tried:

  • enter "int turnNumber" to count how many turns have been done so far and to punish paths that make too many turns. (the algorithm takes too long to complete, sometimes very long)
  • calculate the distance of Manhattan from start to finish. Divide that number by two, and then remove the double-cost penalty from nodes whose heuristic is near that middle. (for some situations, the algorithm fell into an infinite loop)

Are there any ideas on how to redistribute the rpm in the middle, since it is possible to establish the maximum possible connection between the logical gates while maintaining the "minimum pivot" condition?

If you want to see the code: https://gist.github.com/linaran/c8c493bb54cfca764aeb

Note. The canvas I work with is unlimited. EDIT: Method for calculating cost and heuristics - "calculateCost" and "manhattan"

+3


source to share


1 answer


1. You wrote that you have already tried the start / end position of the swap

  • but my courage tells me if you calculate the path from B to Out
  • then the turn is close to Exit , which is OK in most cases because most Gates have one conclusion.

2. Anyway, I'll change the cost per turn policy a little:

  • let P0,P1

    - path endpoints
  • let Pm=(P0+P1)/2

    - midpoint
  • so that you want the queue to be as close to the midpoint as possible, as it can be
  • so change the turn cost tc

    to depend on distance fromPm

  • tc(x,y)=const0+const1*|(x,y)-Pm|

  • which should do the trick (but I haven't tested it this way to deal with the bias)
  • it can create some strange patterns so try euclidean and manhatan distances.
  • and choose the option with the best results
  • enter image description here

3. Another approach -



  • fill in the map from both the starting and ending points immediately
  • And stop when they meet
  • you need to distinguish between cost from start point and end point.
  • or use negative values ​​for stellar values ​​and positive values ​​for the start of the end point.
  • or allocate ranges for two (range must be larger than xs * ys map size in cells / pixels)
  • or add the flag value to the value inside the map cell

4.you can mix 1.and 2.together

  • so calculate Pm

  • find the nearest free point to Pm

    and let it beP2

  • and decide the path P0->P2

    andP1->P2

  • so the turns will be close to P2

    that are next to Pm

    , which is desirable

[notes]

  • The 3rd approach is the most reliable and should lead to the desired results.
0


source






More articles:


All Articles