Assignments > Assignment 2: Crowd dynamics
In this assignment, you will work in teams to experiment with a specific aspect in crowd simulation. You can choose from the projects mentioned below.
This year, you will work in teams of 4 or 5 students, and there will probably be 10 teams in total. If you have any preference for a specific project and/ or team mates, then you can enter your top 3 project list and desired team mates before/ on 15 November, via a link I will send you during the first lecture.
Motivation
Some students may wonder why we are not letting you create your own crowd simulation system. The main reason is that it is incredibly difficult to get such a system 100% right. Our research group has been developing such a software system for years, and it's still not perfect, so it would be crazy to ask you to do something similar in two months time. Instead, you will focus on a specific part of it.
During this assignment, you will notice that achieving particular types of behaviour is quite hard, and you will need to use some existing software in creative ways to make agents do exactly what you want. This may sometimes be because of limitations of the software, but it will usually be caused by the difficulty of the problem itself. Therefore, you will need to write a short report about how you programmed your crowd, e.g., what workarounds or tricks you used.
Development tips
- You can choose any programming language. A small bonus can be received when you run your demo in a browser (via WebAssembly).
- You're free to use other resources (such as code, tutorials, assets, plug-ins, previously made own work, etc.), as long as you properly acknowledge the sources you have used. Of course, this assignment is all about solving crowd-related problems, and not about creating nice resources, so spend your time wisely. A small bonus can be received when you're using ChatGPT-derived programs to partly generate your code.
- For each assignment holds that it requires to advance the state of the art, so simply running an existing solution is not sufficient.
- We expect that each student spends at least 85 hours on this assignment, so start early!
Write a report
Along with the demonstrator itself, your team also has to hand in a short report (of around 6-8 pages) about the problems that you have solved. Please motivate your choices. This report should explain which problems you have tried to solve, what solutions already exist in literature, what solution(s) you had in mind initially, and how you have eventually solved the problem(s). Also assess the software you've used: what is useful about it, what could be improved, and what functionality have you missed? How did you work around any limitations that you encountered? Try to be as critical about your own implementation as you have been about the papers you have reviewed.
Present your work (three times)
Yes, three times:
- On 27 November, you will give a 7-minute presentation of your project approach and plan. It's important to carefully narrow down the work you'll be doing, because each Project is too large to carry out in time. You'll get some feedback, in particular on the scope of your work. If your approach is based on a certain paper, do not assume that other students have read this one. The goal is to get you started early, to check whether you are on the right track, and to teach your fellow students about a crowd simulation topic.
- On 20 December, you will present your prototype and a demo during 7 minutes. Please mention the problems you've encountered, and which ones you've tackled and/or solved. Did you need to change your scope?
- You can incorporate the given feedback into the final project, which will be presented on 22 and 24 January (15 minutes). (You all need to be ready on the 22th, and the presentation order will be determined later.) What problem(s) have you solved? Did you come up with a generic solution? What solutions have you created?
Please try to make the presentation educational for your audience: explain carefully what problem(s) you have solved, which assumptions you have made and how you have solved them. Give an extensive demo. What problems did you encounter? Did this give rise to a more generic solution, or did this limit the application of your technique? Why?
You will not get a grade for the first two presentations; these presentations will give the lecturer a good impression of how much effort you have put into the assignment. Also, it is educative and fun to see each other's results after 2 months of hard work :)
If you have the feeling that you are stuck, please do not hesitate to contact your lecturer.
Hand everything in
Before the deadline (January 31), please hand in the following deliverables on Blackboard (NB if the files are too big, then send the teacher a download link, and update the report to Blackboard):
- the report;
- the slides of your presentation;
- a very short movie that shows your results (with at least a full HD resolution, but preferrably 4K);
- a working version of your game / software;
- a way for me to access the source code, preferably the link to your UU Git repository (if you have used this);
- A high-resolution (preferrably 4K) screenshot that represents your work.
Grading
The lecturer will grade your results on a 0-10 scale, based on the following factors, in decreasing order of importance:
- difficulty of the problems you have solved; this is dependant on the types of asssumptions you have made;
- overall effort you have put into the project as a group;
- thoroughness of the report;
- entertainment and smartness value: bonus points will be given if your solution is smart, generic, or well put together.
In most cases, implementing a full paper or implementing a complete solution is not possible in the given time. It is perfectly fine and even necessary to make assumptions (and to state them). In that case, ensure that your implementation is generic and that it works in all cases under these assumptions.
Projects
You can choose one of the following projects:
1. Crowded game
Create a game that features 5K+ simultaneous agents in your favorite game engine. The more the better. How can you ensure that the game stays playable and fun? What kind of level design allows so many agents? Chances are high that the agents get stuck somewhere.
You may also decide to use the crowd simulation plugin for Unreal Engine of uCrowds. In that case, the game needs to feature at least 10K agents per CPU core. The disadvantage is that IP restrictions will apply.
2. Counting crows
Create a simulation of 100K real-time (animated) birds that flock in a 3D environment in a web application compiled to Web Assembly (and JS). What architecture allows such a real-time simulation? How can you visualize and animate them in real-time with a decent fps?
Creating a big flock is not difficult, but realizing a big one that is fast and runs on the web may prove challenging.
3. Messy navigation mesh
Extract a correct multi-layered walkable environment from the Recast library. Research how you can extract a high-quality walkable environment. How can you better deal with modeling errors (like gaps), difficult geometry (like stairs that have different heights or very thin geometric elements)?
4. Move, move, move
A well-proved method for collision avoidance is based on Reciprocal Velocity Obstacles (RVO). However, this method has difficulties dealing with static (non-moving) agents, especially in dense crowds. Extend the method such that static agents are taken into account in a realistic way. What is realistic anyways? Do some research on how real people avoid other humans standing still. Which agents should move, and how? What types of scenarios can be distinguised? Should they be treated differently?
5. High grade: don't cut corners
RVO is still a well-proved method for collision avoidance. That doesn't change over 1 paragraph :-). However, this method, and, in general, other collision avoidance algorithms are integrated into crowd simulation frameworks that steer the global direction of the agents to navigate around an obstacle. Consequently, these algorithms tend to cut corners, and, hence, the agents tend to hug the obstacle(s). Do some research on how humans try to keep some distance from obstacles if possible. Show that your solution is effective in different circumstances, like a sparse versus a dense crowd, and in crossing crowd flows with obstacles.
6. The performer S01E01
This is an assignment for students interested in optimization. Pull every trick up your sleeve to optimize a multi-threaded RVO implementation without changing the collision avoidance. How does the performance behave when the number of threads/core is increased?7. The Cyclist
Construct an interaction model for bicycles and pedestrians. You may assume that the indicative routes for the bicycles are given (by a user). How can 2 bicycles coordinate their motions when there is an imminent collision? How about bicycle-pedestrian collision avoidance? Use your favorite game engine to make a simulation model.
8. You're a star
One of the most used algorithms in games is the A* algorithm. Even when you create an efficient implementation, applying this algorithm on a crowd of 100K+ agents to plan a global path in a big environment (of say 25 squared kilometers) may prove to be too costly. Be a star, and design and implement a variant that is fast enough to work in huge environments with huge crowds. You don't need to plan paths for so many agents, but the algorithm should be fast enough so that it could handle 100K+ agents in real time in such big environments.
9. Big oh ow
In the paper, The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh, we showed that the multi-layered medial axis (and Explicit Corridor Map) can be constructed in O(n log n log k) time, where n is the number of boundary vertices and k is the number of connections between the layers. However, we think that the time can be improved to O(n log n).
Give the construction of the improvement, or show it cannot be done. What is the optimal O then?
Choose this assignment if you want to focus solely on theory, or if you don't want to program.