# How should I store/access data for a cover system?

I’m working on a cover system to go with a pathfinding algorithm, and I’ve settled on using a lookup table. I’m considering using a Dictionary, with positions stored as the keys, but it’s the values that are stumping me.

I’m using a 2D array of nodes to hold navigation data, where each node holds a list of the 8 immediate neighbours. My plan is to find every node n with an unwalkable neighbour, and then find the direction from n to the neighbour. That’s easy enough, but I’m just not sure how to store the multiple directions.

I should probably consider how to access the data during runtime as well. I’ve figured out how to get an approximate direction of attack when a bullet hits a unit. The idea there is to consider the nearest possible covering positions, and then calculate the angle between that position and the direction of attack. If the direction of attack is within the stored range, then the unit that’s under attack should have some cover at that position.

With the above in mind, my initial thought was to store the range of directions as an array (i.e. Vector3[ ] ), inside a dictionary that uses the position as a key. However, I’d like to know if there’s a better way, especially since I don’t think there’s a way to find the dictionary key that is the closest match to the unit’s current position.

The folks at Guerrilla Games did a good presentation on cover selection in Killzone: http://www.guerrilla-games.com/presentations/gdce05_killzone_ai.pdf

If you don’t mind using more memory, you can store more information in each node and make your runtime really fast. In each node, store information about every other node, such as the amount of cover between them. Then the runtime cost is just O(1) to determine how good cover is from, say, [1,1] to [4,2].

If you want to find the best cover in the closest n nodes, it just costs O(n) to do a simple lookup on each node and choose the best one. You can even have asymmetry, where cover from [1,1] to [4,2] is good, but cover from [4,2] to [1,1] is not as good.

You can also store the walkability to every other node. Say zero means you can’t get there from here. If the walkability from [1,1] to [4,2] is zero (which is just another O(1) lookup), then you don’t even need to pathfind since you know you can never get there.

If you need to conserve memory, you can break up your map into zones and only store node data within each zone. Between zones, you can store a single zone-to-zone value instead.

Similarly, instead of breaking up your map into a 2D array, you can store a graph of waypoint nodes. Then in each waypoint node you can store cover and walkability to other waypoints. Then your pathfinding algorithm gets really easy, and it’s just a matter of using a steering behavior to move from waypoint to waypoint. You’ll see some images similar to this in the Guerilla Games presentation I linked above.

I actually came across that paper, which is where I got the idea. I just wasn’t entirely sure on how to implement it. But thanks for the extra suggestions; I’ll keep them in mind.