# Advanced target visibility working

**Posted:**March 13, 2011

**Filed under:**GuiltySpark, Halo, Programming, School Leave a comment

GuiltySpark now extracts the map’s BSP and performs ray casting for better detection of target visibility. In fact, it can determine if the line between any two arbitrary points is obstructed by any part of the level (minus the scenery at this point). How I did this is simple in concept: imagine the map as a number line from 1 to 10 instead of a 3D space. Suppose the two points I want to check are 2 and 5. The BSP works by recursively subdividing the space into two halves. In one half we have the set {1, 2, 3, 4, 5}, and in the other we have {6, 7, 8, 9, 10}. Both points are in the first set, so half of the entire map can now be ignored. The next subdivision gives the sets {1, 2, 3} and {4, 5}. The points, 2 and 5, would now lie in different sets and so we stop here. This means that both {1, 2, 3} and {4, 5} may contain a number between 2 and 5 that intersects their ray. As you can see, we can’t *only* consider the first set because we would miss 4, and likewise for 3 if we only considered the second set. We next consider all the smallest subdivisions of these two groups: {1}, {2}, {3}, {4}, {5}. These are called the leaves and they represent surfaces. Their surface may be located somewhere between 2 and 5, but that doesn’t mean they intersect the ray. Thus each leaf in the range {2} to {5} is checked for ray intersection.

Last night was a total code-a-thon and I ended up writing all the ray-BSP intersection code. I didn’t get a chance to test it last night due to a couple bugs, which I have resolved just this~~ morning ~~11:50 (morning for me). One bug was forgetting to check if the BSP node child indices are -1. I was already checking if they had their 0x80000000 bit set, which indicates that they are a leaf containing BSP2D references and not another BSP3D node, but an index of -1 says that there is no node at all on that side of the plane. I think this is due to the way Halo creates its BSPs. When building a BSP, it’s difficult to know where to place planes to divide the level properly. I think that the developers chose arbitrary polygons and used the planes they lie on. If this polygon defines the exterior of the geometry at a concave part of the level then there’s a chance the plane won’t intersect any other part of the map and so one side just faces outside the map. In reality, this happens rarely meaning Bungie chose a good heuristic. The next bug was not handling flagged plane indices in surfaces, causing an out of bounds error when accessing my planes array. I’m not sure what a flagged plane index means, but flipping the flag bit seems to have no negative effect.

In any case, the number of flagged planes is probably so low that any problems caused by it would only rarely affect GuiltySpark’s ability to determine if the target is visible or not. Worst case scenario: it shoots at a few walls accidentally. This new method is still a vast improvement over the old target visibility detection. The BSP is extracted in the blink of an eye, so GuiltySpark can do it during gameplay without any hiccups. I thought I would have to read Halo’s memory in large chunks to extract it quickly, but it turns out that wasn’t necessary. GuiltySpark extracts the BSP only once when the target visibility data source is initially requested by the AI, at which point it’s stored internally until you restart the AI. The actual calculations for the ray intersection are fast too. I found plenty of opportunities to prune my options and limit the amount of calculation required.

To calculate if the ray intersects a polygon, I find the point of intersection between the ray and the polygon’s plane. I then project the polygon and the intersection point into 2D space based on the dominant component of the plane’s normal (ensures best topology). The Jordan curve theorem is used next; if an arbitrary ray from the intersection point crosses an even number of the polygon’s edges, the intersection point lies outside the polygon.

So what does this mean for users of GuiltySpark? The bot now knows if a target is visible despite distance and how much the aimbot is leading them. You could also turn off the aimbot when the target is not visible, so no more locking on through walls. All-in-all, this new addition makes for a more believable and human-like bot. With a half-decent AI script, nobody will be able to tell they are playing against a program.

# BSP extraction

**Posted:**March 12, 2011

**Filed under:**GuiltySpark, Halo, Programming, School Leave a comment

Over the past while I’ve made a lot of progress reversing Halo’s BSP. Now that I can extract the information, I just need to write the algorithms to work with it. As I’ve mentioned previously, one goal is determining target visibility by checking if any polygon in the BSP intersects the ray between your player and the target. To do this, I’ll find the smallest possible node of the BSP that contains but does not divide the two points. Every leaf under this node will contain potential ray-intersecting polygons.

Here’s what I learned about Halo’s BSPs: