Unit picking

In this article I’ll try to explain how the object picking works in KaM Remake, why is it worse than in classic KaM and how it is going to get better in next release. Proceed inside if you are interested to learn how does the game knows where the mouse click has landed. Images and technical details included.

Tile-based picking (current approach)

Essentially games logic operates with a grid. The map is a 2D rectangular array that consists of square tiles. Much like in chess, each unit is taking exactly one tile (houses take several tiles, but for now we will not touch them). The height effect in KaM is mostly aesthetical, it affects tiles passability, but it does not affect units travel speed or how many units can stand on one tile. When a click happens the game would convert cursor position from screen space to maps 2D grid space and if the clicked tile has a unit it will be picked. In other words this means that if you wanted to pick a unit you had to click on a tile where that unit is standing right now:

The blue quad shows the area you had to click in order to select pikeman that is standing on it. As you can see that area does not matches his body shape that well. If you clicked on his head the click would go to the empty tile above and nothing will get picked. The situation is even worse if you wanted to pick a walking unit. The place unit is located is rounded to a nearest tile. Notice how far archers flag carrier is from the place where you need to click to select him:

Imagine players frustration clicking on a unit and getting nothing or another unit. Is there a way to solve this problem? Even in old KaM unit selection was pixel-perfect. We know it’s possible, but how?

Pixel-testing (vanilla KaM approach)

Old KaM could do pixel-perfect picking because all the games sprites were in system memory. CPU had direct access to pixel data. That means the game could hit-test sprites that are drawn under the cursor right in the drawing cycle. Here’s the pseudo-code how it may have looked like:

//Render all visible sprites
for i := 0 to VisibleSpriteCount - 1 do
begin
  //Render the sprite
  RenderSprite(Sprite[I]);

  //Fast test if cursor is within sprites rectangle
  if InRect(Cursor, Sprite[I].Rect) then
  begin
    //Get exact cursor position within sprites rectangle
    PX := Cursor.X - Sprite[I].X;
    PY := Cursor.Y - Sprite[I].Y;

    //Check if there's opaque pixel in that position
    if Sprite[I].Pixels[PX,PY] <> 0 then
      //Remember picked sprite
      Cursor.Object := Sprite[I].Object;

    //If there's any sprite above it will get picked instead
  end;
end;

//We don't have KaM source codes, so that's just an idea

However with KaM Remake that is not gonna work because we use OpenGL for render which operates with GPU and GPU memory. On games startup we load the sprites from the disk only to pass them to video memory, as soon as that’s done we flush them from system memory (that’s some 140mb saving). Afterwards sprite data is not directly accessible to the CPU. Of course we could try and read that back from video-memory, but this is quite slow operation since GPUs are made with directional data transfer in mind. Proper GPU approach is slightly different. Since drawing on GPU is practically free, we can employ so-called “color-picking” technique.

Color-picking (new approach)

Color-picking is named so because we ask GPU to draw different objects with different colors to a “selection buffer” which is invisible to a player. We are going to render a bunch of sprites that are already in GPUs memory (which is practically free operation). Then we read just one pixel that is under the cursor and knowing its color we can easily detect to which of the rendered objects it belongs.

From talk to rendering – each active object has an unique ID in the game. We take that ID and encode it into RGB color. Here’s result:

As you can see there are some issue: Trees (that are rendered in black, because they have no IDs) occlude the soldiers. Opaque trees almost prevent player from picking soldiers behind them. This is not good for the player, because he will not be able to pick soldiers in woods. Serfs arms are rendered separately without an ID, they should inherit serfs ID. On the other hand units shadows should not be pickable. Each issue is easy to deal with by different techniques. After fixing these minor issue we have the following picture in our “selection buffer”:

How is it looking from the implementation point of view?

 Technical side

After normal frame is rendered as usually to the back buffer and swapped to display we fill everything with black (black means no ID) and render objects sprites once again, but this time we don’t show it to the player. Only the game has access to the render result and read the pixel color under the mouse cursor.

First tricky part is to make OpenGL to render opaque texture pixels with a flat color we need. For that we use this clever bit of code found at StackOverflow:

//Render textures without semi-transparency.
//Anything below 0.9 will be discarded (i.e. shadows)
glEnable(GL_ALPHA_TEST);
glAlphaFunc(GL_GREATER, 0.9);

//Texture will not be blended with background
glBlendFunc(GL_ONE, GL_ZERO);

//Set up custom combining mode where texture color is ignored
glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_COMBINE);
glTexEnvi(GL_TEXTURE_ENV, GL_COMBINE_RGB, GL_REPLACE);
glTexEnvi(GL_TEXTURE_ENV, GL_SRC0_RGB, GL_PREVIOUS);
glTexEnvi(GL_TEXTURE_ENV, GL_SRC1_RGB, GL_TEXTURE);
glTexEnvi(GL_TEXTURE_ENV, GL_OPERAND0_RGB, GL_SRC_COLOR);
glTexEnvi(GL_TEXTURE_ENV, GL_OPERAND1_RGB, GL_SRC_COLOR);

For each sprite we set up a color that will represent its ID. Typical OpenGL render offers 24 bits for RGB values. We can split the ID into bytes and code this like so:

//SHR is bitwise shift to the right
glColor3ub(ID and $FF, ID shr 8 and $FF, ID shr 16 and $FF);

We also discard any inactive objects (trees and flags mostly). Here’s what we get in the selection buffer in the end:

Now we can read the pixel under the cursor with a glReadPixels procedure and combine its RGB values back into an ID. That ID belongs to a unit that is standing there.

That’s it. Now you know another improvement that will be in the next KaM Remake version. Thanks for reading! 🙂