I am… not math oriented, dropped out of High School Geometry, and this is a random problem I ran into while working on a project.
I dabble in crypto for cryptocurrency related work, so I’m familiar with very basic graph theory, DAGs and the like, and I guess algebra.
I hope I’m wording my question appropriately. Let me try and add some context and put the problem into laymen terms in case I very terrible misworded my title.
- There is a 10v10 player video game. On each team, there is a designated captain.
- Each side only has access to the x, y position of their own captain. This is the only exact data we have.
- Players don’t even know their own x, y on the map.
- Each player knows the distance (within a 5 or 10 unit range, ie. 5 – 15 units away) to another player from their location, if under 40 units.
- The map is a few thousand units by a few thousand units. Lets say 3000×3000 for the example.
- When a player gets <40 units from the enemy captain, they will know within a 5 or 10 unit range how far they are.
- The enemy captain does not report their distance from us.
- You know which of the 1-19 secret points is the enemy captain.
- These limitations are on data given to plugins for automation only. The actual gameplay does not have these limitations, so don’t imagine real people running around blind in a dark room.
Assume that each team player can share their own data with each other, each player has access to the following data:
- Their captain’s exact x, y position.
- Their distance as a 5 or 10 unit range from every player of their team as well as the enemy captain, if under 40 units.
- Each player’s distance from enemies as a 5 or 10 unit range (within 40 units), but not vice versa (enemies do not report to us).
Essentially, we have a maximum of 20 data points (distance ranges between every team player and every other player, enemies included). Plus we have the single x, y of the team captain.
I may be completely off here, but drawing this out, it seems like we can start at our known captain position a and draw “donuts” (min range, max range) representing potential locations of other players, removing the “donut hole” as possibilities.
If possible, I need an algorithm that will use the given data and “estimate” the position of the enemy captain.
So ideally, players would group up within 40 units to get the most information, and then once we can get a high enough “resolution” for the estimation, we’d consider it a success and report that to our team. My suspicion is that because we know our captain’s (x, y), once they get <40 yards from the enemy captain, if we have enough players nearby, we can “bruteforce” a configuration (the distances between players) to find a set of points where their distances match the ranges we have recorded from the game.
I have a couple of concerns.
When visualizing this it started to eerily remind me of asymmetric cryptography, more specifically, the discrete log problem to solve for the secret key. Not quite the same, but I am worried the complexity may be high or even unsolvable due to time.
It is essentially a starting point surrounded by many “donuts” with holes (because distance is a range and not exact units – so we draw two circles and the area between is our “donut”), and those donuts then have their own donuts to represent their distances from each other. Some configuration should give a perfect overlap on the donuts where we can estimate an “area” where our hidden point / enemy is. Do we just start rolling the dice and bruteforce the infinite possibility of x, y positions for each player, until we “match” our data set?
Is the answer always going to be some infinite set of points within some locus or circle because we only have a range for each player and not exact distance? Can we narrow our secret coordinate guess to within a couple units somehow? A couple dozen? hundred?
If solvable, is there a “magic” or “good enough” number of values I’d need to solve? Because we only know distances between players if they’re <40 units apart, our data set fluctuates wildly in real time. Is there some number of distance sets where this becomes feasible to solve?
Okay… please school me. Is this doable? How do I begin to deconstruct these circles into pseudocode and what kind of number theory helps me figure out problems similar to these? Is this possible WITHOUT at least a partial bruteforce?