Constellation Puzzles Meet Graph Theory in New Euler Path Game

What if you could turn a beloved video game minigame into a standalone puzzle challenge? That’s exactly what one hobby developer accomplished by creating a browser-based puzzle game inspired by Dragon Age: Inquisition’s Astrarium minigame. The twist? The puzzles are now procedurally generated and rooted in graph theory—a move that ensures every challenge remains solvable while offering fresh layouts with each playthrough.

The game, called Starglyphs, challenges players to connect stars on a grid-shaped constellation by tracing paths without retracing or lifting their finger. While the core mechanic draws parallels to classic line-drawing puzzles, the underlying algorithm leverages Euler paths to guarantee solutions. Euler paths are sequences of edges in a graph that visit every edge exactly once, making them ideal for generating puzzles that are both engaging and fair.

From Inspiration to Implementation

The developer, a longtime fan of Dragon Age: Inquisition, spent hundreds of hours mastering the Astrarium minigame—a spatial puzzle where players connect stars based on constellation guides. Intrigued by the mechanics, they wondered if it was possible to automate the creation of such puzzles while ensuring they remained solvable. After researching graph theory concepts, they discovered Euler paths as the perfect foundation.

// Example of Euler path generation in Starglyphs
function generateConstellation(gridSize) {
  const graph = buildGraph(gridSize);
  const eulerPath = findEulerPath(graph);
  return renderConstellation(eulerPath);
}

The result is a visually vibrant puzzle game where players connect stars in sequences that mirror real astronomical constellations. Unlike static puzzles, Starglyphs generates new layouts dynamically, preventing repetition and keeping the experience fresh. The game’s colorful aesthetic and intuitive controls further enhance its appeal, making it accessible to both casual players and puzzle enthusiasts.

The Algorithm Behind the Stars

Euler paths aren’t just a theoretical curiosity—they’re a practical tool for puzzle design. In Starglyphs, the algorithm first constructs a graph where stars represent nodes and potential connections represent edges. The goal is to find a path that traverses every edge exactly once, a property that ensures every puzzle has a valid solution.

To achieve this, the developer implemented a backtracking algorithm with optimizations to handle larger grids efficiently. The process involves:

• Randomly generating a graph structure
• Checking for Eulerian trail conditions (exactly zero or two vertices with odd degree)
• If conditions are met, constructing the path
• If not, regenerating the graph until a solvable configuration is found

This method guarantees that players never encounter an unsolvable puzzle, a common frustration in puzzle games. The algorithm’s adaptability also allows for scaling difficulty by adjusting grid size or adding constraints like blocked connections.

What’s Next for Starglyphs?

While the game is currently available as a web-based experience, the developer has bigger plans. They’re actively working on a Steam release, which will introduce additional features such as leaderboards, cloud saves, and expanded puzzle packs. A mobile version is also in development, promising on-the-go puzzle-solving with touch-friendly controls.

The project highlights the creative potential of merging classic puzzle mechanics with modern algorithmic design. By grounding its core in Euler paths, Starglyphs transforms a familiar concept into something entirely new—proving that even well-trodden territory can yield fresh discoveries when viewed through a computational lens.

With procedural generation at its heart, the game invites players to explore an infinite sky of challenges, each one a unique constellation waiting to be uncovered.