Website/Blog about the things you need to know to make a modern RTS game
Flow Fields: Line of Sight
30 Jan 2014
Our current Flow Fields implementation is pretty good, but when the units are near to the destination, they will exhibit behaviour that looks wrong to the player. “Why isn’t he just moving straight to where I clicked!? They can walk right there!!! Stupid Robots!”
Luckily, this isn’t too hard to solve, at least a little bit :)
Note: The implementation I will describe here differs from the one in Game AI Pro. This one is much simpler (and probably quicker), but lower quality.
So how can we determine if a grid cell has Line of Sight to the destination cell? There are a few simple rules we can use:
- If you are the destination cell, you have Line of Site
- If you are a direct straight line neighbour of the destination cell, you have Line of Site
We can then expand these out a bit further
If you are a straight line from the destination and the next cell closer to the destination has Line of Site, so do we
This is the rule we will abuse a bit. We need to handle the non straight vertical or horizontal to the destination case. For this we will look at the axis that we are the furtherest from the destination on, so if we are 2 across from the exit and 1 up, we will look at our neighbour in that direction, if they have LOS and the diagonal towards the exit has LOS, we do to.
If the grid cell in the most influential direction towards the destination has LOS and the diagonal towards the destination has LOS, so do we
We also need to have a special case, if we are an exact diagonal to the exit, we only have LOS if all of the grid cells in the direction of the destination have LOS (so the diagonal, the one horizontally closer and the one vertically closer)
With these rules we can easily work out if any grid cell has Line of Site to the destination. As we can only calculate if a grid cell has LOS if we already know whether its neighbours that are closer to the exit have LOS we need to calculate it moving out from the destination cell, so we can just plug this in to our existing dijkstra fill!
We have a new field, losGrid a 2D array of booleans. false: No/unknown LOS, true: has LOS. All fields are initially set to false. Upon visiting each
So our dijkstra fill now looks as follows, new lines have a +
The important part is the implementation of calculateLos, which is just implemented using the rules above.
This gives us the following result, cells with Line of Site are highlighted in yellow