Hello. I am currently trying to develop a fairly simple Turn-Based Tactics engine, similar to Fire Emblem, and I am having trouble finding the set of nodes that a player/computer can attack in one turn. I have a set of nodes, A, that represent all of the places that the player/computer can reach. I need to find all of the nodes that are x steps away from any one of the nodes in A. Right now, I'm using Dijkstra to find all of the nodes that can be reached, and then calling a breadth-first search from each of those nodes. However, because of the environment I'm working in, this is very slow. Is there any way that I can improve the speed? Thanks, -Mnementh

It's hard to tell without knowing a lot of details about your program. Of the top of my head, if the map looks anything like an image (2D grid), you can try using image-processing techniques. For instance, the convolution of the places that you can reach with a circle will have non-zero values in exactly the places that you can shoot. This convolution can be computed pretty fast using FFT. As I said, this may or may not be a good idea in your case, and it's hard to tell before trying it (if it's even possible to implement in your particular situation).

Quote: Right now, I'm using Dijkstra to find all of the nodes that can be reached, and then calling a breadth-first search from each of those nodes.

Well, that's always going to be quite slow, although for a turn-based game it shouldn't be a big issue. But if you're doing a breadth-first search from each of the reachable nodes, why don't you just incorporate this into your initial reachable search? i.e. you just do one search to find all attackable nodes before moving. If movement and attacks have different rules for traversal, then you could alter the function which opens nodes, so that the rules for opening nodes on search is based on the node's current depth (if it's greater than movement distance, the node can only be achieved by attacking).

Presumably once you know what you can attack, there should be some obvious candidates.

Another option would be to take your set A, and figure out whether any attackable entities lie with the region A plus the additional x. Then you can handle those entities individually. If there aren't many attackable enemies relative to the space you are looking at (i.e. a wide open region with a handful of attackables), this would be the preferred method.