4
\$\begingroup\$

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: enter image description here

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.

Just to add I will be using this in a heated loop and so I have the additional requirement that this must be done efficiently.

EDIT: this picture illustrates why I think a box casting would work for loose grid: (The box must be bigger than the objects contained in the grid.)

enter image description here

\$\endgroup\$
3
  • \$\begingroup\$ I don't understand how a loosebgrid works for small objects let alone a ray. How do collisions with objects that done end up in the same grid as a large object work? \$\endgroup\$ Commented Nov 30, 2014 at 4:08
  • \$\begingroup\$ The grid size must be strictly greater than whatever object it contains. I use multiple grids for objects with very different sizes. For small objects, just query the cells that it overlaps for collision. \$\endgroup\$ Commented Nov 30, 2014 at 4:13
  • \$\begingroup\$ You may be interested in Intersection of a thick line with a grid. \$\endgroup\$ Commented Oct 4, 2024 at 11:01

3 Answers 3

Reset to default
4
\$\begingroup\$

Your problem is not the ray cast, but that your grid cell doesn't reflect its actual state or in other words it might contain objects that it doesn't know about. When a certain object intersects a grid cell, the grid cell should know about it, this way when an object intersect multiple grid cells each grid cell should have a reference to that object, this should be done when the object position is updated.

If you don't want to update the grid cells, one possibility is to check the 1st neighbors for each cell you hit.

I also want to assert that having a thick (or cylindrical) ray cast is not the correct solution for your problem, it will be much more expensive to cast a cylinder or use multiple rays each time than the normal ray cast, the correct way to do it, is to correctly update the grid cells.

Another alternative is to use Octrees this way each grid cell will be strictly bigger than the objects inside of it, and you will have hierarchical stricture. The problem with octrees is that they are much harder to update.

\$\endgroup\$
5
  • \$\begingroup\$ Getting the 1st neighbour should work. Do you have an implementation that doesnt result in lots of duplicates of the same cells? I wouldnt be using the thick ray for actual intersection test but I only need an algorithm for getting the possible cells that the ray may intersect something. False positives are ok. \$\endgroup\$ Commented Nov 30, 2014 at 20:04
  • \$\begingroup\$ Also I dont quite understand what you mean by loose grid doesnt reflect the actual state. See my edited OP; it seems like a box cast would hit all the relevant cells. \$\endgroup\$ Commented Nov 30, 2014 at 20:43
  • \$\begingroup\$ I agree that having grid cells that don't know they are occupied is the root problem. \$\endgroup\$ Commented Nov 30, 2014 at 20:51
  • \$\begingroup\$ @user55564 I mean it can contain objects it doesn't have references to. Also I don't understand what do you mean by "Do you have an implementation that doesnt result in lots of duplicates of the same cells?" \$\endgroup\$ Commented Dec 1, 2014 at 6:02
  • \$\begingroup\$ @concept3d I take that back, do you have any implementation I can look at? \$\endgroup\$ Commented Dec 1, 2014 at 6:19
1
\$\begingroup\$

As per @Krom Stern's suggestion, this is my solution to this problem.

An incomplete, but working box cast algorithm for uniform grid: http://jsfiddle.net/d5ab67fj/1/. It currently is missing the end point cases and it only increment in X direction, but the algorithm itself is working. It will not miss any cells that the box would hit and it will not include any cells that the box would have missed (save for the end points in the incomplete implementation).

Also, why I choose to use this method rather than a non loose grid:

1) All my objects contained in grid are strictly smaller than grid size. This has important performance advantage because a large object requires many cells to be updated whenever it moves. If you need to support DYNAMIC objects with vastly different sizes, I highly reccomand use multiple uniform grid of various sizes rather than 1 size fit all structure such as quad/octree.

2) All my objects in the said grid are expected to require grid cell updates at every game step; as you can imagine, this is more costly in a non loose grid.

3) I need to call raycast less often than objects requiring updates.

4) Although in a loose grid, you need to hit more cells for raycast/collision tests, every cell contains less objects on average (due to the non overlapping nature). This may or may not make a difference depending on your needs.

\$\endgroup\$
0
\$\begingroup\$

Given that you cast just one ray and that objects can take no more than closest neighbor tiles in any of 8 directions, you just need to expand your resulting list of tiles 1 tile in every direction. Either while you detect the tiles rays goes through, or after you have the whole list - depends on your needs/constraints.

\$\endgroup\$
3
  • \$\begingroup\$ Getting the neighbours should work. Do you have an implementation that doesnt result in lots of duplicates of the same cells? Preferably detect the tiles as the ray goes through so you can bail early if the ray hits something. \$\endgroup\$ Commented Nov 30, 2014 at 20:10
  • \$\begingroup\$ @user55564: It depends on how you detect the tiles that ray goes through. \$\endgroup\$ Commented Dec 1, 2014 at 6:14
  • \$\begingroup\$ do you have a sample implementation I can look at? \$\endgroup\$ Commented Dec 1, 2014 at 6:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.