Simulating video game sprite collisions...

I've been making arcade games in SL for awhile now, but one thing's kept me from really going hog wild... sprite collisions.

In a video game, there's the need to check if two arbitrary rectangular boxes are overlapping each other -- ie, Pac-Man bumps into a ghost, etc. This has to be a speedy operation since it'll be done quite frequently and with a wide variety of sprites.

In SL, I'm mystified as to how I can do this. There's two possibilities.

First method, all sprites are part of the same linkset. Makes things a lot easier on the game owner, since they can delete one object and that de-rezzes the game, and the script doesn't have to rez up objects and try to communicate with them to control them.

Problem is, the only functions I see to get data from a linked object are llGetLinkName, llGetLinkKey, llGetLinkNumber... and that's it. There's certainly no llGetLinkPos to detect position or llGetLinkSize to detect sprite size. I could use linkmessages to pass the data back and forth but again, this has to be a SPEEDY operation, done quite frequently. I could have all control code and check code be in the root script and just tell the sprites where to move to, but independently moving sprites = faster code and less prone to weird sprite lag.

Second method, all sprites are actually objects rezzed by the game object, hovering in front of its "screen" and using SL's collision systems to detect collision. Independently scripted sprites which don't need to "poll" for collisions, simply await the collision event, would be VERY speedy.

Problem is, and the wiki's of no use here, would this even work for non-physics based objects? And what about the screwy bounding boxes? My previous attempts at a simple dartboard were met with failure, with darts stopping random distances away from the actual board. Would getting an ACCURATE collision if I used this technique? Or could it be a visible distance away and still trigger the collision?

Third method... something I'm not aware of yet. Always open to the idea I haven't considered all the possibilities...

Your thoughts? How can this problem be best solved?

I think I tried a collision detection object with non-physical movement, and it didn't work. I think I concluded that this was because non-physical movement instantly moves the object from point A to point B (even though the client interpolates that movement for the user), so it's not actually going through anything, it just ends up at its destination. But that was a long time ago, so my memory could be faulty, and things may have changed. I've also found that the physics engine gets squirrely as the colliding objects get smaller. Again, long time ago, and there are others here who are much more up-to-date on testing the limits of the physics engine.

One option might be to use physics combined with llVolumeDetect. That would make your sprites phantom (so they'd go through each other under lag), but the system would only have to detect inter-penetration (and would register a collision event if it did), it wouldn't have to calculate the physics of the collision itself. That *may* run smoother, and you'd have to handle any bouncing off / etc actions in the scripts, since the physics engine will see these as phantom objects.

VolumeDetect is an option... as noted, it'd mean sprites couldn't be 'solid', per se, but I doubt they woul'dve been even otherwise. All game that works with this limitation (uses collisions to detect single-hit enemy kills, not blocking walls) would be able to use this technique.

One problem is that in order to MOVE a phantom, physical prim, I'd need to use llMoveToTarget. Which damps movement, for that wacky yet generally undesired "slows down as it approaches" effect. Also a pain for sprites you want to make hard motions left, right, up, down depending on user input... in those cases you don't want to say "Go over here, you know, whenever you feel like it, over this timespan", you want to give it a short hop over a short time like llSetPos does.

Finally, there's collision is accuracy... so far the physics system, in my limited exploration, has been made of fail and wholly inaccurate. I'll perform some experiments but I don't expect much.

If only I had llGetLinkPos... that'd make all these problems go away!

I think you can make move-to-target fairly snappy by specifying short damping times, but like I said, I haven't messed with physics in a long time. Good luck with your project

'ello, Seven~
If the sprite movement is being controlled via a main script, or the objects are stationary, you might be able to fake it; I'm still working on a cleaner way to do this, but it's my plan for the RPG game you saw a while back. Essentially, just get the direction the player is facing, and what the square they are facing is. Though this may not work with say, a side-scroller.

That's fine for a single sprite and a scrolling background, like an RPG, but for something where you want dynamic enemies or other elements beyond the background it's not going to work. Collision is still an issue; the only thing texture offsets on a backdrop solves is scrolling.

Not quite what I meant, Sevs, but you're right. Even a llMoveTo leaves room for error if the AI script is just telling it to move to a new location, so not even preprogrammed AI would work. As such, it seems the only possible way to get it is, indeed, checking for the collision itself.

Alright, here's the test I'm gonna attempt tomorrow.

Sprites have names of "Name,X,Y". X and Y are integers representing a single 'step', a tiny increment of distance, but not a full blown sprite-sized grid reference. Collision can be detected by checking llGetLinkName, splitting up the CSV (or if it's faster, yanking out the integers with llGetSubString!), then comparing one sprite's position against a range of steps that added up equal the span of the sprite.

For example, say that the screen is a 1m x 1m square. A single X/Y integer represents 0.05 meters. Sprites are 0.2 meters across. That means that if you want to check collision of a 0.2x0.2 sprite, you need to see if X1 >= (X2 - 2) and X1 <= (X2 + 2) and Y1 >= (Y2 - 2) and Y1 <= (Y2 + 2). Relatively fast integer checks, there, and provided you don't have to run too many collision tests per 'cycle' should work fine.

...if that makes any sense.

My hope is that llSetName is fast enough that it can convey the repositioning of a sprite near simultaneously with the sprite's actual movement. I've had good luck using sprite renamers for the ammo counters in Zombie Meltdown, and those have to react pretty fast, so this may work.

If this madness works I'll release a Sprite Driver script in the next OpenArcade update.

Not sure if I'm getting all the subtleties here, but fwiw, I like the integer collision arithmetic idea, and share the experience that collisions seem imprecise, but I'm not gr0king the rationale for using the prim name to communicate between the "sprites" and the gameboard (and/or other sprites). Since only the sprites themselves could change the prim name, they must already have scripts inside--I think necessary, in lieu of something like llGetLinkPos--so why not just use link messages? (Reading the initial post, maybe we think that handling these events is slower than polling llGetLinkName()... but that's certainly not obvious to me... so maybe I'm missing it altogether.)

But... well, I know *nothing* about video games, so beware of total lossage here, but... why do the sprites need to know anything? Couldn't the whole thing be done with an omniscient master gameboard update script and a bunch of slave scripts that move the sprites around with llSetLinkPrimitiveParams (multiple slaves per sprite, to overcome delay built-in to that function)? The idea is that collision detection can be a memory operation within the master update script.

All those are valid methods, too. I'm just trying to find the FASTEST method.

I've tried "Master script, dummy sprite" which tells the sprite, via linkmessages, where to reposition itself. In a sim with any time dilation lag, there's a tendency for the sprite to lag behind the actual action, causing incorrect output. Plus, this doesn't solve the need for fast collision checks in general -- even with a central brain and dummy sprites a good, fast routine is needed, which I think I've got by making a sub-grid based on integers instead of pure positional floats.

My hope is that by distributing the workload across various scripts, sprites can move independently and, if one happens to lag a little in performance, it won't matter because the others can always get an absolute check on the sprite's position via llGetLinkName. The reason I'm using that instead of link messages is, as you guessed, a matter of speed... it's my GUESS (there's no hard data available to back it up because LSL is so undocumented) is that detecting the name is faster than sending a linkmessage of "Where are you?", then waiting to hear back with another linkmessage of "I'm at X,Y."

Edit: Just saw your other post - not sure why I didn't see it before

You might have to do a combo of a few methods to get the best results. If you use integer grid positions, then I would think that would be a faster check in a main control than global or even local position vectors so if you haven't tested it that way...

If you're sending linkmessages to each prim separately, then it can be fairly fast as the message is received almost instantly from what I've seen, and I'm not sure if llLinkMessage has the innate 0.2s programmed delay a lot of others have. I know that all of the llSetLink commands should have these, so I would definitely follow the route of having them move themselves, but I still think you could have a script in the main control track their movements as I feel this is the best way to detect a collision efficiently.

If the collision event would fire for non-physical items, I might think differently, but it won't...no matter what you do. There has to be some sort of physics involved to get a collision result. Even llVolumeDetect requires that the colliding object be a physical object. You might be able to do something with Volume detect and having the prims go physical immediately after they move, and using volume detect on all of them...but in a fast paced game dealing with something like sprites, I don't think that would be very efficient and games that use physics are usually pretty easy to cheat at.

You could have each piece announce its position after every change? My initial concern with that would be a flood of messages, but it's probably 1/2 the message load of a request-reply protocol, especially if they both need to occur once for every move/frame.