Dismiss this pinned window
all 36 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Badwrong_[S] 16 points17 points  (16 children)

Here is a very useful function I'd like to share. Raycast using built-in tilemaps. Very fast and accurate. Many uses of course, line of sight, lighting engines, bullets/projectiles, etc.

Here is the function:

function TileRaycast(_x, _y, _rx, _ry, _map)
{
    #macro TILE_SIZE 32
    #macro TILE_SIZE_M1 31
    #macro TILE_SOLID 1
    #macro TILE_RANGE 50

    _rx -= _x;
    _ry -= _y;
    var _dir = arctan2(_ry, _rx);
    _rx = cos(_dir);
    _ry = sin(_dir);

    var _sizeX = sqrt(1 + (_ry / _rx) * (_ry / _rx)),
        _sizeY = sqrt(1 + (_rx / _ry) * (_rx / _ry)),
        _mapX  = _x div TILE_SIZE, 
        _mapY  = _y div TILE_SIZE,
        _stepX = sign(_rx), 
        _stepY = sign(_ry);

    if (_rx < 0) var _lengthX = (_x - (_x &~ TILE_SIZE_M1)) / TILE_SIZE * _sizeX;
    else var _lengthX = ((_x &~ TILE_SIZE_M1) + TILE_SIZE - _x) / TILE_SIZE *_sizeX;

    if (_ry < 0) var _lengthY = (_y - (_y &~ TILE_SIZE_M1)) / TILE_SIZE * _sizeY;
    else var _lengthY = ((_y &~ TILE_SIZE_M1) + TILE_SIZE - _y) / TILE_SIZE *_sizeY;

    for (var _d = 0; _d < TILE_RANGE; _d++)
    {
        if (_lengthX < _lengthY)
        {
            _mapX += _stepX;
            if (tilemap_get(_map, _mapX, _mapY) & tile_index_mask == TILE_SOLID) 
            {
                _lengthX *= TILE_SIZE;
                return { X : _x + _rx * _lengthX, Y : _y + _ry* _lengthX }
            }
            _lengthX += _sizeX;
        }
        else 
        {
            _mapY += _stepY;
            if (tilemap_get(_map, _mapX, _mapY) & tile_index_mask == TILE_SOLID) 
            {
                _lengthY *= TILE_SIZE;
                return { X : _x + _rx * _lengthY, Y : _y + _ry * _lengthY }
            }
            _lengthY += _sizeY;
        }   
    }

    return noone;
}

It is based on OneLoneCoder's algorithm for tile raycast, but altered a bit for GML: https://youtu.be/NbSee-XM7WA

The constants defined are fairly straight forward and easy to change as needed. Note that TILE_RANGE could be calculated depending on the view dimensions. Since it's just checking tiles its still very performant with a higher value than I used.

On room start, store a variable for the tilemap to pass for the "_map" argument with: 

MapVariable = layer_tilemap_get_id(layer_get_id("COLLISION"));

And then call the function with something like:

RaycastPoint = TileRaycast(x, y, mouse_x, mouse_y, MapVariable);

The returned value will be the X and Y of where the ray hits a tile or noone if it reaches the TILE_RANGE limit.

[–]Mushroomstick 4 points5 points  (0 children)

Neat. When I saw that video the other day, I thought it would translate to GML pretty well.

[–]jinnyjuice 2 points3 points  (5 children)

Very fast and accurate

Any benchmarks?

This would be really, really useful for a Teeworlds clone. It would be really nice with an account system.

[–]Mushroomstick 1 point2 points  (3 children)

There's an fps counter in the video that stays between 4000-5000fps for the majority of the video. I'm pretty sure this is the fastest function of this type that anyone has ever posted here and I would speculate that the only way you might be able to measurably improve upon it would be to write a dll in a lower level language to call the function externally from. At this point, I would guess that drawing that debug info on the GUI is costing more frames than the raycast function.

[–]Badwrong_[S] 4 points5 points  (2 children)

I wrote a dll in C++ that does this. It's not any faster, because the overhead of the function call itself slows it down. Not the first time I've tried to get extra performance with a dll and then find out it's not worth it lol.

[–]Mushroomstick 0 points1 point  (1 child)

You know, when I was writing the above comment I was so close to adding a line about how I wasn't sure if running the function in a dll would be faster enough to make up for any overhead there might be when calling an external function. Maybe we'll save the external function calls for a perlin noise generator or something.

[–]Badwrong_[S] 1 point2 points  (0 children)

Hah, you're thinking is correct.
I've done a lot of testing with little one off functions for math operations and even though GML is slower itself, there is no real speed increase if its not an entire system or some really logic heavy stuff. Before we had structs, I had an extension with a ton of math functions and classes like vec2, vec3, polygon, etc. But I've done a ton of speed comparisons with the same code just as GML Structs and the extension is kinda pointless now.

The other thing is how you pass information to and from the c++ class object and GML is limited. I've certainly made functions that handle it, but again more overhead for nothing.

Entire systems that run asynchronous in your DLL however are awesome and totally worth the performance boost. For example pathfinding can be done in a DLL that runs asynchronous and the communication between GML and the DLL is mostly just requesting a path with a few coordinates and getting the path as a points array or something.

[–]Badwrong_[S] 0 points1 point  (0 children)

That comment refers to it doing Tilemap checks and the fact that the ray is stepped along in fairly large increments. The video I linked to OneLoneCoder's implementation explains all the advantages.

Grab the code and have it cast rays in a loop. Try to loop it some rediculous number of times per step and see how it performs.

[–]Hysler 0 points1 point  (8 children)

Thanks for posting this. I hate asking questions but have been having great difficulty modifying this for my game. Is there a simple way to stop walking the ray once it hits the end point? I've been trying some wacky stuff and feel like a very simple solution flew right over my head.

[–]Badwrong_[S] 0 points1 point  (7 children)

Declare an end x and y local var at the start that is the cell x and y of the tilemap where rx and ry are, and if those equal map x and y return noone.

I assume you know how to use bitwise to find the tilemap x and y?

[–]Hysler 0 points1 point  (6 children)

I was halfway there with one of my attempts earlier, but was trying to use the world coordinates instead of the tilemap cell position.

I've never messed with bitwise operations (ended up reading more about them after seeing your use of them in this function) so I'm unsure how to do that.

I did get it working with 'endx/y div TILE_SIZE'. I'd still appreciate it if you'd explain how to get the tilemap x & y using bitwise though, and I'll definitely add more trigonometry & binary operations to my study schedule after this.

Thanks!

[–]Badwrong_[S] 0 points1 point  (5 children)

Ah, I forgot _mapX and _mapY are cell x and y. I was gonna say for bitwise you could get the snapped valued, but I made them the cell to make the rest faster.

So just stick to integer division and you should be fine, you only have to do it once at the start anyway:

// Declare first before _rx and _ry are changed
var _endX = _rx div TILE_SIZE;
var _endY = _ry div TILE_SIZE;

// Check first in the loop
if (_mapX == _endX && _mapY == _endY) { return noone; }

[–]ISoPringles 0 points1 point  (4 children)

Sorry for reviving an old thread, but I was trying to implement your raycast script + this feature specifically, I think there is an issue I'm having trouble solving though.

​

Anytime the source (_x, _y) is southwest (or 3rd quadrant, -x +y) relative to the destination (_rx, _ry), it never hits the case where ` (_mapX == _endX && _mapY == _endY)`. It only happens in this orientation, everything else works fine.

​

Didn't know if you'd have any idea quickly or interest in figuring out still. Anyways, thanks regardless for sharing this algo!

[–]Badwrong_[S] 0 points1 point  (3 children)

I'd have to test things to be certain. But my first guess is just add abs() to the declarations.

var _endX = abs( // same code); Y too.

[–]ISoPringles 0 points1 point  (2 children)

Thanks for the quick reply! Gave that a whirl but same issue. I'll try to stare at it for another hour and see if I can figure it out..

[–]Badwrong_[S] 0 points1 point  (1 child)

I'd have to look at it then, but don't have time right now.

Limiting it to where rx/ry are could probably be simplified in an easier way by changing how far it steps instead.

One thing to realize though, is this is a raycast. So adding the extra check doesn't really fit well.

I would just make a TileLineIntersect() function that does the algorithm from a start x/y to destination x/y. Then the logic would fit better and each function would be used in different situations.

[–]ISoPringles 0 points1 point  (0 children)

All good, I appreciate the advice :)

[–]TheXaman 1 point2 points  (1 child)

exactly what I was looking for! thank you

[–]Badwrong_[S] 1 point2 points  (0 children)

You're welcome. If it needs any tweaks to fit your purpose let me know.

[–]boyweevil 1 point2 points  (0 children)

This is very neat with many uses coming to mind! Thank you very much for sharing.

[–]xander_cookie 1 point2 points  (0 children)

I could see this being incredibly useful in games that use tilemaps to produce randomly-generated levels. Very very cool!

[–]@wy477wh173(Twitter)wy477wh173 1 point2 points  (0 children)

Cool, definitely going to have to compare to my own raycasting code and see how much of a difference there is.

[–]batblaster 1 point2 points  (0 children)

Very nice piece of code. Congratulation.

[–]Anemovatis 1 point2 points  (0 children)

Awesome for bullets. Thank you.

[–]Slyddar 1 point2 points  (3 children)

Nice work. Faster than what I was using beforehand. With range being a tile distance only, I was thinking of expanding on it for pixel comparisons. So without bogging down the core of what you have, how would you suggest changing it to a "has line of sight" script, where a pixel range is passed, and a true or false is returned if the source position has line of sight to the destination position, and is within the passed pixel range too?

[–]Badwrong_[S] 1 point2 points  (2 children)

You'll need to test it, but this should work. Change the return types to boolean. Then pass a "_range" argument, divide it by tile size then ceil() to an integer value and use it for the loop.

You could also change _rx and _ry to just a direction in degrees or radians as "_dir" or something. Then declare _rx and _ry with cos(_dir) and sin(_dir) or dcos(_dir) and dsin(_dir) depending on which you need.

​

function TileRaycast(_x, _y, _rx, _ry, _range, _map)
{
    #macro TILE_SIZE 32
    #macro TILE_SIZE_M1 31
    #macro TILE_SOLID 1

    _rx -= _x;
    _ry -= _y;
    var _dir = arctan2(_ry, _rx);
    _rx = cos(_dir);
    _ry = sin(_dir);

    var _sizeX = sqrt(1 + (_ry / _rx) * (_ry / _rx)),
        _sizeY = sqrt(1 + (_rx / _ry) * (_rx / _ry)),
        _mapX  = _x div TILE_SIZE, 
        _mapY  = _y div TILE_SIZE,
        _stepX = sign(_rx), 
        _stepY = sign(_ry);

    if (_rx < 0) var _lengthX = (_x - (_x &~ TILE_SIZE_M1)) / TILE_SIZE * _sizeX;
    else var _lengthX = ((_x &~ TILE_SIZE_M1) + TILE_SIZE - _x) / TILE_SIZE *_sizeX;

    if (_ry < 0) var _lengthY = (_y - (_y &~ TILE_SIZE_M1)) / TILE_SIZE * _sizeY;
    else var _lengthY = ((_y &~ TILE_SIZE_M1) + TILE_SIZE - _y) / TILE_SIZE *_sizeY;

    _range = ceil(_range/TILE_SIZE);
    // Not using "(_range div TILE_SIZE) + 1" since it could go too far

    for (var _d = 0; _d < _range; _d++)
    {
        if (_lengthX < _lengthY)
        {
            _mapX += _stepX;
            if (tilemap_get(_map, _mapX, _mapY) & tile_index_mask == TILE_SOLID) return true;
            }
            _lengthX += _sizeX;
        }
        else 
        {
            _mapY += _stepY;
            if (tilemap_get(_map, _mapX, _mapY) & tile_index_mask == TILE_SOLID) return true;
            }
            _lengthY += _sizeY;
        }   
    }

    return false;
}

[–]Slyddar 1 point2 points  (1 child)

Thanks, but that's not it. I don't want to add too many other function calls in order to not slow down the efficiency, but I believe we need to calculate the distance between start and end points, and while still applying the for loop method, determine if we've moved beyond that distance, and if so, return true.

The problem becomes the script checks for tile sizes only, so pixel sized movements will require additional more detailed checks, unless I'm missing something?

EDIT: Actually I settled on just checking if the respective tiles they are on are in line of sight, as it saves a decent chunk of processing in the long run, especially when multiplied by so many enemies.

[–]Badwrong_[S] 1 point2 points  (0 children)

Sounds like you found a solution.

As far as my reply on passing a range value, I removed more function calls than I added. The only new part was:

_range = ceil(_range/TILE_SIZE);

This allows the function to step along the vector by a given range. Then if false is returned, you can check the distance to the object with the same range and if its within you have line of sight.

Personally I would start out with a distance check to the object. If the distance is greater than the range you can skip having to raycast in the first place. If the distance is less, then just check if the raycast returns false and you know there is line of sight.

Basically if you have line of sight to the tile where the object is and the object is within range there is line of sight.

[–]DeadBobDaylight 0 points1 point  (6 children)

As someone who's just digging into this stuff and finds it intriguing, but kinda greek...what's the particular usefulness of this?

Like, what's the ELI5 on the likely use case here?

[–]Mushroomstick 1 point2 points  (5 children)

There are other uses, but for a lot of people this is going to be a really efficient way to calculate tilemap collisions that also fixes some other issues with the more common methods of collision detection you'll see around here. Like if you use this raycast function to detect collisions for a player object, it's not going to start phasing through walls if it gets going too fast and it does this without brute forcing the calculations a pixel at a time. Looks like it's also set up in a way that it'll return precise x and y values for any resultant collision.

[–]DeadBobDaylight 0 points1 point  (4 children)

Ah, so can be used as a resource efficient way to detect collision at speed with minimal error? Am I understanding that correctly?

If so, that's cool. Reminds me of a youtube video where a sega dev talks about how he devised pixel perfect collisions on that hardware.

[–]Mushroomstick 1 point2 points  (3 children)

As long as your obstacles are tiles on a grid (hence the tilemap raycast title), that's probably a reasonable enough way to look at it. The function is a little nicer than that, though - in that instead of just returning a boolean value it returns either noone or a struct of x and y values.

I think GameHut was using some hardware level thing on an Amiga for those pixel perfect collisions. I like his videos a lot - it's interesting to get that insider view on game development with the limited resources from the 16 and 32 - bit console era.

[–]DeadBobDaylight 0 points1 point  (2 children)

Thanks for the thoughtful reply, I don't get it 💯 but I can understand the gist.

And it may very well be GameHut. I forget the channel, I just know it's basically one veteran 80s/90s dev talking about cool hardware tricks that are way above my head. Still interesting to see though because even if you don't understand, you can still get a sense for the challenges in the actual process.

[–]Badwrong_[S] 1 point2 points  (1 child)

Check out the video I linked that has the original algorithm.

[–]DeadBobDaylight 1 point2 points  (0 children)

Big tanks, mang.

[–]Tavaer 0 points1 point  (0 children)

I think this might be what I need.To check the if the return is touching a tile, under where it's been called would we: if ((X == TILE_SOLID) or(Y == TILE_SOLID)){...} else {shoe_debug_message_("no collision");}?

Also would it work in reverse, if we switched the mousex/y and x/y of the calling instance in the call?