QuadTreeGood, SelectionBoxGood, HarvestingGood

Cultura now has harvesting of nodes in it. Next I'd like to work on these items:

• QuadTree for unitsByLocation and structuresByLocation member variables inside Factions
• Fixing... selection box problems again
• Item graphics to be used for when a unit is carrying an item or when a structure holds items

The QuadTree will just be as basic as possible, I'm using it mostly for distance checks but also selection box. I may add non-QuadTree methods like findClosestSomething given a source location.

• Vector of items
• Four QuadTree children
• Insert
• Subdivide
• QueryRange

The QuadTree will have a vector of items in it and also four children (which will be NULL at the start).

Insert will add the item to its children if it is in the range. If the capacity has been reached it then tries to add it to its children instead (creating them if necessary).

Subdivide creates four children that divides out the area of the current node into four equal parts

QueryRange will return the items in the node if the range specified falls within the quad. It then calls the same on all of its children and adds those items to its vector and then returns that. It should probably take in a vector* and create a new vector if it is NULL, which will eliminate the problem of having to create/destroy vectors in the recursive calls of QueryRange.

This function could also be used to find the closest "something" to a particular location. It could call QueryRange with that location as the range, so any items within nodes that hold that location would be returned. This gets me at least all the items in the same node as the location and also more that are around it. Then I simply do a distance check with all those items. Runtime should be n log n.

I'm contemplating only leaf nodes having objects within them. Additionally (which I have left out for now) I want kd tree for structures. Structures don't move around, thus there is no expensive tree balancing but they have excellent nearest neighbour algorithms (versus the mashing of my quadtree I will have to do to get the same level of performance). However, since for early stone age the only structures I expect are resource piles and caves, which are regularly abandoned when you need to move from land region to land region (to avoid exhausting resources), I'm not doing the kd tree until later. I'll call this "iterative development" instead of "I'm too lazy to do this shit right now".

I'd like to point out that the quad tree I am showing here is: very simple and splits the header file into two files. It's a templated class so everything has to be done inline but it doesn't mean your file arrangement can't still mimic a .h and .cpp split.

I am QuadTree:

#pragma once

#include <utility>

template <class T>
class CQuadTree
{
protected:
 std::vector<T> m_items;
 int m_capacity;

 CQuadTree<T>* m_topRight;
 CQuadTree<T>* m_topLeft;
 CQuadTree<T>* m_bottomRight;
 CQuadTree<T>* m_bottomLeft;

 std::pair<int,int> m_lowerLeftBound;
 std::pair<int,int> m_topRightBound; 

public:
 CQuadTree();
 CQuadTree(int capacity, std::pair<int,int> lowerLeftBound, std::pair<int,int> topRightBound);
 virtual ~CQuadTree(void);
 
 void insert(T item, std::pair<int,int> location);
 void subDivide();
 void queryRange(std::pair<int,int> lowerLeftBound, std::pair<int,int> topRightBound, std::vector<T>* itemsFound);
 void remove(T item, std::pair<int,int> location);  

 std::pair<int,int> getLowerLeftBound();
 std::pair<int,int> getTopRightBound();
};

#include "QuadTree.inl"

I am QuadTree inline file:

template <typename T>
CQuadTree<T>::CQuadTree()
{
 m_topRight = NULL;
 m_topLeft = NULL;
 m_bottomRight = NULL;
 m_bottomLeft = NULL;
}

template <typename T>
CQuadTree<T>::CQuadTree(int capacity, std::pair<int,int> lowerLeftBound, std::pair<int,int> topRightBound)
{
 m_capacity = capacity;
 m_lowerLeftBound = lowerLeftBound;
 m_topRightBound = topRightBound;
 m_topRight = NULL;
 m_topLeft = NULL;
 m_bottomRight = NULL;
 m_bottomLeft = NULL;
 m_items = std::vector<T>(); 
}

template <typename T>
CQuadTree<T>::~CQuadTree(void)
{
}

template <typename T>
void CQuadTree<T>::insert(T item, std::pair<int,int> location)
{
 if( !(location.first >= m_lowerLeftBound.first && location.second >= m_lowerLeftBound.second 
  && location.first <= m_topRightBound.first && location.second <= m_topRightBound.second))
 {
  return;
 } 

 if (m_items.size() < m_capacity)
 {
  m_items.push_back(item);
  return;
 }

 subDivide();
 m_topRight->insert(item, location);
 m_topLeft->insert(item, location);
 m_bottomRight->insert(item, location);
 m_bottomLeft->insert(item, location);
 return;
}

template <typename T>
void CQuadTree<T>::subDivide()
{
 if (NULL != m_topRight)
 {
  return;
 }

 int halfx = (m_lowerLeftBound.first + m_topRightBound.first) / 2;
 int halfy = (m_lowerLeftBound.second + m_topRightBound.second) / 2;

 m_topLeft = new CQuadTree<T>(m_capacity, std::pair<int,int>(m_lowerLeftBound.first, halfy), std::pair<int,int>(halfx, m_topRightBound.second));
 m_topRight = new CQuadTree<T>(m_capacity, std::pair<int,int>(halfx, halfy), m_topRightBound);
 m_bottomLeft = new CQuadTree<T>(m_capacity, std::pair<int,int>(halfx, m_lowerLeftBound.second), std::pair<int,int>(m_topRightBound.first, halfy));
 m_bottomRight = new CQuadTree<T>(m_capacity, m_lowerLeftBound, std::pair<int,int>(halfx, halfy));
 
 return;
}

template <typename T>
void CQuadTree<T>::queryRange(std::pair<int,int> lowerLeftBound, std::pair<int,int> topRightBound, std::vector<T>* itemsFound)
{
 //the query should start at the root and we need to have the same vector for all subsequent calls
 if (NULL == itemsFound)
 {
  itemsFound = new std::vector<T>();
 }

 //check if bounds intersect
 if(lowerLeftBound.first >= m_lowerLeftBound.first && lowerLeftBound.second >= m_lowerLeftBound.second 
  && lowerLeftBound.first <= m_topRightBound.first && lowerLeftBound.second <= m_topRightBound.second)
 {
  for (int i = 0; i < m_items.size(); i++)
  {
   itemsFound->push_back(m_items[i]);
  }
 } 
 else if(m_lowerLeftBound.first >= lowerLeftBound.first && m_lowerLeftBound.second >= lowerLeftBound.second 
  && m_lowerLeftBound.first <= topRightBound.first && m_lowerLeftBound.second <= topRightBound.second)
 {
  for (int i = 0; i < m_items.size(); i++)
  {
   itemsFound->push_back(m_items[i]);
  }
 }

 if (m_topRight)
 {
  m_topRight->queryRange(lowerLeftBound, topRightBound, itemsFound);
 }

 if (m_topLeft)
 {
  m_topLeft->queryRange(lowerLeftBound, topRightBound, itemsFound);
 }

 if (m_bottomRight)
 {
  m_bottomRight->queryRange(lowerLeftBound, topRightBound, itemsFound);
 }

 if (m_bottomLeft)
 {
  m_bottomLeft->queryRange(lowerLeftBound, topRightBound, itemsFound);
 }
}

template <typename T>
void CQuadTree<T>::remove(T item, std::pair<int,int> location)
{
 if( !(location.first >= m_lowerLeftBound.first && location.second >= m_lowerLeftBound.second 
  && location.first <= m_topRightBound.first && location.second <= m_topRightBound.second))
 {
  return;
 } 

 //this removes the item but does not perform delete
 int size = m_items.size();
 std::vector<T>::iterator iter = std::remove(m_items.begin(), m_items.end(), item);
 m_items.erase(iter, m_items.end());

 //only perform if we have not yet removed an item
 if( size == m_items.size())
 {
  if (m_topRight)
  {
   m_topRight->remove(item, location);
  }

  if (m_topLeft)
  {
   m_topLeft->remove(item, location);
  }

  if (m_bottomRight)
  {
   m_bottomRight->remove(item, location);
  }

  if (m_bottomLeft)
  {
   m_bottomLeft->remove(item, location);
  }
 } 
 return;
}

template <typename T>
std::pair<int,int> CQuadTree<T>::getLowerLeftBound()
{
 return m_lowerLeftBound;
}

template <typename T>
std::pair<int,int> CQuadTree<T>::getTopRightBound()
{
 return m_topRightBound;
}

For the selection box, I revisited it due to some problems I had. Namely, small square selections needed small fixes and large square selections weren't getting the right height/width. I do all the calculations inside the InputManager. Basically, the first problem was that I needed to calculate width and height using the original coordinate values. Previously I would pass the two game-coordinate corners to the selection algorithm but rather than fix that I instead put the calculation inside the InputManager which had the raw coordinates. Second problem was the offset that could occur depending on where the box started in a square. Third, the width distance is not the same as the height distance since it's across the square. Height is the same but due to the 45 degree rotation, you multiply it by cosine 45 and it comes out to the length of a square side (lucky!).

First we look at what the width and height values are:

Next let's look at what we really want. You'll notice that width is much larger than actual width because when the grid is rotated we want to catch the squares inbetween each column and thus the width is much larger. Height stays the same. (We could have made height much larger and width the same)

We get the width and height of the selection box. Then we adjust for where in a square you clicked. This may add upwards to 1 unit of distance to width or height.

Okay next we want to catch the squares which you just selected the tip of, which we do by ceiling the value of width and height.

Finally, we adjust width to add those inbetween columns. We simply add width - 1 to width.

For visual cues surrounding the carrying of items by units and structures that fill up with goods, I was thinking of adding another entity for the graphics. All of my units and structures derive from the same base class baseUnit. That has a virtual function called giveItem. Upon giving a unit some items and it accepts it, it should then determine whether or not the graphics of what it is holding should be changed. Likewise when it loses items (perhaps a takeItem function?) it should update graphics as needed.

Huzzah!

Now, here are some further issues I want to tackle.

I want to display an for where you click, for moving and other actions. There may be different colour x and whatnot to signify the different actions. Each x is created separately, shown and then hidden after some amount of time. The UIInputManager has a function that is called each frame rendered which has the timeSinceLastFrame in milliseconds. This would allow me to track time passed and hide the entity as needed. If I want to get real fancy, each x is tracked separately to allow you to create a lot of X's (much like how in Starcraft you would see many indicators of where you clicked).

I made units only capable of carrying a single item to make harvesting easier. I don't think that condition should remain. If they have capacity then they should take on stuff. I will have to change harvesting to match this difference. When they do a drop-off they must drop off each item they have until complete. It may mean that during drop-off the site is full or cannot take the other items and thus the unit must go to another drop-off site. The only difference in the code is that a unit must check if empty and if not empty, attempt to drop off the item at the front of the carried items list.

Next I had made items have two ids. An item id and a material id. An item id is like "vase", "pottery", "chair". A material id is like "oak", "pine", "lavastone", "limestone". A resource node would then contain an item and I had it such that item id was "oak" and material id was "oak". That's not really all that correct I think. Instead I will change it so that item ids are resource categories and material is then specifically "oak" or "pine".

As an example, a tree would have an item inside it. The item id is "wood", the material id is "darkwood". I'll make these ids as global const int and in a shared header. I want to make them as simple integers because then nothing needs to recompile if they don't need to look at specific constants. The only place I expect those constants to be directly accessed is in world generation code (that doesn't exist yet outside of test functions). As I add more ids, nothing will recompile (I hope). So a set of ids will be used for raw resources and then the rest for intermediate goods and finished goods. Thereby I don't need to add any more integers to an item to determine what it is and how it can be used.

Similarly, I wanted to add terrain ids. I could bucket these ids into ranges that represent how much they slow down a unit's movement. I'll likely add the slow-down later. However, impassibility could be something simple like if id < 10000 then passable terrain.

Most of the new graphics will be cheap-outs. That is, I'll draw iron node and then iron ore. Then I'll colour it green and bam! New resource called viperstone.

Resources nodes are grass, bushes and trees. They would be all over the place and it would be difficult not to click on them. So I was thinking maybe I need to change right click context to be a "move" command in more cases than it currently is. Right now, only if you click on an empty spot does the unit move there. Given the way the graphics look it's not readily apparent (especially lacking visual cues) that you just told a unit to harvest. And... I don't even think it's entirely expected. Instead I'd rather "hotkey" h to be harvest (I don't have a UI menu, so keyboard shortcuts are what is available for now). The only time it is harvest then, is if you pressed h (key up event) or if you told them to attack an animal.

Another thing to add a sense of industry was the need to process animals. Now, at first I would have liked hunters to kill an animal and then drag the whole animal back to your cave. But then problems with AI and carry limits abound. I can do that but I think it's just overkill. Most people are used to typical RTS style harvesting. If you kill an animal it becomes a pile of resources which you "collect" from. But I can add this in; you collect carcass and not straight up material.

For example, you kill a deer and then harvest it. You then collect "deer carcass" off of it. Following changes from above, the item id is deer carcass but the material id is stuff like "deer meat", "deer bone", "deer skin" and so on. You have to process the "deer carcass" and then it becomes "meat" / "deer meat", "bone" / "deer bone", "furs and skins" / "deer skin". And then you can use that to craft other items.

It was just a neat added level of "realism". I was reading about the Norse in Greenland (who eventually died out there) and how they would go on northern hunting trips to kill walruses (and also caribou). The walruses provided valuable ivory tusks but they needed to be processed (I wasn't clear on what processing the tusks meant other than it was a lot of work). Then once processed, they would sell it to arriving European trade ships for valuable goods such as timber, iron, stained glass or stone (okay, valuable only to the Greenland Norse because their land sucked so much).

This means that resource nodes could have one item (a single item id and a single material id associated with the item), but animals would have a list (a single item id which was "blah carcass" and then multiple material ids to represent the range of stuff an animal would provide). Also this makes a bit easier to determine what you get out of an animal. It's walking around (when alive) with that list of items already inside it, so some things might have antlers (bone), tusks (not sure what category I should put ivory in but bone sounds good), fur, skin and so on.

Generally I don't want to make an engineering-overkill factory class to generate me various animals. If I want to create a new deer and place it on the map, I'd have to know how much meat, bone, skin and so on that it contains. Where to keep that information? Well I'll probably create a class whose sole task is to generate various different stuff. I'm wanting to create 4 mundane and 4 fantasy stuff of each "thing", so that's really only 8 animals. Would I really want to create the infrastructure of a factory class just to make 8 different animals? Nah, an if-else or case switch is good enough (until it's not then I think about what I want to do). Similarly, this class should have methods to create animals, bushes, trees and so on. There's only eight of each type right now so I think it's okay. One way or another I have to write a lot of code for each one. This should be data-driven to be completely honest but uh... not doing that for now. No real excuse.