Engine:Proposals:3D Collision Map
From Damasca
This proposal has been rejected in favour of a better solution, to be formalised on the wiki soon.
This document is a proposal for a new model of generating a collision detection model for maps. Whilst being primarily focused on collision detection enhancements, it also addresses some rendering issues.
Contents |
Existing Solution
Currently, or rather, in the past, we have gone for a purely 2D tile based collision model - mark out tiles as blocking, and that's it. This model works fine for simple tasks, but as will be shown in Problems, it falls short on some accounts. Including, but not limited to, the Bridge Problem - allowing players under and over the same bridge. Proposed extensions to the current model include grouping layers together and giving them arbitrary heights, whilst drawing masks over transition areas between heights (such as on stairs). This is a poor solution, as it is confusing, unintuitive and doesn't cleanly solve all of the problems.
Problems
This proposal identifies the following problems with the current model:
- The Tree and Fence Problem
- The Bridge Problem
- The Jumping Problem
- The Falling Problem
The Tree and Fence Problem
Refer to the following image:
As you can see in this mockup, we want to support allowing the player to go behind and in front of the tree or fence. If you consider that the tiles are just placed flat on the map, it becomes apparent that this is difficult - putting the tiles on a higher layer than the player would allow the player to go under, but not over - and visa versa. The problem is that as far as the engine is concerned, all the tiles are lying flat on the ground - as if the tree had fallen over. This is clearly not the case, and there needs to be a method of expressing this fact to the engine.
Graal handled this by simply not allowing the player to go behind their trees (at least, on all the maps I played on). This, I feel, is poor.
The Bridge Problem
Similar in appearance to the Tree and Fence, this concerns allowing the player to be on top of a bridge, and yet also allow them to go underneath it. The previous proposal for solving this problem involved giving layers arbitrary heights, and then masking out the regions that transitioned between heights - taking care not to add transitions between the sides of the bridge and the layer beneath. This solution was a little too complicated for my liking, would require lots of special case work from the level designer, and didn't neatly solve all the issues - it wouldn't fix the Tree and Fence, for instance - unless you created lots of layers!
The Jumping Problem
In the standard collision model of setting "blocking" tiles, you are in effect creating an infinitely high pillar from the ground upwards - this is what is blocking the player movement. If you imagine that the intention was to block the player from walking through a short fence, then it is obvious that this is ridiculous. Since the pillar is infinitely high, the only way to allow the player to jump over the fence is via hacks and workarounds - turning off the collision detection if the player is in midair. These hacks are only necessary because those "pillars" are infinitely high.
The Falling Problem
This concerns holes in the floors of maps that drop down to other levels - such as a pit, or the edge of a cliff. Again, consider the 2D approach. When the player walks off the edge of the cliff, they expect to start falling. In the 2D approach, scripting, or special case tiles are required to create this illusion. This is required because there is no height information stored in the map data and so the engine simply doesn't know any better! The previous proposal solved this problem through it's use of layer heights and transition masks, but it wasn't clean, and required extra work on the part of the level designer to craft.
My Solution
I propose that maps are given extra meta-data (see Implementation) to allow the engine to generate an accurate 3D representation of the level. By storing level geometry in 3D and giving all actors a 3D position then all the above problems disappear entirely:
Tree and Fence
Trees and fences (and similar objects) can be given real heights - made to stand up - so the engine can trivially render them alongside the players in the correct order. Similarly, collision detection on the tree will just work.
Bridges
This is also trivially solved, as the bridge is now physically separate from the ground below it.
Jumping
Collision information would now have heights associated with everything, so those infinitely high pillars are no longer an issue - the fence is as high as the fence should be. Allowing the player to jump over it is trivial.
Falling
When the player is on top of the cliff they are physically high up - when they step off the engine recognises that there isn't any ground below them any more, and can make them fall visibly without any hacks or workarounds.
Implementation
Implementation is tricky, but not impossible, and will only impact upon the level designer slightly - and hopefully no more so than the transition mask/layer height solution would have done.
Obviously the intention is to present the user and map editor with the 2D representation of a map as it currently - just so this is a clear, this is not about turning Damasca into a 3D game. What we want to do is turn the map, as designed by the editor, into a 3D mesh for accurate collision detection and rendering.
If you consider that the map as drawn by the designer is the projection of a 3D environment onto a 2D plane, then the trick is to unproject the map back to 3D. To do this, it will be necessary to know how the tiles in the map are connected, and their orientation (ground, cliff or sloping).
Editor Changes
The changes to the editor are the most important, I feel. Two new mechanisms will need to be added. One for linking connected tiles together, and one for marking out the different types of tiles. I'll address the latter first.
Marking out tile types
There are (as I can see it) three types of tile important to this unprojection process. Ground tiles, vertical (cliff) tiles, and sloping tiles. In general, tilesets can store this information about their tiles. As a result, marking out tile types will incur no development overhead aside from the initial tileset set-up and any additional tweaks that may be required (perhaps from using a tile in a way that was not originally intended).
See the following mockup for how applying the tile attributes could be coloured to make it easier to check and tweak (red = ground, blue = cliff, sloping is not shown).
Linking connected tiles
This is the crux of the implementation, and is also the step that will put the most work onto the map designer.
It is necessary that the engine be told which tiles, from the tiles around it, it is connected to. If you consider the following screenshot (taken from Dart's perfect cliffs map, with a bit of tweaking from myself):
Concentrate on the left platform first - obviously there are walls on the left and right side of the platform, the back is raised slightly (so the player should be able to go behind the platform), there is a path going up to the platform that the player should be able to walk upon (it is sloped).
What needs to be done in this case, is to link all the ground tiles together with the path, and the path to the upper platform.
In this mockup, I've laid out the tile links:
The links go between tiles that are physically connected in the 3D view. You clearly see how the back of the platform is disconnected from the ground behind, and how the edges of the path are disconnected from the walls to either side.
In order to make this graph easily editable, I propose an editor tool that allows the designer to paint logically connected areas and link them to other logically connected areas (to avoid connecting individual tiles).
Prefabs will be able to have the link graphs saved with them, meaning that when a prefab is placed on a map, the links for it are generated automatically. This will be useful for trees, houses etc.
Conclusion
If this proposal is implemented, not only are all the aforementioned problems solved gracefully, we leave ourselves open for lots of other cool effects, including (but not limited to), real shadowing with day/night cycles (3d mesh = enough info for a good shadow), physics with gravity, flying objects and much more.
The only downside, aside from extra engine development time and some small runtime performance cost is the extra burden on the map designer. Hopefully however, we should be able to design enough tool support to make this is a non issue.
Comments
Please direct all comments to the 3D Collision Map thread.
