Codeforces Round #415 (Div. 2) E. Find a car [or Div. 1 C]

Problem Statement:
Codeforces Round #415 (Div. 2) E. Find a car

Paraphrase:
An integer matrix M is defined as:
M[i][j] = the minimum integer x >= 1 such that:
- M[i][k] != x for all k < j
- M[k][j] != x for all k < i

Example:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Goal: Given a rectangular block in M {(x1, y1), (x2, y2)} and an integer K, compute the sum of elements in that rectangle, but exclude elements whose value is larger than K.

Deterra: A simple game of survival based on Quadtree

I've just finished prototyping a experimental game which makes extensive use of Quadtree for creating the terrain and handling collisions. The game play is simple: there are bombers falling to the terrain and destroy parts of the terrain. How long can you survive before you fall?

Try the game here: Deterra :D

Destructible 2D Terrain Rendering Using QuadTree

When I was in junior high school, I was an addict on playing Gunbound, a Korean turn-based shooting games similar to Worms (but at that time Gunbound was the real thing! haha).

When your shoots hit the ground, it will explode in circular fashion, and the terrain is then destroyed and deformed to the new shaped smoothly. From then on I was quite determined to create the same game, but one thing has always been a hindrance.

 I've always wondered how did they do the rendering on the ground so nicely. When I try to search online for relevant discussion, some suggested using pixel-perfect collision handling, but that is kind of very expensive especially if the map is huge. Then there is a tile-based approach, while it is simple and efficient, it is very limiting in a sense that you cannot have grounds that have arbitrary shapes. Yet the one in Gunbound is arbitrary and natural.

Then I read about rendering terrain using quadtree, and it is awesome! Quadtree is used for keeping track on the "dirt" on the terrain, so each block of pure dirt will get its own node, or otherwise is split into 4 smaller pieces and recursively mapped into the quadtree. The method is really promising and I have just finished a simple implementation of that :D

Here is the link to the demo:
2D Destructible Terrain Rendering using QuadTree

a bit of ds: QuadTree (and Implementation)

A few days ago I made a little implementation on QuadTree on my (still very green) github io page, here is a link: QuadTree Demo

What is cool about this data structure is that like binary tree, it is recursive in nature, so you can write very little code and achieve a highly complex work. I think it is widely use in game programming for collision detections between objects, especially when the number of objects are pretty huge where \(O(N^2)\) check won't cut it.

QuadTree is conceptually very simple. Suppose we have a "quadrant". We will further split this quadrant into four equal parts if and only if there is at least two elements inside this current quadrant. Then we recursively do the same on the four resulting parts. That's it!

For collision detection application, you can determine beforehand how deep is the recursion or how big is the area for which a collision can occur.