How would i make a friend connection search engine

Help and Feedback Scripting Support
#1

  1. What do you want to achieve? Hello, i want to make a search engine that can search if you are “linked friend” with someone for example if i would search BuildIntoGames into the search bar, it would search in my friends, in the friends of my friends and in the friends of the friends of my friends and more.

  2. What is the issue? I have been trying to do it but haven’t found a fast and efficient way to do it.

  3. What solutions have you tried so far? I tried to do it myself and looked online.

1 Like
#2

There just isn’t a good way to do this. Fundamentally this is a pathfinding problem and there isn’t really a good heuristic so you are stuck with a breadth first search. Worst case scenario you would have to search literally every possibility (at least visit every player and query their friends). This is not really feasible. You could in theory speed this up potentially if you could do some form of analysis on the whole and extract potential patterns, but the worst case time would remain the same.

1 Like
#3

I think there is indeed a way to do this because i tried a game that is similar to the one i am making, it has the functionality i want and it can find the target within around 15 seconds even if it’s at 5 friends far from me

1 Like
#4

There is a high chance with a breadth first search you would find the target within only a few hops. And doing a bidirectional search would probably help you converge faster as well. Worst case time though is still searching every single friend connection because there is just no information to exploit between nodes to speed this up.

2 Likes
#5

I just tried that again, it did that search in around 7 seconds

image

The console prints this if it can help someone to find a way

image

1 Like
#6

The answer is pathfinding. There is no other answer. This is a classic pathfinding problem.
As such, worst case requires you to check every node. I would say that you could potentially test by searching to someone with no friends, but a bidirecitonal search would autoterminate because the other side had no friends so that wouldn’t really help.

There are some speedups.
Bidirectional search will increase the chances of a collision between cached users speeding this up.
And cache all the results from either side so that you can look it up locally without needing to query over and over.

You will find most people relatively quickly. Most people are only a couple of steps away, but this problem does scale badly if there is not an early answer.

It’s also worth noting that it’s not necessarily true that this is the “shortest” path, just a path that was found. A simpler problem since you don’t have to check everything, but might still work for your case.

But fundamentally the algorithm you want is a bidirectional breadth first search with caching.

1 Like
#7

It also looks like the game has a pretty weird caching system because, when i try to search another target, it tries to go through a friend of mine that i don’t have in my friends list anymore.

1 Like
#8

Yeah, i will try to find a solution, thank you for trying to help

2 Likes
#9

On a reread this sounds a bit more terse than I would like, but oh well.

Fundamentally though this is the psudocode

local person1
local person2

local person1List = {person1={Parent=nil}}
local person2List = {person2={Parent=nil}}

for i=1, QUERY_LIMIT do
  local rPerson1 = person1List.random()
  for person in rPerson1.getFriends() do
     person1List[person] = {Parent = rPerson1}
     if person2List[person] then
        --path found, reconstruct
    end
  end

local rPerson2 = person2List.random()
  for person in rPerson2.getFriends() do
     person2List[person] = {Parent = rPerson2}
     if person1List[person] then
        --path found, reconstruct
    end
  end
end

And the reconstruction is just following up on both sides from that individual. The person being found being shared between both the person1 list and person2 list and each just creating a chain by repeating .Parent until there isn’t a parent

It’s not super complete though since you’ll need to make sure the chosen random one hasn’t already been processed. But that’s the concept at least. And a random person is chosen because there is no hidden information for us to guess where is a good place to go. We might be able to search the person with the most friends to maximize our caching, but that requires a query so I just randomly select

1 Like