search

CameronJung / ChopperTankFlak

A simple rock-paper-scissors strategy game
0 stars 0 forks source link

The AI's turn takes too long #23

Closed CameronJung closed 1 month ago

CameronJung commented 3 months ago

Larger Maps and larger numbers of units cause the AI's turn to take too long. This is particularly bad on Operation Pangea.

CameronJung commented 3 months ago

Right now I believe the main culprit for this issue is the A* search algorithm. It might be better just to have a global look up table for navigation and initializing it during a loading screen than conducting these searches at runtime.

CameronJung commented 3 months ago

Another approach could be to use such a table but to instead store the data obtained during the A* search so that the calculations aren't repeated and the load is distributed over time. This also has the advantage that unnecessary calculations aren't performed. However, the disadvantage is that this also adds to the work done during the search, so benefits could bi minimal and situational.

CameronJung commented 2 months ago

I decided this warrants a patch, as opposed to lumping it in with a major update

CameronJung commented 2 months ago

Improvements have been made. However, on android the time the AI takes to make a turn is still too long. I'm not sure why though considering that my phone apparently has a similar processor to my laptop; maybe the graphics is the issue. Further research is warranted.

CameronJung commented 2 months ago

With the current improvements in the branch the AI makes its turn twice as fast. The biggest improvement came from giving the measurement a time budget instead of a set number of iterations per frame. Additionally, distances measured are now stored in a global look up table so they aren't repeated.

CameronJung commented 2 months ago

I might have made a breakthrough, it seems that a lot of the yields in the AI commander are holding back the program by not using frames to their fullest potential. With some of these lines commented out Pangea completes its first turn in ~22 seconds, compared to the ~100 seconds it took before. I will need to do some testing on Android but this might be huge.