Thread: Trouble fixing a critical bug in my WormMove algorithm!

  1. #1
    Registered User
    Join Date
    Apr 2012
    Posts
    19

    Unhappy 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.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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......
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Apr 2012
    Posts
    19
    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

    Worm.cppWorm.hWormBody.cppWormPart.cppWormPart.h

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by laserlight View Post
    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:
    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 cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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 Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Apr 2012
    Posts
    19
    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
    Sprite.cpp
    Sprite.h
    GameObject.h
    GameObject.cpp

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

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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?
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  13. #13
    Registered User
    Join Date
    Apr 2012
    Posts
    19
    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.

  14. #14
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Dogged - please post WormBody.h and your main function.
    Last edited by oogabooga; 07-24-2012 at 09:35 AM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trouble with an algorithm to find edges
    By kbrown51 in forum C++ Programming
    Replies: 3
    Last Post: 08-09-2011, 02:51 PM
  2. Trouble Understanding Structure Algorithm
    By JJohnson in forum C Programming
    Replies: 14
    Last Post: 10-19-2010, 01:27 AM
  3. Trouble Generating Game Algorithm
    By justlivelife15 in forum Game Programming
    Replies: 3
    Last Post: 06-13-2007, 09:58 AM
  4. Errors i'm having trouble fixing
    By yaniv89 in forum Windows Programming
    Replies: 5
    Last Post: 08-26-2005, 02:35 PM
  5. Trouble W/Getline Algorithm
    By drdroid in forum C++ Programming
    Replies: 7
    Last Post: 02-26-2003, 09:39 AM