Stats

  • Locked Locked
  • Replies 2
  • Subscribers 142
  • Views 6569
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

PathFinding algorithm

RicardoGV1

Hi everybody,

I'm currently working on a pathfinder algorithm, long short story this is my scripting/learning timeline (Bold->important)

-Using A* algorithm with lists:
       1.-create a structure ( index, position(x,y), GCost, HCost, FCost, Obstruction(t/nil) ) for each node inside P&Rboundary
       2.-look for the orthogonal neighbors
       3.-use manhattan distance to check if the Gcost to change to neighbor is less than neighbor GCost itself.

This was working great as in the next gif (the video was taken when debuging node by node), but this only work for small boundaries;
(list are not that fast as I thought) when increasing to a normal size layout it was taking so much time. 



-Using SMA* (Simplified Memory Bounded) still with lists was still too slow
-Using SMA* with arrays and without initial node structure creation, just creating when finding neighbors
      The results are not good at all, it get stuck super super easy when facing obstacles and still slow

My questions are:

- Does anybody know any other node based path finder algorithm that think is better for this case?
- Which is the fastest structure to speed up the node creation and parameter modification for every node?
- I've read a lot that skill do not support Multithread, have anybody know a way of speeding this by this means?  (just want to make sure there haven't been any update)

I've some other ideas as using ray casting to find free directions or use some random functions to generate intermediate points to this algorithm, but I want someone advice on this.

  
Regards,
R.Gómez

  • Hi Ricardo,

    Usually the speed is proportional to your grid size and the length of the lists that you will have to constantly traverse.

    Empirically I have found that instead of constructing a list with blockages, that in practice better performance might be achieved if you perform an ABE-based boolean check in the close vicinity of your region of interest instead. I've played around with custom routing solutions, but in the domain of SiPh, where the grid is ~ 10 um and A* algorithm indeed gave me the best performance. ABE also supports multithreading even though it will be a mis-use of it's original intent.

    You can try the same approach in a ray-casting style in different directions and looking for overlaps. You can either adjust the cast step or keep track of the length of given shapes. I know that it sounds controversial, but sometimes switching to ABE is faster even if you create a bunch of unnecessary shapes compared to SKILL list traversal.

    I don't know exactly what exactly is the context of your desired application, but as already stated by you, when there is a significant amount of blockages, even generating a list with them in the beginning seemed non-optimal and I have pretty much switched to dynamic checking whether I am hitting a boundary or not, instead of checking versus the generated blockage database (in whatever form it is).

    I have tried to implement a wide variety of pathfinding algorithms in SKILL, and at least for my SiPh applications nothing came close to A* in terms of performance, so I would say that you are on the right track. Maybe only Soukup is also worth trying and some ray-casting or vector search with your own heuristic function based on you own context. As you have already observed, whatever you pick it always boils down to list traversal and this is why I suggest to try and get rid off that if possible. You will see a degraded performance if less blockages are present compared with the regular approach, but in case you have plenty of blockages you might observe significant improvement.

    I hope that some of this will helps to some extend.

    Regards,

    Petar

  • in reply to p94todorov

    Hi Petar,

    Thanks for your response. you helped me a lot with the information you gave me, appreciate it. 

    Actually It's the same as you, I'm trying to create a routing tool, so I'll try your ABE approach and keep going with the A*.

    Again, thanks a lot!.

    Regard,
    R.Gómez

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.