天道酬勤,学无止境

C#实现OBB碰撞算法


向量类Vec3

public class Vec3
{
    public float X { get; set; }
    public float Y { get; set; }
    public float Z { get; set; }
    public Vec3()
    {

    }

    public Vec3(float _x,float _y,float _z)
    {
        X = _x;
        Y = _y;
        Z = _z;
    }

    #region 操作符
    public static Vec3 operator ^(Vec3 num1, Vec3 num2)
    {
        Vec3 v = new Vec3();
        v.X = num1.Y * num2.Z - num1.Z * num2.Y;
        v.Y = num1.Z * num2.X - num1.X * num2.Z;
        v.Z = num1.X * num2.Y - num1.Y * num2.X;
        return v;
    }

    public static Vec3 operator -(Vec3 num1, Vec3 num2)
    {
        Vec3 v = new Vec3();
        v.X = num1.X-num2.X;
        v.Y = num1.Y - num2.Y;
        v.Z = num1.Z - num2.Z;
        return v;
    }

    public static float operator *(Vec3 num1, Vec3 num2)
    {
        return num1.X* num2.X + num1.Y* num2.Y+ num1.Z* num2.Z;
    }

    public static Vec3 operator *(Vec3 num1, float num2)
    {
        Vec3 v = new Vec3();
        v.X = num1.X * num2;
        v.Y = num1.Y * num2;
        v.Z = num1.Z * num2;
        return v;
    }
    #endregion
}

定义OBB模型

public class OBB
{
    public Vec3 Pos { get; set; }
    public Vec3 AxisX { get; set; }
    public Vec3 AxisY { get; set; }
    public Vec3 AxisZ { get; set; }
    public Vec3 Half_size { get; set; }
}

OBB碰撞算法

public class OBBCollision
{
    ////// check if there's a separating plane in between the selected axes
    //////public static bool GetSeparatingPlane( Vec3 RPos,  Vec3 Plane,  OBB box1,  OBB box2)
    {
        return (Math.Abs(RPos* Plane) > 
            (Math.Abs((box1.AxisX* box1.Half_size.X)*Plane) +
            Math.Abs((box1.AxisY* box1.Half_size.Y)*Plane) +
            Math.Abs((box1.AxisZ* box1.Half_size.Z)*Plane) +
            Math.Abs((box2.AxisX* box2.Half_size.X)*Plane) +
            Math.Abs((box2.AxisY* box2.Half_size.Y)*Plane) +
            Math.Abs((box2.AxisZ* box2.Half_size.Z)*Plane)));
    }

    ////// test for separating planes in all 15 axes
    ////////////public static bool GetCollision(OBB  box1,  OBB box2)
    {
        Vec3 RPos;
        RPos = box2.Pos - box1.Pos;

        return !(GetSeparatingPlane(RPos, box1.AxisX, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisY, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisZ, box1, box2) ||
            GetSeparatingPlane(RPos, box2.AxisX, box1, box2) ||
            GetSeparatingPlane(RPos, box2.AxisY, box1, box2) ||
            GetSeparatingPlane(RPos, box2.AxisZ, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisX, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisY, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisZ, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisX, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisY, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisZ, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisX, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisY, box1, box2) ||
            GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisZ, box1, box2));
    }
}

测试

// create two obbs
//两个OBB A和B
OBB A, B;

// set the first obb's properties
A = new OBB();
// set its center position
//定义A的中心点为(0,0,0)
A.Pos = new Vec3(0, 0, 0);

// set the half size
//定义A的1/2边长(10,1,1),即A的边长为(20,2,2)
A.Half_size = new Vec3(10, 1, 1);

// set the axes orientation
//定义A的x,y,z轴方向
A.AxisX = new Vec3(1, 0, 0);
A.AxisY = new Vec3(0, 1, 0);
A.AxisZ = new Vec3(0, 0, 1);

// set the second obb's properties
B = new OBB();
// set its center position
B.Pos = new Vec3(20, 0, 0);

// set the half size
B.Half_size = new Vec3(10, 1, 1);

// set the axes orientation
B.AxisX = new Vec3(1, 0, 0);
B.AxisY = new Vec3(0, 1, 0);
B.AxisZ = new Vec3(0, 0, 1);

// run the code and get the result as a message
if (OBBCollision.GetCollision(A, B))
{
    //碰撞
    Console.WriteLine("Collision!!!");
}
else
{
    //未碰撞
    Console.WriteLine("No collision.");
}
标签

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 第6-8课:分离轴算法(SAT)与碰撞检测(图文篇)
    物体的碰撞检测是游戏软件中的关键算法之一,两个角色是否能够对话、子弹是否击中了物体,以及是否出现人物穿墙的 bug,都依赖于一套可靠的碰撞检测算法。有很多算法可以实现碰撞检测,基于算法几何的方法有轴对称包围盒算法(Axis-aligned Bounding Box,AABB)、方向包围盒算法(Oriented Bounding Box,OBB)、分离轴算法(Separating Axis Theorem,SAT)、GJK 算法(Gilbert–Johnson–Keerthi Distance Algorithm)等。当然,也可以直接计算光栅图像的像素值来精确地判断物体是否发生了碰撞,这一课将介绍基于分离轴理论的分离轴算法。 算法几何基础 提到算法几何,很多读者会想到各种头疼的公式,放心,涉及本课内容的算法几何理论非常少,只需要知道向量的加法和减法(差)、点积、法向量和投影这四个简单的知识即可。 向量的加法和减法 什么是向量?简单地讲,它的数学意义就是既有大小又有方向的量,也被称为矢量,既然有方向,那就有二维向量和三维向量,这里我们只讨论二维向量。平面几何学意义的向量是一个端点有次序的线段,即有向线段(Directed Segment)。假如坐标原点是 $O(0, 0)$,点 $P$ 的坐标是 $(x, y)$,则线段 $OP$ 的向量表示就是 $P= (x,y)$。 假设有两个向量
  • Unity3d碰撞器映射到2D碰撞器_物理引擎性能优化
    前段时间结束了一个3DX鱼项目,有个技术问题悬而未决。(即:如何把3D物理碰撞器映射到屏幕上做2D碰撞器,以简化碰撞的数学计算和解决一些视角偏差带来的碰撞不到BUG。). 本来也不是特别严重的问题,但是优化过路线算法和内存占用后,该问题带来性能影响的就变得比较突出。 最近终于有时间研究一下这个问题。最终方案效果还不错,分享一下我的成果。 原有场景及存在的问题 原有场景为了使2D的子弹能碰到3D场景中的物体,使用了一个极长的3DBoxCollider伸到3D场景中与3D的目标进行碰撞。 原有场景示意图 但是这样处理有两个比较严重的问题, 使用2D界面,直接与透视视角的3D物体进行碰撞,会出现偏差。PS:原有场景中差异没有那么明显。 整个游戏中,实际上只有2D碰撞,使用3D碰撞消耗较大,特别是使用子弹Z轴太长的3DBoxCollider,造成无意义的额外消耗。 虽然之前通过调整场景等其他操作,做了一些效果优化,但是最终效果还是不够理想。所以,重新做了个方案。 前排提醒 该文章会介绍三种方案,实践部分前面会介绍三个方案公用的部分,后面会介绍三个方案的区别。 这些方案理论上适用于游戏场景中的被射击物体是3D的,3D场景有深度的。但是子弹是2D的游戏类型。参考上面的场景示意图。 PS:如果3D物体的空隙较大,或者动画动作较大,也不适合参考这个方案。 核心思路 处理思路如下
  • 广相碰撞检测方法?(Broad-phase collision detection methods?)
    问题 我正在构建2D物理引擎,我想添加广相碰撞检测,尽管我只知道2种或3种类型: 检查其他所有内容(O(n ^ 2)复杂度) 扫除和修剪(分类和扫除) 关于二进制空间分区的一些知识(不确定如何执行此操作) 但是肯定还有更多选择吧? 这些是什么? 并可以提供每个描述的基本描述或指向描述的链接吗? 我已经看到了这一点,但是我想索取可用的算法列表,而不是满足我的需求的最佳算法。 在这种情况下,“宽相碰撞检测”是物理引擎用来确定其模拟中的哪些物体足够接近以值得进一步研究并可能解决碰撞的方法。 回答1 最佳方法取决于特定用途,但最重要的是要细分您的世界空间,以便(a)每个实体都精确地位于一个细分中;(b)每个细分都足够大,以至于某个细分中的一个实体只能与同一细分或相邻细分中的实体发生碰撞,并且(c)特定细分中的实体的数量应尽可能小。 您如何执行此操作取决于您拥有多少个车身,它们如何运动,对性能的要求是什么以及要在引擎上花费多少时间。 如果您正在谈论物体在一个很大的开放空间中移动,最简单的方法是将世界划分为一个网格,其中每个单元格都比最大对象大,并跟踪每个单元格中的对象列表。 如果您要在经典街机游戏的规模上构建某种东西,那么此解决方案可能就足够了。 如果您要处理在更大的开放世界中移动的物体,则简单的网格将很快变得不堪重负,并且您可能想要某种基于树的结构,例如四叉树,正如Arriu所建议的那样。
  • 手机秒变投篮机,还能模拟投篮真实手感,腾讯微视技术「家底」到底有多厚?
    腾讯微视最近又出黑科技,这款新上线的游戏「AR 投篮机」能让你的手机秒变投篮机。操作方法如下:进入腾讯微视 APP,搜索「AR 投篮」。点击 AR 投篮机,就能进入游戏界面。找到一个背景平面,将篮筐调制最佳投篮位置,对准篮筐,向上滑动篮球,投中篮筐即可得分。该游戏对场地适应性很强,即便在暗光环境下,对单一纹理的地板也能定位。虽然是虚拟投篮,但腾讯微视这款游戏的重力和碰撞都是模拟真实世界的物理特性来设计的。在滑动屏幕投球的过程中,用户滑动的速度、距离、角度共同决定了篮球投掷的落地点,最大程度模拟真实世界投掷物体的力度、方向和重力。用户只要投中几次,掌握投球的力度和技巧,后面可凭借肌肉记忆,持续多次命中,分数的加成也会越来越高,投中的视觉,听觉特效反馈也会越加炫酷和强烈。不仅如此,根据篮板的远近,游戏分为普通模式和挑战模式,模拟现实中的两分球和三分球。连续进球分数达到 20 分以后,筐会开始左右移动,最大程度的还原了投篮机的真实游戏体验。游戏虽小,但背后的技术并不简单,腾讯微视有一支专门负责 AR 技术研发的「微视光流实验室」AR 团队,这款 AR 投篮机耗时四个月,可以说是腾讯微视 AR 技术的集大成者。除 AR 投篮机外,腾讯微视也有很多其他炫酷的 AR 应用,比如「纸片人」、3D 人民币等。AR 是近两年才出现在大众面前的「黑科技」,公众对其认知度并不高。并且在不少人的印象中
  • unity常见面试题
    1. 游戏对象 问题:游戏对象消失三种方法的区别?(enabled/Destroy/active) gameObject.renderer.enabled=fasle 是控制一个物体是否在屏幕上渲染或显示 而物体实际还是存在的 只是想当于隐身 而物体本身的碰撞体还依然存在的 GameObject.Destroy() 表示移除物体或物体上的组件 代表销毁该物体 实际上该物体的内存并没有立即释放 而是在你下下个场景中槽释放内存资源,就是你a场景中Destroy了 一般是在c场景中才真正释放该物体的内存资源(这是我的体会 不知道理解错误没) gameObject.active=false 是否在场景中停用该物体 在你gameObject.active =false中 则你在场景中用find找不到该物体 如果该物体有子物体 你要用SetActiveRecursively(false) 来控制是否在场景中停用该物体(递归的) 副作用:通过GameObject.Find方法查找不到 2. 协同程序(Coroutine) 协同程序,即在主程序运行时同时开启另一段逻辑处理,来协同当前程序的执行。换句话说,开启协同程序就是开启一个线程。 原理:协同程序被开启后作为一个线程在运行,而MonoBehaviour也是一个线程,他们成为互不干扰的模块,除非代码中用调用,他们共同作用于同一个对象
  • 3.Open3D教程——点云数据操作
    点云数据 本教程阐述了基本的点云用法。 随需要的文件链接 1. 显示点云 import open3d as o3d import numpy as np print("Load a ply point cloud, print it, and render it") pcd = o3d.io.read_point_cloud("fragment.ply") print(pcd) print(np.asarray(pcd.points)) o3d.visualization.draw_geometries([pcd]) read_point_cloud: 该方法用于读取点云,它会根据扩展名对文件进行解码。所支持的文件类型 draw_geometries: 查看点云,可以通过移动鼠标来从不同的角度点云。 它看起来像一个密集的曲面,但实际上是一个渲染为曲面的点云。GUI支持各种键盘功能。例如,-键减小点(曲面)的大小。 注:按H键为GUI打印出键盘指令的完整列表。有关可视化GUI的更多信息,请参阅可视化和自定义可视化。 2. 体素下采样 体素下采样使用常规体素栅格从输入点云创建均匀下采样点云。它通常用作许多点云处理任务的预处理步骤。该算法分两步操作: 将点固定为体素。每个被占用的体素通过平均内部的所有点来生成正好一个点。 print("Downsample the point cloud
  • git中的哈希冲突(Hash collision in git)
    问题 如果我在使用git时发生哈希冲突,实际上会发生什么? 例如,我设法用相同的sha1校验和提交了两个文件,git是否会注意到它或损坏其中一个文件? 可以改进git来解决这个问题吗,还是我必须更改为新的哈希算法? (请不要通过讨论这种可能性的可能性来避免这个问题-谢谢) 回答1 在10个卫星上拾取原子 SHA-1哈希是一个40进制字符串...每个字符4位乘以40 ... 160位。 现在我们知道10位大约是1000位(确切地说是1024位),这意味着有1 000000000000000000000000000000000000000000000000000000000000000个不同的SHA-1散列... 10 48 。 这相当于什么? 月亮由大约10 47个原子组成。 因此,如果我们有10个卫星...而您在其中一个卫星上随机选择一个原子...然后继续在它们上随机选择一个原子...那么您将两次选择同一个原子的可能性是两个给定的git commit将具有相同的SHA-1哈希的可能性。 对此进行扩展,我们可以提出一个问题... 在开始担心冲突之前,您需要在存储库中进行多少次提交? 这与所谓的“生日攻击”有关,后者又称为“生日悖论”或“生日问题”,它表示当您从给定的集合中随机选择时,您极有可能需要很少的选择采了两次但是“令人惊讶地很少”在这里是一个相对的术语。
  • 如何执行c#碰撞检测?(How to do c# collision detection?)
    问题 c#中是否有任何预定义的方法可以进行碰撞检测? 我是c#的新手,正在尝试获取两个椭圆的碰撞检测功能,是否有任何预定义的方法可以实现碰撞检测? 我已经有绘制椭圆的代码,什么是启动碰撞检测的好方法? private void timer1_Tick(object sender, EventArgs e) { //Remove the previous ellipse from the paint canvas. canvas1.Children.Remove(ellipse); if (--loopCounter == 0) timer.Stop(); //Add the ellipse to the canvas ellipse = CreateAnEllipse(20, 20); canvas1.Children.Add(ellipse); Canvas.SetLeft(ellipse, rand.Next(0, 500)); Canvas.SetTop(ellipse, rand.Next(0, 310)); } // Customize your ellipse in this method public Ellipse CreateAnEllipse(int height, int width) { SolidColorBrush fillBrush = new
  • Java哈希图搜索真的是O(1)吗?(Is a Java hashmap search really O(1)?)
    问题 我已经看到了一些关于Java哈希图及其O(1)查找时间的有趣声明。 有人可以解释为什么会这样吗? 除非这些哈希图与我购买的任何哈希算法有很大不同,否则必须始终存在包含冲突的数据集。 在这种情况下,查找将是O(n)而不是O(1) 。 有人可以解释他们是否为O(1),如果是,他们如何实现这一目标? 回答1 HashMap的一个特殊功能是与平衡树不同,它的行为是概率性的。 在这些情况下,通常以最坏情况事件发生的可能性来讨论复杂性通常是最有帮助的。 对于哈希映射,当然是在映射恰好充满的情况下发生冲突的情况。 碰撞非常容易估计。 p碰撞= n /容量 因此,即使元素数量很少的哈希图也很可能会经历至少一次碰撞。 大O表示法使我们可以做一些更引人注目的事情。 观察任意固定的常数k的情况。 O(n)= O(k * n) 我们可以使用此功能来改善哈希图的性能。 我们可以考虑最多发生两次碰撞的可能性。 p碰撞x 2 =(n /容量) 2 这要低得多。 由于处理一次额外碰撞的成本与Big O性能无关,因此我们找到了一种无需实际更改算法即可提高性能的方法! 我们可以将其概括为 p碰撞xk =(n /容量) k 现在,我们可以忽略任意数量的碰撞,并且最终产生的碰撞比我们所考虑的要少得多。 通过选择正确的k,您可以将概率降低到任意微小的水平,而无需改变算法的实际实现。 我们通过说哈希映射很有可能具有O
  • Unity3D面试题+答案
    第一部分 1. 请简述值类型与引用类型的区别 答:区别: 1. 值类型存储在内存栈中,引用类型数据存储在内存堆中,而内存单元中存放的是堆中存放的地址。 2. 值类型存取快,引用类型存取慢。 3. 值类型表示实际数据,引用类型表示指向存储在内存堆中的数据的指针和引用。 4. 栈的内存是自动释放的,堆内存是 .NET 中会由 GC 来自动释放。 5. 值类型继承自 System.ValueType, 引用类型继承自 System.Object 。 可参考 http://www.cnblogs.com/JimmyZhang/archive/2008/01/31/1059383.html 2. C# 中所有引用类型的基类是什么 答:引用类型的基类是 System.Object 值类型的基类是 System.ValueType 同时,值类型也隐式继承自 System.Object 3. 请简述 ArrayList 和 List 的主要区别 答: ArrayList 存在不安全类型 ‘ ( ArrayList 会把所有插入其中的数据都当做 Object来处理) 装箱拆箱的操作(费时) List 是接口, ArrayList 是一个实现了该接口的类,可以被实例化。 4. 请简述 GC (垃圾回收)产生的原因,并描述如何避免? 答: GC 回收堆上的内存 避免: 1 )减少 new 产生对象的次数
  • 创建APK扩展文件的步骤(Steps to create APK expansion file)
    问题 我已经开发了应用程序并成功工作。 我已经在我的应用程序中使用了“应用程序许可”功能。 现在,我要在Google Play上上传一个应用程序。 请让我知道步骤,如何使用应用程序许可以及如何创建APK扩展文件? 回答1 扩展文件消除了上传超过100MB apk大小的限制。 上载apk时,您应该附加这些文件。 每个应用程序最多可以为每个APK提供4GB(2GB-主存储区,2GB-补丁)附加数据。 创建扩展文件时必须遵循的命名约定 [main|patch].<expansion-version>.<package-name>.obb 笔记: main -如果没有这些文件,则您的应用程序将无法运行 patch -是那些额外的文件,如果没有这些文件,则您的应用程序可以运行 expansion-version -您提供给APK的版本,因此不同版本的扩展文件不会冲突 package-name name-这是您唯一的软件包名称 .obb我们不会附加,它将在上传时由Google隐式附加 假设您在当前目录中拥有所有内容,那么只需选择所有内容并将其命名为main.2.com.xyz.abc.zip ,然后在上传apk时将其附加 这全部是上传部分,现在是下载部分 首先,您需要通过单击SDK-Manager下载Google额外的程序包 现在,从现有来源创建新项目,并从sdk-path / extras
  • JavaScript:碰撞检测(JavaScript: Collision detection)
    问题 冲突检测在JavaScript中如何工作? 我不能使用jQuery或gameQuery-已经使用了原型-因此,我正在寻找非常简单的东西。 我并不是在寻求完整的解决方案,而只是指出正确的方向。 假设有: <div id="ball"></div> and <div id="someobject0"></div> 现在,球正在移动(任何方向)。 “ Someobject”(0-X)已经预先定义,其中有20-60个随机放置,如下所示: #someobject {position: absolute; top: RNDpx; left: RNDpx;} 我可以创建一个位置为“ someobject(X)”的数组,并在“球”移动时测试碰撞。 for(var c=0; c<objposArray.length; c++){ ........ and code to check ball's current position vs all objects one by one.... } 但是我想这将是一个“菜鸟”解决方案,而且看起来很慢。 有更好的吗? 回答1 首先要具备的实际功能是检测球与物体之间是否存在碰撞。 为了性能起见,最好实现一些粗略的碰撞检测技术,例如边界矩形,以及在检测到碰撞的情况下,如果需要的话,更精确的检测技术,这样您的函数将运行得更快一些,但使用精确的相同的循环。
  • 自动驾驶中的行人防撞系统设计
    行人保护技术研究时当前汽车安全技术研究中的重要组成部分,相对于车内驾驶员和乘客来说,行人与车辆的相对位置和运动状态复杂多变,更具有不确定性,为了更好的有效保证行人等弱势交通参与者,随着汽车安全技术研究的不断深入、传感器及计算机技术的发展,对行人防撞系统开展深入研究是主动安全一大趋势所在。前文对自动驾驶中的行人检测方法进行了详细说明,主要聚焦于行人类型的检测上,那么如何根据检测到的行人类别做其距离、速度及方位跟踪是本文需要考虑的问题。如前所述,对于行人检测来说,首先是需要定义行人各个部位特性,然后融合部位特性识别出行人本身,随后我们对各识别出的行人目标划分相应的跟踪窗口,本行人跟踪识别算法则是主要根据划分的窗口,并对窗口内的行人检测出相应的距离、速度以及方位角等,该过程保证较短时间内做数据更新,实际便实现了对行人的跟踪测试。本文将介绍单目视觉系统下的行人距离、速度检测方法,并针对性的介绍基于卡尔曼预测的行人特征信息跟踪方法。行人跟踪方法概述目前常见的行人目标跟踪算法分为四类:基于模型的跟踪、基于区域的跟踪、基于轮廓的跟踪。1)模型的跟踪方式该方法是根据先验知识结合点、线或区域将被跟踪目标逆合成一个几何模型。该模型可以实线性模型、2D模型、3D模型,用参数化进行定义(如用B样条区描述汽车的形状),该方式可以很好的应用于刚体和非刚体的目标跟踪上。该方法由于有先验知识支持
  • python碰撞检测-python飞机大战pygame碰撞检测实现方法分析
    本文实例讲述了python飞机大战pygame碰撞检测实现方法。分享给大家供大家参考,具体如下: 目标 了解碰撞检测方法 碰撞实现 01. 了解碰撞检测方法 pygame 提供了 两个非常方便 的方法可以实现碰撞检测: pygame.sprite.groupcollide() 两个精灵组 中 所有的精灵 的碰撞检测 groupcollide(group1, group2, dokill1, dokill2, collided = None) -> Sprite_dict 如果将 dokill 设置为 True,则 发生碰撞的精灵将被自动移除 collided 参数是用于 计算碰撞的回调函数 如果没有指定,则每个精灵必须有一个 rect 属性 pygame.sprite.spritecollide() 判断 某个精灵 和 指定精灵组 中的精灵的碰撞 spritecollide(sprite, group, dokill, collided = None) -> Sprite_list 如果将 dokill 设置为 True,则 指定精灵组 中 发生碰撞的精灵将被自动移除 collided 参数是用于 计算碰撞的回调函数 如果没有指定,则每个精灵必须有一个 rect 属性 返回 精灵组 中跟 精灵 发生碰撞的 精灵列表 02. 碰撞实现 def __check_collide(self
  • 简单的哈希函数(Simple hash functions)
    问题 我正在尝试编写一个使用哈希表存储不同单词的C程序,我可以使用一些帮助。 首先,我创建一个哈希表,其哈希数的大小最接近要存储的单词数,然后使用哈希函数为每个单词查找地址。 我从最简单的功能开始,将字母加在一起,结果碰撞率为88%。 然后,我开始对该函数进行实验,发现无论将其更改为什么,碰撞都不会低于35%。 现在我正在使用 unsigned int stringToHash(char *word, unsigned int hashTableSize){ unsigned int counter, hashAddress =0; for (counter =0; word[counter]!='\0'; counter++){ hashAddress = hashAddress*word[counter] + word[counter] + counter; } return (hashAddress%hashTableSize); } 这只是我想出的一个随机函数,但是它给了我最好的结果-大约35%的碰撞。 在过去的几个小时里,我一直在阅读有关散列函数的文章,我尝试使用一些简单的函数,例如djb2,但是所有这些都给我带来了更糟糕的结果。(djb2导致了37%的冲突,这是'更糟,但我期望有更好的结果而不是更糟)我也不知道如何使用其他一些更复杂的参数,例如murmur2
  • 数组去重(JavaScript 为例)
    数组去重,就是在数组中查找相同的元素,保留其中一个,去除其他元素的程。 从这句话揭示了数组去重的两个关键因素: 找到重复项 去除重复项 本文告诉你在遇到去重问题时该如何思考,并以 JavaScript 为例,进行详细解释。使用 JavaScript 示例主要是因为它环境比较好找,而且直接对象 (Plain Object) 用起来很方便。 JavaScript 的环境:Node.js 或者浏览器的开发者控制台。 找到重复项 找到重复项最关键的算法是判定元素是否相同。判定相同,说起来似乎很简单 —— 用比较运算符就好了嘛!真的这么简单吗? 用 JavaScript 来举个例: const a = { v: 10 }; const b = { v: 10 }; 肉眼观察,这里的 a 和 b 相同吧?但是 JavaScript 不这么认为: console.log(a == b); // false console.log(a === b); // false 肉眼观察和程序比较使用了不同的判断方法。肉眼观察很直接的采用了字符串比对的方法,而程序压根没管是不是数据相同,只是直接判断它们是不是同一个对象的引用。我们一般会更倾向于使用符合人眼直观判断的方法,所以可能会想到使用 JSON.stringify() 把对象变成字符串来判断: console.log(JSON.stringify(a)
  • Unity中的物理系统
    文章目录 1.概述 Rigidbody 和 Collider1.1刚体 Rigidbody1.2碰撞体 Colliders1.2.1Collider1.2.2碰撞体分类1.2.3碰撞体与触发器 1.3关节 Joints1.4 角色控制器 CharacterController 2. 刚体2.1 组件属性2.2 父子关系2.3 脚本2.4 动画2.5 刚体和碰撞体2.6 连续碰撞见2.7 比例和单位2.8 其它问题和建议 3.碰撞体3.1 BoxCollider3.2 CapsuleCollider3.3 MeshCollider3.4 SphereCollider3.5 TerrainCollider3.6 物理材质 4.关节 Joints4.1 固定关节 FixedJoint4.2 铰链关节 HingeJoint4.3 弹簧关节 SpingJoint4.4 角色关节 CharacterJoint4.5 ConfigurableJoint 5. 角色控制器 CharacterController5.1 参数设置建议5.2 角色卡住了?5.3 技巧 6. ConstantForce 常量力组件7. WheelCollider 轮子组件7.1 组件说明7.2 工作原理7.3 WheelCollider 的设置7.4 碰撞体问题7.5 车轮阻尼曲线7.6 实践技巧 8. Cloth
  • 圆碰撞检测HTML5画布(Circle Collision Detection HTML5 Canvas)
    问题 我想检查圈子是否相互冲突。 我知道我可以通过获取圆的两个中心之间的距离并从该距离中减去每个圆的半径并查看“距离”是否大于1来做到这一点。 我怎样才能有效地做到这一点(比如说1000个圈子)? 也许我能以某种方式获得最近的20个圆或类似的数字并进行检查? 我也不知道我将如何开始有效地做到这一点。 有任何想法吗? 这是一个例子: http://experiments.lionel.me/blocs/ 回答1 在开始计算距离的精确差异之前,您至少可以比较中心与半径的x / y位置。 该信息可以在圈子中隐式获得,并且只需要一些简单的比较和加/减。 这样一来,您就可以比较所有圆对之间以x / y为单位的简单距离,并丢弃那些显然不是碰撞候选对象的距离,例如 abs(x2 - x1) > (r2 + r1) abs(y2 - y1) > (r2 + r1) ...如果圆心之间的X或Y距离大于半径之和,则它们不能碰撞。 一旦减小了可能的对撞机,然后您就可以进行正式的笛卡尔距离,这就是“繁重”的乘法/除法运算的来源。 回答2 考虑将圆心的坐标存储在一个四叉树中,那么您只需要检查该圆是否与该象限或相邻象限中的其他圆相交。 一个警告是,您需要确保四叉树的叶节点的最小直径是最大圆的半径,否则,您需要检查的不只是相邻节点的交集。 http://en.wikipedia.org/wiki
  • hashmap中的key是有序的么_浅谈HashMap中的hash算法
    原创-转载请注明出处 HashMap是我们常见的一种数据结构,实现Map接口,用来存储键值对,允许null键/值、非同步、不保证有序(比如插入的顺序)。那HashMap中最核心的部分就是哈希函数,又称散列函数。也就是说,哈希函数是通过把key的hash值映射到数组中的一个位置来进行访问。比如: 存在一组哈希值 10,13,7,5,4,20 存在一个长度为10的数组 arrays 定义一个hash函数 int index = h % arrays.length; 10 % 10 = 0 那么 哈希值为10的对象放在数组索引为0的位置上; 13 % 10 = 3 那么 哈希值为13的对象放在数组索引为3的位置上; ...... 20 % 10 = 0 那么 哈希值为13的对象放在数组索引为0的位置上; 这时候大家看出了一个问题,哈希值为10的对象和哈希值为20的对象,放在了一个索引上。发生了碰撞,那么怎么解决这样碰撞呢,有很多种方式,这里不展开叙述。HashMap中维护了一个链表组成的数组。如果冲突的话就添加到链表中,下面来看下hashmap中的hash算法,以Java8源码为例。 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
  • 从APK扩展文件(从obb文件)读取内容(Read content from APK expansion file (from obb file))
    问题 我已经实现了APK扩展文件下载服务,所有服务均来自http://developer.android.com/google/play/expansion-files.html 我可以下载APK扩展文件,并可以使用以下代码查看该文件 try { ZipResourceFile expansionFile = APKExpansionSupport .getAPKExpansionZipFile(this, 3, 0); ZipEntryRO[] zip = expansionFile.getAllEntries(); Log.e("", "" + zip[0].mFile.getAbsolutePath()); Log.e("", "" + zip[0].mFileName); Log.e("", "" + zip[0].mZipFileName); Log.e("", "" + zip[0].mCompressedLength); AssetFileDescriptor fd = expansionFile .getAssetFileDescriptor(zip[0].mFileName); if (fd != null && fd.getFileDescriptor() != null) { MediaPlayer mp = new MediaPlayer(); mp