{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:19:52Z","timestamp":1763810392761,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T00:00:00Z","timestamp":1604102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2018R1D1A1B07048414"],"award-info":[{"award-number":["2018R1D1A1B07048414"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Finding collision-free paths for crowd simulation has been a core technique in video games and the film industry; it has drawn a great deal of attention from computer animation researchers for several decades. Additionally, theoretical modeling of pedestrian has been a hot topic in physics as well because it allows us to predict any architectural failure of buildings and many city planning problems. However, the existing studies for path planning cannot guarantee the arrival order, which is critical in many cases, such as arrival symmetry of the characters within video games or films. To resolve this issue, a path planning algorithm has been developed with a novel method for satisfying the arrival-order constraints. The time constraint we suggest is the temporal duration for each character, specifying the order in which they arrive at their target positions. In addition to the algorithm that guarantees the arrival order of objects, a new user interface is suggested for setting up the arrival order. Through several experiments, the proposed algorithm was verified, and can successfully find collision-free paths, while satisfying the time constraint set by the new user interface. Given the available literature, the suggested algorithm and the interface are the first that support arrival order, and their usability is proven by user studies.<\/jats:p>","DOI":"10.3390\/sym12111804","type":"journal-article","created":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T21:39:56Z","timestamp":1604180396000},"page":"1804","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Crowd Simulation with Arrival Time Constraints"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5807-6719","authenticated-orcid":false,"given":"Mankyu","family":"Sung","sequence":"first","affiliation":[{"name":"Department of Game &amp; Mobile, Keimyung University, Daegu 42601, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2664-3632","authenticated-orcid":false,"given":"SeongKi","family":"Kim","sequence":"additional","affiliation":[{"name":"Division of SW Convergence, Sangmyung University, Seoul 03016, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Van den Berg, J., Lin, M., and Manocha, D. (2008, January 19\u201323). Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Pasadena, CA, USA.","DOI":"10.1109\/ROBOT.2008.4543489"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1109\/TRO.2011.2120810","article-title":"The Hybrid Reciprocal Velocity Obstacle","volume":"27","author":"Snape","year":"2011","journal-title":"IEEE Trans. Robot."},{"key":"ref_3","unstructured":"Van den Berg, J., Guy, S., Lin, M., and Manocha, D. (September, January 31). Reciprocal n-body Collision Avoidance, Robotics research. Proceedings of the 14th International Symposium ISRR, Lucerne, Switzerland. Selected papers based on the presentations at the symposium."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Van den Berg, J., Snape, J., Guy, S., and Manocha, D. (2011, January 9\u201313). Reciprocal Collision Avoidance with Acceleration-Velocity Obstacles. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Shangai, China.","DOI":"10.1109\/ICRA.2011.5980408"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1007\/s11390-014-1469-y","article-title":"Crowd Simulation and its Applications: Recent Advance","volume":"29","author":"Jin","year":"2014","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.17815\/CD.2016.1","article-title":"Merge: A Modular Framework for Simulating Crowd Movement","volume":"1","author":"Curtis","year":"2016","journal-title":"Collectiv. Dyn."},{"key":"ref_7","unstructured":"Ijaz, K., Sohail, S., and Hashish, S. (2015, January 25\u201327). A Survey of Latest Approaches for Crowd Simulation and Modeling using Hybrid Techniques. Proceedings of the 17th UKSIM-AMSS International Conference on Modelling and Simulation, Cambridge, UK."},{"key":"ref_8","unstructured":"Berg, J., Patil, S., Sewall, J., Manocha, D., and Lin, M. (2008, January 15\u201317). Interactive Navigation of Individual Agents in Crowded Environments. Proceedings of the Symposium on Interactive 3D Graphics and Games (I3D), Redwood City, CA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1111\/cgf.12735","article-title":"Coordinated Crowd Simulation with Topological Scene Analysis","volume":"35","author":"Barnett","year":"2016","journal-title":"Comput. Graph. Forum"},{"key":"ref_10","first-page":"3","article-title":"Continuum Crowds","volume":"25","author":"Cooper","year":"2006","journal-title":"ACM Trans. Graph."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"238701","DOI":"10.1103\/PhysRevLett.113.238701","article-title":"A universal power law governing pedestrian interaction","volume":"113","author":"Karamouzas","year":"2014","journal-title":"Phys. Rev. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3072959.3073705","article-title":"Implicit Crowds: Optimization Integrator for Robust Crowd Simulation","volume":"36","author":"Karamouzas","year":"2017","journal-title":"ACM Trans. Graph."},{"key":"ref_13","first-page":"391","article-title":"A fluid dynamic model for the movement of pedestrians","volume":"6","author":"Helbing","year":"1992","journal-title":"Complex. Syst."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Reynolds, C.W. (1987, January 27\u201331). Flocks, Herds, and Schools: A Distributed Behavioral Model. Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, ACM SIGGRAH, Anaheim, USA.","DOI":"10.1145\/37401.37406"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/cav.1424","article-title":"Real-time density-based crowd simulation","volume":"23","author":"Toll","year":"2012","journal-title":"J. Comput. Anim. Virtual Worlds"},{"key":"ref_16","unstructured":"Guy, S., Chhugani, J., Curtis, S., Dubey, P., Lin, M., and Manocha, D. (2010, January 2). PLEdestrians: A Least-Effort Approach to Crowd Simulation. Proceedings of the ACM SIGGAPH\/Eurographics Symposium on Computer Animation, Chapel Hill, NC, USA."},{"key":"ref_17","unstructured":"(2020, October 09). RVO2 Library. Available online: http:\/\/gamma.cs.unc.edu\/RVO2\/."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Yang, L., Qi, J., Song, D., Xiao, J., Han, J., and Xia, Y. (2016). Survey of Robot 3D Path Planning Algorithms. J. Control. Sci. Eng., 2016.","DOI":"10.1155\/2016\/7426913"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1111\/j.1467-8659.2004.00783.x","article-title":"Scalable Behavior for Crowd Simulation","volume":"23","author":"Sung","year":"2014","journal-title":"Comput. Graph. Forum"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kurihaha, K., Vronay, D., and Igagashi, T. (2005, January 2). Flexible Timeline User Interface using Constraints. Proceedings of the CHI\u201905 Extended Abstracts on Human Factors in Computing Systems, Portland, OR, USA.","DOI":"10.1145\/1056808.1056971"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Korkmaz, M., and Durdu, A. (2018, January 20\u201324). Comparing of optimal Path Planning Algorithms. Proceedings of the International Conference on Advanced Trends in Radio-electronics, Telecommunications and Computer Engineering, Slavske, Ukraine.","DOI":"10.1109\/TCSET.2018.8336197"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.protcy.2016.03.010","article-title":"Time-efficient A* algorithm for Robot Path Planning","volume":"23","author":"Guruji","year":"2016","journal-title":"Proc. Technol."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/11\/1804\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:27:28Z","timestamp":1760178448000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/11\/1804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,31]]},"references-count":22,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["sym12111804"],"URL":"https:\/\/doi.org\/10.3390\/sym12111804","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,10,31]]}}}