Have you considered implementing a BSP tree? Even if you make mistakes with the code you are using now, it will be slow with a dog with a grid of any decent size / complexity. BSP or quadtree will greatly improve your code and improve performance, and they are very easy to implement.
Edit
Here is a link to a good BSP tutorial and review.
If you are only interested in terrain (there are no vertical walls, doors, etc.), a square may be more appropriate:
Here is a good four on tutorial on gamedev.net.
Both of these algorithms are designed to split geometry into a tree to simplify the search. In your case, you are looking for polygons for collision purposes. To build a BSP tree (very briefly):
Define the structure of nodes in the tree:
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 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 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; } }
Select the “section” plane (face) from your grid, which roughly divides the rest of the grid into two parts. This is much easier to do with complex geometry, since fully convex elements (spheres, etc.) tend to look like lists instead of trees.
Create a new BspNode instance from the vertices that define the split plane.
- Sort the remaining faces into two lists - one that is in front of the split plane, and one that contains those faces that are behind.
- Go to step 2 until more nodes appear in the list.
When checking for collisions, you have two options.
Single point: check the coordinates that the symbol or object moves against the tree, calling your root node .IsInFront(moveDestination) If the method returns false, the target point is "inside" the grid, and you are faced. If the method returns true, the target point is “off” the grid, and no collision has occurred.
The intersection of the rays. This is a bit complicated. Call the root method node .SplitsRay() with the current position of the object and its target position. If the methods return true , the movement between the two positions will go through the grid. This is an excellent (albeit more complicated) test, because it will capture extreme cases, for example, when the desired movement will completely move the object through the object in one step.
I just quickly threw away this sample code; it is incomplete and probably will not even compile, but it should make you move in the right direction.
Another nice thing about BSP: using the .SplitsRay() method, you can determine if one point is visible on the map from another point. Some games use this to determine if NPC / AI can see each other or real players. You can use a slight modification of this to determine if they can hear each other, etc.
This may seem a lot more complicated than your original approach, but ultimately it is much more powerful and flexible. It is worth your time to explore.