Need help to compose a collider generation algorithm.

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

 

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

• Hertel-Mehlhorn Algorithm
• Polygon partitioning

 

Code (CSharp):

1. using System.Collections.Generic;
2. using UnityEngine;
3.  
4. public class CollisionAlgorithmTest : MonoBehaviour {
5.     public PolygonCollider2D col;
6.     public int chunkSize;
7.     public float tileScale = 1f;
8.  
9.     public bool[][] tiles;
10.     public int[][] tileIds;
11.  
12.     private void Start () {
13.         tiles = new bool[chunkSize][];
14.         tileIds = new int[chunkSize][];
15.  
16.         for(int x = 0; x < chunkSize; x++) {
17.             tiles[x] = new bool[chunkSize];
18.             tileIds[x] = new int[chunkSize];
19.         }
20.        
21.         CreateCollider();
22.     }
23.  
24.     void CreateCollider () {
25.         col.pathCount = 0;
26.  
27.         FillTilesArray();
28.         CalculateIds();
29.         GenerateMesh();
30.     }
31.  
32.     void FillTilesArray () {
33.         for(int x = 0; x < chunkSize; x++) {
34.             for(int y = 0; y < chunkSize; y++) {
35.                 tiles[x][y] = Mathf.PerlinNoise(x * 0.15f, y * 0.25f) > 0.5f;
36.             }
37.         }
38.     }
39.  
40.     void CalculateIds () {
41.         int length = 0;
42.         int streakStart = -1;
43.  
44.         for(int x = 0; x < chunkSize; x++) {
45.             for(int y = 0; y < chunkSize; y++) {
46.                 tileIds[x][y] = -1;
47.             }
48.         }
49.  
50.         for(int x = 0; x < chunkSize; x++) {
51.             for(int y = 0; y < chunkSize; y++) {
52.                 bool isCollision = IsCollisionAt(x, y);
53.  
54.                 if(isCollision && streakStart == -1) {
55.                     streakStart = y;
56.                     length = 1;
57.                 } else if(isCollision && streakStart != -1) {
58.                     length++;
59.                 } else if(!isCollision && streakStart != -1) {
60.                     ApplyIdToStrip(x, length, streakStart);
61.                     length = 0;
62.                     streakStart = -1;
63.                 }
64.             }
65.             if(streakStart != -1) {
66.                 ApplyIdToStrip(x, length, streakStart);
67.                 length = 0;
68.                 streakStart = -1;
69.             }
70.         }
71.     }
72.  
73.     void GenerateMesh () {
74.         for(int x = 0; x < chunkSize; x++) {
75.             for(int y = 0; y < chunkSize; y++) {
76.                 int id = tileIds[x][y];
77.  
78.                 if(id != -1) {
79.                     //Get width, calculate height
80.                     int h = IdToLength(id);
81.                     int p = IdToPosition(id);
82.                     int w = 1;
83.  
84.                     //Scan to see if there's not any strips with the same id.
85.                     if(x + 1 < chunkSize) {
86.                         for(int ix = x + 1; ix < chunkSize; ix++) {
87.                             w += (tileIds[ix][y] == id) ? 1 : 0;
88.                         }
89.                     }
90.  
91.                     CreateRectangle(x, p, w, h);
92.                 }
93.             }
94.         }
95.     }
96.  
97.     #region Collision Generation
98.     public void CreateRectangle (int x, int y, int w, int h) {
99.         for(int ix = x; ix < x + w; ix++) {
100.             for(int iy = y; iy < y + h; iy++) {
101.                 tileIds[ix][iy] = -1;
102.             }
103.         }
104.         col.pathCount++;
105.         col.SetPath(col.pathCount - 1, new Vector2[] {
106.             new Vector2(x, y) * tileScale,
107.             new Vector2(x + w, y) * tileScale,
108.             new Vector2(x + w, y + h) * tileScale,
109.             new Vector2(x, y + h) * tileScale
110.         });
111.     }
112.     #endregion
113.  
114.     #region Utils
115.     void ApplyIdToStrip (int x, int length, int position) {
116.         int id = LengthPosToId(length, position);
117.  
118.         for(int y = position; y < position + length; y++) {
119.             tileIds[x][y] = id;
120.         }
121.     }
122.  
123.     bool IsCollisionAt (int x, int y) {
124.         if(x < 0 || y < 0 || x >= chunkSize || y >= chunkSize) {
125.             return false;
126.         }
127.         return tiles[x][y];
128.     }
129.  
130.     int LengthPosToId (int length, int position) {
131.         return position * chunkSize + (length - 1);
132.     }
133.  
134.     int IdToLength (int id) {
135.         return (id - Nebulosa.WorldGen.NoiseUtils.FloorToInt(id / (float)chunkSize) * chunkSize) + 1;
136.     }
137.  
138.     int IdToPosition (int id) {
139.         return Nebulosa.WorldGen.NoiseUtils.FloorToInt(id / (float)chunkSize);
140.     }
141.     #endregion
142. }
143.  

 

Wow, thanks! Exactly what I needed!