标签: collision-detection

我正在构建一个2D物理引擎,我想添加宽相碰撞检测,但我只知道2或3种类型:

• 检查所有内容(O(n ^ 2)复杂度)
• 扫描和修剪(排序和扫描)
• 关于二进制空间分区的一些事情(不知道如何做到这一点)

但肯定还有更多选择吗？这些是什么？并且可以提供每个的基本描述或链接到描述吗？

我已经看到了这个,但我要求提供一系列可用的算法,而不是最符合我需求的算法.

在这种情况下,"广泛相位碰撞检测"是物理引擎用来确定模拟中哪些物体足够接近以保证进一步调查和可能的碰撞解决的方法.

我一直用c ++和java编写我的生活,但在C#上,我觉得这是一个完全不同的动物.

如果在c#中的Dictionary容器中发生哈希冲突,它会做什么？或者它甚至检测到碰撞？

在SDL中类似容器中发生冲突的情况下,有些会使键值部分将数据链接到键值部分,如链表,或者有些人会尝试找到不同的哈希方法.

[2010年6月4日上午10:56更新]

我试图为每个用户制作一个计数器.并且设置用户#没有定义,它可以增加或减少.我期待数据的大小超过1000.

所以,我想:

• 快速访问最好不要O(n),重要的是由于要求我接近O(1),我需要确保我能够强制注销人员才能执行愚蠢的事情.
• 动态增长和缩小.
• 独特的数据.

Hashmap是我的解决方案,似乎Dictionary与c#中的hashmap相似...

我一直在阅读有关stackoverflow和其他网站上的游戏中的碰撞检测.他们中的很多人都谈论BSP,边界线,整合等等.然而,在NES上,他们设法在游戏中进行地板和墙壁碰撞检测,我发现很难相信他们做了很多计算来检测墙壁碰撞.

我想我的问题是,考虑到仅由瓷砖组成的水平,它们是如何检测像Mario和Megaman这样几乎没有处理能力的游戏中与墙壁和地板的碰撞？

• 他们是否遵循运动路径并确定最接近的连接瓦片？(有点搜索)(先验)
• 他们是否确定了与地板的碰撞,然后找出调整角色的最佳方法？(后验)这对于可变的时间步长是有风险的,如果你足够快,你可以跳过一个瓦片.虽然我认为NES游戏的时间步长与电视的刷新率同步.
• 当你在地上时,重力总会影响你的角色吗？或者,当你决定在瓷砖上行走时,你会"关掉它"吗？当你走出悬崖边缘时呢？你需要某种方法来确定你下面的瓷砖.
• 如果你与瓷砖相撞,你会找到该瓷砖的边缘并将角色移动到它的侧面(取决于行进方向)吗？
• 怎么样的超级地铁和马里奥的倾斜瓷砖？
• 那么你可以跳过底部并降落在顶部的"平台"怎么样？如果你正在做'后验',你将如何处理与这些瓷砖的碰撞？

我写了一些基本上是'先验'的碰撞代码,因为它会搜索你将在某个方向上击中的第一个图块.我只是想知道是否有更好的方法.(可能只是使用事后碰撞检测)

例如,检查瓷砖碰撞向下移动的代码(我检查垂直然后水平移动):

  def tile_search_down(self, char, level):
        y_off = char.vert_speed
        assert y_off > 0

        # t_ are tile coordintes
        # must be int.. since we're adding to it.
        t_upper_edge_y = int( math.ceil((char.y+char.h) / self.tile_height ) ) #lowest edge
        while (t_upper_edge_y*self.tile_height) < (char.y+char.h+y_off): # lowest edge + offset

            t_upper_edge_x = int( math.floor(char.x/self.tile_width) )
            while (t_upper_edge_x*self.tile_width) < (char.x+char.w):

                t_x = t_upper_edge_x
                t_y = t_upper_edge_y 
                if self.is_tile_top_solid(t_x, t_y, plane):
                    char.y = t_y*self.tile_height - char.h
                    char.vert_speed = …

好吧,我正在尝试编写一个程序,可以告诉我旋转到140度的30x100矩形中的任何点是否在旋转到200度的另一个30x100矩形内.

老实说,我甚至不知道从哪里开始.我想在进行正常计算之前重新旋转它们,但是它们仍然无法匹配.

我怎样才能做到这一点？

我已经获得了图形模块的分配,其中一部分是计算一组任意形状的最小边界椭圆.椭圆不必是轴对齐的.

这是在使用AWT形状的java(euch)中工作,因此我可以使用所有工具形状来检查对象的包含/交集.

我正在制作一个基于HTML5画布六边形网格的系统,我需要能够检测单击画布时单击网格中的六边形拼贴.

几个小时的搜索和尝试我自己的方法没有任何结果,从其他语言移植实现只是让我困惑到我的大脑迟钝的点.

网格由平顶正六边形组成,如下图所示:

基本上,给定一个点和此图像中指定的变量作为网格中每个六边形的大小(R,W,S,H):

我需要能够确定一个点是否在给定的六边形内.

一个示例函数调用将是pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY)hexX和hexY是六边形图块边界框左上角的坐标(如上图中的左上角).

是否有人知道如何做到这一点？目前速度并不是很重要.

Github Repository(Scripts文件夹,包含.cs文件中的所有代码)

我在团结中有这个奇怪的碰撞错误,这里是它的一个gif:

重新创建:例如,在gif中,我按两个Left arrow并Up arrow直到速度正常化,然后我得到一些为什么卡在一个块中.

当我在XNA中进行游戏时,我之前已经使用了自己的碰撞算法,希望在Unity中不会发生这种情况.

这是播放器脚本PlayerMovement:

using UnityEngine;
using UnityEngine.UI;

namespace Assets.Scripts
{
    public enum Directions
    {
        Back,
        Left,
        Front,
        Right,
        Idle = -1
    }

    public class PlayerMovement : MonoBehaviour
    {
        #region Public Members

        /// <summary>
        /// Maximum speed of the player (Accelerated to over a period of time)
        /// </summary>
        public float speed;

        /// <summary>
        /// Debug UI.Text element
        /// </summary>
        public Text debugText;

        #endregion

        #region Constants

        /// <summary>
        /// Constant …

当我第一次加载对象时,我使用max和min(x,y,z)点计算初始AABB.但这是在物体空间中,物体在世界各地移动,更重要的是旋转.

每次翻译/旋转对象时,如何重新计算新的AABB？基本上每一帧都会发生这种情况,每帧重新计算新的AABB会是一次非常密集的操作吗？如果是这样,那会有什么选择呢？

我知道AABB会使我的碰撞检测不太准确,但实现碰撞检测代码比OBB更容易,我想一次采取这一步骤.

从以下答案中获得一些见解后,这是我当前的代码:

typedef struct sAxisAlignedBoundingBox {
    Vector3D bounds[8];
    Vector3D max, min;
} AxisAlignedBoundingBox;

void drawAxisAlignedBoundingBox(AxisAlignedBoundingBox box) {
    glPushAttrib(GL_LIGHTING_BIT | GL_POLYGON_BIT);

    glEnable(GL_COLOR_MATERIAL);
    glDisable(GL_LIGHTING);

    glColor3f(1.0f, 1.0f, 0.0f);

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, box.bounds[3].y, box.bounds[3].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, …

我正在尝试进行一些碰撞检测.对于这个测试,我使用简单的矩形Shape,并检查它们Bound,以确定它们是否发生碰撞.虽然检测不能按预期工作.我尝试过使用不同的方法移动对象(relocate,setLayoutX,Y)以及不同的绑定检查(boundsInLocal,boundsInParrent等),但我仍然无法使其工作.如您所见,检测仅适用于一个对象,即使您有三个对象,也只有一个检测到碰撞.这是一些演示问题的工作代码:

import javafx.application.Application;
import javafx.event.EventHandler;
import javafx.scene.Cursor;
import javafx.scene.Group;
import javafx.scene.Scene;
import javafx.scene.input.MouseEvent;
import javafx.scene.paint.Color;
import javafx.scene.shape.Rectangle;
import javafx.stage.Stage;

import java.util.ArrayList;


public class CollisionTester extends Application {


    private ArrayList<Rectangle> rectangleArrayList;

    public static void main(String[] args) {
        launch(args);
    }

    public void start(Stage primaryStage) {
        primaryStage.setTitle("The test");
        Group root = new Group();
        Scene scene = new Scene(root, 400, 400);

        rectangleArrayList = new ArrayList<Rectangle>();
        rectangleArrayList.add(new Rectangle(30.0, 30.0, Color.GREEN));
        rectangleArrayList.add(new Rectangle(30.0, 30.0, Color.RED));
        rectangleArrayList.add(new Rectangle(30.0, 30.0, Color.CYAN));
        for(Rectangle block : …

考虑3D中的两个几何对象:

• 与轴对齐并由其中心位置及其范围(边长)定义的立方体
• 一个不与轴对齐并由其顶点位置定义的圆锥,其底边中心的位置,以及顶点的半角

这是一个用C++定义这些对象的小代码:

// Preprocessor
#include <iostream>
#include <cmath>
#include <array>

// 3D cube from the position of its center and the side extent
class cube
{ 
    public:
        cube(const std::array<double, 3>& pos, const double ext)
        : _position(pos), _extent(ext) 
        {;}
        double center(const unsigned int idim) 
            {return _position[idim];}
        double min(const unsigned int idim)
            {return _position[idim]-_extent/2;}
        double max(const unsigned int idim)
            {return _position[idim]+_extent/2;}
        double extent()
            {return _extent;}
        double volume()
            {return std::pow(_extent, 3);}
    protected:
        std::array<double, 3> _position;
        double _extent;
};

// 3d cone …