Firstly, I want to introduce the team of 7, consisting of:
< ADV > Buy the game! Buy the game! Buy the game!
Producer Joshua Wong
Artist & Level Designer Desmond Wong
Audio Engineer Guo Yuan
Programmer Lee Fang Liang
Programmer Hansel Koh
Programmer Adrian Lim
Programmer Bruce Chia
Secondly, a hypnotising video to make you buy the game:
< ADV > Buy the game! Buy the game! Buy the game!
< ADV > Buy the game! Buy the game! Buy the game!
< ADV > Buy the game! Buy the game! Buy the game!
Our group was very diverse and relatively new to commercial console game development. I would say that we mostly did the game with little prior experience in the commercial world other than some hobby games done on our own personal time.
If you have ever played the game, you will find out that there are no limits to the number of objects (we call them props), such as the orange grabbing thing you see in the video above, that you can place when creating a map in the map editor which happens to be only accessible in the purchased version (that's a hint to buy the game!). Furthermore, each prop will react to the player which is basically a ragdoll made up of several oriented bounding boxes (OBBs). So if anyone is crazy enough to bother to count, you can actually find that a single level may consist of as much as a few hundred of these props, especially in the more complex maps in the later stages. And each of these props has to be collided against the player as expected.
Unfortunately, I'm unable to share everything that I worked on but I will say that I did some optimization for this game. In order to hide the details, the abstracted problem here was that the game started to lag really badly in the physics department as one would expect since there are many objects colliding with each other, some moving and other not. I think this problem is not specific to our game alone and I can think of many other games that could have faced this problem if they used some kind of physics in their game. It definitely boils down to the question of how much your CPU can handle before it becomes slower than the frame rate of a game. We used a physics engine called Farseer and it already provided us with a sweep and prune collider back then (I believe they have improved this since then). In other words, the physics was already semi-optimized but it was not entirely suitable for our case. It was not an easy problem to solve for sure and we wasted at least a week on this, firstly to figure out what was causing the lag, and then later to come up with a solution.
Part of our solution was to basically change the collider to a grid-based one (yay local search wins). This of course was only half the battle won since it helped to reduce the number of collisions with stationary objects but if a game had moving objects, the problem was not so simple since it meant that the moving did not stay within its grid cell for long unlike other stationary objects. Furthermore, if a game had many moving enemies or objects that spawned every second or so and there could be alot of problems of how to make them collide with all the other stationary elements as well as moving ones. Well since this _is_ a computing blog, I would actually like to hear what you would do/ how you would solve this problem if you were building this instead of giving the solution to how we dealt with in our case. I do believe that there is possibly no perfect answer but if you do know of one, please prove me wrong!
In particular, would you manage each moving object in the spatial grid (swapping them from cell to cell as they moved, keeping in mind one box may have to be in two adjacent cells if it is crossing over the edge) or would you separately manage them? And give a brief description of how if possible. So please post your comments below!
However, it really placed us at our toes and made us come up with creative ways to solve the problem. I would also have to admit that the things that I learnt in NUS did help, and at the same time, I would say that what we learn in theories are only foundations and application of the theories is always a different experience.
Lastly, I would like to give everyone a brief introduction to the lab I am working for as I did not do it justice in my previous post.
The Singapore-MIT GAMBIT Game Lab is a five-year research initiative that addresses important challenges faced by the global digital game research community and industry, with a core focus on identifying and solving research problems using a multi-disciplinary approach that can be applied by Singapore's digital game industry. The Singapore-MIT GAMBIT Game Lab focuses on building collaborations between Singapore institutions of higher learning and several MIT departments to accomplish both research and development.
Find out more about it here: http://gambit.mit.edu/campaign/index.php
Posts
2 comments:
Here's my stab at the problem... assuming i understood things correctly.
Assuming that a square grid scheme is in use, we can say that props could spatially occupy between 1 to 4 grid squares. So props may be assigned to more than 1 grid square.
We now consider 2 kinds of moving props, player controlled props, and game controlled props. The difference being the predictability of their motions, we can't tell where player controlled props will move to.
For game controlled props, we just maintain a list of these moving props and perform collision detection for each of them with other props found in the grid squares they overlap. The motions of these props are also predictable, so we may be able to exploit some coherency characteristics in the algorithm. Or alternatively we could use broadly defined collision regions where collision detection "turned on" for moving props only when these props fall within these regions. These regions could be defined during level design.
Since player controlled props will always be used in collision detection, we need to determine the prop's area of influence over the underlying grid. When we have these grid squares, we will be able to find the nearby props to perform collision detection with.
Did i answer the question fully?
I guess I would consider that as the second option, which is to consider moving props separately. This I feel is an easier strategy than maintaining the moving props in the spatial grid.
I think I will explain a little bit more about what I mean by maintenance and separate because there seems to be some confusion.
First of all, you can consider the moving props as the same category, whether they are game controlled or player controlled. This is because it is usually about the _current_ state. Few physics or rather none that I know actually predict the motion of where objects will be in the next frame. It is hard enough to know the current position and decide whether it will collide with anything.
In terms of separately maintaining moving props. I mean that you do not add them to the spatial grid, and instead consider them separately in as a list or other. However, this lacks the advantage the spatial grid gives as it means that each moving prop will have to be tested against all other moving props O(N^2) as you are not sure where the other moving props are.
If you maintain the moving props in the spatial grid. It means that when the prop moves, you will need to update all the cells it belongs to. For example, as it leaves one cell and moves into the next, you need to remove it from the previous cell's list. This is an additional overhead that you have to bear but you get the advantage that the moving props do not need to be collided against each other separately.
I hope that clears things up! Please continue to post which you would decide on!
And thanks shijun for being the first to reply!
Post a Comment