基于直线交点的少量末影之眼计算要塞坐标方案

说明：
本文内容层于2018年6月发布于MCBBS，并被设为推荐，但因为时间久远而不再可见，因此全文挪到博客中了。

毕竟刚高考完就写的，也不是什么高级方法，看看就好。

使用地址：网页使用，C++源码见本文

一、前言

Minecraft中生存模式且非作弊的条件下，主世界要塞是通往末地并击杀末影龙的唯一途径，且其内部有丰富的宝藏。这意味着要塞在Minecraft玩家梦寐以求之地。而Minecraft的道具末影之眼会为我们指向最近的要塞方向，这位我们寻找要塞提供了极大的便利。但是每次抛出的末影之眼都有1/6概率遭到破坏。而事实上，寻找要塞的只需两个末影之眼表明方向即可。当然，多抛几次有利于减小误差。这类教程可能之前已经有坛友发过，而这次会将这个方法讲得更细致，这里将简要地探讨利用两次（或更多）末影之眼方向的数据来直接定位要塞坐标的方法。

二、基本原理

1. 坐标

在数字上反映了玩家在主世界中的位置。坐标基于一个由三条交于一点（即原点）的坐标轴而形成的网格。玩家会出生在距离原点数百方块的位置上。x轴反映了玩家距离原点在东（+）西（-）方向上的距离；z轴反映了玩家距离原点在南（+）北（-）方向上的距离。（粘贴自wiki，CC BY-NC-SA 3.0）。

2.调试屏幕

F3键呼出，显示区块缓存、内存使用、各种参数、玩家的当前坐标和当前游戏帧率图表（粘贴自wiki）。在“两点”法寻找要塞的过程中，我们需要关注调试屏幕中的三个数据：X坐标①Z坐标②与当前朝向（Facing）中的一个参数③。如下图所示：

3.平面上两条非平行线交于一点

这是一个很直观的结论，事实上这是平行线定义的逆否命题。

三、理论计算（两次末影之眼）

在Minecraft中，x轴的正方向为正东方向，z轴的正方向为正南方向，而第二版块中③所表示的值（-180.0~180.0）表示一个角度，其以z轴正方向为始边，顺时针方向为正方向。基于以上原理，两次末影之眼确定要塞的原理大致如下图所示：

其中，A点与B点为末影之眼的抛出点，它们共同指向要塞S点。我们不难发现，如果这两条直线不平行，那么我们可以确定要塞的准确位置。下面，我们将来推导这一个要塞的坐标公式：（作者2021.04.12注：3年前写的，懒得用latex再打一遍公式了）

于是，S点的坐标得以导出，第二版块中的①，②，③分别对应式中的$x$，$z$，$θ$。

四、一个小验证

因为种种原因，验证的图片我实在是找不到了，但可以简单地阐述一下验证步骤与结果：

步骤：
1.在某一点抛出末影之眼，准星指向末影之眼悬停处，记录第二版块中的①②③三项数据；
2.以与1中方向接近90°的锐角方向行走约120米，再重复步骤1；
3.带入第三板块中的计算式，求得要塞坐标；
4.tp至理论坐标，以旁观者模式观测地下构造。

结果：
发现要塞结构（新版本的末影之眼不再指向末地传送门，而是指向要塞结构）位于距脚下5m左右（水平距离）。
（作者2021.04.12注：末影之眼指向要塞的起始楼梯位置）

五、从两个末影之眼到多个末影之眼

从第四版块的验证中我们不难发现，我们的算法基本正确，但仍有些许误差。事实上，由于在调试屏幕中表示朝向的角度只保留了1位小数，而要塞的距离一般距离玩家较远使得角度之差较小（一般都只有8°左右），因此导致的误差可能不小。我们可以用多抛几次末影之眼的方法来进行修正。

修正算法：
1.在多处不同的地点抛出末影之眼（注意确保这些末影之眼指向同一个要塞），记录对应数据，如记录了n组数据；
2.若这n条直线两两相交，则一共有n(n+1)/2个交点；
3.求出覆盖这n(n+1)/2个点的最小圆圆心，以此圆心作为要塞的基准点，而此圆的半径可用于衡量误差。

最小覆盖圆算法： 这个博客已经较为清楚的阐明，此处不再赘述（链接链至CSDN博客）

六、C++源代码

作者2021.04.12注：这是C++版本的代码，现已有JS版本可直接在网页使用，由@lintx移植。

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define MAXN 101
using namespace std;
struct coordinate{
        double x,z;
}loc[MAXN],res[MAXN*(MAXN-1)/2],circle;
double f[MAXN],radius=0;
int n,cnt;
const double pai=3.141592653589793;
coordinate calc(int i,int j){
        coordinate result;
        result.x=(loc[i].x*cos(f[i])*sin(f[j])-loc[j].x*sin(f[i])*cos(f[j])+(loc[i].z-loc[j].z)*sin(f[i])*sin(f[j]))/sin(f[j]-f[i]);
        result.z=(loc[j].z*cos(f[i])*sin(f[j])-loc[i].z*sin(f[i])*cos(f[j])-(loc[i].x-loc[j].x)*cos(f[i])*cos(f[j]))/sin(f[j]-f[i]);
        return result;
}
double get_distance(coordinate a,coordinate b){
        return sqrt(pow(a.x-b.x,2)+pow(a.z-b.z,2));
}
bool In_Cir(coordinate point){
        return get_distance(point,circle)<=radius+0.001;
}
coordinate solve(double A1,double B1,double C1,double A2,double B2,double C2){
        if(A1*B2-A2*B1==0) return circle;
        return (coordinate){(C1*B2-C2*B1)/(A1*B2-A2*B1),(A1*C2-A2*C1)/(A1*B2-A2*B1)};
}
void get_MinCir(){
        double temp;
        for(int i=1;i<=cnt;i++)
                if(!In_Cir(res[i])){
                        circle.x=res[i].x,circle.z=res[i].z,radius=0;
                        for(int j=1;j<i;j++)
                                if(!In_Cir(res[j])){
                                        circle.x=(res[i].x+res[j].x)/2.0,circle.z=(res[i].z+res[j].z)/2,radius=get_distance(res[i],circle);
                                        for(int k=1;k<j;k++)
                                                if(!In_Cir(res[k])){
                                                        circle=solve(2*(res[j].x-res[i].x),2*(res[j].z-res[i].z),pow(res[j].x,2)+pow(res[j].z,2)-pow(res[i].x,2)-pow(res[i].z,2),
                                                        2*(res[k].x-res[j].x),2*(res[k].z-res[j].z),pow(res[k].x,2)+pow(res[k].z,2)-pow(res[j].x,2)-pow(res[j].z,2));
                                                        radius=get_distance(circle,res[k]);
                                                }
                                        
                                }
                }
        
}
int main(){
        //freopen("stronghold.txt","r",stdin);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
                scanf("%lf%lf%lf",&loc[i].x,&loc[i].z,&f[i]);
                f[i]*=pai/180.0;
        }
        for(int i=1;i<=n;i++)
                for(int j=1;j<i;j++){
                        if(f[i]==f[j]) continue;
                        res[++cnt]=calc(i,j);
                }
        for(int i=1;i<=cnt;i++)
                printf("x=%.3lf,z=%.3lf\n",res[i].x,res[i].z);
        random_shuffle(res+1,res+cnt+1);
        get_MinCir();
        printf("\nThe final result is:\n");
        printf("x=%.3lf,z=%.3lf\nr=%.3lf\n",circle.x,circle.z,radius);
        system("pause");
}

七、基于程序的操作验证（图文）

首先，我抛出了4个末影之眼，记录的数据分别如下：

接下来，把这4个数据输入我们的程序（为方便起见，这里已经改为使用文件输入，输入的顺序可能与图片顺序略有不同），输出结果如下：

输出结果中，前6行表示这四条直线两两相交所形成的6个交点的坐标，最后的x,z,r代表着这6个点最小覆盖圆的坐标以及半径。
从输出结果来看，最小覆盖圆的半径只有约10m，当然在我们所理想的误差范围内，下面我们tp至目标点（也就是最小覆盖圆的圆心，x=-494,z=817）进行验证，发现正下方即是要塞，如下图：

八、误差分析

以下操作可能导致严重的误差，请务必避免：

1. 抛出的末影之眼中可能存在两个或更多指向不同要塞。这在程序中的表现为最小覆盖圆的半径可能很大，保证不同末影之眼的抛出点相距不太远即可；
2. 抛出的末影之眼中可能存在两个或更多指向角度相同或极其接近。解决方法见下文的第一点。

以下操作有助于减小误差，由于角度数据中，调试屏幕只保留了一位小数，而最大的误差往往来自于角度之差，因此要使角度之差尽量的大：

1. 抛出一个末影之眼后，与其方向呈接近90度的一个锐角前进，在前进相同距离的情况下大体上可保证角度最大；
2. 前进的距离可大致控制在80~180格，太小可能使角度差值不大，太大可能导致末影之眼指向不同的要塞；
3. 多抛几个末影之眼，建议抛（不同位置）3~4个，由此定位的误差相对较小。 到达理论点后： 因为这只是一个大致位置，要塞可能在该点附近而不在该点上。因此可以向下挖后再向旁边挖挖，或再重复一次前文操作。

九、补充

这是基于点角式直线的计算，我也写过一个两点式的，实测误差更大，有空再填坑。