If this has already been answered, I apologize, since the forums aren't easily searchable at the moment. The only relevant post I could find through clever Google searches was this one, and it didn't get answered, unless I'm missing some of the Witness Wednesday posts.
I'd just like to know more about how collisions were handled in The Witness. I've been puzzling through it on my own, trying to figure out how a similar system might work for a game I'm working on, but I can't help but feel I'm missing a few crucial things.
Here's what I've been able to piece together so far:
From Handmade Hero: Instead of resolving collisions with simplified physical simulation, the closest reachable point to some destination is found. The geometry is made to be "searchable" so that there is an upper bound to the amount of time this can take. In order to only find reachable points, some kind of flood-fill is performed, so there is always a path back to the origin point from the found point. This flood fill is restricted, possibly by the bounding box of the overall movement, to avoid tunneling and other acrobatics.
From this video: The walkable area is determined, somehow. Possibly by a related flood-fill algorithm. A grid is overlaid on the ground to visualize this. It's hard to tell whether the grid is a literal representation or just some way to texture the area. The walkable area changes as scenery, such as the boat, moves around. Traditional collision geometry is shown to be stored in at least the debug build of the game.
My initial thoughts were that as a preprocessing step, the entire ground manifold might have been covered with a large array of cells. Each of them would either be empty or hold a line segment representing the border between walkable and non-walkable areas. It would be easy to make that into a sparsely-stored system as well, and then the walkable area could simply be determined by allocating a chunk around the player and copying the relevant cells into it. Cells are also easy to flood-fill, making it simple to find reachable points.
There are some holes in this idea. The Witness has plenty of things that move, like the boat, and when things move the walkable area changes, which doesn't make much sense if all of the cells are stored statically, since they'd have to be regenerated. Also, in the video, collision geometry is shown to still be stored in the game, which wouldn't be necessary if the searchable cell-based geometry was already computed.
I also considered whether cells might be generated in real-time around the player as they walk. It seems a bit much, almost like doing collision-detection for lots of things instead of just one, but it's a possibility. Another possibility is that the "walk grid" was just a visualization and I am very off-track with all of this.
Could Casey or someone else share some insight as to this kind of collision response?
I'm interested specifically in how the system would perform with full 3D movement, since it seems like The Witness was restricted to working on a ground manifold, and it would be really neat to see it working in all dimensions.
I'd just like to know more about how collisions were handled in The Witness. I've been puzzling through it on my own, trying to figure out how a similar system might work for a game I'm working on, but I can't help but feel I'm missing a few crucial things.
Here's what I've been able to piece together so far:
From Handmade Hero: Instead of resolving collisions with simplified physical simulation, the closest reachable point to some destination is found. The geometry is made to be "searchable" so that there is an upper bound to the amount of time this can take. In order to only find reachable points, some kind of flood-fill is performed, so there is always a path back to the origin point from the found point. This flood fill is restricted, possibly by the bounding box of the overall movement, to avoid tunneling and other acrobatics.
From this video: The walkable area is determined, somehow. Possibly by a related flood-fill algorithm. A grid is overlaid on the ground to visualize this. It's hard to tell whether the grid is a literal representation or just some way to texture the area. The walkable area changes as scenery, such as the boat, moves around. Traditional collision geometry is shown to be stored in at least the debug build of the game.
My initial thoughts were that as a preprocessing step, the entire ground manifold might have been covered with a large array of cells. Each of them would either be empty or hold a line segment representing the border between walkable and non-walkable areas. It would be easy to make that into a sparsely-stored system as well, and then the walkable area could simply be determined by allocating a chunk around the player and copying the relevant cells into it. Cells are also easy to flood-fill, making it simple to find reachable points.
There are some holes in this idea. The Witness has plenty of things that move, like the boat, and when things move the walkable area changes, which doesn't make much sense if all of the cells are stored statically, since they'd have to be regenerated. Also, in the video, collision geometry is shown to still be stored in the game, which wouldn't be necessary if the searchable cell-based geometry was already computed.
I also considered whether cells might be generated in real-time around the player as they walk. It seems a bit much, almost like doing collision-detection for lots of things instead of just one, but it's a possibility. Another possibility is that the "walk grid" was just a visualization and I am very off-track with all of this.
Could Casey or someone else share some insight as to this kind of collision response?
I'm interested specifically in how the system would perform with full 3D movement, since it seems like The Witness was restricted to working on a ground manifold, and it would be really neat to see it working in all dimensions.
The algorithm used in The Witness hasn't been documented yet, and it is the only one of its kind that I am aware of. It's on my list of things to write up, but I have no time to do so at the moment.
- Casey
- Casey