Procedurally Generating Indoor Pathways
Exploring a new technique for wayfinding that doesn’t involve drawing anything by hand.
Wayfinding is a pretty cool problem because everyone is familiar with it. Whether you’re trying to find the nearest coffee shop, planning the commute to your office, or traveling across state lines, everybody wants to know the best way to get there.
The desire to know how to get between two places doesn’t only exist in the outside world though — sometimes you might want directions for how to get somewhere inside a building.
Let’s say it’s your first day at your new job at the big tech company Hooli. You have an important meeting in room 617B on the sixth floor. Getting to the sixth floor is easy because you obviously know where the elevators are, right? But finding room 617B is a bit more complicated than that because each floor in your fancy new office is the size of a small city. What are you supposed to do — run around, reading each room's name like somebody who isn’t already 5 minutes late?
A much better solution here would be to open some maps app on your phone that would tell you where room 617B is and exactly how to get there, or something to that effect.
There are a few things that make this a hard problem to solve:
- You probably don’t even have a map of your office on your phone in the first place (although, you could)
- Getting different pathways between rooms within an indoor space is traditionally a manual and tedious process that involves people literally drawing lines by hand.
Finding the actual pathways for an indoor space is a surprisingly hard and abstract problem, especially when you compare it to finding pathways for an outdoor space.
Outdoor space pathways usually end up being just streets or roads, which is data that the map already has to begin with. For an indoor space, a pathway is more like the absence of the data we begin with since the pathways are the areas between all of the things that we know about (walls, chairs, tables, etc).
Because of this, most ways people solve this problem is by creating the “pathways” data by hand. In other words, someone will go in and draw invisible lines all over the place and use those as “roads”.
That’s lame because it doesn’t scale very well. Imagine having to draw pathways for hundreds or thousands of floors. Super lame. Since we don’t want to be lame, we can try to find a way to generate indoor pathways procedurally, so every floor can have pathways without us having to lift a finger.
Wait, so what even is a “pathway”?
If you think about it for too long, the concept of a “pathway” gets pretty blurry. So let’s take a step back — the problem we’re trying to solve is figuring out a way to get from point A to point B within an indoor space.
To help prevent us from getting distracted by the details, let’s imagine all the floors we’ll be looking at don’t have anything within them — just empty hallways.
So as far as we’re concerned, a “pathway” is just a collection of contiguous line segments from some point A to some point B, such that no line segment intersects through any walls or entities on the floor. That’s basically just a fancy way of saying that a pathway is a bunch of lines that are in-between walls.
Knowing where the walls are is the bare minimum requirement for even attempting to find any pathways, so let’s use this as our starting point — let’s assume that we already have all of the information about where walls are on a floor.
Great! So now that we know where all of the walls are in the form of a bunch of line segments, how can we figure out where all the pathways are? If only there was some kind of magical way of finding line segments in-between other line segments…
Introducing the Voronoi Diagram
Let’s take a break for a minute and talk shapes. In the world of mathematics, there is a special kind of diagram that helps partition geospatial data into groups based on their proximity to one another — it’s called a Voronoi diagram.
The idea is simple but can sound complicated — given a bunch of “source” points on a plane, divide that plane into different sections such that any arbitrary point within a section is closest to that section’s original source point more than any other section’s original source point.
Listen, I get it — it’s kind of hard to explain. The important thing to know is that these diagrams can be used to find which source point you’re closest to, wherever you are on the plane.
Now, I know what you’re thinking — that’s cool, but so what? How does that help us with finding indoor pathways?
Well, that’s the fun part. I noticed an interesting property that these Voronoi diagrams had. Since they’re designed to generate polygons around a point of origin, such that any point within the polygon is closest to its respective origin point than any other, that means there must also exist some points that are equally close to two or more different origin points — those points are actually the ones that form the lines which make up the generated polygons.
Do you know where I’m going with this yet? The line segments that make up each polygon within a Voronoi diagram are equidistant from some two origin points.
Sound familiar? This is incredibly close to the original problem we’re trying to solve with pathways! We are trying to figure out how to find lines between two walls, and this diagram will find us lines between two points.
We now have a way of finding a line segment between two points, so if we just change up our input a little bit and convert those walls into many different points, we should be able to create a Voronoi diagram and “extract” the pathways we’re looking for from the generated polygons.
Sculpting pathways from the marble of Voronoi
Cool, so let’s put this idea to the test. We essentially want to generate a Voronoi diagram with the walls, and then extract the polylines that navigate through the hallways.
Step 1: Generating the Voronoi diagram
Since we need points to create a Voronoi diagram, we can just convert our wall line segments into points.
Instead of just using the start and end positions of the line as its points, we want to generate a bunch of points in between them as well. This is because we want the Voronoi polylines to stay within the hallways.
Recall how the generated polylines are equidistant between any two source points. To ensure we get as many polylines as possible that exist in the hallways, we need more points on the wall line segment.
Once we get all these points, all that’s left is to run it through any Voronoi algorithm you prefer. Since the resulting diagram is technically a bunch of polygons, we should convert them into line segments before we do anything with them. That part is easy — we just iterate through each point in a polygon and form a line segment using the next point in the order we see them.
Step 2: Simplify, simplify, simplify!
Now that we have a bunch of line segments, we need to figure out a good way to simplify our data. We only care about pathways through the floor — we know they’re somewhere in all of these lines, so we need to help ourselves reveal them by removing the lines which will not help us.
Let’s start by figuring out which of these lines are totally useless. In our case here, a line is useless if it either:
- Is outside of our floor’s boundaries (the outer walls).
- Goes through a wall.
We can find any lines that fall outside of the floor’s boundaries by taking the convex hull of the outer walls, and simply pruning any line segments that either intersect with the hull or are outside of the hull.
Similarly, we can find all of the lines that go through walls by comparing each line to our original wall dataset. If a line intersects with a wall, prune it!
And… voilà! We’re left with a bunch of lines (a whole lot less than what we started with at least) that make up some kind of pathway through the entire floor!
Step 3: Make it useful
These lines might make sense to us visually, but not so much to a computer. In order for us to write a performant program for deriving pathways using these lines, we need to convert the data into something more helpful for the job — in our case, a weighted graph works perfectly.
For this graph, the vertices are the start and end points of our line segments, and the edges are just the lines themselves. The “weight” of each edge can just be the distance of the edges in pixels.
With the graph we just created, we can finally start wayfinding! Just pick two points on the floor, find the closest points on any of the edges to designate our true starting and ending positions, and then we can find the shortest path using any “shortest pathfinding” graph algorithm of your choosing.
Step 4: Finishing touches
This works great and now we actually have a pathway between any two points on our floor, however, you’ve probably noticed that the generated path is a bit bumpy.
We can address this by using some polyline smoothing algorithm, but we need to make sure we don’t smooth it out too much.
If the path gets too smooth, then it runs into the risk of smoothing itself through walls since the nature of smoothing a line is to “take shortcuts” between points.
After a bit of path smoothing, we’re left with the result — an indoor pathway that gets us between two places on a floor.
Moving forward
While all of this works, it’s of course still possible to make many improvements.
- Extend this algorithm to account for things like desks, tables, and all other entities on the floor. We would just need to know where those things are and include them in our Voronoi dataset and things will work as expected!
- We could extract the secret sauce from the Voronoi diagram generation and come up with a simpler algorithm that doesn’t waste our time generating as many “bad” lines or polygons.
- Finding the convex hull of the floor is helpful but imperfect. We could instead just find the outer-most part of the entire wall dataset and use that as our bounds instead.
- That path smoothing approach could be refined to always try and simplify a path as much as possible so long as it doesn’t collide with a wall or other entity on the map.
The purpose of this exploration was to see how viable it was to procedurally generate pathways and if it was even possible. With that goal in mind, I think this was a huge success 🎉
