Modeling Bloons Tower Defense as a temporal two‐dimensional knapsack problem with irregular shapes and side constraints: integer programming–based approaches

Abstract In Tower Defense (TD) games, the objective is to defend a specific point on the game map from mobile units by constructing towers with offensive capabilities. In this work, we focus on Bloons Tower Defense (Bloons TD), one of the earliest and most prominent TD games. We show that the problem of finding tower configurations that win Bloons TD can be formulated as a temporal two‐dimensional knapsack problem with irregular shapes and side constraints. We developed two integer programming–based methods using the well‐known dotted‐board model: a greedy strategy, where tower configurations are determined one round at a time, and a multi‐round strategy, where configurations for all rounds are determined simultaneously. Our analysis highlights that certain aspects of the resulting optimization problem, such as defining an objective function aligned with winning Bloons TD and incorporating the temporal dimension arising from the game's multiple rounds, are crucial for finding effective tower configurations. While these aspects do not commonly arise in classical cutting and packing problems, we show how they can be successfully modeled for this TD game. The solutions generated by our approaches were able to win the game, in some cases outperforming human strategies. Overall, this work demonstrates the versatility of cutting and packing techniques, illustrating that models and methods initially developed for industrial applications can have practical relevance in very different domains. All our code, including the game simulation tool we developed, is freely available and can be used for future research in the TD genre.