Trouble fixing a critical bug in my WormMove algorithm!

For those smart coders out there I have a problem which is pushing me to the extent of my knowledge and I need some guidance.

I Am trying to code a multi-sprite object for a game which is loosely inspired by snake. This snake, lets call it a worm, contains a deque which holds the objects for the tail.

To make the worm move I created a system where when the snake rotates, it creates a struct including the position and the direction to rotate and sends it to the deque in the first tail object. Every time it moves, it checks whether it has moved passed it, if so it moves the tail back to the position of the message, works out the time to get there and moves again with the remaining time and checks for another message. If a tail object hits a message, it sends it to the next tail and so on until it is deleted after being used by the last tail object.

This allows for the tail object to exactly follow the path of the worm's head and stop the tail objects from creeping up around corners.

Now this algorithm, which I hope is some what clear, works fine most of the time. However what seems to be quite random, this system fails and the tails fails to turn and travels in the direction it was facing.

Here lies the problem, I have spent a fortnight trying to solve this bug. First I had the tail in a vector which was fine until I tested the grow function. This have a few problems so I changed it to a deque which reduced the frequencies of the breaking. Now im not sure how to solve this problem and I need guidance.

What I think is happening if that the check for passing the message is failing as the messages still exist when the tail breaks apart but I can't see how it is happened and I don't know how to use the debugger for random events like this!!!

Can someone smarter than me see anything that could go wrong in this function that checks if a point is in a line segment.

Code:

---

bool AAH::math::isPointOnLineSeg(sf::Vector2f lineStart, sf::Vector2f lineEnd, sf::Vector2f point)
{
    //work out the line segment as a vector
    sf::Vector2f lineVec = lineEnd - lineStart;

    //work out left hand size of the equation  point-lineStart = t*lineVec
    sf::Vector2f leftSide = point - lineStart;

    //is the line not vertical or horizontal
    if (lineVec.x !=0.0f && lineVec.y !=0.0f)
    {
        //if t for y and x components are the same the point is on the full line
        if ( AreSame((leftSide.x)/(lineVec.x), (leftSide.y)/(lineVec.y) ) )
        {
            //is the point within the line segment
            if ( ( AreSame((leftSide.x)/(lineVec.x), 0.0f) || (leftSide.x)/(lineVec.x) > 0.0f ) &&
                ( AreSame((leftSide.x)/(lineVec.x), 1.0f) || (leftSide.x)/(lineVec.x) < 1.0f ))
            {
                return true;
            }
            else
                return false;
        }
    }
    else if (AreSame(lineVec.x, 0.0f) && lineVec.y != 0.0f)
    {
        //if t for y and x components are the same the point is on the full line
        if ( AreSame(point.x, lineStart.x) )
        {
            //is the point within the line segment
            if ( ( AreSame((leftSide.y)/(lineVec.y), 0.0f) || (leftSide.y)/(lineVec.y) > 0.0f ) &&
                ( AreSame((leftSide.y)/(lineVec.y), 1.0f) || (leftSide.y)/(lineVec.y) < 1.0f ))
            {
                return true;
            }
            else
                return false;
        }
    }
    else if ( AreSame(lineVec.y ,0.0f) && lineVec.x != 0.0f)
    {
        //if t for y and x components are the same the point is on the full line
        if ( AreSame(point.y, lineStart.y) )
        {
            //is the point within the line segment
            if ( ( AreSame((leftSide.x)/(lineVec.x), 0.0f) || (leftSide.x)/(lineVec.x) > 0.0f ) &&
                ( AreSame((leftSide.x)/(lineVec.x), 1.0f) || (leftSide.x)/(lineVec.x) < 1.0f ))
            {
                return true;
            }
            else
                return false;
        }
    }
    return false;
}

bool AAH::math::AreSame(float a, float b)
{
    return std::fabs(a - b) < std::numeric_limits<float>::epsilon()*100;
}

---

Sorry for the long post, I decided to not show all of the code described just of yet.

From what you describe, I suspect the problem is not the function you have shown.

I suspect it is related to the way that the struct (containing position and direction to rotate) is being copied or passed from one "tail object" to the next.

Personally, I would associate the "direction to rotate" with a position. All a segment needs to do, when updating itself, is check if there is a direction to rotate at its current location......

Thanks for the reply.

Yes, having a segment update itself is what I thought of at first but that would require a segment to know about the other segment to send the message so instead the head manages the segments. This also allows the worm to appear as just another object to the game world where updating the worm updates the segments as well.

Any way here is the function that moves the worm (it includes the transfer of the messages). I have also attached the cpp and header files for the worm class, wormBody class and the wormPart class. I hope that the error is located in there somewhere

Code:

---

void Worm::WormMove(float elapsedTime)
{
    //create move vector for the Worm head
    move(elapsedTime);

    //move all the body parts
    float* time = new float;
    for (std::deque<WormBody>::iterator it = _body.begin(); it != _body.end(); it++)
    {
        *time = elapsedTime;
        while (it->MoveBody(time)) //time is a pointer so it will decrease each iteration
        {
            //send position message along the Worm
            if (it != _body.end()-1)
                (it+1)->SendMsg(it->DeleteMsg());
            else
                it->DeleteMsg();
        }
    }
    delete time;
}

bool WormBody::MoveBody(float* elapsedTime)
{
    move(*elapsedTime);

    if (CheckMoveMsg())
    {
        //work out the time taken to get there
        float timeTaken = AAH::math::distance(_position.x, _position.y, GetMoveMessage().position.x,
                                                                        GetMoveMessage().position.y) /_velocity;

        //set the message state to the body part
        SetPosition(GetMoveMessage().position.x, GetMoveMessage().position.y);
        SetRotation(GetMoveMessage().rotation);

        //change the time
        *elapsedTime = *elapsedTime - timeTaken;

        //true means that a position message was used
        return true;
    }
    else
        return false;
}

---

Also today I placed the snake with a large amount of segments to see the result. As expected, the frames were really slow however it was interesting that tail was breaking practically at every turn. Maybe it only happens when it lags and the movement vectors are large!! I can't see how that would break it though :(

Attachment 11843Attachment 11839Attachment 11840Attachment 11841Attachment 11842

I'm guessing now (i.e. no guarantees) but it is an educated guess.

Try changing the inner loop within WormMove() from

Code:

---

        while (it->MoveBody(time)) //time is a pointer so it will decrease each iteration
        {
            //send position message along the Worm
            if (it != _body.end()-1)
                (it+1)->SendMsg(it->DeleteMsg());
            else
                it->DeleteMsg();
        }

---

to

Code:

---

        while (it->MoveBody(time)) //time is a pointer so it will decrease each iteration
        {
            //send position message along the Worm

            WhateverTypeDeleteMsgReturns msg = it->DeleteMsg();
            if (it + 1 != _body.end()) (it+1)->SendMsg(msg);
        }

---

It doesn't help that time is the name of a function in the standard library. You're also overdoing the use of pointers. You could safely declare time (after renaming to avoid a clash with the standard library) as a float, not a pointer. Then you can either pass its address or pass it by reference rather than pointer.

Also, variable names beginning with an underscore are not a good idea. The standard reserves such names for use in the global namespace.

I'm not sure this kind of thing is entirely trustworthy:

Code:

---

if (it != _body.end()-1)

---

The C++ experts here will have to weigh in on that one.

BTW, you haven't posted WormBody.h.

Quote:

---

Originally Posted by oogabooga

I'm not sure this kind of thing is entirely trustworthy:

Code:

---

if (it != _body.end()-1)

---

---

Should be okay since it is a random access iterator, methinks. Plus we know for sure at that point that the deque has at least one element.

Quote:

---

Originally Posted by laserlight

Should be okay since it is a random access iterator, methinks. Plus we know for sure at that point that the deque has at least one element.

---

My worries came from reading this:

Quote:

---

On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

---

Quote:

---

Originally Posted by oogabooga

On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

---

end() returns an iterator, not a pointer. If you worry about end() - 1 because "deques are not guaranteed to have all its elements in contiguous storage locations", then you should worry about it++, because "deques are not guaranteed to have all its elements in contiguous storage locations".

Quote:

---

On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

---

The standard says that `std::container<???>::end()' returns a "one past the end" iterator; thanks to the other parts of the standard relating to sequences a "one past the end" iterator is a valid iterator.

Code:

---

auto i(c.end());
--i; // i is perfectly valid if the iterator supports some form of reverse traversal

---

Code:

---

auto i(c.end());
++i; // i is always invalid in view of the standard because "two past the end" isn't a thing the standard concerns itself with

---

This leaves us with a weird situation where order becomes important even when the "value" would logically be the same.

Code:

---

auto i(c.end());
++i;
--i; // i isn't valid in view of the standard but may work for some libraries

---

Code:

---

auto i(c.end());
--i;
++i; // i is valid in view of the standard and equivalent to `c.end()'

---

Soma

I used to feel uncomfortable about it too. I mean if it were just a plain doubly-linked-list underneath then end() might be the equivalent of NULL right?
But then I saw code internal to the SC++L under MSVC which uses end()-1 for back() I think it was, and stopped worrying about it.

I tried what you said grumpy with no luck. Still it was worth a shot eh!

https://www.youtube.com/watch?v=p2v40yEM3G4

Here is a video of the worm breaking up. As you can see it doesn't happen straight way. That was with 1001 segments however if I only have 100 segments it hardly happens.

I can't find a concrete answer to why these factors affect the problem. Maybe, the system fails with a longer elapsedTime as with more objects the frames are longer which causes the float to be larger. That would also explain that most of the time just before it fails there is a lag spike.

It also might be worth pointing out that the _body was originally a vector but when I had it consistently grow it lagged every time the vector grew due to the creation of a new array. This also broke my handle object to the sprite in another class so I had to create a copy constructor to stop that.
Now that it is in a deque, "the breaking" is less frequent but still it persist to be a pain.

Maybe the two object that these are inherited from affect the problem so here they are
Attachment 11850
Attachment 11851
Attachment 11852
Attachment 11853

Again, any help will be greatly appreciated and if anyone works it out you will get my unofficial super-duper coder status ;)

My concern with the iterators was more related to potential of an operation invalidating an iterator (having seen designs where an object, when it receives a message, does something that affects its parent container). Given the problem description, I couldn't exclude that possibility.

What happens if that inner loop iterates more than once? The first iteration will remove a message from an object, and send it to the next object. What happens if there is no message to be removed on second and subsequent iterations?

Well, what is meant to happen is that the segment moves in the direction the it is facing and the amount of time passed. After that, it should check if it has passed a messages (which says that it should turn). If it has, the direction is changed, it is brought back to the message position and the time left over is calculated to be used with the move function again. This should repeat until no messages have been hit.
If a message is hit a counter is incremented which records the number of messaged used letting the delete function know how many messages to delete.

I don't have time to have a closer look right now but I'll do it later. What really is making this hard is that the bug doesn't always occur but if you saw that YouTube video, when it does it usually happens in multiple corners at one time.

Dogged - please post WormBody.h and your main function.

That worm explosion actually looks kinda cool. I would almost be tempted to make it do something similar in the final game, after solving what causes it unintentionally of course.

@iMalc - haha, yea I had that thought pop into my head. But it would have to be a bit more controlled ;)

Here is WormBody.h and "my" game loop class

Attachment 11855
Attachment 11856
Attachment 11854

When I had my body in a vector, it broke every time it's actual size increased. This creates a new array inside the container so I thought that maybe copying of the segments might be breaking the tail.

I added this code to see if creating a new deque for the body would break the tail. This would happen every time I press space.

Code:

---

    if (Game::GetInput().IsKeyDown(sf::Key::Space))//TEST
    {
        temp = _body;
        _body.~deque();
        _body = temp;
    }

---

What resulted is that it broke when I had 1000 segments consistently , with 100 it only happen some of the time and when I had only 10 I couldn't get it to break at all.

Maybe that clue helps out.

Code:

---

temp = _body;
_body.~deque();
_body = temp;

---

>_<

That's so extremely wrong I fear it may break the U|\|1\/3r$3.

Yog Sothoth!

Do j00Z $33 \/\/|-|@ j00Z have done!?

'/0U'\/3 bR0|<3|\| 7|-|3 3|\|71R3 U|\|1\/3R53.

Seriously though, a destructor ends the life of an object. You can't use the assignment operator on a dead object.

Soma

Errrrrr...... im not sure about the internals of deque but isn't the objects in _body copied into temp (ie they are now seperate objects) so that the destructor is destroying the objects in _body not temp which will be copied into _body again!

It is never okay to call the destructor directly like that.

To do what you want, you should be using:

Code:

---

{
    std::deque<MyType> temp = _body;
    std::swap(temp, _body);
}

---

This performs the copying once and only once, and has no undefined (universe breaking) behaviour.

Quote:

---

im not sure about the internals of deque but isn't the objects in _body copied into temp (ie they are now seperate objects) so that the destructor is destroying the objects in _body not temp which will be copied into _body again!

---

It has nothing to do with the internal implementation. It has everything to do with one simple fact: destructors end the life of an object.

You are not entirely correct about the destructor destroying the objects of `_body'. The destructor destroys `_body' itself which includes the objects that it owns. You can't use a facility of a dead object.

Look at it this way, you are saying "Click the "Okay" button." after you've already turned off your computer. That isn't a thing that you can do.

Quote:

---

To do what you want, you should be using

---

You should prefer an unnamed "temp swap" instead.

Code:

---

std::deque<int>().swap(_body);

---

That does the same thing and kills off the temporary "instantly" without introducing extra scope.

Soma

Cool, that for the info. I'll make sure to never do that again. (I don't want to break the U|\|1\/3r$3 ;))

Now I played around with the elapsedTime in the function that calls the update of all the objects that exist in the game world. If I increase the elaspsedTime then the tail broke quicker. Normally, it is worked out by using a SFML function that gets the time from the last frame meaning that it changes each iteration of the game loop. As it seemed that it was lagging just before the breaking maybe the increased time was a factor. So assuming that it is true and a larger elaspedTime value causes the error, I now have to work out why.

Does this sound logical or should I be looking at something else?

Actually, I have some more news. I was looking at what grumpy was saying and decided I should look into the inner loop of this function.

Code:

---

void Worm::WormMove(float elapsedTime)
{
    int counter = 0;
    int max =0;
    //create move vector for the Worm head
    move(elapsedTime);

    //move all the body parts
    for (std::deque<WormBody>::iterator it = _body.begin(); it != _body.end(); it++)
    {
        counter = 0;
        float timeLeft = elapsedTime;
        while (it->MoveBody(timeLeft)) //time is referenced so it will decrease each iteration
        {
            counter++;
            std::vector<WormPart::MoveMessage> msg = it->DeleteMsg();
            if (it + 1 != _body.end())
                (it+1)->SendMsg(msg);
        }
        if (counter > max)
            max = counter;
    }
    std::cout << "DEBUG MESSAGE: counter is " << max << "\n";
}

---

What I noticed by printing the counter is that when it breaks the counter spikes really high. Quite interesting!!!

Edit: fixed a error in the code

Look at your class hierarchy:

Code:

---

GameObject
  |
 Sprite    ...
  |        |
WormBody  Sprite
  |      /
  WormPart

---

WormPart inherits from Sprite twice. I'm not sure what that will do, but it's probably not what you meant. I'd get rid of the ": public Sprite" part of

Code:

---

class WormPart : public Sprite
{
public:
...

---

Quote:

---

Originally Posted by phantomotap

You should prefer an unnamed "temp swap" instead.

Code:

---

std::deque<int>().swap(_body);

---

That does the same thing and kills off the temporary "instantly" without introducing extra scope.

---

Even better.
I just hope he can understand what that's doing just as well.

oogabooga, you confused me!!!

My class hierarchy is meant to be like this

Code:

---

GameObject
  |

 Sprite 

  |     

  WormPart 

  |      \ 

WormBody  Worm

---

so WormPart should inherent from Sprite but I don't see how WormBody is inheriting directly from Sprite but through WormPart.

Maybe I am blind, so here is the header for WormBody again.

Code:

---

class WormBody : public WormPart
{
public:
    WormBody(float X, float Y, float angle, int colour);
    ~WormBody();
    WormBody(const WormBody& copy);

    void Update(float elapsedTime);
    bool MoveBody(float& elapsedTime);
private:
    void CreatePolygon();
};

---

Hmmm, you're absolutely right. I don't know what code I was looking at! Sorry about that. I'm giving your code a read-through right now. Will let you know if I find something.

I read through your code (while watching The Daily Show and The Cobert Report) and all I noticed was that you misspelled "calculate" in CalualteGridLocations and CalulateBodyRotation. :)

Oh, and CheckMoveMsg should have a "return false" at the end (otherwise it will sometimes not set it's return value properly).

Also, you might want to check that elapsedTime never goes negative after this line:

Code:

---

*elapsedTime = *elapsedTime - timeTaken;

---

How embarrassing that I misspelled calculate twice, opps! Anyway, thanks for reading my code oogabooga. I did notice the missing return false line and added it about a day ago and using a cout statement I have never seen it become negative. For now I just made elapsedTime zero if it is negative but that is not a perfect fix.

Looking at my data while debugging, what is happening is that the messages gets "stuck" on a body piece as a message doesn't get sent across to the next piece and as a result it keeps checking against a message which it has already passed. Leaving all the other messages to built up like a blockage in a pipe.

Now why is message is getting stuck...duno. It could be the functions that delete and send this data that are causing this bug. But what I still think, is that the first function I posted is causing this bug.
I Just read this website and maybe i'm having an error to do with this funny float business. I don't have time right now to look into this as I got a lecture starting but I will get onto it. Anyway, it's something to look into :)

Here is the website: Comparing Floating Point Numbers, 2012 Edition | Random ASCII

In your isPointOnLineSeg function, shouldn't the first case in your outermost if/else if/...
structure be put last? Otherwise it grabs every case where lineVec .x and .y are both not
exactly zero. The test for both non-zero is to protect against division by zero, but since
it's the first case it gets chosen more than it should.


As a test, the implementation below seems fairly inefficient, but you could try it as a replacement
just to see what happens.

Code:

---

// The line segment is point a to b. The point is c.
// The distance from a to b is compared to the sum of the distances from a to c and from b to c.
bool AAH::math::isPointOnLineSeg(sf::Vector2f a, sf::Vector2f b, sf::Vector2f c)
{
    float distAB = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    float distAC = (a.x - c.x) * (a.x - c.x) + (a.y - c.y) * (a.y - c.y);
    float distBC = (b.x - c.x) * (b.x - c.x) + (b.y - c.y) * (b.y - c.y);
    return AreSame(distAB, distAC + distBC);
}

---

I'll make that change to isPointOnLineSeg, thanks.

That function didn't work but I decided to make my own replacement.

Code:

---

// test to see if the point coords are in between the start of the line seg and the end
// by testing that the start and end points of the vector are lower and above the point in question
bool AAH::math::isPointOnLineSegTEST(sf::Vector2f lineStart, sf::Vector2f lineEnd, sf::Vector2f point)
{
    //is line vertical
    if (AreSame(lineStart.x, lineEnd.x))
    {
        if (std::min(lineStart.y, lineEnd.y) < point.y && std::max(lineStart.y, lineEnd.y) > point.y)
        {
            return true;
        }
    }
    //is line horizontal
    else if (AreSame(lineStart.y, lineEnd.y))
    {
            if (std::min(lineStart.x, lineEnd.x) < point.x && std::max(lineStart.x, lineEnd.x) > point.x)
        {
            return true;
        }
    }
    else
    {
            if (std::min(lineStart.x, lineEnd.x) < point.x && std::max(lineStart.x, lineEnd.x) > point.x &&
                    std::min(lineStart.y, lineEnd.y) < point.y && std::max(lineStart.y, lineEnd.y) > point.y)
        {
            return true;
        }
    }
    return false;
}

---

It didn't change that much so I presume that unless the error is concurrent in both functions it not located in isPointOnLineSeg.

However, I noticed this interesting behavior while testing that function. Sometimes pictures are better then words but videos are one up. So here is a video showing what happened. Make sure to read the short description as well.

https://www.youtube.com/watch?v=mnGJ...U&feature=plcp

Cheers for the help guys!