1

I implemented the A* algorithm (actually a modification thereof...) to calculate wiring on a circuit board. While it is fairly fast in finding a path, it takes painfully long (>100ms) to find no path.

From the outlines of the algorithm I have come across it is clear that it will terminate only when the queue of unvisited nodes is empty.

Are there any heuristics to terminate the search for a path early -- possibly when adding additional assumptions?

heavy
  • 11
  • 3
  • 1
    There is no situation under which A* on a circuit-board-sized grid should take a "painfully long" time. There is probably a bug in your implementation. – Matt Timmermans Jul 14 '22 at 13:09
  • what language/compiler/computer? what resolution of grid or graph node count? As previous comment suggest you most likely did not implement your A* correctly leading to big times to be sure what does it mean `painfully long to find` ? is it seconds/minutes/hours? are you doing this on some kind of image using gfx API like `Pixels[][]` or `SetPixel` etc ... they are usually extremly slow and you can expect 1000-10000x speed boost by not using them ... see [How to speed up A* algorithm at large spatial scales?](https://stackoverflow.com/a/23779490/2521214) for some comparison with yours A* – Spektre Jul 14 '22 at 13:50
  • Since I was too lazy to implement it in a multithreaded fashion and the wiring is triggered on user input, even seconds of runtime are too slow. Implementation is done in Lazarus/FreePascal, grid size is 256x256, all data structures were implemented by me... - – heavy Jul 15 '22 at 06:12
  • @heavy 256x256 is very small grid I expect times <20ms on any decent PC if you have seconds then its obviously something wrong in your code (did you use release build? and turn of all debug features like range checking etc...) show your code and add Pascal tag – Spektre Jul 15 '22 at 15:01
  • 1
    Thanks, @Spektre I ported your implementation to pascal, adapted it to suit my needs and it works fine. [Project at github](https://github.com/mschlegel81/digitaltrainer/commit/cc5b4febe2f49440757e829a112f6a3e515603a1) In retrospect my data structures in combination with retries to find better paths (for one start to multiple destinations) were the problem. – heavy Jul 18 '22 at 06:24

1 Answers1

0

I would just define a max cost limit and terminate if no candidate+lowerBoundOfEstimatedCosts is still smaller than this limit.

On a circuit board I would think no path should be longer than 5 times the manhatten distance (just my guess)

An other idea:
Maybe determine if there is a path at all (with some kind of 'flood fill') might be a good idea. It avoids calculating heuristics for each point and therefore should be much faster than searching the hole pace by A*-Search.

In an multi-threaded environment you could run this in a second (maybe low priority) thread and terminate the A*-Search as soon as you fill-approach finds out that there is no path at all.

MrSmith42
  • 9,961
  • 6
  • 38
  • 49