How do I store destructible terrain that characters can walk on?

Question

I'm trying to make a 2d game like Worms (in JS, if it's important). I found 2 possible ways of implementing destructible terrain:

1. Bitmap. Store every pixel in a huge 2-dimensional array
2. Represent the terrain as a f(x, y) function somehow and use the marching squares algorithm with linear interpolation.

But I still don't quite understand how should I calculate worms' movements. When a worm is standing on the ground and is walking in a certain direction, how do I calculate its next position?

I have an idea for how to do it with a bitmap, but I don't think its the best one:

1. Before the match find pixels where the worm can stand
2. When the worm starts walking find some nearby standable pixels with standablePixelsX = wormX + direction, where direction = -1 or +1 based on which direction the player is moving (left or right)
3. And check those selected standable pixels with an areConnected(pixel1, pixel2) function which determines whether a worm can move form pixel1 to pixel2 (checks for blocking ceilings and stuff)

Which way should I implement destructible terrain and whats the best way to calculate worms' movements?

Answer 1

Storage of destructible terrain

For the terrain I would recommend looking at the quadtree data structure. It provides an efficient way to store destructible terrain. For an excellent, in-depth explanation, see Coding Challenge #98.1: Quadtree - Part 1 by The Coding Train.

The core idea of a quadtree is that you don't need to store every individual pixel. When talking about terrain, you will usually have large chunks of neighbouring pixels that have the same value (solid or non-solid). A quadtree takes advantage of this by storing your maps as rectangular chunks. If a chunk is broken (e.g. an explosion destroys terrain causing part of the chunk to be solid and part of the chunk non-solid) it is subdivided into smaller rectangular areas until the granularity is fine enough to have uniform solidity within all rectangles.

Here is an image from a similar Stack Exchange question to illustrate the datastructure:

Movement along arbitrary terrain

You could break movement down into one pixel steps (to the left or the right) and examine three scenario's with each step:

player can move 1 pixel to side and one pixel down
    -> player is moving downhill

player can move 1 pixel to side
    -> player is moving horizontally

player can move 1 pixel to side and up
    -> player is moving uphill

You can simply evaluate the above cases and perform the first possible movement. If none of the three movements are possible, the player is moving into a slope steeper than 45 degrees which is considered a wall.

If you want to move more than 1 pixel per frame, you simply repeat the above procedure multiple times a frame. I.e. instead of

int player_speed = 4;
check_if_can_move(player.x + player_speed) { player.x += player_speed; }

you do:

int player_speed = 4;
for(int i = 0; i < player_speed; i++) {
    check_if_can_move(player.x + 1) { player.x += 1; } else { break; }
}

This is certainly not the most efficient kind of movement, however it perfectly complements a quadtree with detail up to one pixel. Movement is pixel-perfect. For a simple 2D game like Worms this strategy works fine.