Tuesday 20 November 2012

Text Adventure Games C++ Part 3

Verbs introductory
Once again picking up where I left off, this time for a little action, as in verbs. Check my previous posts on the subject of Text Adventures; FIRST POST and SECOND POST. And here is what I am going to cover this time around.

1. Implement some simple VERBS.
2. Get the parser to handle a verb.
3. Demonstrate a sub procedure from the parser (the LOOK procedure).

So, once again, enumerated types come to the rescue here. Using the completed source code from my previous post as a starting point, I will specify some enumerated identifiers for some VERBS. Right after en_ROOMS, I globally set the following verbs...

enum en_VERBS {GET, DROP, USE, OPEN, CLOSE, EXAMINE, INVENTORY, LOOK};

That is, eight verbs. These are pretty common verbs in text adventures. I am not going to get all of them working in the parser by the end of this post, but just "sample"; LOOK.

For the purpose of looping through the verbs (should it be necessary at some stage), I am also going to define a global constant for them, right after const int ROOMS in the source code...

const int VERBS = 8;

Now, verbs will reutilize the word structure that was previously used for directions, in order to set the words and assign the code identifiers for the verbs. In main(), before the loop, I will declare that new array, and call a function to set the verbs...

// In main()
    word verbs[VERBS];
    set_verbs(verbs);

// Function to set the verbs...
void set_verbs(word *vbs)
{
    // Reminder GET, DROP, USE, OPEN, CLOSE, EXAMINE, INVENTORY, LOOK
    vbs[GET].code = GET;
    vbs[GET].word = "GET";
    vbs[DROP].code = DROP;
    vbs[DROP].word = "DROP";
    vbs[USE].code = USE;
    vbs[USE].word = "USE";
    // and so on, see the source code in the link for the rest...
}

Great, I have some verbs set. Now, to use them. But first, the parser must receive the list of verbs as a parameter, so this modification is in order.

// Where the parameters of the parser function read...
bool parser(int &loc, string wd1, string wd2, word *dir, room *rms)
{
    // code...
}
// It will now read...
bool parser(int &loc, string wd1, string wd2, word *dir, word *vbs, room *rms)
{
    // code...
}

And the call to the parser from inside the loop in main() will pass verbs as a parameter...

// Where the call was...
parser(location, word_1, word_2, directions, rooms);

// It will now be...
parser(location, word_1, word_2, directions, verbs, rooms);

With that I am all set to start interacting on a very basic level with some of the verbs held in the array. A good starting point is the LOOK verb. It is common in all adventure games I ever played, and is a simple one word command that the player enters. It is also a good example here because it will be an exceptional case of sub proceduralizing something out of the parser. Generally, my own rule of thumb is to make a procedure for anything that may be used by more parts of a program than one. LOOK could be used twice by the program, for example;

1. When the player types LOOK as a command, and;
2. Automatically invoked whenever the player changes location from one room to another.

Okay, I will move into the parser and do that "trapping" of the VERB. In the parser I will declare a local variable to catch the verb that is passed to it, using my old NONE as -1 to initialize it...

// In the parser function...
int VERB_ACTION = NONE;

And now the simple "verb trap", which is nothing more than a for() loop that compares word_1 (wd1, as passed) to the list of verb words. When a word coincides, it assigns the code of that verb to the variable VERB_ACTION and breaks out of the loop. If no coincidence at all occurs, then the variable VERB_ACTION remains as initialized (NONE). Here is that chunk of code, to be placed in the parser function right after the direction for() loop...

    for(i = 0; i < VERBS; i++)
    {
        if(wd1 == vbs[i].word)
        {
            VERB_ACTION = vbs[i].code;
            break;
        }
    }

And with that I can go on to examine the variable VERB_ACTION. The first logical thing to do would be to deal with a value of NONE, that is to say, the player did not enter a recognized verb.

    if(VERB_ACTION == NONE)
    {
        cout << "No valid command entered." << endl;
        return true;
    }

Personally, I would put this condition check at the very end of the parser function and all other condition checks above it, but that's just me. Now for the LOOK command condition check, which upon validating true simply calls the look_around() function...

    if(VERB_ACTION == LOOK)
    {
        // This is an example of sub proceduralizing a function from the parser.
        look_around(loc, rms, dir);
        return true;
    }

And here is that function...

void look_around(int loc, room *rms, word *dir)
{
    int i;
    cout << "I am in a " << rms[loc].description << endl;
   
    // LOOK should also allow the player to see what exits exist from the current room.
    for(i = 0; i < DIRS; i++)
    {
        if(rms[loc].exits_to_room[i] != NONE)
        {
            cout << "There is an exit " << dir[i].word << " to a " << rms[rms[loc].exits_to_room[i]].description << "." << endl;
        }
    }
}

That can all be compiled and tested now. Not much, as yet. I can walk around my map, and use one "verb" command. But the stage is set to move onto to the next phase, on next post. That is, nouns, better known as items or objects.

Here is the complete source code for what has been done this time around.

And here is a figure of the running program.



That's all for now.

Saturday 10 November 2012

Text Adventure Games C++ Part 2


So, moving on (quite literally for this post) I am picking up where I left off from my last post (entering commands), and am here am going to design a game map and move around inside it with some basic commands. Before actually diving in and trying to program the map, it is a good idea to draw out a map of my world, something like this...


It should go without saying, at this point, that anyone writing an "adventure game" should already have an engrossing "adventure story" in mind.

I will keep it simple. Exits from a room will be only north, east, south and west. I will not do any northeast or up or down type of thing here (though there is no impediment for doing so in more complex maps). First I will number my rooms, from 0 to 10 (that is, eleven rooms). I will also consider my exits to be from 0 to 3, going around clockwise from north (0). Now the problem with using numbers as identifiers is that I will need to write down what each one "equates to" on a sheet of paper and keep track of it all the time I am programming. For example;

0 is a SPORTSHOP
1 is a CASINO... and so on,

...for the rooms, and for the directions...

0 is NORTH,
1 is EAST... and so on.

This is the perfect sitaution for using enumerated types. So, first thing; at the top of my code, just after the #includes, I will declare some enumerated types globally for the directions and the rooms...

enum en_DIRS {NORTH, EAST, SOUTH, WEST};
enum en_ROOMS {SPORTSHOP, CASINO, CARPARK, LOBBY, RESTAURANT, CORRIDOR, STOREROOM, POOL, GARDEN, POND, PUMPROOM};

const int NONE = -1;
const int DIRS = 4;
const int ROOMS = 11;

I will also want an identifier for NO EXIT; check out the map, not all rooms have exits in all directions. I will use a constant integer -1, above declared as NONE. Also, for the purpose of looping through the DIRECTIONS and ROOMS, which will probably be required later on, I will set their number with another couple of constants, DIRS and ROOMS.

Now the programming will be instantly easier to understand. In pseudo code...

if direction commanded is 1 and location is 2 then
    location = 3

...is certainly more difficult to follow than...

if direction commanded is EAST and location is CARPARK then
    location = LOBBY

The Map
But that is just an example. For now, it would be convenient to make a global structure for holding information about each room. And while I am at it, a global structure for words, which will be a multipurpose structure to hold both directions and verbs (ie; basically commands). So, under those constant integers, I will code this;

struct word
{
    string word;
    int code;
};

struct room
{
    string description;
    int exits_to_room[DIRS];
};

That is a basic minimum for each of those structures. I will come back to the word structure in a minute. For now, I want to focus on the room structure. First it has a description. That is just a line of text that offers a description of the room itself, for example "car park". It will be displayed in the game for the player to know where he (or she*) is. The exits_to_room variable, on the other hand is an array, and is the size of the number of directions that the game handles (ie; four of them). Each room has four exits. It does not matter that some of these exits in the game do not exist for specific rooms (for example, you cannot go south or west from the carpark). That is what the NONE constant is for. The exit is still there, it just cannot be used in the game.

Just as a note, exits_to_room should be considered as "room interconnectivity". That is to say (normally) if room 0 exits south to room 2, then room 2 should exit north to room 0. I know deeper consideration of this can lead to ideas of all sorts of weird maps that have exits leading to unexpected rooms, but I sincerely think that it is generally NOT a good idea to deliberately confuse the player like this. The adventure should be the challenge, not the map, unless there is a very good reason why part of the map should be a challenge (for example, the player dies but the game continues with him/her in a strange Labyrinth of the Underworld, trying to get back to life. Heh! Heh! A "serving suggestion").

With that clarified, I will continue and "set" all the rooms for the game. This first requires an array of the structure room to be created in main(). So, somewhere in the beginning of the main() block, before the while() loop, I create;

room rooms[ROOMS];
set_rooms(rooms);

That second line in there is a call to a separate function that is yet to be made, and which will set my rooms characteristics (that is, its description and its exits). Here is that function, in part (see the full listing at the end of this post for the complete version).

void set_rooms(room *rms)
{
    rms[SPORTSHOP].description.assign("sports shop");
    rms[SPORTSHOP].exits_to_room[NORTH] = NONE;
    rms[SPORTSHOP].exits_to_room[EAST] = NONE;
    rms[SPORTSHOP].exits_to_room[SOUTH] = CARPARK;
    rms[SPORTSHOP].exits_to_room[WEST] = NONE;

    rms[CASINO].description.assign("bustling casino");
    rms[CASINO].exits_to_room[NORTH] = NONE;
    rms[CASINO].exits_to_room[EAST] = NONE;
    rms[CASINO].exits_to_room[SOUTH] = LOBBY;
    rms[CASINO].exits_to_room[WEST] = NONE;


    // ...and so on untill all rooms and their exits are completed.
}

Take care doing this. The structure array is passed to the function, and the number of rooms described in the function simply MUST not exceed the size of the array (const int ROOMS), or bad things will happen to the program when it is run. When adding or removing rooms to the map (say, if I want to expand the game) I must first change the value of the global ROOMS, then edit the enumerated type en_ROOMS to include (or suppress) rooms, and finally edit the rooms and their exits in this set_rooms function.

So great, I have my map now, but it would be nice to move around it, too. Here is where I will take the first step in bringing together the command interface from the previous post with what I have done so far on this post. For this, I will start to create that thing which is the heart of an adventure game, from a programming point of view. The Parser.

The Parser (Rudimentary)
So. What is the parser? It is a block of code (I am going to create it as a separate function) that takes a command entered by the player, interprets it, and then executes the command. It can be very lengthy. Efforts can be made to reduce its core size by "proceduralizing" it somewhat (other, smaller sub functions), but I will not worry about that for now. The parser must recognize "words", the structure for which has already been created above. In this case, the parser will receive either one or two words (a direction or a verb and a noun). There will be much more about the parser in future posts; this time around? Well, it stays simple. It will receive direction commands only, so that I may at least navigate my map.

A good place to start, therefore, would be setting the "words" (directions, in this case). So, inside main(), I declare the array of the structure word as directions.

word directions[DIRS];
set_directions(directions);

...and I then write the function that sets the directions...

void set_directions(word *dir)
{
    dir[NORTH].code = NORTH;
    dir[NORTH].word = "NORTH";
    dir[EAST].code = EAST;
    dir[EAST].word = "EAST";

    // ...and so on, through SOUTH and up to WEST.
}

Now that I have set the directions that I will use, I need the way for the player to actually employ them through text commands. Basically, this means that when the player types "east" and presses enter, the program will take the word and check the current room for exits, and if there is an exit to the east, it will transport the player's location to that room. For this to happen, I am first going to need a variable that actually holds the players current position. I will call it the "location" variable, which makes it instantly recognizable. It gets declared and initialized at the top of the main() function...

int location = CARPARK; // using the enumerated type identifier, of course.

Further down in the main() function, inside the while loop, below the section_command() function call, I will call the parser() function, like this...

parser(location, word_1, word_2, directions, rooms);


Now I will actually write the rudimentary parser function itself...

bool parser(int &loc, string wd1, string wd2, word *dir, room *rms)

{
    int i;
    for(i = 0; i < DIRS; i++)
    {
        if(wd1 == dir[i].word)
        {
            if(rms[loc].exits_to_room[dir[i].code] != NONE)
            {
                loc = rms[loc].exits_to_room[dir[i].code];
                cout << "I am now in a " << rms[loc].description << "." << endl;
                return true;
            }
            else
            {
                cout << "No exit that way." << endl;
                return true;
            }
        }
    }
    cout << "No valid command entered." << endl;
    return false;
}

Taken from the top. I create the parser as a bool function. At the moment that is not a very useful thing to do, but when that parser grows, returning a boolean may well be a useful method for error trapping later on. It does no harm at present.

I then declare a local integer (i) to enable me to loop through commands. In this case, I start by looping through the directions. What I am doing is causing the program to compare what the player entered (and was passed to the parser as word_1) with the data for the member word in the structure directions. If word_1 coincides with a word member in the structure, then we have a hit, and the parser then checks if there actually is an exit form the current location in that direction (it checks the exits_to_room member of the room structure). If the result is something other than NONE, then there is an exit there, and the location variable (passed referrenced so that the function can permanently modify it) is moved to the room in that direction, using the directon code. It offers a description of the new room, and breaks out of the function, returning true. If there is no exit in the entered direction, the parser simply states so, and returns. And finally, if nothing that the player entered is recognized by the parser, then it returns false, telling the player that no valid command was entered.

Though not apparent here, this method of using the word structure "code" instead of the "word" itself can considerably shorten the coding of the parser. Eventually, it will permit the use of synonyms, expanding the possibilities of what the player may enter as an acceptable text command. For example, a command like "GO" may also be expressed as "WALK", but both words will have the code GO, making the parser do the same thing for two different words that mean the same thing.

The program can now be compiled and tested. I can now move around my map, entering simple direction commands like north, or east. Hooray! I am going places!

Here is the code of what was done for this post.

Here is a sample out put of what happens when the program is run.



Next time, that parser will be expanded a little, and introduce verbs. As yet, it is only using word_1 of the entered text, and that word must be a direction for the present parser to accept it.

That is all, for this post!

Sunday 4 November 2012

Text Adventure Games C++ Part 1


So, it has been a while again. Oh! How the demands of my job keep me from my beloved hobby!

In the continuing exploration of C++, though short of time lately to really get into more intricate subjects, I decided to revert to something simpler and, surprisingly, never tried before by yours truly. Text adventures. Why this is surprising is two-fold. One: The first ever game I played (on someone's Commodore Vic 20, lent to me for one afternoon sometime back in 1981 or so), and indeed my first ever experience of computers, was a text adventure (and it was to be my only experience of computers until my own Spectrum in 1986) . Two: It turns out to be quite easy to write a simple console style text adventure with the power of C++. Everyone should try it; it is fun!

Warning: I decided to tackle the challenge completely unprimed; that is to say, without reference to any books or tutorials about the subject, in order that it be a test of my "problem solving abilities". Therefore, the results on this post may not be "standard", if such a thing exists, for text adventures.

First Steps:
As far as I was able to deduce, text adventures are initially about two things, from a programming point of view. First, handling input text and second, moving around a map. Things like getting, dropping and using objects, and the occurrence of events in the adventure, will come later.

Though I can see now that handling text strings could have been a little bit of a chore previously (in the days when text adventures were first popular), with the tools available in C++, it is pretty much a simple task. The idea goes something like this;

1. The player inputs a line of instructions.
2. The program divides the line into individual words.
3. The program interprets the words and checks if the instruction makes any sense.
4. The program executes the command, if it makes sense, or by default informs the player that the command made no sense.
5. The program loops back to asking for a command to be input by the player.

The first item is very easy, using C++'s standard iostream and string.

#include "iostream"
#include "string"

using namespace std;

int main()
{
    string command;
   
    while(1 == 1) // Temporary condition for now...
    {
        command.clear();
        cout << "What shall I do? ";
        getline(cin, command);
        cout << "Your raw command was " << command << endl;
    }
    return 0;
}

I do not recommend compiling and running this fragment because of the infinite loop in the while statement, but this is as simple as simple gets for inputting a command. Now there are a few considerations, as I am about to move into the second item of the list; dividing the line into separate words. The first consideration is; how many words of the command do I want to be actually interpretted? For this example I want to keep it as simple as possible. By that I mean that I only want to interpret one or two words of the command, which restricts the player to either inputting a direction or a verb and a noun. For example, the player can input at the comand prompt...

What shall I do? north

or...

What shall I do? get keys

So, if the player inputs something like...

What shall I do? go get a club and hit yourself over the head with it

...will result in the program only interpretting the words "go" and "get", which will be an invalid command input. Straight off the bat we can see that some ground rules are established. With that in mind, I will continue to expand the above snippet. I need to make a function that will section the raw command line into one or two words. So, first the expansion of main()...

#include "iostream"
#include "string"
#include "vector" // For the command handling function.
#include "cctype" // Will be used to eliminate case sensitivity problems.

using namespace std;

int main()
{
    string command;
    string word_1;
    string word_2;
   
    while(word_1 != "QUIT") 
// I have provided an escape condition from the loop here
    {
        command.clear();
        cout << "What shall I do? ";
        getline(cin, command);
        cout << "Your raw command was " << command << endl;
        word_1.clear();
        word_2.clear();
        // Call the function that handles the command line format.
        section_command(command, word_1, word_2);
       
        // For test purposes, output the command after formatting by the function.
        cout << word_1 << " " << word_2 << endl;
       
    }
    return 0;
}

I have added vector and cctype headers, and two more strings (word_1 and word_2). These strings will hold the two words I want from the sectioned command line, for later parsing. In the while loop I also call a function (section_command) and pass it three arguments (command, word_1 and word_2). Here is that function, which does as its name implies; it sections the command.

void section_command(string Cmd, string &wd1, string &wd2)
{
    string sub_str;
    vector words;
    char search = ' ';
    size_t i, j;
    // Split Command into vector
    for(i = 0; i < Cmd.size(); i++)
    {
        if(Cmd.at(i) != search)
        {
            sub_str.insert(sub_str.end(), Cmd.at(i));
        }
        if(i == Cmd.size() - 1)
        {
            words.push_back(sub_str);
            sub_str.clear();
        }
        if(Cmd.at(i) == search)
        {
            words.push_back(sub_str);
            sub_str.clear();
        }
    }
    // Clear out any blanks
    // I work backwords through the vectors here as a cheat not to invalidate the iterator
    for(i = words.size() - 1; i > 0; i--)
    {
        if(words.at(i) == "")
        {
            words.erase(words.begin() + i);
        }
    }
    // Make words upper case
    // Right here is where the functions from cctype are used
    for(i = 0; i < words.size(); i++)
    {
        for(j = 0; j < words.at(i).size(); j++)
        {
            if(islower(words.at(i).at(j)))
            {
                words.at(i).at(j) = toupper(words.at(i).at(j));
            }
        }
    }
    // Very simple. For the moment I only want the first to words at most (verb / noun).
    if(words.size() == 0)
    {
        cout << "No command given" << endl;
    }
    if(words.size() == 1)
    {
        wd1 = words.at(0);
    }
    if(words.size() == 2)
    {
        wd1 = words.at(0);
        wd2 = words.at(1);
    }
    if(words.size() > 2)
    {
        cout << "Command too long. Only type one or two words (direction or verb and noun)" << endl;
    }
}

This function uses both vector and cctype functions. The cctype function toupper() is used to turn any lower case letters in the command line into upper case. This process is to simplify the internal workings of the program. All text commands in the program will be interpreted in upper case, but the player is still free to input lower case.

I want to go through that function bit by bit. I am going to use a space character to split the words of the command line, as it can be (reasonably) safe to assume that the command line will be input with spaces between words. A local substring will be used to "collect" the letters of each word in the command line, while no space occurs, and when a space occurs, it will push the substring (containing the word) into the local string vector. The substring is cleared, and the process is repeated for the next series of letters, either up to the next space, or to the end of the command line string, whichever happens first. By the end of the process, I will have a local string vector loaded with the individual words of the command line.

That said, there is at least one possible and plausible problem. If the player, by typo mistake, entered more than one space between words, the above method will "collect" and pushback a blank word into the vector. In a rudimentary effort at error trapping, I will endevour to eliminate the occurence of these blank words. I search through the vector strings, from end to beginning (ie; backwards) looking for such blank words. If one is found, it is erased with an iterator reference from the beginning of the vector (note, I do not actually use an iterator, just the reference that is normally used to set an iterator). Yes, a bit crude, as there are other ways to do this, but doing it this way exempts me from having to reinitialize the vector iterator every time the vector changes size because a blank word was eliminated.

Next, the remaining words in the vector need to be converted to upper case (as explained why above, and will become clearer later). The loop goes through each character in each vector string looking for the occurence of lower case characters and converting them to upper case.

Finally, the first two words of the string vector only are returned to the main loop by the function (wd1 and wd2). The rest of what was written on the command line is, basically, wasted time by the player. So, why do I go through the trouble of "collecting" all the words in the command line? Future expansion! One day, I might want to create a text adventure that accepts more complex commands, like for example "open door using crowbar", instead of just "use crowbar". The section command function is already up to meeting that challenge as it is now.

So, the program may be compiled and run now. I will have a console application that prompts me for a command and, after entering it, shows me the first two words of that command in upper case. Not very exciting, as yet, but more is coming on this somewhat archaic but none-the-less fun subject.

Click here for some code of what has been done on this post.

Here are some references to the headers used in this post...
cctype
vector
string
iostream
more on vector

And here is a sample output of the program so far...


Next time, navigating a game world map, where the enum types really come into their own!

That's all, for now!


Thursday 2 August 2012

Basic Trigonometry in Coding C/C++

As I missed putting up a post for July, it is time I put up a post or two during August on this "semi-abandoned" blog. I have been busy with work, and though I have been doing the odd bit of coding, I have not had the time to compose a post for here. Nevertheless, here I am now.

Nothing special this time. Just a review of some vital 2D trigonometry. There is little doubt that there is something slightly amiss with me, as I wake up each day as a blank sheet with regard to what I did or learned the day before, I have the bad feature of forgetting even important things until I refresh my memory with some trigger or another (and several coffees and a Red Bull). This post will my C++ trigonometry trigger!

There will be no tags for this post to aid searching, as it is a bit of a personal rant. If you are someone other than me reading this, then you stumbled in on it. Don't worry, you may read it, if you like - just don't think of it as any sort of "lesson", please. There are many, much better, "learn trigonometry" pages out there.

I'll start with the easiest thing. How does the computer figure trig? Well, quite normally, in essence. If I plotted a point using sin( ) and cos( ), this is what the computer "thinks" of as angles (in radians, of course)...


...and to convert Radians to Degrees (and vice versa), the following formulas may be used...

Degrees = Radians x (180 / Pi)

Radians = Degrees x (Pi / 180)

Now it is a bit of a pain in the backside (if you are programming games that use maps) that, first; you must use radians instead of degrees, and second; your natural "north" (ie; 0.0) is pointing over to the right of the screen instead of up. However, no real hassle, as a little bit of coding can produce a neat header like this one of mine to circumvent these problems, but that's another story.

What are tan( ), atan( ), and atan2( )?
First, here are the docs;
tan
atan
atan2

They speak for themselves. I want to cover the basics here. Here is a right angled triangle...


Now, I always had some trouble learning things other people's way. All that blah-blah about a line off a circle and such did not (ever) explain to me what a tangent was.

A TANGENT is simply the length of one of the (right-angle) sides of the triangle divided by the other, basically ignoring the hypotenuse (c). It gives you (and is essentially) the ratio of the dividend to the divisor.

So, one tangent is;

28 / 46 = 0.608695
...the other is;
46 / 28 = 1.642857

...and that's what all the hullabaloo is all about. Think of it as a fraction, if you like (28/46 or 46/28), and that is basically it. Think "The Ratio of the Side of the Triangle which is the Numerator to the side Side of the Triangle which is the Denominator in your Fraction".

That ratio can recover the length of either of the sides if you know the other side's value.

28 / 0.608695 = 46
...and...
46 x 0.608695 = 28

Want to know the value of angle (A)? That is where ArcTangent comes in. Feed it the fraction...

Atan( 28 / 46 ) = 31.33º  or  0.546788 rads

...and you get the value of Angle (A). How about angle (B)? Feed it the other fraction.

Atan( 46 / 28 ) = 58.67º  or  1.024007 rads

The Tan() function can be used if you know either of the angles formed by the right angled side with the hypotenuse. It will give you the ratio of the side OPPOSITE the angle you feed it...

Tan(58.67º)  = 1.642772

That's angle (B), giving us the ratio of side (b), with a small rounding error :).

And if you know is the angle, let's say (A) and any of the sides, lets say (a), you may directly use the tangent of that angle and the known value to calculate the adjacent...

28 / Tan(31.33º) = 46

Yeah, because Tan(31.33º) is simply 0.608695. Looks familiar now? No worries. Now; want to see an example of going nowhere?

Atan( Tan( 31.33º ) ) = 31.33º

Heh! Heh! Heh! Heh!

But now I want to clarify a difference (C/C++) between atan( ) and atan2f( ). This snippet shows what happens when we attempt to get the angles of 8 points from an origin of zero, using both atan() and atan2f();

Pastebin_Sample_1_Link

So, let's have a look at that. Once the program is run it becomes immediately apparent that atan() and atan2f() seem to provide different answers for points 0, 6 and 7. Or do they really?


In reality, no. The difference is that atan's answer handles the angles as four quadrants (4 x 90º), alternating positive / negative twice, and atan2f as two semi-circles (2 x 180º), one positive and one negative. In short, if you used atan instead of atan2f, you would need to do some quadrant differentiation (explained later on in this post), something that becomes unnecessary with atan2f. So, the latter is more convenient for game programming.

In fact, some other trigonometric functions (like sine and cosine) will handle the whole 0.0 to 6.28318 radians, without resorting to a negative and a positive half arc. This is even more convenient, but you will need to - or should - correct the results of any atan2f return (if your program uses it) to conform. Fortunately, it is easy...

if(angle < 0.0f)
{
     angle += (M_PI * 2);
}

...and, essentially, you are away.

What are sin( ), cos( ), asin( ) and acos( )?
Again, the docs...
sin
cos
asin
acos

But first, a quick anecdote of the sort of stupidity I am capable of. In school, back in 1984, I hated trigonometry and never really understood it, as the teachers were equally as incapable of explaining it in a way I could relate to. Two years later I had my first computer. Suddenly mathematics was exciting, and I wanted to write my own games. Unfortunately, the only memory that remained of trigonometry was this thing of Pythagoras;

Hypotenuse = Adjacent² + Opposite²

So, I wanted to make a game where a ship sailed from port to port. I struggled and figured out this bit of code;

Pastebin_Sample_2_Link

Well, it wasn't quite THAT bit of code. It was in Spectrum BASIC, but the algorithm was the same. What I had done with the lines...

    float x_ratio = x_dist / slant_distance;
    float y_ratio = y_dist / slant_distance;

...was re-invent sine and cosine. A bit later on, about a week later, I thought to myself; 

"Wouldn't it be nice if there was a function that did that calculation?" 

And then I rediscovered (that is, partly recalled through the fog of forgetfulness in my head), ArcTangent, Sine, and Cosine. I believe this "rediscovery" of trigonometry is well in among the "Top Ten Most Joyous" moments of my existence. Here is the alternative code..









Enough nostalgia...

Here's my sample graphic;



So, the Sine and Cosine are simply the result of dividing the length of the opposite or adjacent - of angle (A) - by the hypotenuse. In the graphic, a triangle is formed inside the circle. The hypotenuse (c) is equivalent to the radius of the circle, 32 cm. On a 2D Cartesian graph, the center of the circle is at points (0,0). Point (pt), where the radius (hypotenuse) ends, the values on the x and y axes are, respectively 24.5 cm and 20.6 cm.

Dividing the opposite by the radius will give the ratio of the distance (pt) is along the y axis, in relation to that radius. This is the Sine.

20.6 / 32 = 0.64375




Dividing the adjacent by the radius will give the ratio of the distance (pt) is along the x axis, in relation to that radius. This is the Cosine.





24.5 / 32 = 0.76563


So, the Sine is related to the opposite, and the Cosine to the adjacent. That needs to be borne in mind, because the same applies for the ArcSine and ArcCosine, which will provide us the value of angle (A), much like ArcTangent did for Tangent.

If you are using the Sine value, utilize ArcSine, feeding it the fraction Opposite / Hypotenuse.

Asin( 20.6 / 32) = 40º  or in radians,  0.699 

...and if you are using Cosine value, utilize ArcCosine, feeding it the fraction Adjacent / Hypotenuse.

Acos( 24.5 / 32 ) = 40º  or in radians,  0.699

So, barring some rounding precision errors, using the Cos( ) and Sin( ) functions with angle (A) should produce much the same Sine and Cosine values as were calculated above.

Sin( 40º ) = 0.64412

Cos( 40º ) = 0.7660

So, how is that useful? Multiply each by the hypotenuse and you will get the displacements along the y and x axes that represent point (pt).

Y = Sin( 40º ) x 32 = 20.57

X = Cos( 40º ) x 32 = 24.51

So, shall I be silly now? If we don't know the length of the hypotenuse, but we do know the angle and the length of the opposite (y axis displacement), we can shuffle the formula around to calculate the hypotenuse...

20.57 / Sin( 40º ) = 32.0

And finally, how to go nowhere again....

Asin( Sin( 40º) ) = 40º

Acos( Cos( 40º ) ) = 40º

But wait, there's more! Get this now and you take away additional two items of trigonometry trivia, totally free, today;

Acos( Sin( 40º ) ) = 50º

Asin( Cos( 40º) ) = 50º

What? Why? Well, basically, both Sine and Cosine deal only with angles up to 90º, so obtaining an ArcCosine of a Sine or an ArcSine of a Cosine will give you the remainder of the angle to complete 90º.

But, hey, that raises a question, doesn't it? In game programming, we almost invariably have to deal with the whole 360 degrees (or better said, the whole Pi x 2), and not just 90º. No worries. The position of the point relative to its origin will fall in one of four quadrants, each of a 90º arc...



Most of the time, we will be feeding sin( ) and cos( ) radians in game programs. The problem can be solved by feeding them the radians as depicted in the very first figure of this post (two semi-circles). Notice that computer screens have your normal Cartesian coordinates reversed on the Y axis, counting up as the go down the screen. X is normal. The maths, however, is still standard. 

Some proof? Here is a runnable snippet of C/C++...


Pastebin_Sample_4_Link

The "angle" is negative, in radians. If the code is run, you will notice that the Y coordinate moves away from zero in the negative direction. If I plotted those coordinates on a screen, the point would be travelling diagonally UP and to the RIGHT.

Run it with; 

float angle = -2.35619f;

Where is the point going to go?

Or better still, feed it this...

float angle = 3.92699f;

...it's the same thing! Compare.


Why not? C++ handles it, now. I seem to remember some other languages (Spectrum BASIC, if I am not mistaken) did not, which required some serious quadrant differentiation to get things going the way you wanted them to go.

However, do be careful with asin() and acos(). They WILL return to the four quadrants format, and will require some interpretation by the code to get thing absolutely right. Try this;

float angle = asinf(sin(4.71237)); 
// That is, we are giving it 270 degrees (in radians 4.71237) and expecting it to give back
// the same 4.71237. But it gives us minus 1.57078, equivalent to minus 90 degrees...

Oops! We need to correct for the quadrants. The next two code samples will attempt to clarify this "problem"...

WITHOUT correction (plain straight asin)...

Pastebin_Sample_5_Link

And now, WITH quadrant correction...



Pastebin_Sample_6_Link



The above snippet converts the asin() tendency to treat the full circle as four quadrants of 90º into a full 360º positive degrees (or as it really is, 0.0 to 6.28318 radians). Here's a figure to further clarify...




Note that acos() treats the circle much as asin() does, generally, and requires a similar correction itself, but there is no reason to go into that right here, as it is much the same sort of thing, and not difficult to figure out once the above is understood. 

So, that wraps that up. Now, onto something else; the Cosine Rule.

Cosine Rule
There are no C/C++ functions for this. The Cosine Rule is a very real world sort of application, where you might be able to measure the length of the three sides of a triangle, but cannot accurately measure the angles. It is also real worldly in that it does not necessarily have to deal only with a right angles triangle. Joy!

So, I am a surveyor and I measure the sides of a piece of land. The dimensions are;

a = 75 m, b = 110 m, c = 60...


...but I don't know what any of the angles in the corners are. So, the first thing to remember about the Cosine Rule (and indeed, the Sine Rule) is that it always refers to the side opposite the angle. In other words, the angle that "makes" the other side. For example, angle (A), by virtue of the lengths of side (b) and (c), makes side (a).

So I want to find angle (A). The formula is this, and it is saying, if you read it, almost exactly what I wrote in words above;

( ( c² + b² ) - a² ) / (2 x c x b)

Let me do that;

( ( 60² + 110²) - 75² )  /  ( 2 x 60 x 110)

( ( 3600 + 12100 ) - 5625 )  /  13200

( 15700 - 5625 )  /  13200

10075  /  13200  =  0.76325

Okay, that answer is the Cosine of angle (A). Get the ArcCosine of that, and you have the angle.

Acos( 0.76325 ) = 40.25º

Ace, right? The other two angles are obtainable by the same method;

Cosine of Angle (C)  =  ( ( 110² + 75² ) - 60² )  /  ( 2 x 110 x 75 )

Cosine of Angle (B)  =  ( ( 60² + 75² ) - 110² )  /  ( 2 x 60 x 75 )

Sine Rule
Like the Cosine Rule, this handles non-right angles triangles, too. And it can be quite useful for some situations in games, especially for sorting out interception angles. But, before we get to that, what is Sine Rule, or at least, how does it work?

The Sine Rule states that (look at the figure above, in the Cosine Rule section again);

Side (a) / Sin(A) will give you the same answer as Side(b) / Sin(B), and Side (c) / Sin(C) is also the same thing.

a / Sin(A)  =  b / Sin(B)  =  c / Sin(C)

Well simple, then. Do notice, it all has to do with the sides opposite the angles, which stands to reason as we are dealing with Sine, after all. The Rule is used this way around to determine lengths of unknown sides. So, I know that;

Side (a) = 75 m, and I know Angle (A) = 40.25º and Angle (B) = 108.63º. This is enough information to give me the length of Side (b)...

75 / Sin(40.25º)  =  b / Sin(108.63)

116.077 = b / 0.9476

b = 116.077 x 0.9476

b = 109.99

With rounding errors, but yeah, 110 meters, which is right. You may call the result of 75 / Sin(40.25º) - that is, 116.077 - the "magic number" of this triangle, if you like. It is going to be the same result for any of the sides.

Want Side (c)? Simple. I know two angles and I know that the internal angles of ANY triangle add up to 180º. So straight off the bat, I can obtain Angle (C)...

C = 180º - (40.25º + 108.63º)

C = 31.12º

And with that, I am armed to keep using the Sine Rule to obtain the length of Side (c). I already know from the previous computation that the "magic number" is 116.077, so I may reuse it here...

c = 116.077 x Sin(31.12º)

c = 59.99 m

And that's that. Or is it? I can ALSO use the Sine Rule to determine ANGLES. It involves turning the Sine Rule on its head, like this...

Sin(A) / a  = Sin(B) / b  =  Sin(C) / c

So, I know two side and an angle. For example,

Side (a) = 75 m and Side(b) = 110 m, and Angle(B) = 108.63º

I want Angle (A)...

Sin(A) / 75  =  Sin(108.63º) / 110

Sin(A) / 75 = 0.00861456

Sin(A) = 75 x 0.00861456

Sin(A) = 0.6461

A = Asin(0.6461)

A = 40.25º

So yeah. That's about it, really. Here's another code snippet that uses Sine Rule to calculate an interception course. Have fun relearning in the future! I know you will...

Interception_Code

Bye for now!



Saturday 31 March 2012

Allegro 5.1 / OpenGL Heightmap Loader

Back again after a break from coding, enforced by work (alas). This time I am here with some more OpenGL and something I always wanted to tackle; heightmaps. Again, I am using Allegro 5.1 as the API, and decided to use some of A5's features to accomplish the task. Two of the neat things about A5 for this purpose are the al_get_pixel() and al_unmap_rgb() functions, which allow you to get the pixel color and extract them into their rgb components, perfect for reading heightmaps. Also, to speed up the reading of a bitmap, pixel by pixel, there is the al_lock_bitmap() function, which turns the bitmap temporarily into a memory bitmap. It all helped. Now, I decided to use greyscale images, which each shade is represented by an equal value of the rgb components (eg; mid grey might be something like r = 128, g = 128, b = 128), so I would only need to use one of the components.

All that is very well, but I also had another objective; that my heightmap loader be able to read (and convert into terrain) any size of bitmap, so that I would not be restricted to reading only 100 x 100 or any other fixed size greyscale heightmap. To accomplish this, I decided to use STL vector, so that any size in total pixels could be stored in the vector, depending on the dimensions of the loaded heightmap bitmap. The basic idea is that each pixel will represent a point of terrain, with 3D Cartesian coordinates, where, the X and Y dimensions of the bitmap will be the respective OpenGL X and Z coordinates, when multiplied by a land_scale factor, and the color will be the elevation (OpenGL Y coordinate), the lighter the grey, the higher the elevation. Here's the heightmap I made for the experiment...


Originally, my intention was to use GL_TRIANGLE_STRIP to make the terrain, but around the web I found reports that it showed some (speed) inferiority when compared to using straight forward triangles with the now familiar glEnableClientState() function, so I dispensed with the idea of using GL_TRIANGLE_STRIP, and quite happily, too, as I was not too fond of it really.

So, that constitutes the preamble of the conditions I set myself for declaring mission accomplished. As per usual, the full code listing is posted at the end of the discussion. I will get to it, now.

The first task would be to load the bitmap, read the pixels, and create the 3D coordinates for each point. This is, really, the easy bit. Here's a code snippet...


vector<GLfloat> verts;

int BMP_WIDTH;
int BMP_HEIGHT;

ALLEGRO_BITMAP *ht_bmp = al_load_bitmap("landtile.jpg"); // load the heightmap.
ALLEGRO_COLOR ht_pixel;

int bmp_x = 0;
int bmp_z = 0; // the Y axis of the bmp, really, but considered "z" for conversion to OpenGL coords.

GLfloat land_scale = 5.0f;
GLfloat height_scale = 100.0f;
GLfloat height_true = 0.0f;

unsigned char r, g, b; // To store the retreived r,g,b components of each pixel.

// here I get the dimensions, in pixels, of the loaded heightmap.

BMP_WIDTH = al_get_bitmap_width(ht_map);
BMP_HEIGHT = al_get_bitmap_height(ht_bmp);

// In the full listing, there are a couple of "autocentering variables here, omitted in this snippet.
// Also, in the full listing, look out for the al_lock_bitmap() around here.

So, I now have my heightmap loaded and the program knows the bitmap's dimensions. Each pixel (point) needs to be "expanded" into 3 place holders for the x,y,z coords.

// Reserve the space in the vector, which is a good practice, with the total number of coordinate place holders...
verts.reserve(size_t(BMP_HEIGHT * BMP_WIDTH * 3)); // An x,y,z for each pixel read.

// ..and populate the verts vector...
for(bmp_z = 0; bmp_z < BMP_HEIGHT; bmp_z++)
{
    for(bmp_x = 0; bmp_x < BMP_WIDTH; bmp_x++)
    {
        verts.pushback(GLfloat(bmp_x * land_scale)); 

        // Get the "height" of the OpenGL Y coord according to the "color" of the pixel...
        ht_pixel = al_get_pixel(ht_bmp, bmp_x, bmp_z);
        al_unmap_rgb(ht_pixel, &r, &g, &b); // Thanks, Tomasu!

        height_true = GLfloat(float(r) / 255.0f) * height_scale; // Uses only the red component...
        verts.pushback(height_true); // Assign the value to the vector.

        verts.pushback(GLfloat(bmp_z * land_scale));
    }

}

al_destroy_bitmap(ht_bmp); // Once the values are stored in the vector, no further need for the bitmap.

So yeah, the height of the bitmap times the width times three will create the required number of places for the x, y, z for each pixel.
Now, to continue, I will be using the OpenGL glDrawElements() function. This, essentially, does the same thing that I did manually on this post. that is, connecting the points by indexing. Basically, it works this way;

glEnableClientState(GL_VERTEX_ARRAY);
glVertexPointer(3, GL_FLOAT, 0, verts);
glDrawElements(GL_TRIANGLES, points_count, GL_UNSIGNED_INT, points);
glDisableClientState(GL_VERTEX_ARRAY);

Looks pretty simple. verts is the array that holds the vertices of each point to be connected, in sets of three (x,y,z). points is the order in which the vertices need to be connected to make the triangles. But hang on. I need to generate those connection points automatically. I will look at a simplified version of the problem. Here is an array of the points, considered a multidimesnional array, but really a contiguous vector.



25 points (0-24), in this case, gives me 16 squares into which I need to draw 32 triangles. First step, I need to reduce 25 to 16. So, BMP_WIDTH is 5 and BMP_HEIGHT is 5. I can get 16 very easily...

(BMP_WIDTH - 1) * (BMP_HEIGHT - 1) = 16



And I can draw the triangles very easily using the triangle pair count (which is the 16 that I got). First triangle...

vector<GLuint> points;

for(i = 0; i < triangle_count; i++)
{
    // Triangle 1
    points.push_back(i);
    points.push_back(i + 1);
    points.push_back(i + BMP_WIDTH);
    ....

And the second triangle...

    //Triangle 2
    points.push_back(i + 1);
    points.push_back(i + BMP_WIDTH);
    points.push_back(i + BMP_WIDTH + 1);
}

Going around counter clockwise. But there's a problem. Every time the calculation gets to the end of a row, it needs to skip a triangle pair in order to start drawing a new row, otherwise I get the last triangle of the first row warping across to the first triangle of the second row.


I need to have a dummy number to skip at the end of each row, so that the drawing of the triangles breaks. I modify the triangle count by the number of rows of squares, which is, indeed, the (BMP_HEIGHT - 1). So triangle count looks like this...

triangle_count = ((BMP_WIDTH - 1) * (BMP_HEIGHT - 1)) + (BMP_HEIGHT -1);

And implement a row skip counter (call it width_count). The function now looks like this...


int width_count = 0;
triangle_count = ((BMP_WIDTH - 1) * (BMP_HEIGHT - 1)) + (BMP_HEIGHT -1);

for(i = 0; i < triangle_count; i++)
{
    if(width_count == (BMP_WIDTH - 1)) // That is to say, it counts up to the end of the row...
    {
        continue; // Skip drawing that triangle pair...
        width_count = 0; // Reset width_count to 0.
    }
    else
    {
        // Triangle 1
        points.push_back(i);
        points.push_back(i + 1);
        points.push_back(i + BMP_WIDTH);

        //Triangle 2
        points.push_back(i + 1);
        points.push_back(i + BMP_WIDTH);
        points.push_back(i + BMP_WIDTH + 1);

        width_count++; //count each pair of triangles drawn.
    }
}



And that is, basically, how I did it. I suppose you could use a modulus of (BMP_WIDTH - 1) to accomplish the same thing, and omit the width_count, right?

Here's a screen shot and the complete listing on my pastebin account (easier than formatting it here...).


THE COMPLETE ALLEGRO 5.1 LISTING HERE!

And with a most basic color for height algorithm function added somewhere in there it is easy to make a pseudo scenery generator! Had some fun with this one.


That code not included here, maybe a refined version next time, so...

Until the next post; bye, for now!