Implementation of recursive algorithm

Question

I've got two kinds of object, Ball and Platform. Balls have an (x,y) coordinate and the platforms have (x_begin, x_end, y). There can be at most 80 Platforms.

I was asked to find the shortest path for any given Ball to the ground (y=0). Note that the output of this should only be the minimum distance.

Given the constraints I thought it would be best to use brute force: calculate all the possible distances to the ground, and then return the minimum.

What I thought I'd do, is write a recursive function: first calculate the vertical distance to the nearest platform, and then branch into right and left, and back again. The breaking condition would be when all paths reach the ground.

    void calculateDistances(Ball b, vector<Platform> ps, vector<float>* distances)
    {
        //The idea is to have, for every branch
        // distances[i] = vertical distance
        // distances[i+1] = distance to right
        // distances[i+2] = distance to left
        Platform* p = NULL;
        float d_y = verticalDistanceToNearestPlatform(ps, p); // "p" now holds the platform the ball is on
        if (d_y == 0) 
            return; //already on floor
        distances->push_back(d_y);

        d_x_right = distanceToRightEdgeOfPlatform(p);
        distances->push_back(d_x_right);
        d_x_left = distanceToLeftEdgeOfPlatform(p);
        distances->push_back(d_x_left);
    }

The problem here is obvious... how on Earth do I make this recursive?

Many thanks!

PS: this problem is meant to be solved in approximately two and a half hours.

Answer 1

A recursive solution (say, horizontalDistanceToGround(x, y)) would involve computing the horizontal distance from some arbitrary point (x, y) to the nearest point on the ground, as follows:

• If there's no platform between (x, y) and the ground, then return 0.
• If there's any platform between (x, y) and the ground, then find the nearest such platform (i.e. that has the greatest platform_y less than y). If that platform is located at (platform_min_x, platform_max_x, platform_y), then return the minimum of (x - platform_min_x) + horizontalDistanceToGround(platform_min_x, platform_y) and (platform_max_x - x) + horizontalDistanceToGround(platform_max_x, platform_y). This basically computes the minimum distance needed to get from the current x position to an end of the platform, and from there to the ground.

I'll leave finding the nearest platform between (x, y) and the ground (if there is one) to you to figure out.

The shortest distance from ball to ground is then distanceToGround(ball_x, ball_y) + ball_y.

NOTE: Updated as per @MooingDuck's useful comment regarding the vertical distance being irrelevant to the recursion.