Need help to compose a collider generation algorithm.

Unity Engine
1

Hey there,

I’m working on a procedural 2d sandbox game. We decided to make our tile system. The visual mesh generation works well, but we having some issues with generating a proper collider for our chunks. I decided to try and find a new algorithm to generate the collider since I wasn’t able to find a good solution online.

My goal:

  • Our game would need to have a polygon-based collision. We already tried edge collision and we felt objects were more prone to clipping trough the terrain.
  • The algorithm shouldn’t take long to generate the collision obviously
  • The algorithm should give out an optimized mesh, group tiles together.
  • I found out an image of what our goal would look like

I need help to find what we should do to create a somewhat similar or better collision algorithm.
All clues that might help us is appreciated,
Thanks

2

I found out some keywords that could help me but I don’t get much result with them:

3 
using System.Collections.Generic;
using UnityEngine;

public class CollisionAlgorithmTest : MonoBehaviour {
    public PolygonCollider2D col;
    public int chunkSize;
    public float tileScale = 1f;

    public bool[][] tiles;
    public int[][] tileIds;

    private void Start () {
        tiles = new bool[chunkSize][];
        tileIds = new int[chunkSize][];

        for(int x = 0; x < chunkSize; x++) {
            tiles[x] = new bool[chunkSize];
            tileIds[x] = new int[chunkSize];
        }
       
        CreateCollider();
    }

    void CreateCollider () {
        col.pathCount = 0;

        FillTilesArray();
        CalculateIds();
        GenerateMesh();
    }

    void FillTilesArray () {
        for(int x = 0; x < chunkSize; x++) {
            for(int y = 0; y < chunkSize; y++) {
                tiles[x][y] = Mathf.PerlinNoise(x * 0.15f, y * 0.25f) > 0.5f;
            }
        }
    }

    void CalculateIds () {
        int length = 0;
        int streakStart = -1;

        for(int x = 0; x < chunkSize; x++) {
            for(int y = 0; y < chunkSize; y++) {
                tileIds[x][y] = -1;
            }
        }

        for(int x = 0; x < chunkSize; x++) {
            for(int y = 0; y < chunkSize; y++) {
                bool isCollision = IsCollisionAt(x, y);

                if(isCollision && streakStart == -1) {
                    streakStart = y;
                    length = 1;
                } else if(isCollision && streakStart != -1) {
                    length++;
                } else if(!isCollision && streakStart != -1) {
                    ApplyIdToStrip(x, length, streakStart);
                    length = 0;
                    streakStart = -1;
                }
            }
            if(streakStart != -1) {
                ApplyIdToStrip(x, length, streakStart);
                length = 0;
                streakStart = -1;
            }
        }
    }

    void GenerateMesh () {
        for(int x = 0; x < chunkSize; x++) {
            for(int y = 0; y < chunkSize; y++) {
                int id = tileIds[x][y];

                if(id != -1) {
                    //Get width, calculate height
                    int h = IdToLength(id);
                    int p = IdToPosition(id);
                    int w = 1;

                    //Scan to see if there's not any strips with the same id.
                    if(x + 1 < chunkSize) {
                        for(int ix = x + 1; ix < chunkSize; ix++) {
                            w += (tileIds[ix][y] == id) ? 1 : 0;
                        }
                    }

                    CreateRectangle(x, p, w, h);
                }
            }
        }
    }

    #region Collision Generation
    public void CreateRectangle (int x, int y, int w, int h) {
        for(int ix = x; ix < x + w; ix++) {
            for(int iy = y; iy < y + h; iy++) {
                tileIds[ix][iy] = -1;
            }
        }
        col.pathCount++;
        col.SetPath(col.pathCount - 1, new Vector2[] {
            new Vector2(x, y) * tileScale,
            new Vector2(x + w, y) * tileScale,
            new Vector2(x + w, y + h) * tileScale,
            new Vector2(x, y + h) * tileScale
        });
    }
    #endregion

    #region Utils
    void ApplyIdToStrip (int x, int length, int position) {
        int id = LengthPosToId(length, position);

        for(int y = position; y < position + length; y++) {
            tileIds[x][y] = id;
        }
    }

    bool IsCollisionAt (int x, int y) {
        if(x < 0 || y < 0 || x >= chunkSize || y >= chunkSize) {
            return false;
        }
        return tiles[x][y];
    }

    int LengthPosToId (int length, int position) {
        return position * chunkSize + (length - 1);
    }

    int IdToLength (int id) {
        return (id - Nebulosa.WorldGen.NoiseUtils.FloorToInt(id / (float)chunkSize) * chunkSize) + 1;
    }

    int IdToPosition (int id) {
        return Nebulosa.WorldGen.NoiseUtils.FloorToInt(id / (float)chunkSize);
    }
    #endregion
}
4

Wow, thanks! Exactly what I needed!