dynamic cone shape changes depending on obstacles - reference to Third Eye Crime app

Question

I've seen the Trailer of "Third Eye Crime".

How can you realise the blue field of view cone so that it's shape changes depending on obstacles?

My attempt was to cast rays till an obstacle occurs and then I take the end points of the rays to draw the cone shape.

The problem with my method is that the precision of the cone depends on the number of rays. Besides the more rays are casted the worse the performance.

Here you can see the rays:

Here you can see the cone shape drawn with the end points of the rays:

Are there better solutions?

Answer 1

Here I've found several answers:

https://code.google.com/p/straightedge/

http://www.redblobgames.com/articles/visibility/

Answer 2

Your question has been bugging me all day but I can't find a fully working answer. My work notes are too much for me to write it as a comment so I am adding it as an answer.

My first issue was to test for a contact between a field of view line and any obstruction object. Unfortunately SpriteKit only has the contactBitMask which can do this job AND provide contact coordinates.

I looked at SKNode's intersectsNode: but its return value is only a BOOL and we need coordinates.

I also looked at Apple's Sprite Kit Programming Guide's section Searching for Physics Bodies. This deals with line of sight, obstacles, etc... The command used here is bodyAlongRayStart:end:. The return is the first physics body it intersects with but without providing the coordinates for the actual contact point.

The code I ended up with first draws the complete line of sight cone. Next any lines found contacting an object got the contact point using contact.contactPoint and then deleted the offending line. So far so good. But I ran into trouble trying to draw the deleted line to the new end point (contact point). For some inexplicable reason only some of the deleted lines are being redrawn and not all.

Keep in mind this is rough code so slap it, pull it and throw it against the wall a couple of times. You don't really need the array for example. I hope this will steer you in the right direction or you can spot something I am too blind to see.

Side note: I ran this in simulator iPhone (4 inch) landscape.

#import "MyScene.h"

typedef NS_OPTIONS(uint32_t, CNPhysicsCategory)
{
    Category1  = 1 << 0,
    Category2  = 1 << 1,
    Category3  = 1 << 2,
};

@interface MyScene()<SKPhysicsContactDelegate>
@end

@implementation MyScene
{
    SKSpriteNode *player;
    SKSpriteNode *obstacle1;
    SKSpriteNode *obstacle2;
    SKSpriteNode *obstacle3;
    SKSpriteNode *obstacle4;

    NSMutableArray *beamArray;

    int beamCounter;
}

-(id)initWithSize:(CGSize)size
{
    if (self = [super initWithSize:size])
    {
        self.physicsWorld.contactDelegate = self;

        beamArray = [[NSMutableArray alloc] init];

        beamCounter = 0;

         player = [SKSpriteNode spriteNodeWithColor:[SKColor redColor] size:CGSizeMake(20, 20)];
        player.position = CGPointMake(100, 150);
        [self addChild:player];

        obstacle1 = [SKSpriteNode spriteNodeWithColor:[SKColor blueColor] size:CGSizeMake(200, 20)];
        obstacle1.name = @"obstacle1";
        obstacle1.position = CGPointMake(250, 100);
        obstacle1.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:obstacle1.size];
        obstacle1.physicsBody.affectedByGravity = NO;
        obstacle1.physicsBody.categoryBitMask = Category2;
        obstacle1.physicsBody.collisionBitMask = 0x00000000;
        [self addChild:obstacle1];

        obstacle2 = [SKSpriteNode spriteNodeWithColor:[SKColor blueColor] size:CGSizeMake(40, 40)];
        obstacle2.name = @"obstacle2";
        obstacle2.position = CGPointMake(400, 200);
        obstacle2.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:obstacle2.size];
        obstacle2.physicsBody.affectedByGravity = NO;
        obstacle2.physicsBody.categoryBitMask = Category2;
        obstacle2.physicsBody.collisionBitMask = 0x00000000;
        [self addChild:obstacle2];

        obstacle3 = [SKSpriteNode spriteNodeWithColor:[SKColor blueColor] size:CGSizeMake(50, 20)];
        obstacle3.name = @"obstacle3";
        obstacle3.position = CGPointMake(530, 130);
        obstacle3.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:obstacle3.size];
        obstacle3.physicsBody.affectedByGravity = NO;
        obstacle3.physicsBody.categoryBitMask = Category2;
        obstacle3.physicsBody.collisionBitMask = 0x00000000;
        [self addChild:obstacle3];

        for (int y = 0; y <= 320; y++)
        {
            SKShapeNode *beam1 = [SKShapeNode node];
            beam1.name = [NSString stringWithFormat:@"%i",beamCounter++];
            CGMutablePathRef pathToDraw = CGPathCreateMutable();
            CGPathMoveToPoint(pathToDraw, NULL, player.position.x, player.position.y);
            CGPathAddLineToPoint(pathToDraw, NULL, 600, y);
            beam1.path = pathToDraw;
            [beam1 setStrokeColor:[UIColor yellowColor]];
            [beam1 setLineWidth:2.0];

            beam1.physicsBody = [SKPhysicsBody bodyWithEdgeFromPoint:CGPointMake(player.position.x, player.position.y) toPoint:CGPointMake(600, y)];
            beam1.physicsBody.affectedByGravity = NO;
            beam1.physicsBody.categoryBitMask = Category1;
            beam1.physicsBody.contactTestBitMask = Category2;

            [self addChild:beam1];

            [beamArray addObject:beam1];
        }
    }
    return self;
}

-(void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
    //
}

-(void)update:(CFTimeInterval)currentTime
{
    //
}

- (void)didBeginContact:(SKPhysicsContact *)contact
{
    NSLog(@"bodyA:%@ bodyB:%@",contact.bodyA.node.name, contact.bodyB.node.name);

     uint32_t collision = (contact.bodyA.categoryBitMask | contact.bodyB.categoryBitMask);

    if (collision == (Category1 | Category2))
    {
        CGPoint newEndPoint = contact.contactPoint;

        [beamArray removeObject:contact.bodyA.node.name];
        [contact.bodyA.node removeFromParent];

        SKShapeNode *beam1 = [SKShapeNode node];
        beam1.name = [NSString stringWithFormat:@"%i",beamCounter++];
        CGMutablePathRef pathToDraw = CGPathCreateMutable();
        CGPathMoveToPoint(pathToDraw, NULL, player.position.x, player.position.y);
        CGPathAddLineToPoint(pathToDraw, NULL, newEndPoint.x, newEndPoint.y);
        beam1.path = pathToDraw;
        [beam1 setStrokeColor:[UIColor greenColor]];
        [beam1 setLineWidth:2.0];

        [self addChild:beam1];

    }
}

@end

Removing the touching lines:

Removing the touching lines and replacing the removed lines:

Answer 3

How I would do it is send out a ray at the edges of view and make note of the points that they hit. Then find points that are important(corners of objects for example), form rays with those points and use those rays to find collisions past those points and finally fill triangles with the points and the "source" of the light.

I might get a chance to make pictures to help demonstrate my algorithm later but this is what I have now.

Answer 4

I think the efficient way to do this is to use Bresenham's Algorithm. There are lots of references and example code in the Wikipedia references section.

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm