Page 1 of 1

Strange performance behaviour

PostPosted: 29 Jun 2016, 15:44
by paul424
Have you noticed there is considerable FPS diffrence when it comes between small and large maps, altough we invented culling and have only visible tiles pluged-in ? I wonder what else connected to the size of the map could slow down game. A blind guess is : The A* path finding algorithm ? , but it shouldn't be much of a hassle ... should it .. ?

Re: Strange performance behaviour

PostPosted: 30 Jun 2016, 09:23
by hwoarangmy
It could be worth using a profiler to figure out...

Re: Strange performance behaviour

PostPosted: 01 Jul 2016, 18:33
by hwoarangmy
I've had a look and it seems there is indeed a problem with the astar algo when the map is big. IMO, it comes from the vector with the tiles (open and closed lists). I will have a look

Re: Strange performance behaviour

PostPosted: 01 Jul 2016, 23:37
by hwoarangmy
I've pushed a commit in my PR about the A Star optimization. Once it is merged, please try again if you see improvements

Re: Strange performance behaviour

PostPosted: 02 Jul 2016, 01:18
by paul424
"From the tests I've done, for an accessible path behind rock tiles, I go from 5 minutes to 200 ms so it is pretty better"

He he , I don't understand , what I get on my machine is about ~3fps advantage ...

Re: Strange performance behaviour

PostPosted: 02 Jul 2016, 09:17
by hwoarangmy
paul424 {l Wrote}:He he , I don't understand , what I get on my machine is about ~3fps advantage ...
I'm talking about my commit about A* optimization.

Concerning culling, I also get around 3-5 fps advantage with creature culling.

Re: Strange performance behaviour

PostPosted: 02 Jul 2016, 12:51
by paul424
Yes, but what changed from 5min to 200ms ?

Re: Strange performance behaviour

PostPosted: 02 Jul 2016, 21:42
by hwoarangmy
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