Unit Actions

Well, I am working on having units act upon given commands right now in my RTS game, and I have some questions on how would be the best way to go about some things.

For my game:

Left Mouse-Click == Select Unit
Right Mouse-Click == Have selected unit perform primary action at position of right mouse-click.

Take Age of Empires for example. The left and right mouse clicks in my game perform the same operations. Left selects units, right attacks/moves/gathers.

Also, at the current moment I keep all of my entities in the game stored in a std::vector. This way I can simply iterate through every entity each frame and do the proper updating to each entity. In my Entity::Update() function, the first thing I do is check for left clicks on the mouse. If a left click has occurred, I check to see if it has occurred in the area of that entity. If so, I select that unit. If not, I deselect the unit.

Then, if the unit is selected, I check for right clicks, which imply that the user wants the selected unit to act in some sort of way. Up to now the only action has been to move (as was seen in my recent Alpha demo on my other thread about 1 week ago). That is all well and good, but now I need to add additional actions such as attack and gather (mainly working on attack right now).

Therefore, this is what I have implemented:

Psuedo Code:

Code:

---

if ( Entity is Selected )
{
        if ( Right Click has occurred )
        {
                Get Position on screen in which click occurred;
                Set destination of entity to that position;
                Check to see if enemy unit is at that position;
                if ( enemy exist at position )
                        Set Target to that enemy entity;
        }
}

---

Now, that seems pretty sensible to me. What I am wondering about is how I am implementing my checking to see if an enemy exists at the target location.

At the current moment, I call a function which iterates through the entire entity list and checks the position of each entity. If a certain entity is located at the right-clicked position, and that entity is an enemy of the selected enemy, then I set it as the target entity of the selected entity, and break out of the loop. In essence, it is an O(n) algorithm. This O(n) algorithm is run for every selected unit on the map. Therefore, if every single entity on the map is selected, it is order O(n^2). However, it is highly unplausable that every entity on the map will be selected. At most their might be 25 units selected at a time.

Do you think this is a good way to go about doing things? One obvious optimization is to split the entity list and have a seperate entity list for each player. That will happen later in development, but the project is not yet ready for that.

However, another thought has popped into my mind. I am not sure how efficient it would be, however, and so I thought I would throw it out in front of all of you guys and see what you think. What if, when I update each entity each frame, I look at its world position, and then I go to the physical map and make that specific position on the map point to that entity, basically tying that position on the map and that entity together. Then, when I right click, I simply take the map position, see if it is pointing to any entity, see if that entity is an enemy, and then set it as a target.

It seems efficient, but yet it also seems like it might be complicated at the same time. So what do you think about it?

Also, if you know of any other good methods, what are they?

On a side note:
Since objects proably get destroyed and created often, why don't you use an std::list instead of an std::vector?

Well I've got a solution for you...but you might not like it.

Try using a quadtree.

First store a bounding box for each unit...you probably already have this. Divide your map into a set amount of quads using recursion.

If the unit is not in the quad you are searching...move to its neighbor. You should be able to find the unit in under 5 recursions depending on how deep your tree goes. This will also work for multiple selections -> ie: the bounding box becomes the box that the player draws around the units.

I think this has O(log n) but I could be wrong.

Attached is a DOS quadtree example:

Usage: quadtree <depth>

If depth is too large then a stack fault or out of memory error can occur.
This does not construct a quadtree...it just illustrates what it is doing. To see it go slower simply up the depth to about 10 and you will see what is taking place.

If you want to you can put a getch() in the CreateQuadTree function() to further slow it down. Simply press a key to move to the next recursion.

I read your post twice and I am not sure about the recursive O(n) algorithm. However, you seem to know what youa re talking about so I cannot really comment (I do not personally know what it is).

For a generalized way of implementing very believable entity movement is to simulate a processor for each entity. Each entity has its own instruction pointer, and with the instruction pointer comes an 'operation code'. Then, you get to invent your own instruction set! The operation code typically holds:

A floating point scalar
An opcode identifier
An entity pointer
An integer
A vector

so you have:
struct OPCODE
{
int OPCode;
Vector OPVector;
float OPFloat;
int OPInt;
Entity *OPEntPptr;
}

This seems like a total hack at first, but this is mroe or less how it is done professionally. Think about it, whenever you want to do *anything* with any unit in the world, it must involve one of those datatypes. If not, then you simply dont' use it! For example, you may want to attack an enemy, that requires various things
a) knowing what the entity is (entity pointer)
b) knowing WHERE the entity is (vector)
c) how fast to move towards target persecond (float)

you would then need to enumerate the types of operations:

Code:

---

enum
{
Attack=0,
Move,
Idle,
Patrol,
NumOfInstructions
}

---

Each physical entity will own these things to make this work:

Code:

---


class ENTITY
{
public:
void Update();
static OPCODE instructions[NumOfInstructions]; //all that is needed is to set the OPCode identifier
//with these, which are typically held in either your enum or in #defines of a file
int instructionpointer(0);
int fetch(1); //true / false, tells the simulated process whether or not to fetch a new instruction
OPCODE instruction; //the actual instruction owned by each entity
}

---

then in your handy dandy update function, you do something like this:

Code:

---

if(fetch) //do we need a new instruction yet?
//i.e have we accomplished what we previously wanted to do,
//or, have we quit trying to do what we previously wanted to do?
{
this->instruction = ENTITY::instructions[instructionpointer];
//init values specific to scenario, i.e player position, or new target
fetch = 0;
}

switch(instruction.OPCode)
{
case Attack:
{
//run your program attack code until you kill target or give up
break;
}

case Move:
{
//do stuff
break;
}

case Idle:
{
//DONT do stuff :)
break;
}

}

---

etc etc. I've made several syntax mistakes but its hard to show how this works. When you get it right, it works perfectly. You are starting to go down a road where you manually must check EVERY SPECIFIC condition in the world ALL of the time and things wont happen automatically. Obviously the next instruction pointer you want the program to do is decided upon algorithmically in each of those switch statements. You can have 10,000 possible actions, and depending on the outcome of each action you can branch off to potentially any other action, which is also a basis in neural nets and simulated human response.

and just an example

Code:

---

        case        Attack:
                {
                        if(EntityIsDead(instruction.OPEntity))
                        {
                                instructionpointer = Patrol; //or you can decide to idle, depending on random numbers
                                fetch        =        1; //tell engine to update my instruction set
                        }
                        else
                        {
                                //Calculate attack angles to player, you could even add MORE opcodes such that there is a specific
                                //'calculate pitch and yaw' instruction added to your instruction set, otherwise, you are in attack mode
                                //so continue attacking
                        }
                        break;
                }

---

The very nice thing about this type of implementation is that your recursive 0(n) algorithm can be encapsulated, but more effectively utilized, using this setup. Now if only I could get the whole grammar thing right

He was discussing how to effectively 'find' the unit in the list that has been selected...not how to move them convincingly.

My algo will work super fast. With 10000 units the time it would take is: 4 recursions.

yeah i realized that, but there still needs to be conditions for breaking off the search and coordinating what new actions to take, etc, which is why i thought i could post that junk above :)

doesn't really matter though i guess

I'm kind of interested in this topic, but I don't quite understand your idea, Bubba. So you divide a large quad into smaller ones...Then...um you keep dividing it a certain number of times (based on depth) and search through much smaller quads? I'm having trouble seeing how this could be very efficient.

And what you said makes it sound like he's searching for a specific unit, when it sounded like he was just checking to see if any units were at a specific position.

Maybe I'm just stupid :confused:

Quote:

---

Originally Posted by JaWiB

I'm kind of interested in this topic, but I don't quite understand your idea, Bubba. So you divide a large quad into smaller ones...Then...um you keep dividing it a certain number of times (based on depth) and search through much smaller quads? I'm having trouble seeing how this could be very efficient.

And what you said makes it sound like he's searching for a specific unit, when it sounded like he was just checking to see if any units were at a specific position.

Maybe I'm just stupid :confused:

---

There's a great visual representation at gametutorials.com (though its an oct-tree demo, not quad. same idea though)

check it out Fifth one down

OK I actually checked out http://www.gamedev.net/reference/pro...res/quadtrees/

And I think I understand the basics of it...But I still fail to see how it relates to his problem...

Thanks for the replies guys.

vNvNation, even though your response was not exactly what I was looking for, I do love your idea. Of course I do already have an enum of actions such as ATTACK, WALK, GATHER, etc., but I never thought of implementing them like opcodes. That is definitely an idea I will consider. Thanks for that idea. I like it a lot.

Bubba, thanks for your idea about speeding up my search method. Like JaWib, I don't know much about quadtrees, as I have never used them before. But I think it's time I use them since I have been programming for 6 years now!!! So I will definitely search the quadtree/octtree tutorials that have been posted on my thread and consider using them.

Recently I just purchased Tricks of the Windows Game Programming Gurus from Half Price Books for $12 (I love Half Price books...such great prices!!). I am not sure if it discusses quadtrees in it, but I will check.

Anyways, thanks all for the ideas and help.

I'm glad that you like the idea david. Another thing I wanted to point out for that whole opcode paradigm is that you can break sequences down to cut down on the amount of processing that needs to be done. For example, instead of running the entire algorithm you have for path finding, you might be able to run one or two steps per frame, or base the number of steps you run based on the frame time itself. In this case the OPCode data would hold the results of the last search step you ran. Otherwise, running a complete recursive search of the map to find other entities might take up too much process time, and not leave enough time for rendering (which in a 2D game isn't as much of an issue, but it will be once you start throwing a good amount of entities in there). Obviously, a potential problem can occur because the other entities are always moving, but, it is just an idea.

Quadtrees relate to this because:

1. We know where the user clicked.
2. We have all the coordinates of our units.
3. We know the bounding boxes of those units.

Therefore if the bounding box of the unit clicked is not within a certain quad...we discard that quad. Then we divide the quad that we have determined the unit is in..into smaller quads and do the same check. So on the first recursion you eliminate 3 very large areas that might contain any number of units. You will see why this algo is so fast very quickly.

To visually illustrate. Take a piece of paper. Draw an X anywhere on the paper. Draw a bunch of O's all over the rest of the page. The paper is our map and the X is our unit and the O's are other units. Now divide the paper into 4 equal sections -> tear it in the middle on the horizontal and tear it down the middle on the vertical. If the X is not in the new sections...we discard those sections. Now look at the piece that the X is in. Tear it in half vertically and horizontally. If the X is not in a new piece...discard it. Now take the piece that the X is in...tear it in half vertically and horizontally. Now we should be able to determine where exactly our X is. If not tear it again and do the same check until you get 'close enough' to the X. Our 'close enough' is the bounding box of the unit.

Now take the pieces of paper that have the O's on them. You should have 3 large pieces of paper, followed by 3 smaller pieces, etc., etc. This is because our X is guaranteed to be in at least one of them or one of the quads.

First count the number of O's on the biggest 3 pieces. Now you see how many units we discarded in 1....count it...1 recursion. Very powerful.

Now you see what I'm getting at??


Compile this code and run it. Heck, if you have a version of BASIC you could get this up and running quickly and simply use LINE(x,y)-(x2,y2),color,BF for the boxes or quads.

Code:

---

#define DESIRED_WIDTH 4
 
//This will only work correctly if x and y begin at 0
void CreateQuads(int x,int y,int x2,int y2)
{
  if ((x2-x)<=DESIRED_WIDTH) return;
 
  int midx=(x2+x)>>1;
  int midy=(y2+y)>>1;
  int red=rand()%255;
  int grn=rand()%255;
  int blu=rand()%255;
 
  DrawBox(x,y,x2,y2,red,grn,blu);
 
  //Top left
  CreateQuads(x,y,midx,midy);
 
  //Top right
  CreateQuads(midx,y,x2,midy);
 
  //Bottom left
  CreateQuads(x,midy,midx,y2);
 
  //Bottom right
  CreateQuads(midx,midy,x2,y2);
}

---

I'm still having trouble seeing your point. Wouldn't you still have to search through the entire list of units? I mean, unless you have an array of 10,000 elements (or however many tiles you have) you couldn't just discard the first n elements, because any one of them could be at any position on the map...So like you have a vector to store the units (maybe allocating space for 100 units), even if you put them in order from 0,0 to 100,100 (or whatever) you still can't tell how many of the units are in a specific region without searching the whole thing...

I'm just having trouble seeing how you could design this to work the way you say it would...

typically a section of the world would contain a list of pointers to the entities that are within that particular section. Whenever an object is moved, it undergoes a process called "relinking", where you calculate what parts of the world each object's bounding box lies in, and removing itself from the previous parts of the world it no longer resides in. You do not have to recurse the entire world when you do this. Then, when a mouse click occurs, you only need to
a) recursively calculate where the mouse click occured (this will typically lie in only one part of the world, but could overlap onto several different parts depending on the size of the mouse click bounding box

b) search each part that the moues click resides in and check each of its entities if the mouse click overlaps the entity bounding box

...or you only have to search the first time through. The second search would only search units that passed the first test.

no, you misunderstand! The first search just finds what parts of the world the mouse lies in (it can lie in an arbitrary number, but practically in 2D the most is 4). Then, for every single part of the world the mouse is in, search the pertinent entities to see if the mouse bounding box overlaps the entity bounding box. You must search every one because typically your mouse can overlap more than one unit (if it is enclosed in a box), in that case you want the closest.

Wouldnt something like this work too:
If you always keep track of what units are visible why not store pointers to those units in a list and only search through that list? That would probably reduce the amount of units to search through quite much unless you have like 100-200 units visible at the same time.

Keep in mind that is exactly what we have been saying the whole time...the only way you can find those visible objects is by recursively searching the quadtree

There is no need to find where the mouse is. The mouse is the origin of the system. We test everything against the mouse. It is much easier to test like this instead of first finding the mouse in the tree and then finding the units as well.
We test all bounding boxes of the objects against the bounding box of the mouse. Besides if you search the entire list on the first recursion and then logarithmically reduce the number of units to search....the time involved is still nothing compared to the O(n^2) linear search.

Quote:

---

typically a section of the world would contain a list of pointers to the entities that are within that particular section. Whenever an object is moved, it undergoes a process called "relinking", where you calculate what parts of the world each object's bounding box lies in, and removing itself from the previous parts of the world it no longer resides in. You do not have to recurse the entire world when you do this.

---

Hm so you would have a world object with several different regions and when you move a unit you (possibly) place it into a different region? Or something along that line...Could someone post a basic class design to show how it would be set up?

Download quake2 source
www.idsoftware.com
open project, search (in all files) 'relink' or 'linkedict'