|
|
|
| Raycasting problems |
|
aybabtu
Member #2,891
November 2002
|
I'll try to compile it today... |
|
MindCode
Member #2,031
March 2002
 |
I once wrote a raycasting engine (many a moon ago). I had the same speed problem. 23yrold is going in the right direction, take larger steps at first, until you know your going to hit something, then when collision has been verified, you can actually calculate the point of collision from there. My method involved a tile based system. Each "tile" (or block) was fixed size (I used 128 which was also the texture width and height). I only stepped the tiles, so it went pretty fast. When the tile was hit I did a little extra trig to find out the horizontal (x) coord of the surface it hit which then went into texture mapping. If you want your textures to look even better I would suggest using some kind of mip-mapping scheme. Since your already sampling the texture in a linear fashion (vertically) it would simply be a matter of summing non-visible texels around the visible one and taking an average. Also I would suggest you switch to fixed point math. I'm not a big proprieter of fixed point since (in most cases) floating point is not as slow anymore, but converting floating point to integer is (on many cpu's). In the core of loop you are converting the step values to integers so that they can index the map array. this: x_tile = x_tile_step >> 16; if(map[x_tile][y_tile] == EMPTY) is much better than this: x_tile = (int) (x_trig_step / MAP_SIZE); if(map[x_tile][y_tile] == EMPTY) I wish I still had that source code for raycaster. It ran swift on my POS 100mhz laptop. And it was light too, only about 30 lines or so in the core loop. ______________________________________ |
|
23yrold3yrold
Member #1,134
March 2001
 |
Thanks for the tip about fixed, MC, but I'll worry about just getting it working for the moment Here's my latest attempt. It stopped crashing as soon as I added the fstream to log certian values; it's almost like it knows I'm watching it 1#define __GTHREAD_HIDE_WIN32API
2
3#include <math.h>
4#include <fstream>
5#include <allegro.h>
6using namespace std;
7
8#define TILE 64
9#define TILESHIFT 6
10#define SCREENWIDTH 320
11#define SCREENHEIGHT 200
12#define M_PI 3.1415926535897932
13
14int level[9][9]={
15{1,1,1,1,1,1,1,1,1},
16{1,0,0,0,0,0,0,0,1},
17{1,0,1,0,1,0,1,0,1},
18{1,0,0,0,0,0,0,0,1},
19{1,0,1,0,1,0,1,0,1},
20{1,0,0,0,0,0,0,0,1},
21{1,0,1,0,1,0,1,0,1},
22{1,0,0,0,0,0,0,0,1},
23{1,1,1,1,1,1,1,1,1}};
24
25int view[320];
26int texture_map[320];
27int px = 65;
28int py = 65;
29int p_old_x = 65;
30int p_old_y = 65;
31int ps = 5; // player speed
32float pa = 1; // player angle
33
34BITMAP* front;
35BITMAP* backdrop;
36BITMAP* texture;
37
38// float cast_ray(int x, int y, float a);
39float CastRay(int xpos, int ypos, double angle, int& t);
40void draw_view();
41void do_raycasting();
42bool collisions();
43void my_draw_circle(BITMAP *b, int x, int y, int radius, int color);
44
45int main()
46{
47 allegro_init();
48 install_keyboard();
49 set_color_depth(16);
50 set_gfx_mode(GFX_AUTODETECT, SCREENWIDTH, SCREENHEIGHT, 0, 0);
51 text_mode(-1);
52
53 front = create_bitmap(SCREENWIDTH, SCREENHEIGHT);
54 backdrop = create_bitmap(SCREENWIDTH, SCREENHEIGHT);
55
56 for(int i = 0 ; i < 100 ; ++i) hline(backdrop, 0, i, 320, makecol(200, 200, 255 - i));
57 rectfill(backdrop, 0, 100, SCREENWIDTH, SCREENHEIGHT, makecol(0,100,0));
58 texture = load_bitmap("texture.bmp",NULL);
59
60 while(!key[KEY_ESC])
61 {
62 clear(front);
63 blit(backdrop,front,0,0,0,0,SCREENWIDTH,SCREENHEIGHT);
64 do_raycasting();
65 draw_view();
66
67 if(key[KEY_A])
68 {
69 px += (int)(ps * cos(pa - M_PI / 2));
70 py += (int)(ps * sin(pa - M_PI / 2));
71 }
72 if(key[KEY_D])
73 {
74 px -= (int)(ps * cos(pa - M_PI / 2));
75 py -= (int)(ps * sin(pa - M_PI / 2));
76 }
77 if(key[KEY_LEFT]) pa -= 0.1;
78 if(key[KEY_RIGHT]) pa += 0.1;
79 if(key[KEY_UP])
80 {
81 px += (int)(ps * cos(pa));
82 py += (int)(ps * sin(pa));
83 }
84 if(key[KEY_DOWN])
85 {
86 px -= (int)(ps * cos(pa));
87 py -= (int)(ps * sin(pa));
88 }
89 if(collisions() == true)
90 {
91 px = p_old_x;
92 py = p_old_y;
93 }
94 else
95 {
96 p_old_x=px;
97 p_old_y=py;
98 }
99
100 if(pa < 0) pa += M_PI * 2;
101 if(pa > M_PI * 2) pa -= M_PI * 2;
102
103
104 // draw the little compass/circle
105 line(front,160,100,160+(25*cos(pa)),100+(25*sin(pa)),makecol(0,0,255));
106 line(front,160,100,160+(25*cos(pa-0.523598)),100+(25*sin(pa-0.523598)),makecol(255,255,0));
107 line(front,160,100,160+(25*cos(pa+0.523598)),100+(25*sin(pa+0.523598)),makecol(255,255,0));
108 my_draw_circle(front,160,100,25,makecol(255,0,0));
109 textout_centre(front,font,"N",160,65,makecol(0,0,255));
110
111 textprintf(front, font, 15, 5, makecol(0,0,255), "%f (tan = %f", pa, tan(pa));
112
113 vsync();
114 blit(front,screen,0,0,0,0,SCREENWIDTH, SCREENHEIGHT);
115 // if(key[KEY_S]) save_bitmap("wolf.pcx",front,NULL);
116 }
117
118 destroy_bitmap(front);
119 destroy_bitmap(texture);
120 destroy_bitmap(backdrop);
121
122 return 0;
123}
124END_OF_MAIN()
125
126// called once from int main()
127void do_raycasting()
128{
129 double angle = pa - 0.523598;
130
131 ofstream ofile("anglelog.txt");
132
133 for(int i = 0 ; i < SCREENWIDTH ; ++i)
134 {
135 ofile << angle << ", " << tan(angle) << endl;
136
137 // get the distance of the ray
138 view<i> = (int)(cos(angle - pa) * CastRay(px, py, angle, texture_map<i>));
139
140 // increment the angle
141 angle += 1.04719 / SCREENWIDTH;
142 }
143}
144
145// called once from int main()
146void draw_view()
147{
148 int tall = 0;
149 int distance_from_top = 0;
150
151 for(int i = 0 ; i < SCREENWIDTH ; ++i)
152 {
153 tall = (int)(64.0 / view<i> * 277.0);
154 distance_from_top = (SCREENHEIGHT - tall) / 2;
155 stretch_blit(texture, front, texture_map<i>, 0, 1, 64, i, distance_from_top, 1, tall);
156 }
157}
158
159// trivial function called once fron int main()
160void my_draw_circle(BITMAP*b,int x,int y,int radius,int color)
161{
162 float angle = 0.0;
163
164 while(angle < 360)
165 {
166 putpixel(b, x + (radius * cos(angle)), y + (radius * sin(angle)), color);
167 angle += 0.1;
168 }
169}
170
171// called once from int main()
172bool collisions()
173{
174 return (bool)level[px >> TILESHIFT][py >> TILESHIFT];
175}
176
177float CastRay(int xpos, int ypos, double angle, int& t) {
178 // initialize (X_Ycheck, X_Xcheck) with first vertical wall and
179 // (Y_Ycheck, Y_Xcheck) with the first horizontal one
180 float X_Ycheck, X_Xcheck, Y_Ycheck, Y_Xcheck;
181 float X_Yinc, X_Xinc, Y_Yinc, Y_Xinc;
182
183 // ofstream ofile("anglelog.txt");
184
185 // hacka hacka hacka ....
186 double tangent = tan(angle);
187 if(tangent >= 0.0 && tangent < 0.1) tangent = 0.1;
188 if(tangent <= 0.0 && tangent > -0.1) tangent = -0.1;
189 if(tangent > 9999) tangent = 9999;
190 if(tangent < -9999) tangent = -9999;
191
192 // ofile << angle << ", " << tangent << endl;
193
194 // sin(90) == 1; sin(270) == -1
195 if(sin(angle) > 0) // The y-values are increasing
196 {
197 Y_Ycheck = (ypos / 64) * 64 + 64;
198 Y_Xcheck = xpos + (Y_Ycheck - ypos) / tangent;
199 Y_Xinc = 64 / tangent;
200 Y_Yinc = 64;
201 } else { // The y-values are decreasing
202 Y_Ycheck = (ypos / 64) * 64 - 1;
203 Y_Xcheck = xpos + (Y_Ycheck - ypos) / tangent;
204 Y_Xinc = 64 / tangent;
205 Y_Yinc = -64;
206 }
207
208 // okay, let's check for a wall
209 while(level[(int)Y_Xcheck >> TILESHIFT][(int)Y_Ycheck >> TILESHIFT] == 0)
210 {
211 Y_Xcheck += Y_Xinc;
212 Y_Ycheck += Y_Yinc;
213 }
214
215 // cos(0) == 1; cos(180) == -1
216 if(cos(angle) > 0) // The x-values are increasing
217 {
218 X_Xcheck = (xpos / 64) * 64 + 64;
219 X_Ycheck = ypos + (X_Xcheck - xpos) * tangent;
220 X_Xinc = 64;
221 X_Yinc = 64 * tangent;
222 }
223 else // The x-values are decreasing
224 {
225 X_Xcheck = (xpos / 64) * 64 - 1;
226 X_Ycheck = ypos + (X_Xcheck - xpos) * tangent;
227 X_Xinc = -64;
228 X_Yinc = 64 * tangent;
229 }
230
231 // okay, let's check for a wall
232 while(level[(int)X_Xcheck >> TILESHIFT][(int)X_Ycheck >> TILESHIFT] == 0)
233 {
234 X_Xcheck += X_Xinc;
235 X_Ycheck += X_Yinc;
236 }
237
238 float xcheck = (X_Xcheck - xpos) * (X_Xcheck - xpos) + (X_Ycheck - ypos) * (X_Ycheck - ypos);
239 float ycheck = (Y_Xcheck - xpos) * (Y_Xcheck - xpos) + (Y_Ycheck - ypos) * (Y_Ycheck - ypos);
240
241 if(xcheck < ycheck)
242 {
243 t = (int)X_Ycheck % TILE;
244 return sqrt(xcheck);
245 }
246 else
247 {
248 t = (int)Y_Xcheck % TILE;
249 return sqrt(ycheck);
250 }
251}
EDIT: Wow -- |
|
aybabtu
Member #2,891
November 2002
|
Well, I sped it up a lot by merging the cast_ray() and map_texture() functions into one, inside the for() loop in do_raycasting. This give a substantial speed increase, but it's still very slow (about 2 frames per second). I still don't have the distortion fixed. Maybe I should rewrite it...I only have about 100 lines of code, it shouldn't be too hard to fix it up, though... |
|
23yrold3yrold
Member #1,134
March 2001
|
Did you try mine? It's still buggy, but I think my method is more on the right track than yours. Now where's that math pro ... -- |
|
aybabtu
Member #2,891
November 2002
|
Quote: Did you try mine? It's still buggy, but I think my method is more on the right track than yours.
I just saved it to a disk so I can take it to my room and compile it. I'm sure yours is better than mine, as your A) More experienced than me...and B) Used that tutorial more (I've only used it so far to do texture mapping and "fix" the distortion). Quote: Now where's that math pro ... We need to lure some of those people from "What is 0?" thread...:P |
|
23yrold3yrold
Member #1,134
March 2001
|
I've never done a raycaster and I only just read the tutorial. You're doing something totally different -- |
|
aybabtu
Member #2,891
November 2002
|
Well...help me fix it! This: "You're just doing something totally different " doesn't really help me, does it!? Whatever...I'm not a very "mathy" person. If I was, I bet I could fix this up very nicely. But, I'm not, so this is what I come up with... I'm going to change most of the floats in cast_ray to fixed point. Also, contributing to my problem is the fact that I do 320 stretch blits every frame. The drawing alone is probly enough to slow it down substantially. Wait! I think I see an advantage to yours right now! Your finding the X_inc and Y_inc once every ray, that way there isn't so much math being done!! Yay! I think that makes much more sense! Happy day!8-) |
|
23yrold3yrold
Member #1,134
March 2001
|
Quote: Well...help me fix it! Help me fix mine and I'll help you fix yours -- |
|
Kitty Cat
Member #2,815
October 2002
 |
aybabtu: your code won't compile here.. I keep getting the error "conversion from `float' to non-scalar type `fix' requested" over and over again. -- |
|
Ace
Member #1,781
December 2001
 |
There's a raycasting section in "Tricks of the Game Programming Gurus" by Andre LaMothe, if any of you have it or can get it. If either of you can't get access to it, I can type of the code for the examples and post it here (I have no clue where my cd is, grrrrr). I think I'm going to join in on the action and do a small raycasting game for the upcoming RPGDX como. - Ace |
|
23yrold3yrold
Member #1,134
March 2001
|
If you (or anyone) could post a small example, that would be dandy. If it's any easier, you could just point out the error in my code, since it's pretty close to the desired effect ... -- |
|
Ace
Member #1,781
December 2001
|
Eeek, well I'm not really sure how they work. I'll try to get the example's code typed up. It may help you out some and maybe I can figure it out as I type it up. - Ace |
|
23yrold3yrold
Member #1,134
March 2001
|
-- |
|
aybabtu
Member #2,891
November 2002
|
Yay! I have no more speed problems!! I changed my raycasting code so that it doesn't redo the math to move the ray every loop. I get at least 5-10 fps, which is a great improvement. I know it's not good, but it's a lot better. Help: How do I get/display the fps? Kitty Cat: Sorry...I don't know how to fix that...possibly because of the lines that say (float)cos(angle); My code isn't exactly "right". Ace said: I think I'm going to join in on the action and do a small raycasting game for the upcoming RPGDX como. What's the "RPGDX com[p]o?" RPG competition? 23: Those sites are good. I remember t3h second one from when I was just starting out programming in QBASIC (they were way over my head:P). |
|
Ace
Member #1,781
December 2001
|
Heh. Como. I've been The King of Typos lately. Blech. The RPGDX comPo is a weekend competition coming up on the weekend of the 28th. You have the weekend to design an RPG. You can use preexisting code, but everything else has to be done during the weekend. Check out RPGDX for more information. - Ace |
|
23yrold3yrold
Member #1,134
March 2001
|
Quote: How do I get/display the fps? Have a variable that counts the number of screen redraws (just increment the variable everytime you blit the buffer to the screen). Declare an int fps variable which will hold the fps. Finally, have a timer variable increment every second. Now, display fps onscreen. Whenever the second timer increments, assign the variable counting screen redraws to fps, and reset it. So you have a timer counting the seconds, a variable counting the frames drawn, and a variable to assign the fps so you can display it onscreen. Geddit? -- |
|
aybabtu
Member #2,891
November 2002
|
Quote: Geddit? Yup! That's simple. Ace: How are you going to use raycasting in your RPG? Are you going to make one of those "3D" dungeon things? Although, yours wouldn't be as fake as those, because they just use predrawn images.::) EDIT: |
|
Carrus85
Member #2,633
August 2002
 |
The only thing I can think of to increase the speed of the program is to use a lookup table (which I think has been already suggested earlier) Although, if you just do this once, it shouldn't be to hard... Some other possiblities of things that you could do to increase speed is... lets see... You could eliminate the floats/doubles. I'm pretty sure that if you used FIXED point stuff it would run faster (just because of some of the CPU opimizations behind it). You might even be able to just get a fixed accuracy or something by eliminating the decimal part of the return value. I mean, when you get right down to it, I don't think you are really going to need much beyond the thousands decimal place, maybe even the hundreths... You could also implement some max viewing distance (as suggested in the tutorail) just to prevent excessive calculation.
|
|
aybabtu
Member #2,891
November 2002
|
<u><b>*NO DISTORTION*</u></b>:D8-);D:-*:o:):P;) It was my displaying!!!!! I changed mine to 23's way to get the "tall" variable, and it works great! BTW: 23, I ran your program, and I see what you're talking about. It looks nice, but I couldn't figure out what's causing that bug. Does it do the same thing without texture mapping? Hmm...I'm not very experienced, so I'm not the one to go to. |
|
23yrold3yrold
Member #1,134
March 2001
|
Quote: It was my displaying!!!!! I changed mine to 23's way to get the "tall" variable, and it works great! I got the math for that from that one site up there, btw Yeah, it's the same without texture maps, since it's the walls that move, not the textures. I'll probably hack at it for fun tonight, maybe look at that Java engine (how hard could it be to understand? -- |
|
aybabtu
Member #2,891
November 2002
|
Quote: I got the math for that from that one site up there, btw You should have had that a long time ago
Why didn't you guys point it out sooner? Too obvious? Well, the important thing is that I can move on now Quote: maybe look at that Java engine (how hard could it be to understand? It seems it could be almost directly ported to C. Just change some of the function declarations and such (like remove the "public" from them). Quote: Still wouldn't mind a math guru saving me some time though (wink, wink).
Ya'd think that the title "Raycasting problems" would just scream "MATH GURUS!! GET OVER HERE!!". Well, I guess it depends on if they know what raycasting is. Carrus said: The only thing I can think of to increase the speed of the program is to use a lookup table (which I think has been already suggested earlier) I'm going to do that. I've found (with the help of 23) that the cos() and sin() functions take up a lot of time. And, every time I draw a line, I'm using a cos() function to fix the distortion. I'm going to use that ViewFix table thing for the distances. I don't really know how, though...:-/mostly because the distortion correction uses player_angle (PA) to do it's thing... |
|
23yrold3yrold
Member #1,134
March 2001
|
Well the cos() and sin() in my CastRay() function can be removed completely in favour of just checking if the angle is in a certian range. The Java code is a bit tricky for me to understand, but the render() function seems to be doing things not quite in line with the article linking to it, so it's still confusing me. And some of the more useful engines on that big list are broken links. I made a fresh post on GameDev; hopefully I'll get a bite quickly. And your function went slowly not just because you were using sin() and cos(), but because you were adding infintesimal values. You could just precalculate those values outside the loop, you know -- |
|
aybabtu
Member #2,891
November 2002
|
Quote: And your function went slowly not just because you were using sin() and cos(), but because you were adding infintesimal values. You could just precalculate those values outside the loop, you know Did I fix it? |
|
23yrold3yrold
Member #1,134
March 2001
|
As of the last bit of code you posted ... no. If you're ever calling cos(angle) in a loop when angle never changes, you should just precalculate cos(angle) and use that instead. -- |
|
|
|
But it doesn't crash, and most of the walls work, but there's always the odd one sticking out. Plus the strafing and moving don't always go in the right direction. I still have no idea what I'm doing (other than waiting for a math guru to show up 
I thought I was doing pretty well until I started wandering around the map. Depending on the angle and how you move, it either works really well or absolutely horrid 
