Pathfinding in AutoCAD with the A-Star Algorithm (A*)

[heschr]

Hello,

 

for a project I needed to find the shortest way between two points in a network, so I searched for a pathfinding algorithm in AutoLISP. Since I did not find anything - here comes my implementation of the A* pathfinding algorithm. (If you don't know what A* is - I got my information here: http://en.wikipedia.org/wiki/A*_search_algorithm)

 

The program finds the shortest way in a network of polylines between two points, the polylines representing the paths you are allowed to move along. Two polylines are considered connected if one of their vertices match. The resulting path is returned as a new polyline.

 

The program and a test.dwg are attached to this post.

 

 

I would like to extent the network/edges in a way, that polylines are also considered connected if the vertice of one of them is on the line of another. I could use some help with that.

 

I hope this is useful for someone.

astar_01.lsp

test_01.dwg

Edited September 12, 2014 by heschr

[Shady_Potato]

This is Amazing work!, but what if there were multiple Objectives? Could there be a way to create a multi-objective pathfinder? For example In HVAC; Say If the Staring point is Given, But I want to Route my ducts to multiple Registers, Is there a way A* could do that?

 

[ronjonp]

There is also THIS.