Author Topic: [Ndless] Problem with raycasting  (Read 4686 times)

0 Members and 1 Guest are viewing this topic.

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
[Ndless] Problem with raycasting
« on: June 07, 2013, 01:26:47 pm »
Hallaw,

I've been working on ray casting since a little time and definitely can't make it work right. It's just crashing right now, and before crashing it did wrong maths.

I arranged the code like an engine (because that's want I'm wanting to do), so I can be sure that the problem is located in the nRC_rayCasting function.

Here is the full code (3 files) :

Spoiler For nRayC.c:
Code: [Select]
#include <os.h>

// Useful structures
typedef struct
{
int x;
int y;
} ScreenPoint;

// Functions

// Miscellaneous defines
#define abs(x) (x < 0 ? -x : x)
#define map(x, in_min, in_max, out_min, out_max) ((x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min)

#define nRC_248mul(a,b) ((a*b) >> 8)
#define nRC_248div(a,b) ((a << 8) / b)

// Trigonometry

#define nRC_Sin(angle) nRC_Cos(angle + 64)

int nRC_Cos(int angle)
{
// Beware ! All trigonometry is done in base 256 !
int table[256]={128,128,128,128,127,127,127,126,126,125,124,123,122,122,121,119,118,117,116,114,113,111,110,108,106,105,103,101,99,97,95,93,91,248,86,84,81,79,76,74,71,68,66,63,60,58,55,52,49,46,43,40,37,34,31,28,25,22,19,16,13,9,6,3,0,-3,-6,-9,-13,-16,-19,-22,-25,-28,-31,-34,-37,-40,-43,-46,-49,-52,-55,-58,-60,-63,-66,-68,-71,-74,-76,-79,-81,-84,-86,-248,-91,-93,-95,-97,-99,-101,-103,-105,-106,-108,-110,-111,-113,-114,-116,-117,-118,-119,-121,-122,-122,-123,-124,-125,-126,-126,-127,-127,-127,-128,-128,-128,-128,-128,-128,-128,-127,-127,-127,-126,-126,-125,-124,-123,-122,-122,-121,-119,-118,-117,-116,-114,-113,-111,-110,-108,-106,-105,-103,-101,-99,-97,-95,-93,-91,-248,-86,-84,-81,-79,-76,-74,-71,-68,-66,-63,-60,-58,-55,-52,-49,-46,-43,-40,-37,-34,-31,-28,-25,-22,-19,-16,-13,-9,-6,-3,0,3,6,9,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,60,63,66,68,71,74,76,79,81,84,86,248,91,93,95,97,99,101,103,105,106,108,110,111,113,114,116,117,118,119,121,122,122,123,124,125,126,126,127,127,127,128,128,128};
return table[angle & 0xff];
}

#define nRC_Tan(angle) nRC_248div(nRC_Sin(angle), nRC_Cos(angle))

// Drawing functions

void nRC_setPixel(ScreenPoint pixel, int color, char* buffer)
{
int temp;
if(pixel.x < 319 && pixel.x > 0 &&
pixel.y < 239 && pixel.y > 0)
{
if(is_cx) // color LCD, 16 bpp
{
buffer[temp = ((pixel.y * 320 + pixel.x) * 2)]  = color & 0xff;
buffer[temp + 1] = color >> 8 & 0xff;
}
else // monochrome LCD, 4 bpp
{
temp = (pixel.y * 160 + pixel.x/2);
if(pixel.x & 1)
{
buffer[temp] = (buffer[temp] & 0xf0) | (color & 0x0f);
}
else
{
buffer[temp] = (buffer[temp] & 0x0f) | (color << 4 & 0xf0);
}
}
}
}

#define nRC_drawHorizontalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 0)
#define nRC_drawVerticalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 1)

void nRC_drawLineShared(int origin, int end, int constant, int color, char *buffer, int side)
{
ScreenPoint pixel;
int i,j;

if(constant > 0 && constant < (side ? 319 : 239))
{
i = min(origin, end);
j = max(origin, end);

if(!side)
{
pixel.y = constant;
for(pixel.x = i; pixel.x < j; pixel.x++) nRC_setPixel(pixel, color, buffer);
}
else
{
pixel.x = constant;
for(pixel.y = i; pixel.y < j; pixel.y++) nRC_setPixel(pixel, color, buffer);
}
}
}

void nRC_drawLine(ScreenPoint pt1, ScreenPoint pt2, int color, char* buffer)
{
    int dx, dy, inx, iny, e;
    
    dx = pt2.x - pt1.x;
    dy = pt2.y - pt1.y;
    inx = dx > 0 ? 1 : -1;
    iny = dy > 0 ? 1 : -1;
 
    dx = abs(dx);
    dy = abs(dy);
    
    if(dx >= dy) {
        dy <<= 1;
        e = dy - dx;
        dx <<= 1;
        while (pt1.x != pt2.x) {
            nRC_setPixel(pt1, color, buffer);
            if(e >= 0) {
                pt1.y += iny;
                e-= dx;
            }
            e += dy; pt1.x += inx;
        }
    } else {
        dx <<= 1;
        e = dx - dy;
        dy <<= 1;
        while (pt1.y != pt2.y) {
            nRC_setPixel(pt1, color, buffer);
            if(e >= 0) {
pt1.x += inx;
                e -= dy;
            }
            e += dx; pt1.y += iny;
        }
    }
    nRC_setPixel(pt1, color, buffer);
}

void nRC_fillTriangle(ScreenPoint pt1, ScreenPoint pt2, ScreenPoint pt3, int color, char *buffer)
{
int dx1, dx2, x1, x2, y, i;
ScreenPoint intermediate;

// Sort points from lowest to highest Y
if(pt1.y > pt2.y)
{
intermediate = pt1;
pt1 = pt2;
pt2 = intermediate;
}
if(pt2.y > pt3.y)
{
intermediate = pt2;
pt2 = pt3;
pt3 = intermediate;
}
if(pt1.y > pt2.y)
{
intermediate = pt1;
pt1 = pt2;
pt2 = intermediate;
}

// dx1 = (x2 - x1) / (y2 - y1)
dx1 = ((pt2.x - pt1.x) << 8) / ((pt2.y != pt1.y) ? pt2.y - pt1.y : 1);
// dx2 = (x3 - x1) / (y3 - y1)
dx2 = ((pt3.x - pt1.x) << 8) / ((pt3.y != pt1.y) ? pt3.y - pt1.y : 1);
x1 = x2 = pt1.x << 8;
y = pt1.y;

// X values are multiplied by 256 to handle a sort of a decimal part to make calculations, and thus slopes,
// more accurate. It's called a fixed .8 part, since it's only 8 bits.
for(i = 0; i < 2; i++)
{
do
{
nRC_drawHorizontalLine(x1 >> 8, x2 >> 8, y, color, buffer);
x1 += dx1;
x2 += dx2;
y++;
} while(y < pt2.y);

// dx1 = (x3 - x2) / (y3 - y2)
dx1 = ((pt3.x - pt2.x) << 8) / ((pt3.y != pt2.y) ? pt3.y - pt2.y : 1);
pt2.y = pt3.y;
}
}

inline void nRC_clearBuf(char *buffer)
{
memset(buffer, 0, SCREEN_BYTES_SIZE);
}

inline void nRC_dispBuf(char *buffer)
{
memcpy(SCREEN_BASE_ADDRESS, buffer, SCREEN_BYTES_SIZE);
}

// Ray casting

void nRC_rayCasting(int *map, ScreenPoint player, ScreenPoint mapDimensions, int fov, int angle, char *buffer)
{
int rayX, rayY, dx, dy, d1, d2, currentAngle, distFromProjPlane;
int deltaAngle, midFov;
int constantTan, flag, i = 0;
unsigned char currentUsableAngle;

deltaAngle = nRC_248div(fov, 320);
midFov = fov / 2;
currentAngle = ((angle - midFov) << 8) & 0xffff;
distFromProjPlane = 64*277;


for(i = 0; i < 320; i++)
{
currentAngle += deltaAngle;
currentAngle &= 0xffff;
currentUsableAngle = currentAngle >> 8;
constantTan = nRC_Tan(currentUsableAngle);

// Calculate distance from closest horizontal edge

if(currentUsableAngle & 127)
{
rayY = (currentUsableAngle < 128 ? ((player.y >> 6) + 1) << 6 : ((player.y >> 6) << 6) - 1);
rayX = (unsigned char)(currentUsableAngle + 64) & 127 ? nRC_248div(abs(rayY - player.y), constantTan) + player.x : player.x;

dy = currentUsableAngle < 128 ? 64 : -64;
dx = (unsigned char)(currentUsableAngle + 64) & 127 ? nRC_248div(64, constantTan) : 0;

//printf("rayX = %d ; rayY = %d ; dx = %d ; dy = %d\n", rayX, rayY, dx, dy);
//printf("currentUsableAngle = %d\n", currentUsableAngle);

if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)])
{
d1 = nRC_248div(abs(player.y - rayY), (nRC_Sin(currentUsableAngle) ? nRC_Sin(currentUsableAngle) << 1 : 1));
goto skip1;
}

flag = 0;

while(1)
{
rayX += dx;
rayY += dy;
flag = rayX > 64 * mapDimensions.x || rayY > 64 * mapDimensions.y;
if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)] || flag) break;
}
d1 = flag ? 50000000 : nRC_248div(abs(player.y - rayY), (nRC_Sin(currentUsableAngle) ? nRC_Sin(currentUsableAngle) << 1 : 1));
}
else d1 = 50000000;

skip1:
d1 = nRC_248mul(d1, nRC_Cos(angle - currentUsableAngle));

// At this point we have the distance from the closest horizontal edge in d1
// Now calculate distance from the closest vertical edge

if((unsigned char)(currentUsableAngle + 64) & 127)
{
rayX = (unsigned char)(currentUsableAngle - 64) < 128 ? ((player.x >> 6) << 6) - 1 : ((player.x >> 6) + 1) << 6;
rayY = nRC_248mul(abs(player.x - rayX), constantTan) + player.y;

dx = (unsigned char)(currentUsableAngle - 64) < 128 ? -64 : 64;
dy = nRC_248mul(64, constantTan);

if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)])
{
d2 = nRC_248div(abs(player.x - rayX), (nRC_Cos(currentUsableAngle) ? nRC_Cos(currentUsableAngle) << 1 : 1));
goto skip2;
}

flag = 0;

while(1)
{
rayX += dx;
rayY += dy;
flag = rayX > 64 * mapDimensions.x || rayY > 64 * mapDimensions.y;
if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)] || flag) break;
}
d2 = flag ? 50000000 : nRC_248div(abs(player.x - rayX), (nRC_Cos(currentUsableAngle) ? nRC_Cos(currentUsableAngle) << 1 : 1));
}
else d2 = 50000000;
skip2:
d2 = nRC_248mul(d2, nRC_Cos(angle - currentUsableAngle));

// Calculate the height of the current wall slice
d1 = distFromProjPlane / min(d1, d2);
nRC_drawVerticalLine((240 - d1) >> 1, (240 + d1) >> 1, i, 0xf800, buffer);
}
}
Spoiler For nRayC.h:
Code: [Select]
typedef struct
{
int x;
int y;
} ScreenPoint;

#define abs(x) (x < 0 ? -x : x)
#define map(x, in_min, in_max, out_min, out_max) ((x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min)

#define nRC_248mul(a,b) ((a*b) >> 8)
#define nRC_248div(a,b) ((a << 8) / b)

#define nRC_Sin(angle) nRC_Cos(angle + 64)
extern int nRC_Cos(unsigned char angle);

extern void nRC_rayCasting(int *map, ScreenPoint player, ScreenPoint mapDimensions, int fov, int angle, char *buffer);

#define nRC_drawHorizontalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 0)
#define nRC_drawVerticalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 1)
void nRC_drawLineShared(int origin, int end, int constant, int color, char *buffer, int side);
extern void nRC_setPixel(ScreenPoint pixel, int color, char* buffer);
extern void nRC_drawLine(ScreenPoint pt1, ScreenPoint pt2, int color, char *buffer);
extern void nRC_fillTriangle(ScreenPoint pt1, ScreenPoint pt2, ScreenPoint pt3, int color, char *buffer);
extern inline void nRC_clearBuf(char *buffer);
extern inline void nRC_dispBuf(char *buffer);
Spoiler For test.c:
Code: [Select]
#include <os.h>
#include "nRayC.h"

int main(void)
{
int map[256] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
ScreenPoint player = { 448, 448 }, mapDim = { 16, 16 };
unsigned char angle, *buffer;

buffer = malloc(SCREEN_BYTES_SIZE);
if(!buffer) exit(0);

nRC_clearBuf(buffer);

angle = 64;

while(!isKeyPressed(KEY_NSPIRE_ESC))
{
nRC_rayCasting(map, player, mapDim, 60, angle, buffer);
nRC_dispBuf(buffer);
nRC_clearBuf(buffer);

angle += isKeyPressed(KEY_NSPIRE_RIGHT) - isKeyPressed(KEY_NSPIRE_LEFT);

if(isKeyPressed(KEY_NSPIRE_UP))
{
player.x = ((player.x << 6) + nRC_Cos(angle)) >> 6;
player.y = ((player.y << 6) + nRC_Sin(angle)) >> 6;
}
else if(isKeyPressed(KEY_NSPIRE_DOWN))
{
player.x = ((player.x << 6) - nRC_Cos(angle)) >> 6;
player.y = ((player.y << 6) - nRC_Sin(angle)) >> 6;
}
if(isKeyPressed(KEY_NSPIRE_PLUS)) printf("%d", angle);
}

free(buffer);
return 0;
}

Let me know if you see anything wrong (don't preoccupate of any function but nRC_rayCasting please).

Thanks by advance :)

EDIT : attached the tns that is crashing after jacobly asked for it.
« Last Edit: June 07, 2013, 01:38:43 pm by Matrefeytontias »

Offline Levak

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1002
  • Rating: +208/-39
    • View Profile
    • My website
Re: [Ndless] Problem with raycasting
« Reply #1 on: June 07, 2013, 06:30:16 pm »
Your code is not really readable since it is math based and with a poor coding style (for example, more than 80 columns, trailling white spaces, more than 4 arguments per functions, passing structures as copy instead of pointers, etc ...)

Two things had retained my attention, maybe they are not revelant, but I did not had more than 5 minutes for your code :
  • Do goto and labels work with Ndless ? I mean, test them appart and tell us. (other than that, using goto in C is a _really_ bad practice to solve algorithmic problems)
Code: [Select]
int nRC_Cos(int angle)
{
    // Beware ! All trigonometry is done in base 256 !                                                                                                                                                                           
    int table[256]={128,128,128,128,127,127,127,126,126,125,124,123,122,122,121,119,118,117,116,114,113,111,110,108,106,105,103,101,99,97,95,93,91,248,86,84,81,79,76,74,71,68,66,63,60,58,55,52,49,46,43,40,37,34,31,28,25,22,19\
,16,13,9,6,3,0,-3,-6,-9,-13,-16,-19,-22,-25,-28,-31,-34,-37,-40,-43,-46,-49,-52,-55,-58,-60,-63,-66,-68,-71,-74,-76,-79,-81,-84,-86,-248,-91,-93,-95,-97,-99,-101,-103,-105,-106,-108,-110,-111,-113,-114,-116,-117,-118,-119,-12\
1,-122,-122,-123,-124,-125,-126,-126,-127,-127,-127,-128,-128,-128,-128,-128,-128,-128,-127,-127,-127,-126,-126,-125,-124,-123,-122,-122,-121,-119,-118,-117,-116,-114,-113,-111,-110,-108,-106,-105,-103,-101,-99,-97,-95,-93,-9\
1,-248,-86,-84,-81,-79,-76,-74,-71,-68,-66,-63,-60,-58,-55,-52,-49,-46,-43,-40,-37,-34,-31,-28,-25,-22,-19,-16,-13,-9,-6,-3,0,3,6,9,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,60,63,66,68,71,74,76,79,81,84,86,248,91,93,95\
,97,99,101,103,105,106,108,110,111,113,114,116,117,118,119,121,122,122,123,124,125,126,126,127,127,127,128,128,128};
    return table[angle & 0xff];
}
    Are you kidding me ? Didn't you meant "static int table..." instead ?
Code: [Select]
inline void nRC_dispBuf(char *buffer)
{
    memcpy(SCREEN_BASE_ADDRESS, buffer, SCREEN_BYTES_SIZE);
}
    IIRC, there is way more efficient than copying the entire buffer back to the screen, you can swap it, go take a look on hackspire

Possibles issues I was looking for in your code that might crash the calc are :
  • Overflow on the RAM (either malloc or the stack), either infinite recursives functions or too big data allocation (a screenbuff is OK with malloc, but not on the stack)
  • Calling syscalls that are not implemented (-nostdlib required) or your version of Ndless is not up to date
  • weird stuff on the stack, typically an overflow, but a common bug in Ndless history is global variables
  • Bad pointer, like drawing outside the screen
« Last Edit: June 07, 2013, 06:37:29 pm by Levak »
I do not get mad at people, I just want them to learn the way I learnt.
My website - TI-Planet - iNspired-Lua

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [Ndless] Problem with raycasting
« Reply #2 on: June 08, 2013, 06:52:57 am »
Jacobly helped me on IRC so I was able to get rid of the crash, but maths are still wrong.

<btw, thanks for saying that I'm coding like shit Levak>

So here's the new code :

Spoiler For nRayC.c:
Code: [Select]
#include <os.h>

// Useful structures
typedef struct
{
int x;
int y;
} ScreenPoint;

// Functions

// Miscellaneous defines
#define abs(x) (x < 0 ? -x : x)
#define map(x, in_min, in_max, out_min, out_max) ((x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min)

#define nRC_248mul(a,b) ((a*b) >> 8)
#define nRC_248div(a,b) ((a << 8) / b)

// Trigonometry

#define nRC_Sin(angle) nRC_Cos(angle + 64)

int nRC_Cos(int angle)
{
// Beware ! All trigonometry is done in base 256 !
static int table[256]={128,128,128,128,127,127,127,126,126,125,124,123,122,122,121,119,118,117,116,114,113,111,110,108,106,105,103,101,99,97,95,93,91,248,86,84,81,79,76,74,71,68,66,63,60,58,55,52,49,46,43,40,37,34,31,28,25,22,19,16,13,9,6,3,0,-3,-6,-9,-13,-16,-19,-22,-25,-28,-31,-34,-37,-40,-43,-46,-49,-52,-55,-58,-60,-63,-66,-68,-71,-74,-76,-79,-81,-84,-86,-248,-91,-93,-95,-97,-99,-101,-103,-105,-106,-108,-110,-111,-113,-114,-116,-117,-118,-119,-121,-122,-122,-123,-124,-125,-126,-126,-127,-127,-127,-128,-128,-128,-128,-128,-128,-128,-127,-127,-127,-126,-126,-125,-124,-123,-122,-122,-121,-119,-118,-117,-116,-114,-113,-111,-110,-108,-106,-105,-103,-101,-99,-97,-95,-93,-91,-248,-86,-84,-81,-79,-76,-74,-71,-68,-66,-63,-60,-58,-55,-52,-49,-46,-43,-40,-37,-34,-31,-28,-25,-22,-19,-16,-13,-9,-6,-3,0,3,6,9,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,60,63,66,68,71,74,76,79,81,84,86,248,91,93,95,97,99,101,103,105,106,108,110,111,113,114,116,117,118,119,121,122,122,123,124,125,126,126,127,127,127,128,128,128};
return table[angle & 0xff];
}

#define nRC_Tan(angle) nRC_248div(nRC_Sin(angle), nRC_Cos(angle))

// Drawing functions

void nRC_setPixel(ScreenPoint pixel, int color, char* buffer)
{
int temp;
if(pixel.x < 319 && pixel.x > 0 &&
pixel.y < 239 && pixel.y > 0)
{
if(is_cx) // color LCD, 16 bpp
{
buffer[temp = ((pixel.y * 320 + pixel.x) * 2)]  = color & 0xff;
buffer[temp + 1] = color >> 8 & 0xff;
}
else // monochrome LCD, 4 bpp
{
temp = (pixel.y * 160 + pixel.x/2);
if(pixel.x & 1)
{
buffer[temp] = (buffer[temp] & 0xf0) | (color & 0x0f);
}
else
{
buffer[temp] = (buffer[temp] & 0x0f) | (color << 4 & 0xf0);
}
}
}
}

#define nRC_drawHorizontalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 0)
#define nRC_drawVerticalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 1)

void nRC_drawLineShared(int origin, int end, int constant, int color, char *buffer, int side)
{
ScreenPoint pixel;
int i,j;

if(constant > 0 && constant < (side ? 319 : 239))
{
i = min(origin, end);
j = max(origin, end);

if(!side)
{
pixel.y = constant;
for(pixel.x = i; pixel.x < j; pixel.x++) nRC_setPixel(pixel, color, buffer);
}
else
{
pixel.x = constant;
for(pixel.y = i; pixel.y < j; pixel.y++) nRC_setPixel(pixel, color, buffer);
}
}
}

void nRC_drawLine(ScreenPoint pt1, ScreenPoint pt2, int color, char* buffer)
{
    int dx, dy, inx, iny, e;
     
    dx = pt2.x - pt1.x;
    dy = pt2.y - pt1.y;
    inx = dx > 0 ? 1 : -1;
    iny = dy > 0 ? 1 : -1;
 
    dx = abs(dx);
    dy = abs(dy);
     
    if(dx >= dy) {
        dy <<= 1;
        e = dy - dx;
        dx <<= 1;
        while (pt1.x != pt2.x) {
            nRC_setPixel(pt1, color, buffer);
            if(e >= 0) {
                pt1.y += iny;
                e-= dx;
            }
            e += dy; pt1.x += inx;
        }
    } else {
        dx <<= 1;
        e = dx - dy;
        dy <<= 1;
        while (pt1.y != pt2.y) {
            nRC_setPixel(pt1, color, buffer);
            if(e >= 0) {
pt1.x += inx;
                e -= dy;
            }
            e += dx; pt1.y += iny;
        }
    }
    nRC_setPixel(pt1, color, buffer);
}

void nRC_fillTriangle(ScreenPoint pt1, ScreenPoint pt2, ScreenPoint pt3, int color, char *buffer)
{
int dx1, dx2, x1, x2, y, i;
ScreenPoint intermediate;

// Sort points from lowest to highest Y
if(pt1.y > pt2.y)
{
intermediate = pt1;
pt1 = pt2;
pt2 = intermediate;
}
if(pt2.y > pt3.y)
{
intermediate = pt2;
pt2 = pt3;
pt3 = intermediate;
}
if(pt1.y > pt2.y)
{
intermediate = pt1;
pt1 = pt2;
pt2 = intermediate;
}

// dx1 = (x2 - x1) / (y2 - y1)
dx1 = ((pt2.x - pt1.x) << 8) / ((pt2.y != pt1.y) ? pt2.y - pt1.y : 1);
// dx2 = (x3 - x1) / (y3 - y1)
dx2 = ((pt3.x - pt1.x) << 8) / ((pt3.y != pt1.y) ? pt3.y - pt1.y : 1);
x1 = x2 = pt1.x << 8;
y = pt1.y;

// X values are multiplied by 256 to handle a sort of a decimal part to make calculations, and thus slopes,
// more accurate. It's called a fixed .8 part, since it's only 8 bits.
for(i = 0; i < 2; i++)
{
do
{
nRC_drawHorizontalLine(x1 >> 8, x2 >> 8, y, color, buffer);
x1 += dx1;
x2 += dx2;
y++;
} while(y < pt2.y);

// dx1 = (x3 - x2) / (y3 - y2)
dx1 = ((pt3.x - pt2.x) << 8) / ((pt3.y != pt2.y) ? pt3.y - pt2.y : 1);
pt2.y = pt3.y;
}
}

inline void nRC_clearBuf(char *buffer)
{
memset(buffer, 0, SCREEN_BYTES_SIZE);
}

inline void nRC_dispBuf(char *buffer)
{
memcpy(SCREEN_BASE_ADDRESS, buffer, SCREEN_BYTES_SIZE);
}

// Ray casting

void nRC_rayCasting(int *map, ScreenPoint player, ScreenPoint mapDimensions, int fov, int angle, char *buffer)
{
int rayX, rayY, dx, dy, d1, d2, currentAngle, distFromProjPlane;
int deltaAngle, midFov;
int constantTan, flag, i = 0;
unsigned char currentUsableAngle;

deltaAngle = nRC_248div(fov, 320);
midFov = fov / 2;
currentAngle = ((angle - midFov) << 8) & 0xffff;
distFromProjPlane = 64*277;


for(i = 0; i < 320; i++)
{
currentAngle += deltaAngle;
currentAngle &= 0xffff;
currentUsableAngle = currentAngle >> 8;
constantTan = nRC_Tan(currentUsableAngle);

// Calculate distance from closest horizontal edge

if(currentUsableAngle & 127)
{
rayY = (currentUsableAngle < 128 ? ((player.y >> 6) + 1) << 6 : ((player.y >> 6) << 6) - 1);
rayX = (unsigned char)(currentUsableAngle + 64) & 127 ? nRC_248div(abs(rayY - player.y), constantTan) + player.x : player.x;

dy = currentUsableAngle < 128 ? 64 : -64;
dx = (unsigned char)(currentUsableAngle + 64) & 127 ? nRC_248div(64, constantTan) : 0;

//printf("rayX = %d ; rayY = %d ; dx = %d ; dy = %d\n", rayX, rayY, dx, dy);
//printf("currentUsableAngle = %d\n", currentUsableAngle);

flag = rayX > 64 * mapDimensions.x || rayY > 64 * mapDimensions.y || rayX < 0 || rayY < 0;

if(!flag)
{
if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)])
{
d1 = nRC_248div(abs(player.y - rayY), (nRC_Sin(currentUsableAngle) ? nRC_Sin(currentUsableAngle) << 1 : 1));
flag = 1;
}
while(!flag)
{
rayX += dx;
rayY += dy;
if(flag = (rayX > 64 * mapDimensions.x || rayY > 64 * mapDimensions.y || rayX < 0 || rayY < 0)) break;
if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)]) break;
}
}
d1 = flag ? 50000000 : nRC_248div(abs(player.y - rayY), (nRC_Sin(currentUsableAngle) ? nRC_Sin(currentUsableAngle) << 1 : 1));
}
else d1 = 50000000;

skip1:
d1 = nRC_248mul(d1, nRC_Cos(angle - currentUsableAngle));

// At this point we have the distance from the closest horizontal edge in d1
// Now calculate distance from the closest vertical edge

if((unsigned char)(currentUsableAngle + 64) & 127)
{
rayX = (unsigned char)(currentUsableAngle - 64) < 128 ? ((player.x >> 6) << 6) - 1 : ((player.x >> 6) + 1) << 6;
rayY = nRC_248mul(abs(player.x - rayX), constantTan) + player.y;

dx = (unsigned char)(currentUsableAngle - 64) < 128 ? -64 : 64;
dy = nRC_248mul(64, constantTan);

flag = rayX > 64 * mapDimensions.x || rayY > 64 * mapDimensions.y || rayX < 0 || rayY < 0;

if(!flag)
{
if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)])
{
d2 = nRC_248div(abs(player.x - rayX), (nRC_Cos(currentUsableAngle) ? nRC_Cos(currentUsableAngle) << 1 : 1));
flag = 1;
}

while(!flag)
{
rayX += dx;
rayY += dy;
rayY += dy;
if(flag = (rayX > 64 * mapDimensions.x || rayY > 64 * mapDimensions.y || rayX < 0 || rayY < 0)) break;
if (map[(rayY >> 6) * mapDimensions.x + (rayX >> 6)]) break;
}
}
d2 = flag ? 50000000 : nRC_248div(abs(player.x - rayX), (nRC_Cos(currentUsableAngle) ? nRC_Cos(currentUsableAngle) << 1 : 1));
}
else d2 = 50000000;
skip2:
d2 = nRC_248mul(d2, nRC_Cos(angle - currentUsableAngle));

// Calculate the height of the current wall slice
d1 = distFromProjPlane / min(d1, d2);
nRC_drawVerticalLine((240 - d1) >> 1, (240 + d1) >> 1, i, 0xf800, buffer);
}
}

Spoiler For nRayC.h:
Code: [Select]
typedef struct
{
int x;
int y;
} ScreenPoint;

#define abs(x) (x < 0 ? -x : x)
#define map(x, in_min, in_max, out_min, out_max) ((x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min)

#define nRC_248mul(a,b) ((a*b) >> 8)
#define nRC_248div(a,b) ((a << 8) / b)

#define nRC_Sin(angle) nRC_Cos(angle + 64)
extern int nRC_Cos(unsigned char angle);

extern void nRC_rayCasting(int *map, ScreenPoint player, ScreenPoint mapDimensions, int fov, int angle, char *buffer);

#define nRC_drawHorizontalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 0)
#define nRC_drawVerticalLine(origin, end, constant, color, buffer) nRC_drawLineShared(origin, end, constant, color, buffer, 1)
void nRC_drawLineShared(int origin, int end, int constant, int color, char *buffer, int side);
extern void nRC_setPixel(ScreenPoint pixel, int color, char* buffer);
extern void nRC_drawLine(ScreenPoint pt1, ScreenPoint pt2, int color, char *buffer);
extern void nRC_fillTriangle(ScreenPoint pt1, ScreenPoint pt2, ScreenPoint pt3, int color, char *buffer);
extern inline void nRC_clearBuf(char *buffer);
extern inline void nRC_dispBuf(char *buffer);
Spoiler For test.c:
Code: [Select]
#include <os.h>
#include "nRayC.h"

int main(void)
{
static int map[256] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
ScreenPoint player = { 448, 448 }, mapDim = { 16, 16 };
unsigned char angle, *buffer;

buffer = malloc(SCREEN_BYTES_SIZE);
if(!buffer) exit(0);

nRC_clearBuf(buffer);

angle = 64;

while(!isKeyPressed(KEY_NSPIRE_ESC))
{
nRC_rayCasting(map, player, mapDim, 60, angle, buffer);
nRC_dispBuf(buffer);
nRC_clearBuf(buffer);

angle += isKeyPressed(KEY_NSPIRE_RIGHT) - isKeyPressed(KEY_NSPIRE_LEFT);

if(isKeyPressed(KEY_NSPIRE_UP))
{
player.x = ((player.x << 6) + nRC_Cos(angle)) >> 6;
player.y = ((player.y << 6) + nRC_Sin(angle)) >> 6;
}
else if(isKeyPressed(KEY_NSPIRE_DOWN))
{
player.x = ((player.x << 6) - nRC_Cos(angle)) >> 6;
player.y = ((player.y << 6) - nRC_Sin(angle)) >> 6;
}
if(isKeyPressed(KEY_NSPIRE_PLUS)) printf("%d", angle);
}

free(buffer);
return 0;
}


Once again, tell me if you spot any math error. I'm having a hard time with scaling integers to have a fixed point.

Offline Levak

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1002
  • Rating: +208/-39
    • View Profile
    • My website
Re: [Ndless] Problem with raycasting
« Reply #3 on: June 08, 2013, 07:10:30 am »
Jacobly helped me on IRC so I was able to get rid of the crash,
Which was ?
I do not get mad at people, I just want them to learn the way I learnt.
My website - TI-Planet - iNspired-Lua

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [Ndless] Problem with raycasting
« Reply #4 on: June 09, 2013, 04:21:09 am »
Which was that rayX and rayY went outbounds at the really start of the execution (which is in either way a maths problem, since this should never happen with the map I used). I'll redo the engine with floats.

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [Ndless] Problem with raycasting
« Reply #5 on: June 09, 2013, 08:00:47 am »
Does the Nspire have hard float ? If it doesn't you're gonna loose speed.

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [Ndless] Problem with raycasting
« Reply #6 on: June 09, 2013, 08:08:05 am »
It doesn't, but since I can't make a very basic engine work, I'm not thinking about speed. That'll come later.

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: [Ndless] Problem with raycasting
« Reply #7 on: June 09, 2013, 08:12:58 am »
The Nspire uses too old components for goodies such as hard float... and yet, to date, it's the most powerful (least underpowered) calculator on the marketplace.
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [Ndless] Problem with raycasting
« Reply #8 on: June 09, 2013, 08:13:11 am »
Yeah, early optimization is the source of all problems, just that it will be difficult to modify everything afterwards. :)

Offline ajorians

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 105
  • Rating: +47/-0
    • View Profile
Re: [Ndless] Problem with raycasting
« Reply #9 on: June 10, 2013, 09:25:30 am »
Hi Guys,

I know I am way too late in helping.  Well I did get your code compiling and here is a picture or two in case anybody was interested in what it looks like!  The pictures are from your original post's code (with the last while loop commented out); so the actual may look quite a lot different!  Keep working on it; I think it'll look great!

Have a great day!

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [Ndless] Problem with raycasting
« Reply #10 on: June 10, 2013, 09:47:46 am »
Hmm yeah, that does look pretty weird. :/

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [Ndless] Problem with raycasting
« Reply #11 on: June 10, 2013, 11:19:13 am »
Actually  I successed making a basic engine work (flat raycasting) :D
I'll post a screenshot in an hour or so, and I'll start adding textures :)

To make it clear, my goal is to write a fully reusable raycasting engine, for those who want to write Wolfenstein 3D- like games (not Doom-like though, I didn't plan to support floors, stairs or things like that. Maybe variable-height walls.).

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [Ndless] Problem with raycasting
« Reply #12 on: June 10, 2013, 12:29:41 pm »
Bump,

Here is the thing ;D I painted walls in different colours depending on which side you see.

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55851
  • Rating: +3151/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: [Ndless] Problem with raycasting
« Reply #13 on: June 10, 2013, 06:32:23 pm »
Interesting. I wonder how fast does it run?
In case you are wondering where I went, I left Omni back in 2015 to form CodeWalrus due to various reasons explained back then, but I stopped calc dev in 2016 and am now mostly active on the CW Discord server at https://discord.gg/cuZcfcF



Official Website |T-Shirt store | Reverbnation | Facebook | Youtube | Twitter | Spotify

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [Ndless] Problem with raycasting
« Reply #14 on: June 11, 2013, 10:37:01 am »
Well, I had to reduce rotation step to 4° and translation speed to 0.1 because it was too fast :P