An Open Source Backstory: Central64

[#1]

A new open source project on Autodesk’s Git launched and it’s called Central 64.

Central64 is a header-only C++ library for approximating shortest paths through 2D grid-based environments. The library supports a variety of online path planning methods that do not require precomputation. All of the methods provide an option to produce central grid paths. All of the methods can be used with any of the standard rectangular grid neighborhoods up to 64 neighbors.

Upon reading this description, I realized that I wanted to learn more. So, I reached out to Rhys Goldstein, senior principal research scientist, and Kean Walmsley, senior manager/software architect, in hopes of learning how this project got started and its goals. Here’s the interview and I hope you take a moment to check out Central64. Enjoy!

Aliza: Thanks so much for taking time to meet with me about Central64. I really appreciate it.

Rhys: Thanks for reaching out.

Kean: Glad to be here.

Aliza: Okay, let’s jump right in. The first question is “What problem were you trying to solve with Central64? Also, could you describe the customer or industry who will benefit from it?

Rhys: Sure. We have a simple and well defined problem. Let’s say you have a 2-dimensional map. An example could be a map of a building or it could be any kind of environment. Let’s say you have two points. The goal is to produce the shortest path from one point to the other. This is a standard, classic problem.

An example of people who may use this are independent game designers. So, if you are writing your own computer game, you might need one of these algorithms and this could be an option.

At Autodesk Research, we use this kind of algorithm for analyzing buildings. So, if you are an architect or an architectural researcher, you could generate a bunch of paths through a building. Then, you can see where the paths overlap because that will show you the main circulation areas in your building. If you want to do something more sophisticated like you want to do a simulation of people moving through the building, you can use this to see what path each agent would take. An agent is “a simulated human.” In a way, this is technologically similar to a video game where you have simulated humans moving through a space.

Kean: I would like to share a few links here (see below) which include my blog posts that reference the other links.

• A paper on our space analysis algorithm in the Journal of Artificial Intelligence Research   (Throug...

• Path Counting for Grid-Based Navigation  (JAIR)

• Explaining how path counting helps simulate natural navigation (Through the Interface)

• A short and direct walk with Pascal's Triangle (Medium)
• Visibility in space analysis: an explainer (Through the Interface)
• A quick and clear look at grid-based visibility  (Medium)

Aliza: Thanks for sharing those links, Kean. For my next question, why is it called Central64?

Rhys: The “Central” comes from an algorithm we developed called Central Path Finding. It’s a method where you use this counting trick. This is where you generate a whole bunch of paths. The number of paths can get astronomical but you can still count them quickly. Then, you select a path that goes through the points with the highest path counts.

For example, there might be locations where thousands of paths cross and other locations where only one or two paths cross. If you pick the locations with the highest number of paths that cross a single point, then you end up with this very direct path. This is our own invention. It’s a faster method than some other previous ones. For example, there is a method where you do these line-of-sight tests. This is where you check for a straight line of sight between all these points. With this method, you end up having to do hundreds of thousands of line-of-sight tests and it’s very time consuming. With our method, this counting trick, you pick out a path quite quickly.

It's called “Central” because the points where you have a lot of paths crossing tend to be central. They tend to be in the middle of all the paths. You should check out one of the Medium articles that explains this further. (Folks, all links are posted above.)

Kean: By the way, the JAIR paper (see links above) will be more dense but the Medium articles make it easy to get a sense for how this works.

Rhys: The “64” part comes from the fact that when you have a grid of points, you have to decide how many of its neighboring points you want to use in the algorithm. In the simplest case, you can have a neighborhood of four points, which is just north, east, south and west. But, you can also step it up and use eight points which would include northeast, northwest, southeast, and southwest. If you want, you can start doubling it. You start off with 4, then 8, then 16, then 32 and then 64. Sixty-four is the largest neighborhood we support. We are not recommending that people use the 64 neighborhood. It’s not the best – it’s the most accurate but also the most time consuming. Sixty-four is the maximum that we support and this is where the name Central64 comes from. Check out the README on our repo, https://github.com/Autodesk/Central64, because it explains this with images.

Aliza: Thanks so much for breaking that down. It’s super helpful background. My final question is “What kinds of contribution are you looking for or asking for from the community?”

Rhys: Sure, small improvements would be nice – those that would improve the quality of the code. It depends on what people are interested in. Also, if someone wants to make a big enhancement and take it to the next level, then we can have a discussion with them.

Central64 is a practical solver and people can use it to produce paths quickly. But, it can also be a framework for research – especially for those who want to improve the algorithms and learn something.

Kean: It’s worth noting that one of the main motivators was this idea of being able to create citable descriptions of the algorithms. It’s deliberately very focused. There are a lot of things that it doesn’t do. It’s not like we want people to build out complicated real-world capabilities into the library itself because it might distract people from the overall goal which is to educate people on these fundamentals.

So, if people are going to contribute, it would be good to bring other algorithms that complement the ones that are there or broaden it but not deepen it too much. It shouldn’t get too confusing for people. This is meant as a tool for creating awareness around the core concepts rather than being a real-world solution for solving complex path finding problems.

Rhys: An example of something that would be a big change is going from two dimensions to three dimensions. For some people this would be a necessity, but we would need to discuss that because that would be a major change to the code. This introduces complexity and it would have to be done right. We encourage smaller contributions or a discussion.

Aliza: And with that, I’d like to thank both of you. I learned a ton and I appreciate both of you taking time to break things down a bit and provide the background to this project.

Rhys: Thanks for doing this interview.

Kean: Thanks for spreading the word.

🤔 Folks, ready to learn more? Check out Central64’s repo at https://github.com/Autodesk/Central64 

About Kean and Rhys...

• Rhys Goldstein is senior principal research scientist at Autodesk
• Kean Walmsley is senior manager/software architect at Autodesk