Posted in Hidden Asset Programming

Line-of-sight with subtiles

May 21st, 2012 - 10:38 pm

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:

Full tiles

Guard's (green) line-of-sight to the player (blue) is blocked by a wall (red)

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:


Using subtiles, the guard's line-of-sight isn't blocked by the wall

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.



May 22nd, 2012 10:38 pm

Yay Updates! Looks like you found a great solution to line-of-sight.


May 22nd, 2012 10:38 pm

Don’t forget about “quasi-3D/2.5D”… :>

Small/short walls, obstacles, desks, hedges, fences, some cars (small ones or with windows) will not cover standing character (like mentioned window in a wall)… but will allow to hide for crouching or crawling characters. Let’s assume that hight of a character is:
A) standing – 4/4,
B) crouching – 2/4,
C) crawling – 1/4.

Situation/places for 2D:
1) some “obstacle” lower than 4/4 – A is visible, B and C are hide,
2) some “obstacle” lower than 3/4 – A is visible, B and C are hide,
3) some “obstacle” lower than 2/4 – A and B are visible, C is hide,
4) open range (“lower than 1/4”) – in all three cases player’s character (PC) is visible.

Of course, in your case it could be easier to divide it by 10: 10/10, 5/10 and 2/10.

So it’s somehow 3D and you’ll need some kind of “vertical net/grid” for 3rd dimension when NPCs and PC aren’t on the same level while PC is hiding after some obstacle. Let’s consider some situations:
1) NPC and PC on the same level – easy situation, no need for “vertical angles”,
2) NPC is one level higher/lower than PC – in this situation NPC can see more (when higher) or less (when lower); e.g. for obstacle 5/10 sight of “vertical view” could be 7/10 when NPC is higher or 3/10 when is lower,
3) and it should depend on range from mentioned obstacle – NPC close to a window could be able to see crouching PC on the other side (with the same lights).

Don’t forget about shadows – where are light there are shadows. In some situation shadow could give PC’s location away or at least makes NPC suspicious.

Oh boy! You have a lot of work to do with “Hostile Takeover” engine. Maybe some pleasant vacation with “ASCII Sector” improvements…? ;-)

Leave Comment

You must be logged in to post a comment.