Create path to move player from current position to new position through a "turn circle"

Question

I've been wracking my brain for a couple of days trying to come up with a way to move a player from there current position to new position using Swift and SpriteKit. Sounds relatively easy.

Now, I know I can use a CGPath and a SKAction to move the player along a path, but what I need to know is how to create the path for the player to move along.

I need the player to move through a predetermined radius as it turns towards the new point first as it moves, let me demonstrate...

So, the red circle is the player and their current orientation, the large circle is the turn radius and the red crosses are possible points where the player wants to move to (obviously you'd only have one at any point in time, but the idea is demonstrate the difference in movement between one possible point and another)

Also, the player could move left or right depending in which ever path is shortest to the target point.

What I tried (sorry the list is kind of short)...

Basically, I know the current position/orientation of the player; I know the radius of the turn circle and I know the point I want to move to. I need to calculate the arc through which the player will need to initially move through to orientate themselves to the new point (tacking on a CGPathAddLineToPoint to the end of the arc should be trivial)

Other then spending copious amounts of time reading through the docs, Googling, reading blog posts and tutorials, I also tried looping through a series of angles from a start angle through a given iteration level (+/-0.5 degrees for example) and calculating the angle between the current point and next point on the circle and comparing that to the angle of the current point to the target point and basically selecting the angle with the lowest difference/delta ...

So, the two red circles represent two points on the circle, the blue line represents the angle between them, the green line represents the angle from the first point to the target point.

Let's just say, that while that might possibly work, I'm kind of horrified at the idea and hope that it might be possible to come up with a better/faster solution.

I'm not sure if something like CGPathAddArcToPoint would help, as it would create an arc from my players current position to the target point, rather then allow the player to move through a turning circle.

Once the player leaves the turning circle, I'm not particular fussed if the move in a straight line or not (ie they could curve slightly to the target point), but I'm currently focused on trying to calculate the required arc needed to get the player started.

Sorry, my maths is pretty poor, so, please, be nice

The code "currently" looks something like (a complete mess)

func pointTowards(point thePoint: CGPoint) {

    // Need to calculate the direction of the turn

    //let angle = atan2(thePoint.y - self.position.y, thePoint.x - self.position.x) - CGFloat(180.0.toRadians());
    let angle = angleBetween(startPoint: self.position, endPoint: thePoint) - CGFloat(180.0.toRadians())

    if (self.zRotation < 0) {
    //  self.zRotation
    //  self.zRotation = self.zRotation + M_PI * 2;
    }

    let rotateTo: SKAction = SKAction.rotateToAngle(angle, duration: 1, shortestUnitArc: true)
    rotateTo.timingMode = SKActionTimingMode.EaseInEaseOut

    self.runAction(rotateTo)

    let offset = CGPoint(x: rotorBlur.position.x, y: rotorBlur.position.y + (rotorBlur.size.width / 2))
    let radius = rotorBlur.size.width / 2.0
    var points: [AnglesAndPoints] = self.pointsOnCircleOf(
        radius: radius,
        offset: offset);

    let centerPoint = CGPoint(x: offset.x + radius, y: offset.y + radius)

    var minAngle = CGFloat.max
    var minDelta = CGFloat.max
    for var p: Int = 1; p < points.count; p++ {
        let p1 = points[p - 1].point
        let p2 = points[p].point

        let point = angleBetween(startPoint: p1, endPoint: p2) - CGFloat(180.0.toRadians())
        let target = angleBetween(startPoint: p1, endPoint: thePoint) - CGFloat(180.0.toRadians())

        let delta = target - point
        if delta < minDelta {
            minDelta = delta
            minAngle = points[p - 1].angle
        }

    }

    println("projected: \(minAngle); delta = \(minDelta)")

    if let pathNode = pathNode {
        pathNode.removeFromParent()
    }

    //points = self.pointsOnCircleOf(
    //  radius: rotorBlur.size.width / 2.0,
    //  offset: CGPoint(x: 0, y: rotorBlur.size.width / 2));

    let path = CGPathCreateMutable()
    CGPathAddArc(
        path,
        nil,
        0,
        rotorBlur.size.width / 2,
        rotorBlur.size.width / 2,
        CGFloat(-180.0.toRadians()),
        minAngle,
        true)
    pathNode = SKShapeNode()
    pathNode?.path = path
    pathNode?.lineWidth = 1.0
    pathNode?.strokeColor = .lightGrayColor()
    addChild(pathNode!)

}

func pointsOnCircleOf(radius r : CGFloat, offset os: CGPoint) -> [AnglesAndPoints] {

    var points: [AnglesAndPoints] = []

    let numPoints = 360.0 * 2.0
    let delta = 360.0 / numPoints
    for var degrees: Double = 0; degrees < numPoints; degrees += delta {

        var point: CGPoint = pointOnCircle(angle: CGFloat(degrees.toRadians()), radius: r)
        point = CGPoint(x: point.x + os.x, y: point.y + os.y)
        points.append(AnglesAndPoints(angle: CGFloat(degrees.toRadians()), point: point))

    }

    return points

}

func pointOnCircle(angle radians:CGFloat, radius theRadius:CGFloat) -> CGPoint {

    return CGPointMake((cos(radians) * theRadius),
        (sin(radians) * theRadius));

}

func angleBetween(startPoint p1: CGPoint, endPoint p2: CGPoint) -> CGFloat {

    return atan2(p2.y - p1.y, p2.x - p1.x) //- CGFloat(180.0.toRadians());

}

Basically, I went about pre-calculating the points on a circle of a given radius with a given offset, which is just horrible and if I had the time right now, would re-work it so that the point was dynamically created (or I could cache the values some how and simply translate them), but as I said, this was such a horrible idea I really wanted to find a different way and abandon this approach

I'm pretty sure that the current code doesn't take into the players current orientation and it should be supplying a start angle and direction (counter/clockwise) in which to iterate, but I've gotten to the point I'd like to see if their is simply a better solution then this before trying to fix any more issues with it

Answer 1

Funny, I actually have motion in my game almost exactly as you described except that instead of always going clock-wise when on the right side and counter-clock when on the left, it will pick the closer path.

So I grabbed some of the code and modified it sightly to fit your description. It will move left when the target point is to the left of the player, else it will move right. You can also set the speed of the node, as well as the radius and position of the "orbit."

My implementation however does not use SKActions and paths to move. Everything is done dynamically in real-time which allows for collisions with the moving objects and greater motion control. However if you absolutely need to use paths with SKActions let me know and I'll try to come up with a solution. Essentially what it comes down to is finding the arc to the tangent points (which the code already does to an extent).

The physics calculations come from my two answerers here, and here.

The way the implementation works is that it first determines the final destination point, as well as the angular distance to the best tangent point using a secondary circle to find the tangent points. Then using centripetal motion, the node moves along the path to the tangent point and then switches to linear motion to finish moving to the end destination.

Below is the code for the GameScene:

import SpriteKit

enum MotionState { case None, Linear, Centripetal }

class GameScene: SKScene {
    var node: SKShapeNode!
    var circle: SKShapeNode!
    var angularDistance: CGFloat = 0
    var maxAngularDistance: CGFloat = 0
    let dt: CGFloat = 1.0/60.0 //Delta Time
    var centripetalPoint = CGPoint() //Point to orbit.
    let centripetalRadius: CGFloat = 60 //Radius of orbit.
    var motionState: MotionState = .None
    var invert: CGFloat = 1
    var travelPoint: CGPoint = CGPoint() //The point to travel to.
    let travelSpeed:CGFloat = 200 //The speed at which to travel.

    override func didMoveToView(view: SKView) {
        physicsWorld.gravity = CGVector(dx: 0, dy: 0)
        circle = SKShapeNode(circleOfRadius: centripetalRadius)
        circle.strokeColor = SKColor.redColor()
        circle.hidden = true
        self.addChild(circle)
    }
    func moveToPoint(point: CGPoint) {
        travelPoint = point
        motionState = .Centripetal

        //Assume clockwise when point is to the right. Else counter-clockwise
        if point.x > node.position.x {
            invert = -1
            //Assume orbit point is always one x radius right from node's position.
            centripetalPoint = CGPoint(x: node.position.x + centripetalRadius, y: node.position.y)
            angularDistance = CGFloat(M_PI)
        } else {
            invert = 1
            //Assume orbit point is always one x radius left from node's position.
            centripetalPoint = CGPoint(x: node.position.x - centripetalRadius, y: node.position.y)
            angularDistance = 0
        }
    }

    final func calculateCentripetalVelocity() {
        let normal = CGVector(dx:centripetalPoint.x + CGFloat(cos(self.angularDistance))*centripetalRadius,dy:centripetalPoint.y + CGFloat(sin(self.angularDistance))*centripetalRadius);
        let period = (CGFloat(M_PI)*2.0)*centripetalRadius/(travelSpeed*invert)
        self.angularDistance += (CGFloat(M_PI)*2.0)/period*dt;
        if (self.angularDistance>CGFloat(M_PI)*2)
        {
            self.angularDistance = 0
        }
        if (self.angularDistance < 0) {
            self.angularDistance = CGFloat(M_PI)*2
        }
        node.physicsBody!.velocity = CGVector(dx:(normal.dx-node.position.x)/dt ,dy:(normal.dy-node.position.y)/dt)

        //Here we check if we are at the tangent angle. Assume 4 degree threshold for error.
        if abs(maxAngularDistance-angularDistance) < CGFloat(4*M_PI/180) {
            motionState = .Linear
        }
    }

    final func calculateLinearVelocity() {
        let disp = CGVector(dx: travelPoint.x-node.position.x, dy: travelPoint.y-node.position.y)
        let angle = atan2(disp.dy, disp.dx)
        node.physicsBody!.velocity = CGVector(dx: cos(angle)*travelSpeed, dy: sin(angle)*travelSpeed)

        //Here we check if we are at the travel point. Assume 15 point threshold for error.
        if sqrt(disp.dx*disp.dx+disp.dy*disp.dy) < 15 {
            //We made it to the final position! Code that happens after reaching the point should go here.
            motionState = .None
            println("Node finished moving to point!")
        }
    }

    override func update(currentTime: NSTimeInterval) {
        if motionState == .Centripetal {
            calculateCentripetalVelocity()
        } else if motionState == .Linear {
            calculateLinearVelocity()
        }
    }

    func calculateMaxAngularDistanceOfBestTangent() {
        let disp = CGVector(dx: centripetalPoint.x - travelPoint.x, dy: centripetalPoint.y - travelPoint.y)
        let specialCirclePos = CGPoint(x: (travelPoint.x+centripetalPoint.x)/2.0, y: (travelPoint.y+centripetalPoint.y)/2.0)
        let specialCircleRadius = sqrt(disp.dx*disp.dx+disp.dy*disp.dy)/2.0
        let tangentPair = getPairPointsFromCircleOnCircle(centripetalPoint, radiusA: centripetalRadius, pointB: specialCirclePos, radiusB: specialCircleRadius)
       let tangentAngle1 = (atan2(tangentPair.0.y - centripetalPoint.y,tangentPair.0.x - centripetalPoint.x)+CGFloat(2*M_PI))%CGFloat(2*M_PI)
       let tangentAngle2 = (atan2(tangentPair.1.y - centripetalPoint.y,tangentPair.1.x - centripetalPoint.x)+CGFloat(2*M_PI))%CGFloat(2*M_PI)
        if invert == -1 {
            maxAngularDistance = tangentAngle2
        } else {
            maxAngularDistance = tangentAngle1
        }
    }

    //Not mine, modified algorithm from https://stackoverflow.com/q/3349125/2158465
    func getPairPointsFromCircleOnCircle(pointA: CGPoint, radiusA: CGFloat, pointB: CGPoint, radiusB: CGFloat) -> (CGPoint,CGPoint) {
        let dX = (pointA.x - pointB.x)*(pointA.x - pointB.x)
        let dY = (pointA.y - pointB.y)*(pointA.y - pointB.y)
        let d = sqrt(dX+dY)
        let a = (radiusA*radiusA - radiusB*radiusB + d*d)/(2.0*d);
        let h = sqrt(radiusA*radiusA - a*a);
        let pointCSub = CGPoint(x:pointB.x-pointA.x,y:pointB.y-pointA.y)
        let pointCScale = CGPoint(x: pointCSub.x*(a/d), y: pointCSub.y*(a/d))
        let pointC = CGPoint(x: pointCScale.x+pointA.x, y: pointCScale.y+pointA.y)
        let x3 = pointC.x + h*(pointB.y - pointA.y)/d;
        let y3 = pointC.y - h*(pointB.x - pointA.x)/d;
        let x4 = pointC.x - h*(pointB.y - pointA.y)/d;
        let y4 = pointC.y + h*(pointB.x - pointA.x)/d;
        return (CGPoint(x:x3, y:y3), CGPoint(x:x4, y:y4));

    }

    override func touchesBegan(touches: Set<NSObject>, withEvent event: UIEvent) {
        let touchPos = (touches.first! as! UITouch).locationInNode(self)
        node = SKShapeNode(circleOfRadius: 10)
        node.position = CGPoint(x: self.size.width/2.0, y: self.size.height/2.0)
        node.physicsBody = SKPhysicsBody(circleOfRadius: 10)
        self.addChild(node)

        moveToPoint(touchPos)
        calculateMaxAngularDistanceOfBestTangent()  //Expensive!

        circle.hidden = false
        circle.position = centripetalPoint
    }
}

Note that the circle you see is another node I added to the scene to make the motion more visible; you can easily just remove it. When debugging you might also find it useful to add nodes at the tangent points. The tangentPair tuple inside the calculateMaxAngularDistanceOfBestTangent function contains the two tangent points.

Additionally note that finding the tangent points/angles is expensive but it only happens each time you need to move to a new point. If however you game requires constantly moving to a new point, using this algorithm repeatedly on many nodes can be costly (always profile before assuming this though). Another way to check when to move from centripetal motion to linear motion is to check if the velocity vector is approaching the end position as shown below. This is less accurate but allows you to remove the calculateMaxAngularDistanceOfBestTangent function entirely.

let velAngle = atan2(node.physicsBody!.velocity.dy,node.physicsBody!.velocity.dx)
let disp = CGVector(dx: travelPoint.x-node.position.x, dy: travelPoint.y-node.position.y)
let dispAngle = atan2(disp.dy,disp.dx)

//Here we check if we are at the tangent angle. Assume 4 degree threshold for error.
if velAngle != 0 && abs(velAngle - dispAngle) < CGFloat(4*M_PI/180) {
    motionState = .Linear
}

Lastly let me know if you need to use paths with SKActions, regardless I think I will update this last part showing how this is done (unless someone beats me to it! And as I mentioned earlier the code I posted does this to an extent.) I don't have time to right now but hopefully I get a chance to soon! I hope something mentioned in this answer helps you. Good luck with your game.

Update including SKActions

The code below shows getting the same exact effect except this time using SKActions to animate a CGPath to the tangent angle then to the final destination point. It is much simpler as there is no longer a manual calculation of centripetal and linear motion, however because it is an animation you lose the dynamic real-time motion control that the solution above provides.

class GameScene: SKScene {

    var centripetalPoint = CGPoint() //Point to orbit.
    let centripetalRadius: CGFloat = 60 //Radius of orbit.
    var travelPoint: CGPoint = CGPoint() //The point to travel to.
    var travelDuration: NSTimeInterval = 1.0 //The duration of action.
    var node: SKShapeNode!
    var circle: SKShapeNode!

    override func didMoveToView(view: SKView) {
        physicsWorld.gravity = CGVector(dx: 0, dy: 0)
        circle = SKShapeNode(circleOfRadius: centripetalRadius)
        circle.strokeColor = SKColor.redColor()
        circle.hidden = true
        self.addChild(circle)
    }
    //Not mine, modified algorithm from https://stackoverflow.com/q/3349125/2158465
    func getPairPointsFromCircleOnCircle(pointA: CGPoint, radiusA: CGFloat, pointB: CGPoint, radiusB: CGFloat) -> (CGPoint,CGPoint) {
        let dX = (pointA.x - pointB.x)*(pointA.x - pointB.x)
        let dY = (pointA.y - pointB.y)*(pointA.y - pointB.y)
        let d = sqrt(dX+dY)
        let a = (radiusA*radiusA - radiusB*radiusB + d*d)/(2.0*d);
        let h = sqrt(radiusA*radiusA - a*a);
        let pointCSub = CGPoint(x:pointB.x-pointA.x,y:pointB.y-pointA.y)
        let pointCScale = CGPoint(x: pointCSub.x*(a/d), y: pointCSub.y*(a/d))
        let pointC = CGPoint(x: pointCScale.x+pointA.x, y: pointCScale.y+pointA.y)
        let x3 = pointC.x + h*(pointB.y - pointA.y)/d;
        let y3 = pointC.y - h*(pointB.x - pointA.x)/d;
        let x4 = pointC.x - h*(pointB.y - pointA.y)/d;
        let y4 = pointC.y + h*(pointB.x - pointA.x)/d;
        return (CGPoint(x:x3, y:y3), CGPoint(x:x4, y:y4));
    }

    func moveToPoint(point: CGPoint) {
        travelPoint = point

        //Assume clockwise when point is to the right. Else counter-clockwise
        if point.x > node.position.x {
            centripetalPoint = CGPoint(x: node.position.x + centripetalRadius, y: node.position.y)
        } else {
            centripetalPoint = CGPoint(x: node.position.x - centripetalRadius, y: node.position.y)
        }

        let disp = CGVector(dx: centripetalPoint.x - travelPoint.x, dy: centripetalPoint.y - travelPoint.y)
        let specialCirclePos = CGPoint(x: (travelPoint.x+centripetalPoint.x)/2.0, y: (travelPoint.y+centripetalPoint.y)/2.0)
        let specialCircleRadius = sqrt(disp.dx*disp.dx+disp.dy*disp.dy)/2.0
        let tangentPair = getPairPointsFromCircleOnCircle(centripetalPoint, radiusA: centripetalRadius, pointB: specialCirclePos, radiusB: specialCircleRadius)
        let tangentAngle1 = (atan2(tangentPair.0.y - centripetalPoint.y,tangentPair.0.x - centripetalPoint.x)+CGFloat(2*M_PI))%CGFloat(2*M_PI)
        let tangentAngle2 = (atan2(tangentPair.1.y - centripetalPoint.y,tangentPair.1.x - centripetalPoint.x)+CGFloat(2*M_PI))%CGFloat(2*M_PI)

        let path = CGPathCreateMutable()
        CGPathMoveToPoint(path, nil, node.position.x, node.position.y)
        if travelPoint.x > node.position.x  {
            CGPathAddArc(path, nil, node.position.x+centripetalRadius, node.position.y, centripetalRadius, CGFloat(M_PI), tangentAngle2, true)
        } else {
            CGPathAddArc(path, nil, node.position.x-centripetalRadius, node.position.y, centripetalRadius, 0, tangentAngle1, false)
        }
        CGPathAddLineToPoint(path, nil, travelPoint.x, travelPoint.y)

        let action = SKAction.followPath(path, asOffset: false, orientToPath: false, duration: travelDuration)
        node.runAction(action)
    }

    override func touchesBegan(touches: Set<NSObject>, withEvent event: UIEvent) {
        let touchPos = (touches.first! as! UITouch).locationInNode(self)
        node = SKShapeNode(circleOfRadius: 10)
        node.position = CGPoint(x: self.size.width/2.0, y: self.size.height/2.0)
        self.addChild(node)

        moveToPoint(touchPos)

        circle.hidden = false
        circle.position = centripetalPoint
    }
}