How FriendPath Works: Bidirectional BFS Explained

The data we have to work with

Roblox exposes a public friends API at https://friends.roblox.com/v1/users/{id}/friends. Given a user ID, it returns the IDs of every public friend of that user. That's it. No mutual-friend index, no precomputed graph — just a single lookup, one user at a time.

So the problem becomes: given two usernames, and the ability to query one user's friend list at a time, find the shortest chain connecting them.

The naive approach

The obvious algorithm is a breadth-first search starting from one user. You expand outward in layers:

• Layer 0: just user A
• Layer 1: A's friends (let's say ~50 of them)
• Layer 2: friends of A's friends (50 × 50 = 2,500)
• Layer 3: 125,000
• Layer 4: 6.25 million
• Layer 5: 312 million — more than the entire active Roblox userbase

You stop the moment you find user B. The problem: even though Roblox is "only" six degrees deep, layer 4 alone requires 6 million API calls. Each call takes a network round trip (50-200 ms). Even running 200 requests in parallel, that's 30+ minutes just for layer 4. For deeper paths, the math gets unmanageable fast.

The fix: search from both ends simultaneously

The breakthrough is almost embarrassingly simple. Instead of searching from just A, search from both A and B at the same time, alternating layers. Stop the moment the two frontiers collide — the moment the same user shows up in both searches.

Here's the difference visually. To find a 6-hop path:

• One-direction BFS: expand to layer 6 from A — ~15 billion users theoretically
• Bidirectional BFS: expand to layer 3 from A AND layer 3 from B — ~125,000 each, total ~250,000

The savings compound exponentially with depth. For a 4-hop path it's a ~50× speedup. For 6 hops it's more like 10,000×.

It's a similar trick to meet-in-the-middle attacks in cryptography. Two parallel searches that each cover half the depth always crush a single search that covers the full depth, because the search space is exponential in depth.

The detection step (where most implementations get it wrong)

Detecting the collision between two frontiers is subtle, and there's a great writeup by zdimension titled "Everyone gets bidirectional BFS wrong" that goes into this in painful detail. The short version:

Most implementations check "did the new user we just discovered exist in the other frontier?" That sounds right but is subtly wrong: it misses paths where two frontiers meet at the same depth through a user neither has fully expanded yet. You can end up reporting a longer path than the optimal one.

The correct approach: after expanding a layer from one side, check every node in that newly-discovered layer against the other side's visited set, not just its frontier. FriendPath tracks both visited sets in two hash maps that hold each user's parent pointer for reconstruction. When a collision is found, we walk back up both parent chains and stitch them together to produce the actual path.

The infrastructure that makes it fast in practice

Even with bidirectional BFS, a 5-hop search might need to fetch friend lists for 5,000–50,000 users. Doing that serially over Roblox's API would take hours. So:

• Concurrency pool. The server keeps ~250 in-flight friend-list requests at a time. Each layer of the BFS is processed as a single big batch.
• Proxy rotation. Roblox rate-limits requests per IP, so we rotate across several public mirrors of the Roblox API (roproxy.com, rotunnel.dev, etc.). When one rate-limits us, the queue auto-switches to the next.
• Cache. Recently-fetched friend lists are cached in memory for a short window so repeated searches don't re-fetch the same users.
• Streaming progress via SSE. The frontend uses Server-Sent Events so you can watch the search expand layer by layer in the progress log. This isn't required for the algorithm but it's a lot more interesting to watch than a spinner.

Edge cases the algorithm has to handle

• Private friends lists (UK accounts under the Online Safety Act, or manually-private accounts) — we detect them and stop expanding through that node, otherwise we'd just see an empty friend list and incorrectly conclude the user has no path
• Banned accounts — the friends endpoint returns 404 or 410; we skip cleanly
• Self-friend edge case — if A == B, return depth 0 immediately
• One user has zero friends — certain accounts like Roblox (ID 1) and Builderman (ID 156) have no public friends, so no path can possibly exist; we surface that as an explicit message instead of timing out

Why it scales to 70 million users

The clever thing about bidirectional BFS in a small-world network like Roblox is that it doesn't actually have to know about the 70 million users that exist. It only ever touches the small fraction that lie within (d/2) hops of either endpoint — usually a few thousand to a few hundred thousand. The graph could be a billion nodes and the algorithm wouldn't slow down, because the relevant subgraph is exactly the same size.

If you want to use it programmatically

FriendPath exposes the same search through a public API. There's a free public endpoint that returns the path as JSON, plus a metered endpoint for higher-volume use. The full reference is on the docs page.