Jump to content


Photo

Ray-tracing collisions!


  • Please log in to reply
34 replies to this topic

#1 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 06 July 2010 - 04:10 PM

Hey there. This is something I wrote like half a year ago, and decided to share it ;D

Intro?

Ever wanted a way to check whether the line collides with an instance, pixel-by-pixel, without killing the framerate? Methods already exist, but most are not very efficient as the distance increases, some are not even efficient on small distances like 100px... This script can successfully cast 180 rays and keep an fps of 94 on my machine!

What is ray-tracing?

It's a process of following a ray (line), looking for information we're interested in. In this case, the ray is casted and is looking for a collision with an object specified.

How come your script is so "efficient"???

It creates multiple chunks of the ray, checks for each line is it colliding. If the line collides, it checks for each pixel for where the exact position is.

What's your script's performance?

Posted Image

This is a chart that shows my PC's performance using the script.
Left shows how many rays can be casted under what FPS, while drawing a primitive connecting each collision point.
Right shows the exact same, but without drawing the primitive.

900 Rays casted, each running an average of around 200 pixels in distance, doing it 12 times in one second with my script...
Same that, but with traditional way of ray-tracing takes 4-5 seconds!

You're lying!

Posted Image
In yer face!

UPDATE! Mirror (fixed gmk) by Newly Discovered:
http://host-a.net/Jo..._raytracing.gmk

Run in debug mode, so you can watch your frame-rate!
First room of the example consists of one ray, looking for collision with the spinning object.
Left mouse click controls the position of the object.
Pressing Space bar switches from normal ray-tracing to my advanced ray-tracing.
Enter leads you to the next room...

Second room consists of an object controllable by left click.
It fires multiple rays, depending on resolution specified in the object.
It also draws a primitive connecting every collision point. It looks like that object's field of vision =D

Omg awesome, now, can you provide a script in txt format here please?... Maybe also tell us what each argument stands for?


/*
Args:
0 = angle at which the ray is running (real)
1 = object the ray is seeking (object name)
2 = maximum distance the ray will travel (real)
3 = chunk size. The length of lines the ray is divided (real)
*/

var i, a, _x, _y, _x2, _y2;

_x2=x
_y2=y

if collision_point(x,y,argument1,1,1)
{
off_x=x
off_y=y
exit;
}

for (i=1;i<argument2;i+=argument3)
{
_x=x+lengthdir_x(i,argument0)
_y=y+lengthdir_y(i,argument0)
if collision_line(_x2,_y2,_x,_y,argument1,1,1)
{
for (a=i-argument3;a<argument2;a+=1)
{
_x=x+lengthdir_x(a,argument0)
_y=y+lengthdir_y(a,argument0)
if collision_point(_x,_y,argument1,1,1)
{
off_x=_x
off_y=_y
return true;
exit;
}
}
}
_x2=_x
_y2=_y
}
off_x=_x
off_y=_y
return false;

Cheers! =D

~ Krele

Edited by krele, 29 July 2010 - 11:16 PM.

  • 0

#2 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 07 July 2010 - 11:34 PM

Bump =/...

This is why most developers hate GMC...
  • 0

#3 Rani_sputnik

Rani_sputnik

    GMC Member

  • GMC Member
  • 424 posts
  • Version:GM:Studio

Posted 08 July 2010 - 02:25 AM

I think if you pointed out to people that this will allow them to use uber fast shaddow and lighting effects, you will get a billion replies a second :P That's all anyone seems interested in on the community haha.

Excellent stuff man I go 990 fps as an average on the first room (lmao my comp is old as :D) it made me very happy to see.

Thank you for brightening up my day man.
  • 0

#4 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 08 July 2010 - 09:02 AM

I think if you pointed out to people that this will allow them to use uber fast shaddow and lighting effects, you will get a billion replies a second :P That's all anyone seems interested in on the community haha.

Excellent stuff man I go 990 fps as an average on the first room (lmao my comp is old as :D) it made me very happy to see.

Thank you for brightening up my day man.

Yeah... With this people can really create so many things... I don't mean this is revolutionary, but with this people can advance with gm even further... Too bad for them, HA! xD

My PC goes further than even that... 1300 or so. But it is sorta high-end =/.

No, thank YOU for brightening up MY day =D... Glad this is not useless, and someone actually replies rather than download-n-run...
  • 0

#5 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 10 July 2010 - 09:59 AM

Whoopie gmc, you suck at feedback D:
...bump...
  • 0

#6 Kinta

Kinta

    GMC Member

  • GMC Member
  • 147 posts

Posted 13 July 2010 - 05:22 PM

Whoopie gmc, you suck at feedback D:
...bump...


Looks impressive, but I'm not sure what I can make of it. I never used the line collision command before.
But I'm curious. How can I use it for shadows and lighting effects?

And what's the impact on the performance when every casted ray hits an obstacle?

Kinta
  • 0

#7 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 13 July 2010 - 05:26 PM


Whoopie gmc, you suck at feedback D:
...bump...


Looks impressive, but I'm not sure what I can make of it. I never used the line collision command before.
But I'm curious. How can I use it for shadows and lighting effects?

And what's the impact on the performance when every casted ray hits an obstacle?

Kinta

You can cast one line at the center of an object, strike 2 different lines at the objects corners, and then draw a primitive out of it =). Soft shadows would work differently tho.

Sooner a ray hits an obstacle, better the fps it is... That's the sole reason for chunking =D
  • 0

#8 Shadowrend

Shadowrend

    Master of Shadows

  • GMC Member
  • 2968 posts
  • Version:GM8

Posted 13 July 2010 - 05:29 PM

Amazing! This is truly useful but it seems not many people here get it...
  • 0

#9 icicle.flame

icicle.flame

    CyntaxGames

  • New Member
  • 283 posts

Posted 16 July 2010 - 05:05 AM

host-a down but this looks promising...
  • 0

#10 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 16 July 2010 - 08:16 AM

host-a down but this looks promising...

Host-a back up ;D
  • 0

#11 alfa64

alfa64

    GMC Member

  • New Member
  • 53 posts

Posted 17 July 2010 - 03:51 AM

I'll try this, didn't read carefully trhough all the code but i think you used the dicotomic search algorithm as a the main principle, am i right?
If that's so, it can be improved with some ugly math, turning the chunk of rays into some kind of binary tree, saving more performance.
  • 0

#12 TheMagicNumber

TheMagicNumber

    GMC Member

  • GMC Member
  • 5247 posts
  • Version:Unknown

Posted 20 July 2010 - 03:49 AM

It's not pixel perfect, but close.
Posted Image

Other then that it's great.
  • 0

#13 Newly Discovered

Newly Discovered

    Harmonious Genius

  • GMC Member
  • 2475 posts
  • Version:GM8

Posted 25 July 2010 - 03:36 PM

magic, play with the accuracy...chunk variable. 1 would be pixel perfect.
but what's up with this?
http://img715.images...5/4740/bugs.png

it does seem to be faster than my original ray casting which is basically the same.
I haven't studied this technique but I definitely will and apply it to my lighting...so long as the bug is fixed.

thanks!

edit
I see it was the 640 in your adv script. changing it to argument2 and using a variable for a max_distance fixed it.

accuracy (chunk) set to 1 gives me a max of 23 FPS! without any wall objects in the room. max dist is 64.
set to 4 (still decent accuracy) gives me a max of 64 FPS!
this is actually a lot faster than I imagined.
your wall objects suffer the example.
you should set it up with a single solid shape.

thanks again!

Edited by Newly Discovered, 25 July 2010 - 03:46 PM.

  • 0

#14 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 25 July 2010 - 03:44 PM

Both of those aren't bugs...

@TMN:
It's because the ray was casted at an angle where it wouldn't exactly collide with the block. There's a gap if you go 45 degrees =)

@ND:
Accuracy is always pixel perfect no matter how big the chunk is... 1 would be slowest of all.
It's because the primitive is drawn like that. Check the drawing code. Increase the number of rays to hide this effect...
  • 0

#15 thatshelby

thatshelby

    GMC Member

  • GMC Member
  • 3823 posts
  • Version:GM8

Posted 25 July 2010 - 04:04 PM

I really like this! So many things it could be useful for, I think I'm going to attempt to make a light with it for my 3D game. Thanks so much! I wish I understood stuff like that..... I might need some help editing the draw event so that instead of pr_trianglefan it might be something like a circle around the player, that is colored white with an alpha of say, 0.5. I'll work on it. Best of luck to you and your projects.

Cheers. ;)
  • 0

#16 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 25 July 2010 - 04:17 PM

edit
I see it was the 640 in your adv script. changing it to argument2 and using a variable for a max_distance fixed it.

accuracy (chunk) set to 1 gives me a max of 23 FPS! without any wall objects in the room. max dist is 64.
set to 4 (still decent accuracy) gives me a max of 64 FPS!
this is actually a lot faster than I imagined.
your wall objects suffer the example.
you should set it up with a single solid shape.

thanks again!


Accuracy is always the same! xD... Try setting the chunk size to 100 you'll get the same results as if you had chunk of 10. Only the fps would suffer if the chunk is too big, or too small. Best chunk for that example, where object are usually distanced less than 100 px from the player is 10-12.

Yeah, the speed surprised me too. I never thought an algorithm that I made in my sleep could bring such results =D

I will update this example to show what can be done with this =P. Thanks for your interest ;D

I really like this! So many things it could be useful for, I think I'm going to attempt to make a light with it for my 3D game. Thanks so much! I wish I understood stuff like that..... I might need some help editing the draw event so that instead of pr_trianglefan it might be something like a circle around the player, that is colored white with an alpha of say, 0.5. I'll work on it. Best of luck to you and your projects.

Cheers. ;)


Well sure, light could be done, but add too many and your fps will drop alot =)... and wait, 3d game? This works on 2 dimensions only, x and y =(.

Sure, I can help =)... I'll make an example with light soon =D




Thanks everyone ;D <3
  • 0

#17 thatshelby

thatshelby

    GMC Member

  • GMC Member
  • 3823 posts
  • Version:GM8

Posted 25 July 2010 - 04:34 PM

I realize this, and I thought it would work anyway. :D
Ahh well, itwasn't what I was looking for, but it sure is useful, and I definately learned from it.
  • 0

#18 Newly Discovered

Newly Discovered

    Harmonious Genius

  • GMC Member
  • 2475 posts
  • Version:GM8

Posted 25 July 2010 - 05:17 PM

I've modified it a bit and I don't quite understand why you think chunk doesn't make an fps difference.
here's my draw event:
draw_primitive_begin(pr_trianglefan);
draw_vertex_color(round(x),round(y),color,1);
for( i = 0; i < 361; i += accuracy; ){
raytrace_adv(i,objSolid,radius,accuracy);
draw_vertex_color(off_x,off_y,color,1 - point_distance(off_x,off_y,x,y) / radius);}
draw_primitive_end();
I also set it up so mouse wheel changes accuracy to get an accurate idea of how much it affects frame rate.
with accuracy at 1 and radius at 64 I get about 6 fps with no collisions.
with accuracy at 2 and radius at 64 I get about 20 fps with no collisions.
with accuracy at 4 and radius at 64 I get about 50 fps with no collisions.

it's quite an obvious difference.
as for the 'pixel perfect' I was referring to above, I meant the triangle fan.
I know every ray is pixel perfect (for the most part - using round helps but pushes off_x off_y up and left).

as soon as host-a.net is back up I'll upload what I've changed and pm it to you if you'd like.
I also added an alpha check for the second vertex so the light fades without stretching the fade.
oh, and if you didn't notice, I took out the third vertex you drew as it's only using more cpu power to draw it and compute another raytrace_adv check.
changing the 360 to 361 fixes the gap.

Edited by Newly Discovered, 25 July 2010 - 05:20 PM.

  • 0

#19 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 25 July 2010 - 10:44 PM

I've modified it a bit and I don't quite understand why you think chunk doesn't make an fps difference.
here's my draw event:

draw_primitive_begin(pr_trianglefan);
draw_vertex_color(round(x),round(y),color,1);
for( i = 0; i < 361; i += accuracy; ){
raytrace_adv(i,objSolid,radius,accuracy);
draw_vertex_color(off_x,off_y,color,1 - point_distance(off_x,off_y,x,y) / radius);}
draw_primitive_end();
I also set it up so mouse wheel changes accuracy to get an accurate idea of how much it affects frame rate.
with accuracy at 1 and radius at 64 I get about 6 fps with no collisions.
with accuracy at 2 and radius at 64 I get about 20 fps with no collisions.
with accuracy at 4 and radius at 64 I get about 50 fps with no collisions.

it's quite an obvious difference.
as for the 'pixel perfect' I was referring to above, I meant the triangle fan.
I know every ray is pixel perfect (for the most part - using round helps but pushes off_x off_y up and left).

as soon as host-a.net is back up I'll upload what I've changed and pm it to you if you'd like.
I also added an alpha check for the second vertex so the light fades without stretching the fade.
oh, and if you didn't notice, I took out the third vertex you drew as it's only using more cpu power to draw it and compute another raytrace_adv check.
changing the 360 to 361 fixes the gap.

I've said that changing chunk size wouldn't make a difference? Bloody hell, fps improvement is GAINED by chunking, you obviously misunderstood something :lol:
Also, keep in mind the resolution (number of rays casted per frame) also affects framerate... So I would like to know, what resolution you used to get those results? Just for the record :D

That sounds nice, I'm waiting for your upload =P... thanks for fixing that up haha... Your help is appreciated very much <3
  • 0

#20 Newly Discovered

Newly Discovered

    Harmonious Genius

  • GMC Member
  • 2475 posts
  • Version:GM8

Posted 29 July 2010 - 07:03 AM

here's the link:
http://host-a.net/Jo..._raytracing.gmk
  • 0

#21 Nocturne

Nocturne

    Nocturne Games

  • Administrators
  • 21586 posts
  • Version:GM:Studio

Posted 29 July 2010 - 08:37 AM

here's the link:
http://host-a.net/Jo..._raytracing.gmk


Very interesting and quite fast... With an accuracy of 5 and a 250 px radius I got a steady 120fps... With a lower accuracy its good when there is a lot of collisions, but move it out of the area of the object so it draws the complete circle and the fps drops dramaticaly... I will be keeping this on HD for future use!!!
  • 0

#22 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 15 August 2010 - 11:02 PM


here's the link:
http://host-a.net/Jo..._raytracing.gmk


Very interesting and quite fast... With an accuracy of 5 and a 250 px radius I got a steady 120fps... With a lower accuracy its good when there is a lot of collisions, but move it out of the area of the object so it draws the complete circle and the fps drops dramaticaly... I will be keeping this on HD for future use!!!

Glad you like it :D. It's fast, isn't it? =P
  • 0

#23 Ecstats

Ecstats

    GMC Member

  • New Member
  • 844 posts
  • Version:GM8

Posted 16 August 2010 - 03:12 AM

I made a small test (link) to compare your script to collision_line_first from gmlscripts.com, slightly modified. Raytracing is faster when in smaller rooms where the rays won't have to travel very far, however collision_line_first is faster when in more open areas. Perhaps one could try to dynamically swap between the two methods depending on how far away the walls are detected.
  • 0

#24 RamboFox

RamboFox

    Tainted Fortune

  • New Member
  • 992 posts

Posted 26 August 2010 - 10:40 AM

Not exactly a bug, but it is rather bothersome.

Posted Image

What's happening here is that the collision line is skipping pixels diagonally, and since there is no pixels in that diagonal line, it jumps straight between the two pixels on either side.
  • 0

#25 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 26 August 2010 - 12:05 PM

Not exactly a bug, but it is rather bothersome.

Posted Image

What's happening here is that the collision line is skipping pixels diagonally, and since there is no pixels in that diagonal line, it jumps straight between the two pixels on either side.

It's a bad idea to even handle solid blocks like that. Just put another layer of blocks to close gaps like that. Or, more efficiently, use a solid map =)
  • 0

#26 slam drago

slam drago

    The slam drag

  • New Member
  • 422 posts
  • Version:GM:Studio

Posted 18 November 2011 - 06:27 PM

Interesting.

Sorry to bump dead topic.
  • 0

#27 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 19 November 2011 - 01:30 PM

Interesting.

Sorry to bump dead topic.

Haha it's ok. Maybe this topic will receive more feedback =)
  • 0

#28 norisak

norisak

    GMC Member

  • GMC Member
  • 131 posts
  • Version:GM8

Posted 26 November 2011 - 01:49 PM

Thanks for this!
I managed to create some cool lighting effects from this!

Here are some screenshots:

Posted Image

Posted Image
  • 0

#29 krele

krele

    GMC Member

  • GMC Member
  • 622 posts
  • Version:GM:Studio

Posted 27 November 2011 - 03:42 AM

Thanks for this!
I managed to create some cool lighting effects from this!

Here are some screenshots:

Posted Image

Posted Image

I made this just so I could make a dark themed zombie game with field of vision mechanics, just like yours! Good job! =D
  • 0

#30 norisak

norisak

    GMC Member

  • GMC Member
  • 131 posts
  • Version:GM8

Posted 14 February 2012 - 09:10 PM

Posted Image
This is a trimmed screenshot of my game that is zoomed in. If you look at where to light hits the wall, it looks uneven. It seems that the lightrays randomly hits the wall, or one pixel into the wall, making it look like this.
I managed to fix this by modifying the script a little bit:

Spoiler

The change I made was that when ray collides with the wall, it goes back 1 pixel, and collision checks that last bit with extra precision. This will cause a few more collision checks (up to four), but it will make the light hit the wall smoothly.
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users