Fixing Selection Box

The original selection box code had some problems and the issue dealt with the fact that your box is drawn as if the grid were a normal cartesian plane but the reality is that it is rotated 45 degrees clockwise. This creates oddity in the coordinates. For instance, which point is more to the "left"? You have to calculate based on "translated" coordinates to figure that out because just looking at only the x or only the y would give you inaccurate results. If you wanted the height of a box that is facing the user in the non-rotated view then you have to translate.

Here's a figure to show what I mean:

And now here is the updated code that draws the selection box properly to the correct size:

                //get the bottom left corner and the top right corner based on the two locations
  std::pair<float,float> firstCorner = std::pair<float,float>(m_firstBoxCorner.first + m_firstBoxCorner.second, m_firstBoxCorner.second - m_firstBoxCorner.first);
  std::pair<float,float> secondCorner = std::pair<float,float>(m_mousePos.first + m_mousePos.second, m_mousePos.second - m_mousePos.first);
  
  float width = 0;
  float height = 0;

  if(firstCorner.first < secondCorner.first)
  {
   width = Ogre::Math::Abs((firstCorner.first - secondCorner.first) * Ogre::Math::Cos(Ogre::Degree(45)));
  }
  else
  {
   width = Ogre::Math::Abs(firstCorner.first - secondCorner.first) / 2;
  }

  if(firstCorner.second < secondCorner.second)
  {
   height = Ogre::Math::Abs((firstCorner.second - secondCorner.second) * Ogre::Math::Cos(Ogre::Degree(45)));
  }
  else
  {
   height = Ogre::Math::Abs(firstCorner.second - secondCorner.second) / 2;
  }


  float leftX = m_firstBoxCorner.first;
  float bottomY = m_firstBoxCorner.second;
  float rightX = m_mousePos.first;
  float topY = m_mousePos.second;

  //secondCorner is left of firstCorner
  if (secondCorner.first < firstCorner.first)
  {
   //move right
   rightX += width;
   topY += width;

   //move left
   leftX -= width;
   bottomY -= width;
  }

  //secondCorner is below firstCorner
  if (secondCorner.second < firstCorner.second)
  {
   //move up
   rightX -= height;
   topY += height;

   //move down
   leftX += height;
   bottomY -= height;
  }

  std::pair<float,float> lowerLeftCorner = std::pair<float,float>(leftX / UNIT_DISTANCE, bottomY / UNIT_DISTANCE);
  std::pair<float,float> topRightCorner = std::pair<float,float>(rightX / UNIT_DISTANCE, topY / UNIT_DISTANCE);

We can use the same logic to figure out the two corners and feed that into our unit selection code. But for unit selection itself there's an additional step which I will call "square picking". Based on the two corners (bottom left and top right) it needs to "pick" the squares that were selected. The issue arises when we get to really small selections, the square picking is much more apparent. Let's take a look at this example:

Maybe in the future I'll implement "fuzziness" to the edges of the selection. Players might not expect that the instant the box touches a square that it selects it. There may be some other "one off" box selection problems but for now I'll move onto context-sensitive right-click. Let's move some units around!

Selection Box

In order to create a selection box, I want a very simple green box. It appears when you press the left mouse button, expands to where your pointer is and knows how to create the box no matter whether your second corner your mouse pointer makes is above/below or to the left or right of your starting point.

To begin, I made a quad. Well actually, I made a set of four lines that made a square and made it unit size. Simple enough.

The input manager handling the UI takes in the mouse input. Wherever the mouse clicks, if it is a left mouse button press then the position is recorded. As long as the button is held down, the box is displayed and the position of the mouse represents the second corner of the box. When the mouse button is released, the box disappears (if it was a left mouse button release).

Okay, so we've the box and it appears where we click. But if we drag we could go and make any of the four other possible corners of a rectangle. The second corner could be the top left, top right, bottom left or bottom right. But that's important. We want to draw our box at the bottom left and then scale it outward to the top right corner so that it is the right size.

Then my next problem is calculating the bottom left corner. Well, if we simply took the lowest x and lowest y, it would be flat wrong. Unfortunately this is isometric coordinates. But, if instead we translated our two corners into the form of

(x,y) => ((x+y) , (y-x))

Now you have the isometric style x and y coordinates that matches what the player sees. As you move right, x+y increases. As you move up, y-x would increase. It is correct... but only enough to determine which is more "left" and which is more "down". You'll notice some weird division going on, it has to do with the fact that you've got a square rotated on the side and I'm trying to determine the length and thus scale the unit sized quad I had before correctly. Also don't be a foolbag like I was and use Ogre::Entity->scale instead of properly using Ogre::Entity->setScale. Yeah, results are not good if you use the wrong method. Hurr.

std::pair<float,float> firstCorner = std::pair<float,float>(m_firstBoxCorner.first + m_firstBoxCorner.second, m_firstBoxCorner.second - m_firstBoxCorner.first);
std::pair<float,float> secondCorner = std::pair<float,float>(m_mousePos.first + m_mousePos.second, m_mousePos.second - m_mousePos.first);
  
float x = m_firstBoxCorner.first;
float y = m_firstBoxCorner.second;
  
float width = 0;
float height = 0;
    
if(firstCorner.first < secondCorner.first)
{
 width = Ogre::Math::Abs((firstCorner.first - secondCorner.first) / Ogre::Math::Sqrt(2));
}
else
{
 width = Ogre::Math::Abs(firstCorner.first - secondCorner.first) / 2;
}

if(firstCorner.second < secondCorner.second)
{
 height = Ogre::Math::Abs((firstCorner.second - secondCorner.second) / Ogre::Math::Sqrt(2));
}
else
{
 height = Ogre::Math::Abs(firstCorner.second - secondCorner.second) / 2;
}

if (secondCorner.first < firstCorner.first)
{
 //move left
 x -= width;
 y -= width;
}

if (secondCorner.second < firstCorner.second)
{
 //move down
 x += height;
 y -= height;
}

Ogre::SceneNode* pSelectionBoxSceneNode = m_selectionBoxEntity->getParentSceneNode();
pSelectionBoxSceneNode->setPosition(Ogre::Vector3(x, y, 0)); 
pSelectionBoxSceneNode->setScale(Ogre::Vector3(width, height, 1));
pSelectionBoxSceneNode->setVisible(true); //hope this call isn't expensive 

Notice that when I get the x,y coordinate it is a bit inaccurate (perhaps off by 1). I might also be able to take the x,y from the original points based on who was more to the left and bottom but I'll have to convince myself of that later.

What do we do? We start our box at the bottom left. Then we scale it out according to the width and height. We use the translated points for that.

Ogre::SceneNode* pSelectionBoxSceneNode = m_selectionBoxEntity->getParentSceneNode();
pSelectionBoxSceneNode->setPosition(Ogre::Vector3(x, y, 0)); 
pSelectionBoxSceneNode->setScale(Ogre::Vector3(width, height, 1));
pSelectionBoxSceneNode->setVisible(true); //hope this call isn't expensive

Then we can use these values to scale our box.

pSelectionBoxSceneNode->setScale(Ogre::Vector3(width, height, 1));

And remember that we needed to rotate our square 45 degrees along the z axis otherwise it'll be an expanding diamond instead of a square!

Ogre::Quaternion boxRotationZ = Ogre::Quaternion(Ogre::Degree(45), Ogre::Vector3::UNIT_Z);
pSceneNode->rotate(boxRotationZ);

Voila

Given what you see here, you might have asked... gee does your selection code from before work? Yeah probably not. Some testing of it last night revealed lots of issues. I believe the above code works much better so I'm going to do the same thing when picking which squares to look at. I'll work on that more later, for now I've made it "work", but the square picking at the edges are terribly inaccurate.

RTS Input

Just wanted to point out a little strange thing I ran into, which is what I consider "syntactic" (although I suppose it is technically not). I wanted to make a std::hash_map using an std::pair. In C++ that most people are using, it seems that if you want to use std::pair then you'll run into a type cast error because it tries to hash a pair object but it can't! You'll have to define your own hash function and use it with the std::hash_map. Poop!

Here is the code if you are interested. This is as simplified as I could make and thus you should replace it with what you need yourself. (Such as a more complicated hash function)

#include <hash_map>

struct hash_int_pair : public std::hash_compare< std::pair<int,int>>
 {
  const size_t operator() ( const std::pair<int,int> &p ) const
  {
    return p.first * 10000 + p.second;
  }

 bool operator() ( const std::pair<int,int> &a, const std::pair<int,int> &b) const
 {
  if (a.first == b.first)
  {
    return a.second < b.second;
  }
  else
  {
    return a.first < b.first;
  }
 }
};

typedef std::hash_map<std::pair<int,int>,std::vector<CUnit>, hash_int_pair> UnitMap;

Anyhow, we move into the world of the basic RTS UI and forget about isometric engine performance right now. We can go back to that when it becomes too slow again. Right now we want to be able to move the mouse around, click, capture the click and translate it into a unit selection box. Nothing fancy. Anything inside the box gets selected. But, there is the standard RTS selection algorithm.

• Select your own units first
• Select enemy units if any, but only the first
• Select animals if any, but only the first
• Select a piece of terrain if it was just a click

Drawing a box around the units is a bit confuzzling due to the rotated nature of the cartesian xy plane. Here is a little excerpt of the mash up code I wrote to just do it. I convert the coordinates into something "rotated" and then convert back and forth as necessary to get the right numbers. This is a bit inaccurate but close enough for now.

Quickly explained, the code basically selects a box along a zig-zagging top, iterate downward to reach the bottom zig-zagging row and then move to the next column toward the right.  I'm quite sure there's lots of problems with this right now but I'm just trying to get mouse picking working initially.

void CFaction::getUnitsByArea(std::pair<int,int> firstCorner, std::pair<int,int> secondCorner, std::vector<CUnit*> &unitsInArea, bool getFirstUnitOnly)
{
//convert coordinates into (x+y),(y-x)
std::pair<int,int> convertedFirstCorner = std::pair<int,int>(firstCorner.first + firstCorner.second, firstCorner.second - firstCorner.first);
std::pair<int,int> convertedSecondCorner = std::pair<int,int>(secondCorner.first + secondCorner.second, secondCorner.second - secondCorner.first);

int leftX = convertedFirstCorner.first < convertedSecondCorner.first ? firstCorner.first : secondCorner.first;
int rightX = convertedFirstCorner.first < convertedSecondCorner.first ? secondCorner.first : firstCorner.first;
int topY = convertedFirstCorner.second < convertedSecondCorner.second ? secondCorner.second : firstCorner.second;
int bottomY = convertedFirstCorner.second < convertedSecondCorner.second ? firstCorner.second : secondCorner.second;

//this is actually too fine grain
int currColumnX = leftX;
int currColumnY = topY;
bool moveDownRight = true;
for (int i = 0; i < (Ogre::Math::Abs(convertedFirstCorner.first - convertedSecondCorner.first) + 1); i++)
{
int jMax = Ogre::Math::Abs(float(convertedFirstCorner.second) - float(convertedSecondCorner.second)) / 2.0f;
for (int j = 0; j <= jMax; j++)
{
//shift down
int x = currColumnX + j;
int y = currColumnY - j;

std::pair<int,int> currLocation = std::pair<int,int>(x,y);

for (int i = 0; i < m_unitsByLocation[currLocation].size(); i++)
{
unitsInArea.push_back(&m_unitsByLocation[currLocation][i]);

if (getFirstUnitOnly)
{
return;
}
}
}

if (moveDownRight)
{
currColumnX++;
moveDownRight = false;
}
else
{
currColumnY++;
moveDownRight = true;
}
}
}

What do in Ogre3d land?  We create a ray based on the mouse position.  Ogre provides an API to do so.  We then calculate it's intersection with the XY plane.  Ogre also has code to do this.  Then we translate the x, y coordinates to a game coordinate (I have a constant called UNIT_DISTANCE in my code).


if (btn == OIS::MB_Left)
{
Ogre::Ray mouseRay = m_nCamera->getCameraToViewportRay(evt.state.X.abs/float(evt.state.width), evt.state.Y.abs/float(evt.state.height));
std::pair<bool, Ogre::Real> intersectionValues = mouseRay.intersects(Ogre::Plane(Ogre::Vector3::UNIT_Z, 0));

Ogre::Vector3 intersectionPoint;
if (intersectionValues.first)
{
intersectionPoint = mouseRay.getPoint(intersectionValues.second);
//translate the intersection point into gameworld coordinates
m_firstCorner = std::pair<int,int>(intersectionPoint.x / UNIT_DISTANCE, intersectionPoint.y / UNIT_DISTANCE);
}
}


And now let's see it!

Okay, so a static image doesn't really help show it. :P

In any case, it will have to be improved with several features.  First, I need to draw the selection box.  Second, make sure the box works no matter how you define the two corners.  Third, add in the ability to use shift and alt clicking which is a pretty standard UI interface.  The selection is somewhat inaccurate due to the weird isometric layout, but I'll just leave it alone for now (also because I box based on actual grid squares instead of something more fine).

Easier IsometricGood

If you read the last post, certainly it seems that was a lot of work just to get blocking to look right. You weren't satisfied? Neither was I! This is my second solution which also works. I wanted to do an alpha check and then a depth check and then decide to overwrite the pixel in a particular square, all the while using batched geometry (and the issues that causes when it draws super quads which overlaps properly between super squares but not between smaller squares).

Ultimately, I've changed the rendering order such that objects that cannot possibly block each other can be written in large batches. I merely have to keep the ordering between layers but not between squares. So I batch up the grass, the bushes, rendering it in order of: terrain, grass, bushes. Then comes the new trickery. I am drawing in 3d but showing a 2d game, so what do? Well, I draw the trees, the only objects that are taller than a square in the game so far, with a little bit of "height".

Try to picture the above across the 2d plane. The squares in the bottom right corner of the map is already closest to the orthographic camera plane because the entire world is tilted 30 degrees downward. Why not use this z-level information to do proper depth checking and z-buffering? The issue was that the default settings is to write every pixel information to the screen no matter the alpha value.

But then there's this in Ogre3d:

pTreeFirstPass->setAlphaRejectSettings(Ogre::CMPF_GREATER, 0, false);

Anything with an alpha channel value of zero is not drawn at all, thus the z buffer doesn't get polluted with magical pixels you can't see. In order to understand why it is a problem let's go back to how it decides the colour value of each pixel.

• Original value is some colour, an alpha value and a z-value of 0. (Remember that nothing writes to the z-buffer, so the z-value is 0)
• NewValue = OldValue * (1 - AlphaValue) + IncomingValue * (AlphaValue)

If the alpha value is always 1 or 0 (which is the case in such 2d graphics), then basically the colour of the pixel is completely overwritten by any new pixel. That is, NewValue = OldValue * 0 + IncomingValue * 1. Therefore, NewValue = IncomingValue. However, what if the incoming value had an alpha channel value of 0? Then the colour remains the same as before. But, if I want my tree quads to record z-value information, then the z-value is overwritten with some new non-zero value. So what do you see on the screen? When it draws the humans it'll see this greater than 0 z-value and thus decide that it "blocks" the human. Yet to you, you see what is "behind" the human. It looks confusing but it's only because when the tree quad is drawn it overwrites the z-value but nothing else and thus blocks anything else from drawing there, yet all you see is grass, not tree.

Now it decides not to draw anything if the alpha channel value is 0, then the z-value is not overwritten. When the human is drawn, then it happily gets drawn overtop the grass, which had a z-value of 0 (that was not overwritten by the tree quad in the square "downwards" from it) but gets blocked when trying to draw overtop a tree that is in front. That is absolutely correct. And thus I avoided having to write some kind of complicated shader to do anything.

In the future I intend to have massive gigantic 5000x5000 maps, which will likely require a simple shader (one that looks at the RGB value of the texture and then draws things specified in a texture atlas... anyway I'll get to that when I have big maps. For now I have small maps so it doesn't matter. EVERYTHING IN MEMORY LIKE I'M A JAVA DEV!)

I may update this post with what I'll do later, but at this point, I'm going to leave the iso-engine alone and optimise it again when I need to (for larger maps or more units). For now, here is a screenshot! Yummy red gazelles and a brown dragon turtle hiding in the forest.