Procedural Levels Generation — Puzzle Game

Interlude

Part 1. Unity and C#. First try and disappointment

  1. Randomly generate the game board
  2. Gather all interconnections of nodes
  3. Multiply those combinations with each other to get all possible combinations
  4. Loop through those combinations to find out only the winning ones
  5. If there are too many (imperative measurement) of winning combinations — drop the level
  6. Run till all the levels are generated
  • Board size ranges from 4x4 to 7x7
  • Maximum count of unoccupied cells per level = 0.75 * board_size ^2
  • Minimum count of unoccupied cells per level = 0.625 * board_size ^2
  • Node can have 1 to 4 outgoing connections depending on its position
  • Each cell has an index
My notebook
  • If a node position is corner — its count can be 1 or 2 depending on a neighbor nodes
  • If a node position is side — its count can be 1 to 3 depending on a neighbor nodes
  • If a node position is inner — its count can be 1 to 4 depending on a neighbor nodes

Part 2. Java. New hopes… and disappointment again

  • Own implementation of Cartesian product has been replaced with Lists.cartesianProduct from Guava library. It works significantly faster.
  • Multithreading with Callable
  • System.gc() call
  • Optimization of collections usage
private Set<List<Connection>> ProcessResults() {
BigInteger expectedCombinations = BigInteger.ONE;
for (List<Connection> value : connectionsMapping.values()) {
expectedCombinations = expectedCombinations.multiply(BigInteger.valueOf(value.size()));
}
System.out.println("expected combinations count " + expectedCombinations);
if (expectedCombinations.compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) > 0) {
return new HashSet<>();
}
...
}

Part 3. Algorithms, way to success

  • Every next node has to have a valid adjusted node. For example, if a given node is to be located on a corner position it should not have two other nodes next to it, otherwise it is unreachable. That part was described already previously.
  • Path size from one node to another cannot be longer than the length of one corner to the opposite one. Unless it is the last node, then it will be the size of remaining unoccupied cells.
  • Every next node should have a connection with the existing one. The same code for the DFT algorithm is reused to find a matching connection. All occupied cells are excluded from the data set.
  • Once the board is filled, count for each node is calculated as the amount of incoming connections.
  • Generated level is checked for uniqueness

Summary

Support

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store