Nathaniel3W":1r697118 said:
We don't all spend our free time writing ray tracers for 20-year-old hardware. To me, anything that isn't gameplay is low-level. That includes physics, which includes collision.
So the lines that you project the collision polygons onto, are they just parallel to the X and Y axes, or do you figure out what's occupied on a line perpendicular to the movement? Is calculating occupied space along an arbitrary line more computationally expensive than checking along the line X=1? Either way, do you have to see what's occupied along the entire line, or do you just look at what's ahead of the movement? I guess you haven't optimized yet, so what are you planning on doing?
I have zero experience in RPGM. I don't suppose you could just let the events move as physics dictate, and then try to return to the path?
The need to write the basics out is still there in the right circumstances. The alternative I could have taken is use Box2D, however that would involve abstracting away a lot of what's happening and adding a thick layer of translation between Box2D and MV. Performance isn't the worry, the worry is that other people will be reading this code and making improvements or extending to suit their game's need, and needing them to know how the magical Box2D works underneath is more to ask than to simply let them read the basic mathematics behind 2D collision detection.
Not to mention, Box2D is a little over-kill. There's other collision libraries that are less physics oriented but then you're at the point of "why involve a 3rd party library when it takes just as long to write it myself?" and with MV I believe it's important to have the entire Plugin in one file, rather than split across library dependencies.
If I was making a game, rather than a Plugin, then I'd just use a third-party library to do this. My game projects I have planned will certainly use libraries.
The lines I project onto are perpendicular to the polygon lines, essentially the surface normal, but for the case of circles there a fast-path check for the line between the circle's centre and the nearest vertex of the testing polygon. Basically project polygon B onto the normals of polygon A, then do the same of A onto B's normals, if there's any gaps then there's no collision.
I don't check along the entire line, that would be more computationally expensive. The solution for checking along the line would be to see if the movement vector crosses the polygon edges at any point, which involves a line-intersection test. As long as one of the two polygons being tested is thicker than the step-size they won't be able to move through each other. The map lines, however, have a thickness of zero; so if the polygon moving towards it is smaller than the step-size it will pass over easy. MV doesn't have movement interpolation (locked to frame-rate) so this behaviour is consistent and isn't surprising.
There is a middle-ground; if the polygon is thinner than step-size in the direction of motion, then do a line-intersection test. I think this isn't necessary for RPG Maker and would end up adding bloat to the Plugin's code, which needs to be readable and simple.
If I was making a Doom-style FPS, then I'd use 2D line-intersection because of the variable frame-rate issue.
The most optimisation I'll probably do for now is a bounding volume hierarchy for the map's collision mesh. My original plan was to dynamically generate the mesh around the player as they move, however the maps in MV are static, so I can actually spend some load-time computing a collision mesh for the map (which I will likely cache to disk as further optimisation).
There is an intensive search and filter for finding all the characters that are potentially colliding (get all characters near bounding-box of motion); this is an area I'll optimise at a later date. It's fine as is, but won't scale when there's lots of events. I've looked at several techniques for updating bounding-box trees for when a single-node moves, just need to find one that fits MV's situation of having either a handful of events or a hundred events.