Howto: raycast which excludes player's geometry

Hi all,

i have small problem with targeting enemies, and some ideas how to deal with it.

Problem: 3rd person view raycast from mouse position or camera center can go through player’s ship (if trying to target enemy ship behind player’s geometry) and closest collision is player and not enemy, which is not desirable result

solution #1: iterate through all collisionresults and find collisionresult with smallest distance that does not have player’s geometry, but i think this throws away speed

solution #2: attach player to another node than the enemies, this seems to be good and also mentioned in tutorial i think. but in multiplayer, all ships probably will be in some shipsNode including all players

i like solution #2 because there is no “ifs” but i think it will fail in multiplayer

is there any other way i cannot see now? :slight_smile: it is funny that my ship can shoot to itself :slight_smile:
i think best way can be, if i can somehow exclude specific nodes from raycast but i dont know if it is possible or how monkeys deal with it :slight_smile:

thanks
ascaria

You could also set the ray’s origin to be offset some distance from the player’s ship. For instance, at
[java]
ship.getWorldTranslation().add(rayDirection.mult(distance))
[/java]

yea i thought about moving raycast in front of the ship, this can be solution #3, it has drawback if enemy is between camera and player (for example when camera is zoomed out far away from player), enemy cannot be targeted.

what about attaching ships differently at different devices, something like:

server:

  • playerNode
  • shipsNode
    • player 1
    • player 2
    • player 3

player1:

  • playerNode
    • player 1
  • shipsNode
    • player 2
    • player 3

player2:

  • playerNode
    • player 2
  • shipsNode
    • player 1
    • player 3

I would go with the iterate,
why?
its simple and probably fast enough, and does not involve a change of the game/render logic.

Well you can also cast a ray to only collide with certain nodes

iterate , and why not test both the solutions to see if it really a disavantage to use iterate in the situation.

Remember the raycast will do a section test in every triangle in your mesh soup (which costly)… so if you include, exclude large amount of spatials, i say large and complex: You should have also a complex separation algorithm like in this example:

A Node contain all the terrain, trees, landscape elements: Landscape
A Node contain all your characters : Characters.
A Node contain all your effects: Effects
Those three contained by rootNode.

If you just want to check the collision with Characters for example, just go and raycast with that specific node. If you then just want to check the Enemies for example, time to get a separation. The separation can be temporial in the time of raycast which you make another excluded node wrap all the spatials that shouldn’t be there in the check and detach. Some info will be lost in this operation (also depend on your game’s logic) so for example the local translation and original parent should be saved somewhere.

This is an interesting question i also try to answer my self, it can be a lot of works in complex scenario, and can be as easy as an iteration… depends

…though do note that normal collision will rule things out based on bounding shape. So it doesn’t hit every triangle… only the ones that already passed the bounding shape test. A leaner “mesh soup” than otherwise might have been understood.

More over, the raycast logic is not too complicated… You can take a look at the source code to see if you can borrow something to use as your own sollution.

As in my framework, i made adhoc casting ultilities with public methods of Ray class.

Adhoc casting method dont use “every” mesh in the Node, also “not just limit” to one Node, and also “one ray” at a time.

You can see it as if you want to check 10 rays with 10 objects at once to see if a Predicate is matched. The most simple form is “if there any of that 10 objects are in the collision results”. Or “if there any of that 10 objects are collided with more than 2 rays”… As doing batch operations (un-rolling or without nested loops style), we saved much more computing cost for the job. Another usecase in my fw is to deal with ray casting with instancing of objects as inspired in below wolfire blog.

http://blog.wolfire.com/2009/11/Fast-object-instancing

The Adhoc ray casting can be very useful in a casting intensive games such as FPS or RTS. So at least take a look at loop unwinding for once and may be come up with your own sollution for your usecase. I also love to hear :slight_smile:

@pspeed said: ...though do note that normal collision will rule things out based on bounding shape. So it doesn't hit every triangle... only the ones that already passed the bounding shape test. A leaner "mesh soup" than otherwise might have been understood.

Yeah, i forget to mention that out of bounding shape will be excluded automaticly. But after bound culling, still there is a huge amount of triangles (terrain for example). So what i trying to say it let him think more about a clean separation before hand, not to make a mesh soup without organization and arrangment, which also a good practise for us all.

@atomix said: Yeah, i forget to mention that out of bounding shape will be excluded automaticly. But after bound culling, still there is a huge amount of triangles (terrain for example). So what i trying to say it let him think more about a clean separation before hand, not to make a mesh soup without organization and arrangment, which also a good practise for us all.

There is a bounding hierarchy in the mesh data, too. It’s not just blindly hitting all triangles… they’ve been divided into a BVH.

So, while it’s bad it’s not eye-bleeding bad.

i did it this way:

pseudocode for RayNode.java
[java]
RayNode {
colideWith(t ray, t results, Spatial… spatialsToExclude) {
for(t child : children) {
if(!shouldExclude(child, spatialsToExclude)) {
child.colideWith(ray, results);
}
}
}
shouldExclude(t spatial, t spatials) {
for(i = 0; i < spatials.length; i++) { // maybe faster than for(type a : b) {} because arraylist do “for(a, b, c) {}”
if(spatials[i] == spatial) {
return true;
}
}
return false;
}
}
rayNode.
[/java]

is here any chance, this will be implemented in core? or im supposed to exclude player different way ? im trying to not subclass classes and use what is available, so built-in “pattern” spatial-control is not even slightly disturbed. difference between ship and tree is that the tree does not have spaceshipcontrol. but i can add it to tree :slight_smile:

im thinking to iterate through collisionresults and exclude player there, rather than use RayNode. but also i think is is nice that certain collision does not neet do be calculated

i cannot have player’s ship in different node than other ships in multiplayer, all ships will be in RayNode shipsNode

@atomix i read your post almost 10 times :smiley: before i understand what you mean :smiley: i think i get it. im not firing ray at whole scene’s branch, lets say shipsNode, but while adding ships, vehicles etc to their nodes, i also add them into my custom “targetables” array which is not part of scene. then i simply iterate through targetables when targeting, so:
[java]
ray = new ray(pos, dir);
results = new collisionresults();
for(spatial x : targetables) {
x.collideWith(ray, results);
}
[/java]
that is brilliant, there is no overheat for targeting unnecesary things and also there is possibility to target things in different branches without need to iterate through whole different branches :slight_smile:

but how can i do this in multiplayer ? do client have one dimensional array with targetables ? and server array of player ids and in that another array of targetables? so when client wants to target, server fires ray at targetables[playerid] ?

Btw, do you use physics?

Cause the physicengine can also do rays, but is really good optimized at it.
-> Also it supports a does collide callback logic.

yea i use physics and i saw it has rays, but i never used them yet. but is it good idea to target enemy with mouse through physics ray?

Well the physics ray uses your collision shape,

eg if you use a capsule for the player, its way cheaper than the actual triangle collisions.

with that targetables array, i can also do something like radar in my ship, and even better, on that radar, i can select ship also without needing an raycast, that is very cool

@Empire yea you are right, i have multiple hull collision shapes in compound shape (wings, body, etc) on ship, so it is relatively good precision, but not absolute. but doing raycast from mouse cursor to physics space, i thing this have big downside, and it is model-physics syncing, as ilustrated here (ship have approx 2-3000kmh so it is real fighter aircraft speed):

(on image is gimpact collision shape, i changed it to several hull collision shapes recently)
i think this means that if you raycast at tip of the wing, ray will miss

@Ascaria :

Well, it’s nice to hear some success feedback. Actually the targetable arrays are also a kind of “divide to conquer” technique that suite to your usecase. Now for sync between network, let’s use imagination again.

The targetable arrays or even the positions of Spatials can be consider the “data” that you want to sync between clients. Now at first let make it specific what you want to sync and how , how much?

A Client should know everything about what happen in the galaxy (position, damages, contact of physics)… So your Server will have to send every changes in that Data, to every Client. Client later catch the Data after a few miliseconds and correct put that Data to use. The direction can also be Client ask Server later if they need new Data, Server answer with appropriate Data.

In reality, your Client doesn’t usually need to know everything, just a couple of ships near their ship.

So you see the Data that Server what to share are divided to parts which are still related to each other: Ship 10 has ship 0-9 around, ship 11 has ship 1,2,3,9,10 around…

Sending all of that infos may be good enough if there is not too much Clients listening.
Sending less overlapped, less replicated, less redudant, less errors infos is a much more difficult problem.

less overlapped, less replicated: this ultimately involve spatial partitioning algorithm which OcTree or RTree 3D to solve KNearestNeiborgh problem may suitable.

less redundant, less errors: this ultimately involve network balancing, network error compressing and networked entity interpolation.
https://developer.valvesoftware.com/wiki/Networking_Entities
http://www.gabrielgambetta.com/fpm3.html

But that’s a nested problem in problem. First make it work, then make it fast!

As my experience in implementing algorithm and datastructure for this problem may also helpful for you to decide what to do quick:

My first try, 7 years ago, I did C++ FPS in Ogre with some insights from
http://www.amazon.com/Structures-Algorithms-Developers-Charles-Development/dp/1584504951
I use QuadTree for positions and interactions computing along with BSP for partitioning things

Second try, 4 years ago, an Network FPS with Unity:
I use OcTree for positions and interactions along with NavMesh cell partitioning (use NavMesh cell as partition space split)! Info about interactions are saved as components of entities, so syncing between client are just normal components communicating. Later, the interacted components are process to procedure Result components (new interpolated position, new damaged status … etc)

Some tries later, till now, i’ve researched a big load of papers and the Java world for the problem. It take looooooong time to actually make something good out of it… and then later comeback to develop your game.

So along the path you may find this libraries interesting:
GlazedList offer rapid way to sync lists. http://www.glazedlists.com/
Java algorithms : https://code.google.com/p/java-algorithms-implementation/
Commons Math offer Space partitioning in good abstraction. Math – Commons Math: The Apache Commons Mathematics Library … and of course offer Mathematical stuffs.
XXL offer an advanced query processing functionality. https://code.google.com/p/xxl/
SpaceBase (commercial) offer a very complete solution http://www.paralleluniverse.co/spacebase/

What i’m doing now is to make a sollution based in XXL with algebra for spatial processing , trees and graphs as datastructure and black magic of concurrent. So later, may be years later… May be my Atom fw can come out with its ultimate solution for the problem also:)

Anyway, don’t know if this will really help you or not but i think there is at least a point to share this knowledge.

Wow im feels small right now :smiley: i will be happy with most trivial multiplayer with maybe 5 players and small levels :slight_smile: these advanced algos much later :slight_smile: i look at those glazer lists but idk if im able to do it now with my experience :slight_smile: in my job im php programmer and creating cms and company’s web on it :slight_smile: i want to develop my skills :slight_smile: those algos looks like mmo algos :slight_smile:

Its long and im on mobile so stop now :smiley: i think my ship will be based on server-client chat tutorial:-)

@Empire Phoenix said: Well the physics ray uses your collision shape,

eg if you use a capsule for the player, its way cheaper than the actual triangle collisions.

Especially is your player consists of multiple geometries.