search

0XDE57 / SpaceProject

An arcadey physics-based top-down 2D, procedurally generated space exploration and shooter game using libGDX. Kinda like Asteroids, only a little bigger.
Apache License 2.0
38 stars 9 forks source link

Voronoi Destruction #11

Open 0XDE57 opened 1 year ago

0XDE57 commented 1 year ago

The technical vision is to have Asteroids break apart into smaller polygons based on a voronoi graph.

I have a prototype that feels very close to working but suffers from broken edge cases. I tried to derive the voronoi points by connecting the circumcenters of the delaunay points. Due to under estimation of complexity to implement, I have differed this for now.

Asteroid destruction is currently done using delaunay triangulation for simplicity. Delaunay is the dual-graph for Voronoi, and still retains the desired effect of:

  1. asteroids satisfyingly shatter into pieces that make up the original body
  2. shattered pieces maintain 1-to-1 surface area and mass of parent body
  3. asteroids and all shattered pieces are simple convex polygons (easy collision detection)

Stretch goal once working; would be to release the voronoi stuff as a separate library for libgdx for others to use.

0XDE57 commented 8 months ago

Alternative to fortunes algo, there is Qhull. I was surprised to find out that my attempt was the same as QHULL (the difference being that I never finished solving it...)

"Qhull computes the Voronoi diagram via the Delaunay triangulation. Each Voronoi vertex is the circumcenter of a facet of the Delaunay triangulation. Each Voronoi region corresponds to a vertex (i.e., input site) of the Delaunay triangulation. " http://www.qhull.org/html/qvoronoi.htm