Raycasting questions

I've been working on a simple raycasting engine for a while now, and I ran into a slightly sticky math problem (how to find the exact position at which a ray first intersects one of the blocks). To find that out, I really only need to know this: what's the fastest way to find out which *side* the ray has struck?

Thanks in advance!

isnt there collision normals that will allow you to do this?

Erm... not quite sure what you're talking about. To clarify, this is all done in the original Blitz Basic (I'm writing a simple, pseudo-3D engine in BB). I've actually sort of got what I want laid out in code now... but it doesn't work :(

Type hit
	Field num ;Which side is being hit
	Field ht# ;Time at which hit occurs
	Field x# ;X-location of hit
	Field y# ;Y-location of hit
End Type

;These two bits weren't actually together, but are needed to understand what's going on
				tx# = Floor(rxp#) ;x pos. of the block
				ty# = Floor(ryp#) ;y pos. of the block
				rxp# = rxp# - rxm# * 2 ;last x position of the ray
				ryp# = ryp# - rym# * 2 ;last y position of the ray
				
				allhit.hit = New hit
				allhit\num = 0
				allhit\ht# = (tx# - rxp#) / rxm# ;Time at which the ray passes through the same x as the left-vertical side 
				allhit\x# = tx#
				allhit\y# = rym# * allhit\ht# + ryp#
				
				allhit.hit = New hit
				allhit\num = 1
				allhit\ht# = (tx# + 1 - rxp#) / rxm# ;" " right vertical side
				allhit\x# = tx# + 1
				allhit\y# = rym# * allhit\ht# + ryp#
				
				allhit.hit = New hit
				allhit\num = 2
				allhit\ht# = (ty# - ryp#) / rym# ;Time at which the ray passes through the same y as the top horizontal side
				allhit\x# = rxm# * allhit\ht# + rxp#
				allhit\y# = ty#
				
				allhit.hit = New hit
				allhit\num = 3
				allhit\ht# = (ty# + 1 - ryp#) / rym# ;" " bottom horizontal side
				allhit\x# = rxm# * allhit\ht# + rxp#
				allhit\y# = ty# + 1
				
			
				For allhit.hit = Each hit ; Weeds out "hits" that are out of bounds (and so do not actually hit)
					Select allhit\num
						Case 0: If allhit\y# < ty# Or allhit\y# > ty# + 1 Then Delete allhit
						Case 1: If allhit\y# < ty# Or allhit\y# > ty# + 1 Then Delete allhit
						Case 2: If allhit\x# < tx# Or allhit\x# > tx# + 1 Then Delete allhit
						Case 3: If allhit\x# < tx# Or allhit\x# > tx# + 1 Then Delete allhit
					End Select
				Next
				
				besthit.hit = First hit
				For allhit.hit = Each hit ;Figures out which of the viable hits strikes first
					If allhit\ht# < besthit\ht# Then besthit.hit = allhit.hit
				Next
				
				;Sets the ray's location to the exact point at which it first hit the block
				rxp# = besthit\x# 
				ryp# = besthit\y#
				
				Select besthit\num ;Extra data (tells which part of a texture to draw for this line)
					Case 0: tex# = ryp# - ty#
					Case 1: tex# = ryp# - ty#
					Case 2: tex# = rxp# - tx#
					Case 3: tex# = rxp# - tx#
				End Select

Got part way to what I think you're after and ran out of time. This will find where a ray hits a box. You just need to go through the hits and find the one closest to the origin of the ray. use mouse and left mouse b to try it..

Global width=800,height=600
boxx1=100
boxy1=100
boxx2=200
boxy2=200

Type hitinfo
	Field x#,y#,side$
End Type

Type rayinfo
	Field x1#,y1#,anglefromhoriz#
End Type

Type boxinfo
	Field tlx#,tly#,brx#,bry#
End Type

box1.boxinfo=New boxinfo
	
ray1.rayinfo=New rayinfo


Graphics 800,600,16,0
While Not KeyDown(1)
	Cls
	If MouseHit(1)
		ray1\x1=Rand(0.,800.)
		ray1\y1=Rand(0.,600.)
		ray1\anglefromhoriz=Rand(0,360)
	EndIf
	
	box1\tlx=MouseX()
	box1\tly=MouseY()
	box1\brx=box1\tlx+100
	box1\bry=box1\tly+200
	
	Color 0,150,150
	Rect box1\tlx,box1\tly,box1\brx-box1\tlx,box1\bry-box1\tly,1	
	Color 0,255,0
	Line ray1\x1,ray1\y1,ray1\x1+1000.*Cos(ray1\anglefromhoriz),ray1\y1-1000.*Sin(ray1\anglefromhoriz)
	
	hit1.hitinfo=wherehit(ray1,box1)
	
	Flip
Wend

Function wherehit.hitinfo(ray.rayinfo,box.boxinfo)
	
	hit.hitinfo=New hitinfo
	
	Text 20,20,ray\anglefromhoriz
	
	;equation of line. Grad=sin (anglefromhoriz)
	; y=sin(anglefromhoriz) x + y1 - sin (anglefromhoriz) x1
	m#=-Tan(ray\anglefromhoriz)
	c#=ray\y1+Tan(ray\anglefromhoriz)*ray\x1
	
	;y pos of hit on left of box at x=tlx...
	yhitleft#=m*box\tlx+c
	;Does this y pos lie within the y extent of box?
	hitleft=(yhitleft>=box\tly) And (yhitleft<=box\bry)
	
	yhitright#=m*box\brx+c
	hitright=(yhitright>=box\tly) And (yhitright<=box\bry)
	
	; x= (y-c)/m
	
	xhittop#=(box\tly-c)/m
	hittop=(xhittop>=box\tlx) And (xhittop<=box\brx)
	
	xhitbottom#=(box\bry-c)/m
	hitbottom=(xhitbottom>=box\tlx) And (xhitbottom<=box\brx)
	
	Color Rand(100,255),Rand(100.,255),0
	
	If hittop Then Rect xhittop-1,box\tly-1,3,3
	If hitbottom Then Rect xhitbottom-1,box\bry-1,3,3
	If hitleft Then Rect box\tlx-1,yhitleft-1,3,3
	If hitright Then Rect box\brx-1,yhitright-1,3,3
	
	
	
	If Not(hittop Or hitbottom Or hitleft Or hitright)
		hit\side$="None"
	EndIf
	
	
	
	Return hit
	
End Function 

oh yeah... will probably crash for ray angles near 90,180 degs tho i haven't seen it... needs work

Close, but no bannana (sp?) - what I'm looking for is where the ray strikes on a 1*1 box (i.e. a block such as would be found in an array). The code that I've posted *should* do the trick, but for some reason it doesn't - the blocks come out all glitchy. I'll try to post a screenshot in a bit to show what I'm talking about.

Yeah, a screenshot would help since I don't fully understand your problem.

I was working on a raycaster that works like this:

The ray ist casting in huge steps, let's say angle*0.2. As soon as the ray enters a new Array field, I mean when array-index is diffrent from the one before, then it is going to make one huge step back and will cast this step in little steps until it reaches the border of the array field. You could then even repeat this with even smaller steps, so you finally have a very correct edge of the block.

But if you want to textue the floor as well then this trick won't work.

Now you want to determine where the ray hit the block? For a texture pixel index you can use a lookup table since you have to multiply the horizontal (0.0 to 1.0) value * Texturewidth.

If you want to know if the ray hits north, south, east or west, there are several Methods to determine this. You can simply compare the index of the previous array field index the ray passed through with the array field index of the block that was hit.

Hi Bagels, I've also been working on a raycaster since I read your post over at blitzcoder! I have been following
this tutorial:

http://www.permadi.com/tutorial/raycast/

When you are already knee-deep ;) into your own approach this might not be so helpful but maybe there are some
pointers there that you can use. My program is working now but I really had to sit down and think about the maths
myself (lol...) in addition to just copying it from the site.

In this approach you find the box you collided with *after* having found the location of the collision. So you already
know exactly where the collision happened, there's no need to figure this out from the box location. Once you know the
spot of the collision, you also have the box that belongs to it, and you can check if it is solid (making it a real
collision).

The potential collision points are always on borders between boxes. You compute these locations by "jumping"
from one border to the next. The angle of the ray of course determines the direction of the jump. Furthermore,
computation is also dependant on whether you are at that moment looking for a collision with a horizontal or a
vertical border in the grid (as that is how the method works).

For instance, suppose you are checking for a collision with a horizontal border, and the current ray is exactly 90
degrees (which is North in my case). This means the jump will always have a deltaY of -SECTOR_SIZE (= from one
border to the next, upwards), and a deltaX of 0 (as the ray goes straight up). If the ray is at another angle the
deltaX has to be computed using tan().

And similar computations are used for looking for collisions with vertical borders.

Then when you have found both, the nearest one is used. You then know the point of collision so you can compute the
distance. (Sometimes there will be only 1 point; for instance when you look for collisions with horizontal
borders and the current ray is at 0 or 180 degrees (going horizontal) there will never be a collision; at other times
the collision will be outside of the map as in your code too). Then the distance is used to compute the height of
that slice of wall.