Vector-Based Collision

[Kaimetsu]

Onwall2 is more or less sufficient for the simple movement of player characters, since they tend to travel at consistent speeds and they can be considered rectangular. However, it is pretty lacking for many other types of collision detection. Rotatable objects are a pretty good example: Rotate a square by thirty degrees and then fire it in an arbitrary direction. Odds are it won't be easy to write fast, reliable code to find out what it'll hit first.

It would be nice, then, to have a function like this:

vectorcollision({line1},{line2},time)

The two lines represent the start and end state of a single vector. It changes linearly from one to the other over a specified time (in most cases we would pass 0.05). The engine examines the path of this vector and determines if/when it will first collide with a blocking object. Then it returns the coordinates and relative time of that collision (we can return arrays, right?).

Alternatively,

vectorcollision({line},dx,dy,drotation,speed)

dx,dy give the velocity of the centre of the line. drotation gives its rate of spin (adjusted to be consistent with the velocity). Again, the engine figures out when and where the lines collides with something and returns its prediction.

[Admins]

Ah that sounds quite complicated. It is planned that there will be some basic vector collision detection for showimgs (clientside-games/effects), but I don't see the reason for npcs or similar. The problem is that you have many moving objects of different shape, a rectangle check or radius check is most of the time the only working way, easy to configure and fast to calculate. I am open to new ideas though, if you have some examples where a better collision detection would help a lot then please post them.

[Kaimetsu]

Well, I'm mostly thinking about vehicles. Like one time I was coding a car for Era, and it had sprites for sixteen different directions. I wanted to add a nice physics system too, but that required some very precise collision detection. If we were just dealing with tiles then it wouldn't be so bad, but I also have to consider players and weird-shaped NPCs and suchlike.

So, what're my options? The best approach I can imagine is to treat the car as a rectangle and divide it into four sides, and then figure out when each of them will intersect with other stuff in the level. But the only precise way to do that is to iterate through every pixel, or build up a geometrical summary of the shape of the level. In either case, it'd be much faster and easier if hardcoded.

Check out the image I attached. It gives a basic summary of my problem.

[Admins]

Ok I understand, don't know why the function should care about the rotation of the colliding line though, since movements must be linear anyway (by setting positions explicitely or using the move command).
The simpliest way would probably be to just check for the tiles by script (several onwall checks along the line in steps of 1 tile). That way you can also theoretically detect diagonal walls. I can add some command for easier collision detection though, but it should be made so that it can be used for many different cases of collision.

[Kaimetsu]

Originally Posted by Stefan

Ok I understand, don't know why the function should care about the rotation of the colliding line though, since movements must be linear anyway

Well, moving linearly from point A to point B between two frames is just an approximation to a smooth, continuous motion. There'd be a difference between a curved path and a linear one, even if it's relatively small.

The simpliest way would probably be to just check for the tiles by script (several onwall checks along the line in steps of 1 tile). That way you can also theoretically detect diagonal walls

Yeah, it kind of works, but you can't get much precision unless you use dozens of checks. Recently I made a little system that scans through the level and builds an array of vectors representing walls (like, if there were a bush in a level then it would define a wall vector for each of its sides). Then I used some fairly simple vector calculations to find out exactly where and when a collision would occur between a wall and a moving object. It's very fast and extremely precise, but it can't handle dynamic objects (players, movable tiles, etc) or NPCs with weird shapes. It's really only good for minigames.

Out of curiosity, how does collision detection work in Graal3D? I haven't had a chance to play with its scripting engine yet

[Admins]

Originally Posted by Kaimetsu

Yeah, it kind of works, but you can't get much precision unless you use dozens of checks. Recently I made a little system that scans through the level and builds an array of vectors representing walls (like, if there were a bush in a level then it would define a wall vector for each of its sides). Then I used some fairly simple vector calculations to find out exactly where and when a collision would occur between a wall and a moving object. It's very fast and extremely precise, but it can't handle dynamic objects (players, movable tiles, etc) or NPCs with weird shapes. It's really only good for minigames.

Would be interesting to see that script We plan to soon add an automatic movement and collision system for showimgs for making client-side games. For serverside it could be interesting to add more shape modes for the setshape command (circle, oval, centered box) and make a function for knowing with which objects the npc/player collides if moved along a specified vector, with options for which objects should be handled (only npcs, only players, only tiles etc.) and returning the impact position, the distance the npc moved, and eventually the collision normal or reflection vector.

Originally Posted by Kaimetsu

Out of curiosity, how does collision detection work in Graal3D? I haven't had a chance to play with its scripting engine yet

It is using the polygons of the objects and is handled by engine. It is taking the polygons of the player and the velocity, and is colliding it against near objects, getting the polygon that touches the thing and the distance. Currently it is not very fast though, so it's basicly taking a box for the players. Only the interior objects (houses, caves) have are more optimized collision detection and use all polygons for collision detection. We will need to change that sometime, to use better collision libraries and make the player movement completely scripted.

[Googi]

Would it work online?

[Kaimetsu]

Originally Posted by Stefan

Would be interesting to see that script

Okay. I attached it to this post.

As a sidenote: It would be nice if there were an event that triggers on the clientside when the board is updated (if there isn't already - I'm a little out of the loop). Since my script just scans the level once when the player enters, it can't deal with changes like when somebody picks up a bush.

We plan to soon add an automatic movement and collision system for showimgs for making client-side games

Hm, sounds like a good idea. If it were my decision, I think I'd just add a single function that takes two images and their positions and tells the script whether or not they intersect. Then it'd be pretty easy to work into minigames, but it would also be flexible enough to use for other applications (like, if you want to check a possible collision without actually drawing an image).

For serverside it could be interesting to add more shape modes for the setshape command (circle, oval, centered box) and make a function for knowing with which objects the npc/player collides if moved along a specified vector, with options for which objects should be handled (only npcs, only players, only tiles etc.) and returning the impact position, the distance the npc moved, and eventually the collision normal or reflection vector

That sounds pretty good. Maybe also some way to define the shape and rotation of the player?

It is using the polygons of the objects and is handled by engine. It is taking the polygons of the player and the velocity, and is colliding it against near objects, getting the polygon that touches the thing and the distance

Hm, that raises an interesting point. Does G3D use varying LOD meshes? If there were a simpler mesh used purely for collision, it'd probably make things a little faster.

We will need to change that sometime, to use better collision libraries and make the player movement completely scripted.

Yeah, sounds like a pretty significant improvement. I had a rough design for a G3D playerworld, but it wouldn't work unless I had a large amount of control over the player's movement.

Originally Posted by Googi

Would it work online?

My vector thing? Yeah, I guess. But it's not very useful in its current state.

[Benm00t]

oo, sorry for treating it like a toy but thats kinda fun to play with. Also, i seemed to notice a bug, which i think is more to do with the program, than the script.

I ran Graal, clicked on "Offline test" instead of editor. Ah well, just open it using this anyway. Used F5, found the level, and when it opened, all the tiles were all funky, and it seems the script then works incorrectly as it is finding non blocking tiles. See image 1.

If you open the level from the editor, or go into the level editor and run the level again, then it works fine. See image 2.

[Kaimetsu]

Originally Posted by Benm00t

I ran Graal, clicked on "Offline test" instead of editor. Ah well, just open it using this anyway. Used F5, found the level, and when it opened, all the tiles were all funky

Yeah, that's pretty strange. Still, my script doesn't set the tiles at any point - it merely checks the onwall status of each 16x16 block in the level. I can only assume that it's some unintended behaviour in the client.

[Rick]

That's because the offline mode uses GK tileset.

[jake13jake]

I'm reviving a dead thread here, but it's not really in vain, I'd think. Vector-based collision would be a very good idea. I am actually working on a cliff-jumping script right now, and it would be a lot nicer if I could make it a diaganol parallelogram shape for the players to touch, rather than 9 or 10 (16x16) setshaped squares for the diagonal ledges.

[Rick]

There are vector related functions in v4. I havn't played with them yet though.

[Kaimetsu]

Originally Posted by Rick

There are vector related functions in v4. I havn't played with them yet though.

Presumably just basic stuff like cross products, normalisation, etc.

[jake13jake]

I still use v2. Anways, what I mean is to be able to shape stuff like a diagonal parallelogram. Right now what I have to do for diaganol walls is like (see attached). It would make a lot more sense to be able to have diagonal shapes for something like this.