Рассматривали ли вы реализацию дерева BSP? Даже если вы исправите ошибки с помощью кода, который вы используете сейчас, это будет очень медленно с мешом любого приличного размера / сложности. BSP или quadtree будут иметь большое значение для упрощения вашего кода и повышения производительности, и их очень легко реализовать.
Редактировать
Вот ссылка на хороший учебник и обзор BSP.
Если вас интересует только местность (без вертикальных стен, дверей и т. Д.), Вам может подойти квадри:
Вот хороший учебник для quadtree на gamedev.net.
Оба эти алгоритма предназначены для разделения вашей геометрии на дерево, чтобы упростить поиск. В вашем случае вы ищете полигоны для столкновения. Чтобы построить дерево BSP (очень кратко):
Определение структуры для узлов в дереве:
public class BspNode
{
public List<Vector3> Vertices { get; set; }
// plane equation coefficients
float A, B, C, D;
BspNode front;
BspNode back;
public BspNode(Vector3 v1, Vector3 v2, Vector3 v3)
{
Vertices = new List<Vector3>();
Vertices.AddRange(new[] { v1, v2, v3 });
GeneratePlaneEquationCoefficients();
}
void GeneratePlaneEquationCoefficients()
{
// derive the plane equation coefficients A,B,C,D from the input vertex list.
}
bool IsInFront(Vector3 point)
{
bool pointIsInFront=true;
// substitute point.x/y/z into the plane equation and compare the result to D
// to determine if the point is in front of or behind the partition plane.
if (pointIsInFront && front!=null)
{
// POINT is in front of this node's plane, so check it against the front list.
pointIsInFront = front.IsInFront(point);
}
else if (!pointIsInFront && back != null)
{
// POINT is behind this plane, so check it against the back list.
pointIsInFront = back.IsInFront(point);
}
/// either POINT is in front and there are no front children,
/// or POINT is in back and there are no back children.
/// Either way, recursion terminates here.
return pointIsInFront;
}
/// <summary>
/// determines if the line segment defined by v1 and v2 intersects any geometry in the tree.
/// </summary>
/// <param name="v1">vertex that defines the start of the ray</param>
/// <param name="v2">vertex that defines the end of the ray</param>
/// <returns>true if the ray collides with the mesh</returns>
bool SplitsRay(Vector3 v1, Vector3 v2)
{
var v1IsInFront = IsInFront(v1);
var v2IsInFront = IsInFront(v2);
var result = v1IsInFront!=v2IsInFront;
if (!result)
{
/// both vertices are on the same side of the plane,
/// so this node doesn't split anything. Check it's children.
if (v1IsInFront && front != null)
result = front.SplitsRay(v1, v2);
else if (!v1IsInFront && back != null)
result = back.SplitsRay(v1, v2);
}
else
{
/// this plane splits the ray, but the intersection point may not be within the face boundaries.
/// 1. calculate the intersection of the plane and the ray : intersection
/// 2. create two new line segments: v1->intersection and intersection->v2
/// 3. Recursively check those two segments against the rest of the tree.
var intersection = new Vector3();
/// insert code to magically calculate the intersection here.
var frontSegmentSplits = false;
var backSegmentSplits = false;
if (front!=null)
{
if (v1IsInFront) frontSegmentSplits=front.SplitsRay(v1,intersection);
else if (v2IsInFront) frontSegmentSplits=front.SplitsRay(v2,intersection);
}
if (back!=null)
{
if (!v1IsInFront) backSegmentSplits=back.SplitsRay(v1,intersection);
else if (!v2IsInFront) backSegmentSplits=back.SplitsRay(v2,intersection);
}
result = frontSegmentSplits || backSegmentSplits;
}
return result;
}
}
Выберите плоскость (грань) раздела вашей сетки, которая примерно делит остальную часть сетки на две части. Это намного проще сделать со сложной геометрией, так как полностью выпуклые элементы (сферы и т. П.), Как правило, выглядят как списки, а не как деревья.
Создайте новый экземпляр BspNode из вершин, определяющих плоскость разбиения.
- Сортировка оставшихся граней в два списка - один, находящийся перед плоскостью разбиения, и один, содержащий те грани, которые находятся позади.
- Переходите к шагу 2, пока в списке не останется больше узлов.
При проверке столкновений у вас есть два варианта.
Одна точка: проверьте координаты, по которым персонаж или объект перемещается относительно дерева, вызывая .IsInFront(moveDestination) вашего корневого узла. Если метод возвращает false, целевая точка находится «внутри» сетки, и вы столкнулся. Если метод возвращает true, целевая точка находится «вне» меша, и столкновения не произошло.
Пересечение лучей. Этот становится немного сложнее. Вызовите метод .SplitsRay() корневого узла с текущей позицией объекта и его целевой позицией. Если метод возвращает true, перемещение между двумя позициями будет переходить через сетку. Это превосходная (хотя и более сложная) проверка, так как она позволяет отследить крайние случаи, например, когда желаемое движение полностью проведет объект через объект за один шаг.
Я просто быстро скомбинировал этот пример кода; он неполон и, вероятно, даже не будет компилироваться, но он должен направить вас в правильном направлении.
Еще одна приятная вещь о BSP: используя метод .SplitsRay(), вы можете определить, видна ли одна точка на карте из другой точки. Некоторые игры используют это, чтобы определить, могут ли NPC / AI видеть друг друга или реальных игроков. Вы можете использовать небольшую модификацию этого, чтобы определить, могут ли они слышать друг друга при ходьбе и т.д.
Это может показаться намного сложнее, чем ваш первоначальный подход, но в конечном итоге он гораздо более мощный и гибкий. Это стоит вашего времени для расследования.