by hwoarangmy » 02 Jul 2016, 21:42
When we compute a path, in the current code, we use a vector to store the processed tiles. In the A* algorithm, when we try the next tile, we have to see if one of its neighboors has already been computed. Thus, we go through the vector. On short paths, it is not a big problem.
But in the old test map (400x400), near the dungeon temple of one of the AI, there is a rock wall. Because of that, when the AI searches for the best place to put the next room, it checks behind the rock wall. The path exists but is very long and not straight forward (more than 50 000 tiles in the processed list). That makes the game look like frozen (the creatures stay idle for some time) when the map is launched because the path computation takes several minutes (freezing the server).
To avoid that, I've used a fast access vector (basically, an array initialized with the number of tiles in the map that is accessed through the tile X and Y allowing to know immediately if a tile is there or not). With this optimisation, on my computer, the time jumped from 5 minutes to 1.5 seconds for computing the path.
In the A* algorithm, we process the tiles beginning from the closer to the destination. In the current code, there is a list with the "to process" tiles and at each iteration, we go through to look for the closest. In my commit, I insert the tiles in the order. That allows to not have to go through the vector to find the closest tile. With this optimization, computing the path dropped to 200 ms.
Note that all the time computations were done on the old test map when the AI looks for placing the room