Collision detection trick.

Imagine you need to collide large groups of soldiers that moves all the time. Use of spatial structures in this case became a pain because of update times. To overcome this we've developed simple solution (I believe it used widely in modern physics engines for broad phase).

Consider picture below (we are looking on 2D version, but algorithm will work in 3D as well). We want to collide two circles:

Simple radius check is good enough in this case. But if you want to collide 1K circles - it will just become impractical. So, what about this colored lines on picture?

Red lines represent left bounds of each object on each axis and green lines represent right bounds. To detect possible collision between all objects on grid, we can perform the following.

Push all bounds to two arrays, one for each axis. Sort arrays by bound position. Iterate through arrays with logic:

• For each left bound consider object as open.
• For each right bound consider object as closed.
• For any bound met ->
• For each opened object ->
• Put potential collision bit into bit-table.
• Repeat for next axis.

If both tables are now show that there is potential collision between two objects (both bits are set) - perform radius check and report collision, if any.

To extent this method, presort bounds of groups of objects (for example units of soldiers). To perform collision between any groups you can do cheap mix of presorted arrays to avoid sorting of very large arrays.

Draw a forest.

While working on our first title in MindLink Studio ("Telladar Chronicles: Decline"), we've set one very ambitious goal for that times: be able to show like 20K soldiers clashing on battlefields. With full 3D representation of everything. Back in 2002 we didn't seen anything like this yet.

I had an obvious idea of using sprites for lowest LODs to be able to draw such a large world. After few years of development and experimentation I've ended up with following solution.

When you need something to be drawn at distance, you ask sprites rendering subsystem to provide you with sprite representation of this. If something already in cache - you're done.

In opposite case subsystem considers size of the thing and selects place for it in sprites cache. This textures are divided on rows of predefined height and it selects one with best smallest row height. It injects sprite into the row, modifying row linked list. Rows contents is managed by subsystem like in any common memory manager. To wipe the row if it become too fragmented just copy it's content to another row, updating the sprites vertexes.

After getting sprite representation, LOD system injects four vertexes into dynamic storage. Great thing about this approach - you can fire-and-forget about your sprites. As long your sprite is alive - it will be rendered in batch with others. And you can just ignore updates for distant objects for any amount of frames (nobody ever will notice this on great distances).

To erase the sprite - ignore it when constructing your next ping-pong index buffer. To reuse the space in vertex buffer - make sure enough frames passed from the moment it was used last time.

In this way we were able to draw forests with hundreds of thousand of trees at real time, still providing nice 3D trees at close distance.

Soldiers was a bit tricky, as you need to animate them to look believable. After months of visual tests I've came to conclusion that you need to provide only 2-3 frames of walking animations to "shimmer" on distance.

Forest in action:

Lighting is a bit outdated. Still there is something like 30K trees in viewport with 30 FPS on SM1 hardware.

Toolset.

Fast thought after visiting one of the numerous Ubi development studios around the globe:
The only way to create exceptional game is to have exceptional tools.

[We thank you, Cap!]
[Applauds]

Seriously. No good tools? No good AAA game for you, sorry.

And the reason behind is pretty obvious: less time per iteration == more iterations for the same budget. More iterations means greater quality. Greater quality means increased value to your customer and increased sales. Profit.

But there is one trick involved. Interfaces and processes for this tools should be built by UI usability experts, not programmers or artists or anybody else. And the good news is - you can find plenty on IT market. I'm wondering why most of the studios ignore this fact?