1
\$\begingroup\$

So I'm writing an adventure game for MSDOS, just a fun challenge for me. I'm trying to get the character to walk along a straight line to his destination (either the next navMesh node or where you clicked). Normally I would simply store the characters x,y as floats and add the direction vector to it for each move, the problem is that cpus before the 486 didn't have FPUs at all so floats are out of the question. So naturally I thought about Bressenham's line algorithm which can be done using all ints. Taking inspiration I came up with this function here which runs every frame:

void character::doWalk()
{
    int x_diff = destination.x - x;
    int y_diff = destination.y - y;

    int x_dist = abs(x_diff);
    int y_dist = abs(y_diff);

    int walk_x_dir = x_diff > 0 ? 1 : (x_diff < 0 ? -1 : 0);
    int walk_y_dir = y_diff > 0 ? 1 : (y_diff < 0 ? -1 : 0);

    if(y_dist >= x_dist || yerror > 0)
    {
        y += walk_y_dir;

        yerror -= path_dist_x;
    }
    else
    {
        yerror += path_dist_y;
    }

    if(x_dist >= y_dist || xerror > 0)
    {
        x += walk_x_dir;

        xerror -= path_dist_y;
    }
    else
    {
        xerror += path_dist_x;
    }
}

path_dist_y is the vertical distance calculated when the character begins walking path_dist_x is the horizontal distance.

This algorithm almost works, it seems that he begins walking at an angle just too shallow to get to the point correctly and he has to change direction near the end of his walk to make it to the point. Any idea what else I could try?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

In Ye olden days we used to use the bottom 16 bits of a long as the fraction part.

struct HiLo
{
public:
    unsigned short m_lo;
    unsigned short m_hi;
};

union LongFraction
{
public:
    LongFraction()
    {
        m_all = 0;
    }
    HiLo m_hilo;
    unsigned long m_all;
};

Then 0-65535 becomes the fraction part.

LongFraction pos;

pos.m_all += 32768; //32768 is 0.5
pos.m_all += 32768; //32768 is 0.5

short x = pos.m_hilo.m_hi;  // this will be 1

Endian-ness would probably require reordering the elements in the HiLo struct.

\$\endgroup\$
0
\$\begingroup\$

You could try doing all relevant calculations on numbers multiplied by e.g. 1000 and then divide/round by 1000 before display.

So if your source and destination are (16;44) and (85;140) you could make the walk logic move say between (16000;44000) and (85000;140000), then on display - convert back tox1 scale. Of course if you are limited to WORDs - multiply by something that stays within WORDs bounds.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .