佈局（setting）從根本上決定了連鎖反應動畫中的難度和複雜程度。然而，據我們所知，過去的研究並未提供佈局（setting）、碰撞序列以及完成整個動畫的複雜度之間的正式描述和推導。而要生成既符合物理上合理，又滿足特定複雜度的佈局（setting）設計過程也很難自動化，而複雜度的驗證通常需要專業知識和大量人力來完成。因此，本論文提出了一種連鎖反應佈局（setting）生成系統，並且可以指定目標複雜度來生成連鎖反應場景。我們的系統用L 系統（Lindenmayer system, L-system）來描述碰撞序列，以系統和分層地描述和推演各種可能的場景，並將它們轉換為樹狀圖（Portfolio）、幾何配置（geometric configuration），生成物理上合理，並包含幾何與物理參數的場景佈局（setting），同時讓蒙地卡羅樹搜尋（Monte Carlo Tree Search, MCTS）探索空間和搜索目標複雜度的佈局佈局（setting）。此外，我們還依據單個元件（element），並參考各個元件（element）幾何配置（geometric configuration）的區域屬性，以及同時參考多個元件之間的關聯，像是整個系統的行進方向改變了多少次、各個分支之間的長度是否相近，以整個系統一起評估的全域屬性，推導出了一個複雜度的評估標準。最後，我們做了一些實驗和用戶研究（user studies）評估了我們系統的效率和評估標準的有效性。

A setting fundamentally determines the difficulty and impressiveness of a shot during a chain reaction animation. However, past researches do not provide formal description and derivation among settings, collision sequences, and the impressiveness to finish entire animations, to the best of our knowledge. It is also hard to automate the design process for physically-plausible settings of targeted impressiveness while impressiveness validation generally requires expertise and massive labor. Therefore, this work systematically proposes a one-play-all-finish chain reaction setting generator with a mechanism to specify the targeted impressiveness for chain reaction scenes. Our system encapsulates collision sequences with L-system for systematic and hierarchical description and deduction of various
shooting strategies, and transforms them to portfolios, geometric configurations, and final plausible settings with geometric and physical parameters while having MCTS explore and search plausible setting of the targeted impressiveness. Furthermore, we also derive a impressiveness metric using the local information of each unit and global information of the whole scene. At the end, we have evaluated our effectiveness and efficiency through several experiments and user studies.

[1] Bobby Pugh, “Rube Goldberg 3D Animation.” https://www.youtube.com/watch?v=0Ye7iAIPhmg&ab_channel=BobbyPugh, 2012.
[2] R. Roussel, M.-P. Cani, J.-C. Léon, and N. J. Mitra, “Designing chain reaction contraptions from causal graphs,” ACM Trans. Graph., vol. 38, pp. 43:1–43:14, jul 2019.
[3] S. Summerville, S. Philip, and M. Mateas, “Mcmcts pcg 4 smb: Monte carlo tree search to guide platformer level generation,” Artificial Intelligence in the Game Design Process, vol. 11, no. 1, pp. 68–74, 2015.
[4] S. Snodgrass and S. Ontañón, “A hierarchical approach to generating maps using markov chains,” in Proceedings of the Tenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE’14, pp. 59–65, AAAI Press, 2014.
[5] E. Hauck and C. Aranha, “Automatic generation of super mario levels via graph grammars,” in Proceedings of the 2020 IEEE Conference on Games (CoG), CoG 2020, (New York, NY, USA), pp. 297–304, IEEE, 2020.
[6] R. Rodriguez Torrado, A. Khalifa, M. Cerny Green, N. Justesen, S. Risi, and J. Togelius, “Bootstrapping conditional gans for video game level generation,” in Proceedings of the 2020 IEEE Conference on Games (CoG), CoG 2020, (New York, NY, USA), pp. 41–48, IEEE, 2020.
[7] J. O. Talton, Y. Lou, S. Lesser, J. Duke, R. Měch, and V. Koltun, “Metropolis procedural modeling,” ACM Trans. Graph., vol. 30, no. 2, pp. 11:1–11:14, 2011.
[8] O. Stava, S. Pirk, J. Kratt, B. Chen, R. Mundefinedch, O. Deussen, and B. Benes,“Inverse procedural modelling of trees,” Comput. Graph. Forum, vol. 33, pp. 118–
131, Sept. 2014.
[9] L. Ferreira and C. Toledo, “A search-based approach for generating angry birds levels,” in Proceedings of the 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, (New York, NY, USA), pp. 1–8, IEEE, 2014.
[10] M. Fridenfalk, “Algorithmic music composition for computer games based on l-system,” in Proceedings of the 2015 IEEE Games Entertainment Media Conference (GEM), GEM 2015, (New York, NY, USA), pp. 1–6, IEEE, 2015.
[11] P. Prusinkiewicz and A. Lindenmayer, The Algorithmic Beauty of Plants. Heidelberg, Berlin, Germany: Springer-Verlag, 1990.
[12] P. Prusinkiewicz, M. James, and R. Měch, “Synthetic topiary,” in Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’94, (New York, NY, USA), pp. 351–358, ACM, 1994.
[13] P. Prusinkiewicz, L. Mündermann, R. Karwowski, and B. Lane, “The use of positional information in the modeling of plants,” in Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’01, (New York, NY, USA), pp. 289–300, ACM, 2001.
[14] Y. Parish and P. Müller, “Procedural modeling of cities,” in Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH’01, (New York, NY, USA), pp. 301–308, ACM, 2001.
[15] J.-E. Marvie, J. Perret, and K. Bouatouch, “The fl-system: A functional l-system for procedural geometric modeling,” The Vis. Comput., vol. 21, no. 5, pp. 329–339, 2005.
[16] Q. Xiong and X.-Y. Huang, “Speed tree-based forest simulation system,” in Proceedings of the 2010 International Conference on Electrical and Control Engineering,
ICECE ’10, (New York, USA), pp. 3033–3036, IEEE Computer Society, 2010.
[17] F. Boudon, C. Pradal, T. Cokelaer, P. Prusinkiewicz, and C. Godin, “L-Py: an L-system simulation framework for modeling plant architecture development based on a dynamic language,” Frontiers in Plant Science, vol. 3, no. 76, 2012.
[18] B. Ganster and R. Klein, “An integrated framework for procedural modeling,” in Proceedings of the 23rd Spring Conference on Computer Graphics, SCCG ’07, (New York, NY, USA), pp. 123–130, ACM, 2007.
[19] M. Lipp, P. Wonka, and M. Wimmer, “Interactive visual editing of grammars for procedural architecture,” ACM Trans. Graph., vol. 27, no. 3, pp. 102:1–102:10, 2008.
[20] G. Patow, “User-friendly graph editing for procedural modeling of buildings,” IEEE Comput. Graph. Appl., vol. 32, no. 2, pp. 66–75, 2012.
[21] G. Smith, M. Treanor, J. Whitehead, and M. Mateas, “Rhythm-based level generation for 2d platformers,” in Proceedings of the 4th International Conference on Foundations of Digital Games, FDG ’09, (New York, NY, USA), pp. 175–182, Association for Computing Machinery, 2009.
[22] N. Shaker, J. Togelius, G. N. Yannakakis, B. Weber, T. Shimizu, T. Hashiyama, N. Sorenson, P. Pasquier, P. Mawhorter, G. Takahashi, G. Smith, and R. Baumgarten, “The 2010 mario ai championship: Level generation track,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 3, no. 4, pp. 332–347, 2011.
[23] N. Shaker, G. N. Yannakakis, J. Togelius, M. Nicolau, and M. O’Neill, “Evolving personalized content for super mario bros using grammatical evolution,” in proceedings of the Eighth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE’12, pp. 75–80, AAAI Press, 2012.
[24] J. Togelius, M. Preuss, N. Beume, S. Wessing, J. Hagelbäck, and G. N. Yannakakis, “Multiobjective exploration of the starcraft map space,” in Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games, CIG 2010, (New York, NY, USA), pp. 265–272, IEEE, 2010.
[25] J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, “Search-based procedural content generation: A taxonomy and survey,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 3, no. 3, pp. 172–186, 2011.
[26] J. Togelius, M. Preuss, N. Beume, S. Wessing, J. Hagelbäck, G. N. Yannakakis, and C. Grappiolo, “The 2010 mario ai championship: Level generation track,” Genetic Programming and Evolvable Machines, vol. 14, pp. 245–277, 2013.
[27] S. Dahlskog, J. Togelius, and M. J. Nelson, “Linear levels through n-grams,” in Proceedings of the 18th International Academic MindTrek Conference: Media Business,
Management, Content & Services, AcademicMindTrek ’14, (New York, NY, USA), pp. 200–206, Association for Computing Machinery, 2014.
[28] M. Traichioiu, S. Bakkes, and D. Roijers, “Grammar-based procedural content generation from designer-provided difficulty curves,” in Proceedings of the 10th International Conference on the Foundations of Digital Games, FDG 2015, (New York, NY, USA), pp. 1–5, Society for the Advancement of the Science of Digital Games, 2015.
[29] V. Volz, J. Schrum, J. Liu, S. M. Lucas, A. Smith, and S. Risi, “Evolving Mario levels in the latent space of a deep convolutional generative adversarial network,” in Proceedings of the Genetic and Evolutionary Computation Conference, GECCO’18, (New York, NY, USA), pp. 221–228, Association for Computing Machinery, 2018.
[30] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of monte carlo tree search methods,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, pp. 1–43, 2012.
[31] D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. Driessche, J. S., I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of go with deep neural networks and tree search,” Nature, vol. 529, pp. 484–489, 2016.
[32] Unity Technologies, “Unity (version2019.1.6f1).” https://unity.com/, 2019.
[33] D. Griffiths, Head First Statistics. O’Reilly Media, 2009.
[34] Y.-T. CHEN, “Html5-confidence-intervals-calculator.” https://github.com/pulipulichen/HTML5-Confidence-Intervals-Calculator/.
[35] C. Kocsis, Leventeand Szepesvári, “Bandit based monte-carlo planning,” in Machine Learning: ECML 2006, pp. 282–293, 2006.
[36] E. Weisstein, “Fisher’s exact test..” https://mathworld.wolfram.com/FishersExactTest.html