Segment Query (raycasting) API requests

Discuss new features and future development.

Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 4:16 am

(Updated with new info 5/21)

So I felt inspired the last day or two and started to implement raycasting. (Hooray and all right?) Actually, it's not really raycasting, but a directed segment query. You can't actually raycast into a spatial hash due to it having an infinite number of cells that would need to be traversed. I think that having an an explicit maximum ray distance is not so bad of a limitation for a 2D game though.

What I have so far is a function cpShapeSegmentQuery() that you can use to query against individual shapes. Parameters are:
  • a shape to query against
  • a segment start and end point
  • a layers bitmask and a group identifier (works just like with between collision shapes)
  • a pointer to a query info struct (pass NULL to have it malloc() and return a new one)

If the segment intersects the shape, it returns the query info struct pointer (or the allocated one). If there is no intersection, it returns NULL.

The query info structure contains the following information:
  • the shape hit by the segment
  • the alpha value of the collision between the start and end point
  • the distance from the start to the collision point (probably going to be removed, easy to calculate if you want it)
  • the collision point (probably going to be removed, easy to calculate if you want it)
  • the normal of the surface at the collision point

Querying against individual shapes isn't super handy, so I still need to implement support in the space and spatial hash. My thought was to have two functions available, one like the current point query function that uses a callback to pass all queried shapes, and another built on top of it that returns the query info for only the closest object hit.

Does that seem reasonable? Am I missing anything obvious or useful?

Currently the point query API has two separate functions for querying static and active shapes. At the time it seemed like a good idea as I was thinking about it in terms of grabbing objects with the mouse. I figured one would want an easy way to only specify active shapes for selection. Now this seems like sort of a bad idea as it means that you need to call both functions if you want both. Not so bad with point queries where you just throw away the value you don't want, but it would be annoying to call a query-for-first-hit function for each set of objects, need to determine which is closer, and free the info for the other. I don't really want to write 6 functions for both point queries and segment queries (active, static, both)x(all, first) when they all practically do the same thing. Active/Static versions could be done away with using on of the layer bits to tag active/static status. What do people think?

At the moment, I'm leaning towards letting the user tag static objects with a layer bit if they want. Other than mouse selection of objects, it doesn't seem useful, and setting a layer bit to mark an object as grabbable would be more flexible anyway.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Segment Query (raycasting) API requests

Postby OneSadCookie » Thu May 21, 2009 6:17 am

Why not have a single API that uses a callback to return results from nearest to farthest, maybe something like

Code: Select all
typedef _Bool (* cpRayIntersectFunction)(
    void    *context,
    cpSpace *space,
    cpShape *shape,
    cpVec    rayOrigin,
    cpVec    rayMagnitude,
    cpFloat  alpha,
    _Bool    shapeIsStatic);

#define CP_RAY_INTERSECT_STATIC (1 << 0)
#define CP_RAY_INTERSECT_DYNAMIC (1 << 1)

typedef unsigned cpRayIntersectFlags;

_Bool cpRayIntersect(
    cpSpace                *space,
    cpRayIntersectFunction  callback,
    void                   *context,
    cpVec                   rayOrigin,
    cpVec                   rayMagnitude,
    cpRayIntersectFlags     flags);


The callback would be called for each shape that intersects the ray, from nearest to farthest, until the callback returns false, or the maximum distance is reached. cpRayIntersect would return true if any collision was reported. Support for NULL callback might be useful.

You sidestep all memory problems and API complications, for the minor inconvenience of having to have a callback even in the simple case.
OneSadCookie
 
Posts: 2
Joined: Thu May 21, 2009 6:05 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 12:47 pm

Well, one problem with traversing a spatial hash is that you don't really get anything in order. With a nice spatial structure like a BSP, you always know that you are traversing the splitting planes in order and can terminate whenever you want. With a spatial hash, a grid cell near the end of traversal could be hashed to the same hash cell as a grid cell near the beginning of the traversal, and within each grid cell you objects certainly won't be in order either. So you basically have to run the entire traversal before deciding which is closest. Though I'm sure there are some heuristics that could be used to cut it down based on grid cell distance estimates or something. I'm somewhat worried that this will make the performance be lackluster.

So to implement what you are suggesting would require finding all intersections, sorting them by distance, then passing them to the callback. Not really so bad implementation-wise, but it's not like it would turn out to be an optimization that allows one to terminate the search early. The only useful early termination would be the trivial "Did I hit anything at all?" case. As far as sidestepping memory issues from the callback passing you a malloc()ed struct, I guess passing the values back as params does get around ever needing to malloc() anything internally even. That I guess is worth something.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Segment Query (raycasting) API requests

Postby OneSadCookie » Thu May 21, 2009 2:55 pm

I think you can do better than that; even though multiple cells may be hashed into the same bin, you know that the bin contains all the collisions for a particular alpha range. It seems that should allow you to do something like:

Code: Select all
make an empty unused collisions list
for each cell on the ray, in order:
    if the unused collisions list contains collisions less than the maximum alpha of this cell:
        // already processed the bin for this cell
        for each unused collision less than the maximum alpha for this cell:
            call the callback
            remove the collision from the unused collisions list
    else:
        check for all collisions within the cell's bin, sort by alpha
        for each collision in this cell with distance less than the maximum alpha for the cell:
            call the callback
        insert the remainder into the unused collisions list, keeping the list sorted by alpha


That doesn't avoid memory allocation, though you can stack-allocate space for a small "unused collisions" list to avoid mallocing until absolutely necessary...
OneSadCookie
 
Posts: 2
Joined: Thu May 21, 2009 6:05 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 3:34 pm

Hmm. I suppose in order to traverse the grid, I will need to be tracking the alpha value anyway, so that part won't really be so hard. I don't really like the ambiguity of keeping a "small number" of allocations on the stack, so I would need to toss a bunch of memory management code into it.

I think I'm going to approach the implementation in a couple of passes. First just iterate all of the objects in the hash and check each individually. This would be a good simple base implementation to test against. Next move onto a normal AABB query that the spatial hash currently supports. That should at least make the performance usable. Then implement a grid traversal query in the spatial hash. As a bonus, that could also be used for hashing line segment shapes. Probably a decent bonus for long diagonal line segments. Once all that is working... Then finally move onto in order traversal of the ray collisions.

I guess I'm not too concerned initially about having in order traversal. If you want all of the collisions and want them sorted, it's not hard to put them in an array and sort them yourself. If you want just the first collision there can be an API call to wrap that. Without in order traversal, finding the first won't be super efficient, but will work without changes once it does get implemented giving you a free speed boost.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Segment Query (raycasting) API requests

Postby majicDave » Thu May 21, 2009 6:04 pm

All sounds pretty good to me.

I can see situations where the exit point may also be useful to know, if that info isn't too difficult to add. Maybe just alphaNear and alphaFar or something?
majicDave
 
Posts: 6
Joined: Thu May 21, 2009 5:44 pm

Re: Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 11:10 pm

I can't really see the exit point being usefull 99% of the time. Circles are the only case where calculating the exit point would be a trivial addition. If you want both, just query the reverse segment against each individual shape returned by the space.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Segment Query (raycasting) API requests

Postby dieterweb » Fri May 22, 2009 2:53 am

Can someone give me e short explanation for what the segment query is useful? Line to Line collisions, bullets?

Thanks,
Thomas
Visit our game Blog: http://zombiesmash.gamedrs.com or follow us on twitter: http://twitter.com/zombiesmash
dieterweb
 
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany

Re: Segment Query (raycasting) API requests

Postby slembcke » Fri May 22, 2009 9:14 am

There are a couple common uses:
  • Line of sight: Check if an enemy can see the player, or vice versa. Shoot a ray from the enemy to the player. If it doesn't hit anything else on the way, then you know it can see the player.
  • Bullets and lasers: Your character fires a fast moving bullet or laser beam. You can approximate the bullet flight by doing a segment query for the trajectory covered by the bullet in that timestep. Similarly for lasers. You just shoot a ray out of the character and see what it hits. The query would return enough information to easily figure out the distance and position of the hit so you could draw the laser beam to stop where it first hits something and to draw some particles at the impact point.
  • Sensors: I recently wrote some AI for a hovering robot in some contract work I did. I used ray casting to find how high the robot was, and adjusted the hovering force accordingly. That way it would automatically hover over obstacles and such. You could use the same thing for proximity sensors as well. To check if your AI object is near a wall or something else. Lastly, you could use them for static sensors in a level like laser tripwires or something like that.
  • Raycast based cars: To avoid using joints and lots of extra bodies in a very fast paced racing game, a common simplification is simply to model the tires as raycast calls. You figure out if the wheels would be touching the ground using a simple raycast distance check from where they are attached and apply impulses/forces accordingly.

Those are the possibilities that come to mind to me anyway.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Segment Query (raycasting) API requests

Postby dieterweb » Mon May 25, 2009 4:18 am

Thank you for this detailed answer. No need for this in my current project, but I will keep this in mind.

Are all of your current cvs changes for this feature?

Thomas
Visit our game Blog: http://zombiesmash.gamedrs.com or follow us on twitter: http://twitter.com/zombiesmash
dieterweb
 
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany

Next

Return to Features/Development

Who is online

Users browsing this forum: No registered users and 1 guest

cron