I am not sure what the correct name is called but here is my problem: I have implemented a casting ray function that works as expected. However, because I am using a loose grid structure, (ie, objects that overlap multiple grids are only put into one grid), the ray cast may miss certain objects. What I need, I think is a box casting where I need to get every grid the box hits from its initial position to final position. Does anyone have such algorithm? Or pointing out to a solution to this problem, thanks!

This pic from N tutorials is a nice summary of this problem:

My ray cast implementation only hit the blue cells but as you can see, it may miss certain objects. They are only put into the grid where the x is.

I'm not sure how the pic shows the problem, since it hits all the objects, is there another case you are thinking of? It does look like that pic is doing a variation of either a Bresenham or Xu's line drawing algorithm. You can modify the algorithms to do width.

If you really want to, you could just create a rectangle of the desired width, and of the desired length, and test the objects against that. You could probably do both the line algorithm from the pic as a first pass, and then only test collision with the rectangle against those objects in the blue squares. That would catch cases where the object is in the tile, but not within the width of the line.

The raycast (which is not Bresenhams, since Bresenhams does not catch all the cells the ray traverse through) only hits the blue cells. However, because I am using the loose grid structure, objects are only put into cells where the x is. Thus, in the picture, the ray cast will miss all 3 objects.

I am using this as a first pass so false positives are ok. But the ray cast first pass is currently under inclusive. I need something like this:

Does the algorithm you posted guarantee that all the gray and blue cells will be hit?

Ah, thanks for the second picture. and longer explanation. Bresenham will only really miss the diagonal case, Wu's will get it, if that's the kind of granularity you need, and then you just need to modify the width.

Something like http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

Just ignore intensity/alpha for your purposes, and consider it to be 'full intensity' or as a square that has been hit by the sweep.

I have implemented Wu's based on the article on the wiki and here is a live version: http://jsfiddle.net/yoc6cq0f/4/. It seems to work ok for x-axis major increments, but sometimes it looks like it misses some diagonals, I dont know if that is just a graphic thing. Also when the mode switches (~45 degrees) there is a noticeable jump with the tiles covered.

Also I dont quite know how to apply Wus to a box with x,y, width and height since Wus, as I understand it, only cares about line thickness.

Relevant portions of the code:

You can get thickness from the box, for your example above, you have the two points of the box perpendicular to the sweep, the distance between them is the thickness. (or cheat and do as you are in your fiddle with multiple lines being cast)

It looks like you might have some sort of error when the slope is y major, and possibly negative? I see it flipping from correct to incorrect in certain cases.

Hello again, I eventually decided to move away from Wu's because it is missing some diagonal cases and I am not if that is due to my implementation or the nature of algorithm. Anyhow, I devised my own algorithm that performs a true box cast that works here: http://jsfiddle.net/d5ab67fj/1/ and I will leave it there for future googlers that may bump into the same problem.

It is incomplete; the ends points are currently over inclusive and the algorithm does not work when x is 0 (or small); that can be easily fixed by allowing it to increment in the Y direction instead of X only. I shall now port it to 3D and hopefully that concludes this exercise for me. Thanks again for your suggest to look into the Wu's algorithm. It gave me the idea on how to tackle the problem.

I think you have a collision detection problem, not a ray-casting problem.

Why can't you put a single object in multiple grid cells? Each cell would contain a list of objects.

I think this would make more sense if you have a very large object that overlaps several grids.

Dont have objects larger than grid; objects are all fast moving, updating adjacent grids all the time is costly; ray cast/ box cast is less frequent than object updates; although ray cast in loose grid traverse more cells, each cell contains less objects on average.