Roguebasin has an interesting article on Dijkstra maps that might help in speeding up hostile creatures’ hunting.

I placed a single NPC on the board, on the other side of the screen, and discovered that the crappy pathfinder I had written earlier was a bigger bottleneck than I expected. Which to be honest was indeed to be expected from a very cheap attempt at a Dijkstra-style system. I had originally written it to facilitate rightclicking on the board to automatically travel to that spot, and even then crossing the entire screen would lock the game up for a couple of seconds.

To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the map’s “floor” cells – skip the impassable wall cells. If any floor tile has a value that is at least 2 greater than its lowest-value floor neighbor, set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made. The resulting grid of numbers represents the number of steps that it will take to get from any given tile to the nearest goal.

In contrast with this stupidly elegant concept, my current system is so bad I’m not gonna bother describing it in anything other than SBAHJ terms.

To hunt for the player, a shared Dijkstra map would be perfectly suited. One character going after the player, having to recalculate the map every time the player moves, was okay if I limited the hunting range to about ten tiles, but imagine having a room full of them! Therefore, I’m considering using shared Dijkstra maps for hunting targets. If the target (which does not need to be the player) moves, the Dijkstra map associated with that target is updated. The map is stored as part of the target and never saved. Since Noxico is realtime, if the target stands still all the hunters can use the same map with no recalculation delays. Perhaps a “being hunted” flag could be added so the hunters’ own maps don’t get updated without due cause…

And if the new pathfinding map generator is less conksuck than what I have now, it can be used for rightclick travel too.