Line-of-sight with subtiles
I was considering just writing an “I’m still alive” blog post to let everyone know that I’m, well, still alive and still very much working on Hostile Takeover. But that’s a pretty short and boring topic, so here’s a completely different blog post instead…
I’ve been working on the AI for Hostile Takeover. I like having a clear goal with the stuff I’m doing, so right now I’m putting the final touches on having a guard patrolling an area (by passing through designated waypoints) and being able to spot and attack you. To determine whether or not the guard can see the player, three factors have to be taken into account: field of view, distance and line-of-sight.
Field of view is simple to implement. You just calculate the angle from the guard to the player and check if it’s within the guard’s field of view (95° to either side). And distance is applied by having the chance of the guard spotting you decrease as the distance increases. But line-of-sight can be a bit more difficult to implement – especially for a 2D game. With a 3D game, you’ve already got the geometry set up in the game world, so you can “just” send of a ray from the guard to the player and check if it intersects with any world geometry. But the geometry of my 2D isometric world is a bit more abstracted.
Walls don’t automatically have volume, for example. Everything plays out on a flat map with just two dimensions, X and Y. There’s no height. No Z-axis. So when a character stops in front of a wall, it’s not because that character’s hitbox was intersecting with the wall’s geometry, as would probably be the case in a 3D game. Instead, the 2D map tells the character that he can’t move from tile A to tile B because there’s a wall in between.
At first, I tried doing line-of-sight by drawing a Bresenham line from the guard to the player with each point on the line being a whole tile. If this line didn’t intersect any walls, there was line-of-sight. The problem with this solution was that it wasn’t very precise. Characters are often moving between tiles and are sometimes only partially obscured by a wall, and using an entire tile as a point on the Bresenham line was too low resolution:
So the solution was quite simply to increase the resolution by dividing each tile into subtiles and occupying these subtiles with whatever could break line-of-sight. I decided that a 10x resolution would be sufficient (primarily because characters have 10 frames of animation when moving from one tile to another, so they can occupy 10 different spots in between tiles, which can be represented by dividing each tile into 10×10 tiles). I’m now just drawing the Bresenham line by using these subtiles as points on the line. Whenever a subtile is plotted, the game checks whether or not this subtile is empty or not. If not, line-of-sight has been broken:
I don’t have to create subtiles for the entire map, just the single tile that the Bresenham line is currently passing through, so it’s neither memory nor processor intensive. To occupy the subtiles, I have a procedure that starts off by setting all 10×10 subtiles as empty, then checking for character, walls and other world objects on that tile. If any are there, the relevant subtiles are filled in.
I believe good ol’ X-COM did something similar, but also had a Z-axis for individual tiles, so it in essence had subcubes that the ray was passing through. This, for example, allowed a bullet to pass through an open window. I’m considering expanding my own system to that as well, since I’ll most likely be adding functionality for shooting at characters on different levels of the map. But I’ll wait and see if it actually ends up being necessary.