Rhys Goldstein, an Autodesk Research colleague with whom I’ve had the great pleasure of collaborating on various projects, over the years, has written an excellent explainer article that has just been published in Towards Data Science. This is intended as a companion to our paper published in the Journal of Artificial Intelligence Research, something I talked about in this recent post.
Firstly, though, a quick shout-out to Zach Kron, who kindly allowed an image of one of his watercolours to be used in the article; one he created with the help of Dynamo and the Space Analysis package, which implements the path counting algorithm.
I won’t go into the specifics of how path counting works – Rhys’s article already does that extremely well – but I’ll summarise the problem and its solution, quickly: using traditional pathfinding algorithms such as A* or Dijkstra on a simple grid can lead to shortest paths being found that are “ugly”. They go from A to B with the same cost as other shortest paths, yet they seem unnatural.
A better approach is to count all the paths between A and B (and between B and A) and then use this information to choose a path that goes through the cells with the highest combined count. This approach generates paths that are more natural (although as they’re grid-based they may still need some smoothing).
This algorithm is being used by Autodesk Research and others to assess the “quality” of building designs and urban plans with respect to walkability and accessibility, in the context of both traditional and generative design workflows. We definitely see much broader potential for this approach, however, which is the main motivation behind publicising the technique via JAIR and TDS.