Sign in to follow this  

raycasting vs. "raycache-ing" for tile-based applications?

This topic is 410 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For a tile-based application with a clearly defined grid. Would/could it be more efficient to use a 'cache' of indexes/tiles relative to the source, for a number of given angles?

For example, rather than performing a typical raycasting method as you might see applied in box2D or similar libraries, and then rounding the values to the grid, (or otherwise checking which tiles are hit by the ray), instead have a precalculated cache of tiles that would be hit for a given angle.

In long-range applications, or high precision angles, this would definitely be more work than its worth, or less accurate than it could be. But let's use an 8x8 chessboard as an example.

For a 90° raycast from 4, 7. You know that it will always hit the tile with one less y, until it reaches zero. This could easily be written in as
(Apologies for the shitty pseudocode)

If vectorangle (within range of 'accuracy') to 90
Hittiles = new 2d array.
For (curY = this.Y, curY>0, curY++)
Hittiles += [x,cury]

And similar code for each relevant angle. With a small grid size like 8x8, the number of relevant angles is reasonably small. And when you don't care about long range accuracy, you could round your vector angles to the (I assume faster) angles.

Is this method faster/more efficient processing-wise than your typical raycasting method? Have you used, or seen this method in use before? And if so, is there an actual name for this?

(An example for application would be a characters fov in a tile-based game, where their viewing area is limited to a 15x15 square)
Or for a more reasonable and understandable pseudocode: a cached list of positions for a given angle (using tan), adjusted in position by the source tile, and any out-of bounds tiles discarded.

Share this post


Link to post
Share on other sites

I guess an optimized version of your thoughts is DDA https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)

This is often implemeted with fixed point integer math (no precision problem).

There is no need to precompute anything (a cached lookup table would be much slower),

instead only the division is done once per ray, the rest is just additions.

 

Also related and similar is Bresenhams line drawing algorithm.

Share this post


Link to post
Share on other sites

I've done this for a pathfinding algorithm that uses the minimal turn radius.  When going through anything that isn't the start or end tiles, I only look at the cardinal directions (N,NW,W, etc), and have all the offsets precalculated for entering neighbor tiles at the given turn radius.  Basically all the Dubin's curves to get to the nearest tiles.  I'm foggy, I believe I cached dubisn for all the nearest tiles two squares away. Because it's cached, I can also take into account the width and length of the vehicle as well.

 

Wu's got a line drawing algorithm as well, here's a pretty picture:

336px-LineXiaolinWu.gif

As well as a circle algorithm.

Edited by ferrous

Share this post


Link to post
Share on other sites

>> Is this method faster/more efficient processing-wise than your typical raycasting method?

 

the first question is:

 

is typical raycasting not fast enough for you?

 

Bressinmham's is usually described as "lightning fast".

 

Beware of premature optimization.

 

How many rays do you have to cast per update? 

 

One per unit with 100 units (100 rays)?

 

or more? 1000? 1 million?

 

unless you're casting rays like a raytracer, odds are you don't need to cache things.

 

But if you do need the speedup, caching can help a bit.

Share this post


Link to post
Share on other sites

Sorry, it would probably be more efficient to say, having a cached/precalculated list of 'crossed tile' coords, for a given SIN/COS/TAN value. So it's more to do with optimizing trigonometric functions than raycasting.

 

I am casting ~200 rays per update, per raycasting object, of which there are many (honestly haven't counted it yet. But at least one thousand.). My grid is 51x51 tiles, and the object is always centered  at 26, 26 in the grid, so i only need to have 1 octant cached. (or angles from 0 degrees to 45 degrees/tan <= 1) Updates occur 10 times per second.

So yeah, the question is moreso:

Is using a cached lookup table of the possible values given x, for trigonometric functions faster than calling those functions >200k times per update?

 

Edited by nullie

Share this post


Link to post
Share on other sites

Is using a cached lookup table of the possible values given x, for trigonometric functions faster than calling those functions >200k times per update?

 

No, trigonometric functions are slow, but not as slow as accessing memory. Probably even if the memory is in cache, and you have little control over what is in cache.

If you think those functions are too slow, profile and test if your assumption is correct.

And if so, using an approximization to trigonometric functions should be much faster than a lookup table, but only slightly faster than sin().

L. Spiro posted one few weeks back.

 

Also, check if you can avoid trigonometric functions completely - mostly it's possible e.g. using dot or cross products.

Share this post


Link to post
Share on other sites

Generally this is a non-issue.

 

You're talking about an 8x8 grid, so you've got a worst case of 64 ray/square intersections or 128 ray/triangle intersections depending on how the boxes are stored.  That ought to take a handful of nanoseconds. Not a performance concern at all.

 
If you've got a bigger world with a few thousand items, generally the first improvement that needs to be made is a spatial grid.  You would pass the ray to the spatial grid system and through a series of rather simple calculations that reduces the query from thousands of tests to less than a hundred or so.  So the spatial grid prunes most stuff out, then you proceed as above.

 

If you've still got too many items, generally the next improvement is to tag items that you frequently search for, such as tagging inventory-able items, tagging UI or touchable items, that sort of thing.  After the spatial grid makes its first pass, you make a second pass to only pick up the items that match the tag, then perform the ray-box intersection as above.

 

 

You can handle an enormous number this type of ray/triangle intersection even on slow machines, I remember even on machines where we had to constantly remind the designers "You've got 66 MHz processor", we still could perform ray casts without much concern.  If you're on a 4GHz multi-core processor this shouldn't be an actual performance issue.

Share this post


Link to post
Share on other sites

This topic is 410 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this