public
Created

Initial solution attempt for [08/08/13] Challenge #131 [Intermediate] Simple Ray-Casting at http://www.reddit.com/r/dailyprogrammer/comments/1jz2os/080813_challenge_131_intermediate_simple/

  • Download Gist
gistfile1.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
#include <stdio.h>
#include <math.h>
 
int main()
{
// World size
int N, M;
scanf("%d %d", &N, &M);
 
// World buffer (N: characters in row, M: number of rows)
bool* worldData = new bool[ N * M ];
for(int m = 0; m < M; m++)
for(int n = 0; n < N; n++)
{
char temp = ' ';
while( (temp = getc(stdin)) == '\n' );
worldData[m * N + n] = (temp == ' ') ? false : true;
}
 
// Read in the origin and rotation
float X, Y, R;
scanf("%f %f %f", &X, &Y, &R);
float x = X, y = Y;
// A ray will always move towards one or two surfaces, like if
// a ray is defined with R of zero, then it always moves to the right,
// and thus we should only search right of us
bool goingRight = cos(R) >= 0.0f; // X+
bool goingDown = (-sin(R)) >= 0.0f; // Y+
float slope = (-sin(R)) / cos(R);
float b = y - slope * x;
 
// Delta-fudge value; used to bump us off for the next test
// Specificly it is used as a "look ahead" to see what we're colliding into
float df = 0.00001;
float dfx = cos(R) * df;
float dfy = -sin(R) * df;
 
// Keep moving one unit-length ahead until we collide with something
bool collisionFound = false;
while( x > 0.0f && y > 0.0f && x <= N && y <= M && !collisionFound )
{
// What is the Y position if we check the block right/left of us
float tx = goingRight ? ceil(x + df) : floor(x - df);
float nextY = slope * tx + b;
 
// What is the X position if we check the block above/below us
float ty = goingDown ? ceil(y + df) : floor(y - df);
float nextX = (ty - b) / slope;
 
// What's closest? (Overkill, we can just use street/hamming-dist)
float dx = sqrt( pow(tx - x, 2.0f) + pow(nextY - y, 2.0f) );
float dy = sqrt( pow(nextX - x, 2.0f) + pow(ty - y, 2.0f) );
 
if( dx < dy )
{
x = tx;
y = nextY;
}
else
{
x = nextX;
y = ty;
}
 
// Collision check
collisionFound = worldData[ N * (int)(y + dfy) + (int)(x + dfx) ];
}
 
// Echo off results
if(collisionFound)
{
printf("%.3f %.3f\n", x, y);
}
else
{
printf("No collision found!\n");
}
 
return 0;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.