GitStats for Groups
Basics
This page contains a more complete description of the project and some notes on how I think the required elements could be completed. To repeat what was written on the main course page, the purpose of this project is to create a large-scale, algorithmically generated, dynamically loaded, virtual world. The large-scale part is correlated to the other two and is just a side effect of them. The idea here is to create an efficient world that is truly huge but didn't require many thousands of human artist hours to create. To do that it needs to be algorithmically generated. That is to say that the things that are found in the world are built, placed, and governed by algorithms. These algorithms have to have certain characteristics. For example, they need to be repeatable so that if you go to a part of the world, leave, and come back, you should see the same things that were there the first time. Related to this is the idea of dynamic loading. Because the world is so large, we should only keep track of things when there is someone around to see it. In the real world a tree falling in the forest still makes a sound, but in our world, the tree shouldn't even be there to fall if it isn't observable. This is what dynamic loading does.
As mentioned on the main page, the world has to have terrain and some vegetation. It will have a lot of other things, but what other things are present depends on what you want to put into it. The reason I say those things have to be put in is that I know how to put them in. I have ideas for other things, but it will require more work on your part to make sure it works. Earlier students working on this project developed algorithms for dealing with water, cities, and the buildings in those cities to various extents. Some pieces that people might want to add will require other pieces to be put in place. I'll describe how the general idea that I have for the layout of data and how the terrain and things on it will be done.
Last time this project was done, we used a spherical world with elevation changes on the sphere. Making the world a sphere though increases the complexity of the vector math that must be used, so this time we will most likely keep the world as a plane with elevation changes. Still, knowing a bit of vector math will certainly be beneficial for some aspects of the project. The world surface will be described by a set of triangular pieces. This structure is chosen because there are easy to use fractal algorithms that do midpoint offsets with triangles. You could also opt to do a Perlin noise algorithm. Everything in the world will be loaded to different "levels" depending on how close it is to a "viewer". So as a viewer nears a piece of terrain that isn't fully loaded, it will split into smaller pieces. This continues down to the levels of resolution that we want for the terrain viewed close up. At different points, other details will also be put into the loading. At the lowest level, things like vegetation will actually be put in. At that level, we might also use a different terrain generation algorithm as well.
Even with dynamic loading, a world the size of the Earth will still have a lot of pieces in it. So we want to store things in a structure that allows us to very quickly find objects by their rough location. We also need to be able to quickly send messages to objects telling them that a viewer is getting closer or that a viewer has moved away. To do this, I anticipate we will use a quadtree or octree structure. This is a spatial tree in 2 or 3 dimensions where each node is broken into 4 or 8 equally sized smaller nodes to provide better resolution. The tree as a whole will be large enough to contain the entire world. My thinking is that items will be put into the tree at a level that corresponds to how large they are or how far away the viewer should be when they are signaled that the viewer is getting close.
Static/Environment vs. Dynamic/Kinematic
There are two basic types of things that can be added to the world: things that move and things that don't move. The things that don't move are significantly more simple than the things that move and the reason is that the things that move have multiple requirements for "background" code that must be done. Things that don't move are basically geometry that has to fit into the dynamic loading and message passing hierarchy. Things that move also have to have some form of AI that causes them to move as well as some basic kinematic/dynamic code that can deal with interactions between things in the world. Because that goes beyond the required scope of the project, it will be up to you and your interests as to how much of that gets written.
In order for any objects in the world to move or change there has to be intelligent code written to support it. Basically, a moving object needs two extra things written on top of what is required for a non-moving object. It must have code to handle interactions with other objects, it must have some form of AI to govern how it moves, and it must have code that detects and does something about when it runs into other things.
It should also be noted that people could put in other environmental factors like weather, climate, or even wind. Part of doing any of those things though is putting in code that manifests the impact that it has.
Distribution of Labor and Organization
Given the size of the class, you can choose to work in one or two groups. If we have two groups, it is possible one of the projects will be done in C++ and the other will be done in Java, otherwise, students will pick which language will be used though I have reasons to prefer Java for future projects. We will use an agile approach to developing the software with tasks/stories that are assigned to different students for them to complete. Each project will have at least four pieces: rendering/geometry, octree organization, terrain, vegetation. I fully expect that there will be other pieces motivated by the interests that people have. As mentioned above, some of those things will be dynamic/kinematic in nature. For those things to function, it means that some work must be done on collision detection/physics for the world. That will likely be a whole different piece of the project. For this reason, static things will be easier to add, but people might find them less appealing. If you want to do something that isn't stationary keep in mind that you will need to have some other code to back it up and you might consider helping to work on that code.
The objective of this course is teaching you how to do OO programming effectively and part of that includes proper separation of interface and implementation. Development on all aspects of the projects will be done in parallel. For people who are working on the things that go into the world, there will be points in time when you will be working on it and won't have any way to put it in the world or much of a way to view it. This might seem a bit odd and like it would make things difficult, but the idea is that if some basic interface has been set between the pieces, you can write functional code that will only require minor refactoring when things are functional to get them working together well.
Just so you have some idea, I expect that we will all spend at least one hour of class time each week doing development.
Code Handling/Organization and Tests
We will be using Git repositories to keep track of the code this semester. I would also like you to write Unit tests for the project. This will be easy for a Java project in Eclipse because of the functionality of JUnit.
References:
Books I have that you can come and look at for this class
Algorithmic Beauty of Plants (in the library)
Infinite Game Universe (two books)
Algorithmic Beauty of Nature
Swarm Intelligence (two books on this topic)
Other books on graphics, gaming, etc.