Game runs very slow with more than 10 enemies on the map

[DavidFidge]

The game runs very slow with more than 10 enemies on the map.

[DavidFidge]

There appears to be minimal cpu usage between turns however it is still going slow.

Performed memory profiling and found that the cause is due to a large amount of garbage collection between turns. A large amount of memory is being allocated then deallocated when monsters move due to field of view and pathing calculations. This is being done in the GoRogue library.

Currently the full map is used for calculating both field of view and for calculating goal maps. This is a known inefficiency which hasn't needed addressing until now. A 100x100 map has 10,000 cells, so a list of points should take up 32 bits 10000 points 2 coords / 8 bits in a byte = 80,000 bytes = 80 kilobytes. Times 20 monsters gives 1.6mb per turn (round this off to 2mb a turn). We have 2 goal maps being updated per monster per turn which ups it to about 6mb. 100 game turns cycles 600mb of memory. To conclude, it is probably not GoRogue that is causing the issue but rather the full map being used for calculations.

Field of view should be simple to fix - monsters just need to have a max visible range applied. The player also needs a max visible range.

Goal maps are a bit more difficult as obstacles and goals are always changing, the map could become radically different between turns and different monsters may have different routines. Example - if the player erects a barrier of walls and the goal map recalculation size was not big enough to encapsulate a path between monster and player even though such a path exists then the monster won't be able to take that path. There are solutions to this though - the monster could immediately switch to a different state, e.g. wander.

The current set of monsters and AI is very limited right now. I think that limiting goal maps to visible range would be enough to fix performance issues. Also need to check that immobiles are not unnecessarily using the wander calculations when they are immobile.

If performance issues continue then a deeper analysis into GoRogue's algorithms will be needed. Alternatively more complicated improvements will need to be looked at e.g. field of view really only needs recalculating for stationary objects if any walls are destroyed or erected during a turn.

[DavidFidge]

Field of view has been addressed.

Goals also use the field of view range. One issue is that monsters can be stuck in an area that is unreachable by any of its goals. For the Wander behavior, the goals are unseen tiles so if there are no unseen tiles in the subset of the map which represents the current goal map, or the goals are disjoint i.e. cut off by walls then all the goal values have a max value set and the monster flip flops between two tiles.

One solution I tried to implement was detecting all max values in the goal map and reducing the max values based on the difference between goal position and monster position. However I realised this won't fix the problem because the goal map is always recalculated each turn and adjacent cells will still have the same value, meaning it will just flip flop again.

Ideas for fixing

• implement a proper maze solving algorithm
• implement a momentum-based system with a wall follower rule for resolving collisions with walls
• temporarily expand the goal map range

[DavidFidge]

Could also consider a different way of wandering. Goal map subsetting work great for Hunt, but Wander may work better by just picking an unexplored point on the map and pathing to it.

For now, temporarily expanding the goal map range seems the easiest approach.

[DavidFidge]

Temporarily expanding the goal map range ends up not working so well because you don't know exactly when to retract it again. Will clean up the code and commit goal map subsets for hunt functionality then look into picking an unexplored point for wander next.

[DavidFidge]

Has now been fixed by using AStar pathing to an unexplored part of the map. Performance has greatly been improved.