Strange performance behaviour

Strange performance behaviour

Postby paul424 » 29 Jun 2016, 15:44

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 .. ?
User avatar
paul424
OD Moderator
 
Posts: 639
Joined: 24 Jan 2012, 13:54

Re: Strange performance behaviour

Postby hwoarangmy » 30 Jun 2016, 09:23

It could be worth using a profiler to figure out...
hwoarangmy
 
Posts: 565
Joined: 16 Apr 2014, 19:13

Re: Strange performance behaviour

Postby hwoarangmy » 01 Jul 2016, 18:33

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
hwoarangmy
 
Posts: 565
Joined: 16 Apr 2014, 19:13

Re: Strange performance behaviour

Postby hwoarangmy » 01 Jul 2016, 23:37

I've pushed a commit in my PR about the A Star optimization. Once it is merged, please try again if you see improvements
hwoarangmy
 
Posts: 565
Joined: 16 Apr 2014, 19:13

Re: Strange performance behaviour

Postby paul424 » 02 Jul 2016, 01:18

"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 ...
User avatar
paul424
OD Moderator
 
Posts: 639
Joined: 24 Jan 2012, 13:54

Re: Strange performance behaviour

Postby hwoarangmy » 02 Jul 2016, 09:17

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.
hwoarangmy
 
Posts: 565
Joined: 16 Apr 2014, 19:13

Re: Strange performance behaviour

Postby paul424 » 02 Jul 2016, 12:51

Yes, but what changed from 5min to 200ms ?
User avatar
paul424
OD Moderator
 
Posts: 639
Joined: 24 Jan 2012, 13:54

Re: Strange performance behaviour

Postby 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
hwoarangmy
 
Posts: 565
Joined: 16 Apr 2014, 19:13

Who is online

Users browsing this forum: No registered users and 1 guest