Penerapan Procedural Content Generation Dengan Optimasi Unbounded Knapsack Problem Dalam Game Tower Defense

Michael Argento, Hanny Haryanto

Abstract


Permintaan konten baru pada game tower defense sulit dipenuhi apabila wave musuh dibuat secara manual karena membutuhkan waktu, sulit diskalakan, dan berisiko menghasilkan tingkat kesulitan yang tidak konsisten. Penelitian ini menerapkan Procedural content generation dengan optimasi Unbounded knapsack problem pada sistem wave spawner dalam prototype game tower defense berjudul Castle Vanguard. Metode yang digunakan memodelkan musuh sebagai item, HP sebagai weight, difficulty value sebagai value, dan total HP per wave sebagai constraint. Permasalahan tersebut diselesaikan menggunakan Dynamic programming untuk menghasilkan komposisi musuh secara otomatis dengan prinsip exact HP fill. Sistem juga menerapkan tier-aware generation, monopoly guard, anti-repetition, dan boss wave untuk menjaga variasi komposisi musuh. Dengan demikian, penerapan Procedural content generation dengan optimasi Unbounded knapsack problem dapat digunakan untuk membentuk wave musuh yang otomatis, terukur, bervariasi, dan mudah diskalakan.


Keywords


Procedural content generation; Unbounded knapsack problem; Dynamic programming; Tower defense; Wave spawner

Full Text:

PDF

References


P. Avery, J. Togelius, E. Alistar, and R. P. van Leeuwen, “Computational intelligence and tower defence games,” in Proceedings of the 2011 IEEE Congress on Evolutionary Computation (CEC), 2011, pp. 1084–1091.

M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup, “Procedural content generation for games: A survey,” ACM Transactions on Multimedia Computing, Communications, and Applications, vol. 9, no. 1, Article 1, 2013.

R. Lara-Cabrera, M. Nogueira-Collazo, C. Cotta, and A. J. Fernández-Leiva, “Procedural content generation for real-time strategy games,” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 3, no. 2, pp. 40–48, 2015.

S. Liu, C. Li, Y. Li, H. Ma, X. Hou, Y. Shen, et al., “Automatic generation of tower defense levels using PCG,” in Proceedings of the 14th International Conference on the Foundations of Digital Games (FDG ’19), 2019, pp. 1–9.

V. Kraner, I. Fister Jr., and L. Brezočnik, “Procedural content generation of custom Tower defense game using genetic algorithms,” in New Technologies, Development and Application IV, vol. 233, 2021, pp. 493–503.

D. M. P. L. Dias, J. P. Sousa, B. Barroso, and I. M. B. Magalhães, “A novel procedural content generation algorithm for tower defense games,” in Proceedings of the 6th International Conference on Algorithms, Computing and Systems (ICACS 2022), 2022, Article 9, pp. 1–7.

D. Hind and C. Harvey, “Using a NEAT approach with curriculums for dynamic content generation in video games,” Personal and Ubiquitous Computing, vol. 28, no. 4, pp. 629–641, 2024.

U. Pferschy, G. Nicosia, A. Pacifici, and J. Schauer, “On the Stackelberg knapsack game,” European Journal of Operational Research, vol. 291, no. 1, pp. 18–31, 2021.

H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems. Berlin: Springer, 2004.

R. Bellman, Dynamic Programming. Princeton, NJ: Princeton University Press, 1957.

S. P. Bradley, A. C. Hax, and T. L. Magnanti, Applied Mathematical Programming. Reading, MA: Addison-Wesley, 1977.

H. Becker and L. S. Buriol, “An empirical analysis of exact algorithms for the unbounded knapsack problem,” European Journal of Operational Research, vol. 277, no. 1, pp. 84–99, 2019.




DOI: https://doi.org/10.62411/tcv.v4i1.3400

Refbacks

  • There are currently no refbacks.


Copyright (c) 2026 Michael Argento, Hanny Haryanto