Bread-first search

[stefnotch]

The fact that this solver is calling a random number generator makes me think that it simply tries out stuff until something works. Is that assessment correct?

An even more overblown well engineered approach would be to try out all possibilities in a breadth-first manner. In fact, I did write something like this. And since nobody said anything about being reasonable, I wrote it in Haskell.

Pro: It's super short and works beautifully

Con: It's in Haskell. Not sure if that's better or worse than Java.

type Cube = Int
type Step = Int
type PossibleRotation = [Int] -- As long as the cube array
data State = S [Step] [Cube]

solvePuzzle :: [State] -> [PossibleRotation] -> [Step]
solvePuzzle states possibleRotations
  | null solutions = solvePuzzle (concatMap (\s -> zipWith (applyRotation s) possibleRotations [0..]) states) possibleRotations
  | otherwise = getSteps (head solutions)
  where solutions = filter (\(S _ cubes) -> all (==0) cubes) states

getSteps :: State -> [Step]
getSteps (S steps _) = steps

applyRotation :: State -> PossibleRotation -> Int -> State
applyRotation (S steps cubes) rotation rotationId = S (steps++[rotationId]) (zipWith (\cube rot -> (cube + rot) `mod` 4) cubes rotation)

-- solvePuzzle [(S [] [0,2,0,0])] [[1,1,0,1],[1,1,1,0],[0,1,1,1],[1,0,1,1]]
-- solvePuzzle [(S [] [0,2,0,0])] [[1,1,0,1],[1,1,1,0],[0,1,1,1],[1,0,1,1]]

Feel free to use the code. Though, if one wants to make something actually usable, I'd recommend writing it in Typescript and having a proper, static website. I'd totally be willing to help if you're interested.

[mgatelabs]

Yes, I did it dirty and used the random number gen instead of "the smart way". Now I just need to figure out how to read this.

I would just think, use the recursion strategy and have it hit every node with a known max depth.

And the whole "Good" direction thing is not needed for most, except for puzzles that have a fixed direction.

[mgatelabs]

I've played and refactored a bunch. Fewer setup calls and it finds the best solution.

9670 Solutions found after 2294145 attempts
--Best Solution Found--
Initial Cube State
[N|N|N|E|W]
Hits
Hit #1 - Cube Index [2] - Triggers [0,4]
[E|N|E|E|N]
Hit #2 - Cube Index [2] - Triggers [0,4]
[S|N|S|E|E]
Hit #3 - Cube Index [1] - Triggers [0,2]
[W|E|W|E|E]
Hit #4 - Cube Index [0] - Triggers [2]
[N|E|N|E|E]
Hit #5 - Cube Index [0] - Triggers [2]
[E|E|E|E|E]

Color Key
Unmodified Cube
Cube to Touch
Modified Because of Touch

[mgatelabs]

I did some work, think it is better now, and it doesn't check everything

Sample

[stefnotch]

Yes, I did it dirty and used the random number gen instead of "the smart way". Now I just need to figure out how to read this.

I can rewrite it in mostly any language you like. And actually add comments. Here it is in Javascript.

/**
 * A possibility that we'll explore in the breadth-first search
 */
class State {
  /**
   * Which cubes did we touch to get to this state?
   */
  steps = [];
  /**
   * How are the cubes arranged? I'm using numbers (0,1,2,3)
   */
  cubes = [];

  constructor(steps, cubes) {
    this.steps = steps;
    this.cubes = cubes;
  }
}

/**
 * Applies a rotation to some cubes. A rotation just describes which cubes get rotated.
 * It then returns a new array of cubes.
 */
function applyRotation(rotation, cubes) {
  if (rotation.length != cubes.length)
    throw new Error("There has to be one rotation for every cube.");
  let newCubes = cubes.slice(); // Copy the array
  for (let i = 0; i < rotation.length; i++) {
    newCubes[i] = mod(cubes[i] + rotation[i], 4);
  }
  return newCubes;
}

function applyAllRotations(possibleRotations, state) {
  // We take every single rotation, and create a new state
  return possibleRotations.map(
    (rotation, i) =>
      new State(state.steps.concat(i), applyRotation(rotation, state.cubes))
  );
}

/**
 * states: We explore all possibilities at the same time. Could be improved by only visiting actually new states.
 * possibleRotations: If we touch cube n, which cubes get rotated
 */
function solvePuzzle(states, possibleRotations) {
  // Solutions are those possibilities where every cube is 0 (facing in the desired direction, could be made better)
  let solutions = states.filter((state) => state.cubes.every((cube) => cube == 0));

  if (solutions.length == 0) {
    // Keep searching
    const newStates = states
      .map((state) => applyAllRotations(possibleRotations, state))
      .flat();
    return solvePuzzle(newStates, possibleRotations);
  } else {
    // Yay, we found a solution
    return solutions[0].steps;
  }
}

function mod(a, b) {
  // Most languages don't implement a proper modulo that handles negative numbers
  // Instead they implement a division-remainder. Ew.
  return ((a % b) + b) % b;
}

solvePuzzle(
  // We haven't done anything yet
  // And the cube at index 1 has been rotated 2 times
  [new State([], [0, 2, 0, 0])],

  // And if we hit the cube at index N, it will get rotated accordingly
  [
    [1, 1, 0, 1],
    [1, 1, 1, 0],
    [0, 1, 1, 1],
    [1, 0, 1, 1],
  ],
);

And the whole "Good" direction thing is not needed for most, except for puzzles that have a fixed direction.

I think the easiest way is to have a function that checks if a solution is valid. That way, you could easily switch out which variant to use at runtime.

9670 Solutions found after 2294145 attempts

Yeah, the max depth variant works. But doing it breadth-first, where you first check all solutions with a max depth of 0, then with a max depth of 1, then with a max depth of 2, and so on is neater. It guarantees that the first solution you find is also the best one.

I did some work, think it is better now, and it doesn't check everything

Sample

Very nice indeed!

[stefnotch]

Oh lol, I also have a super simplistic one that assumes cubes will only ever rotate in one direction

[mgatelabs]

I keep thinking, need to add drag and drop somewhere, or pre-program all the puzzle configurations, but if you just showed up to the puzzle, the pieces are in a fixed direction, here is the answer.

[mgatelabs]

Oh lol, I also have a super simplistic one that assumes cubes will only ever rotate in one direction

This puzzle is why I wrote it.

[stefnotch]

I think the easiest option is to code in every puzzle in the game. Writing something that lets you configure a puzzle seems like it'd be more trouble than it's worth. The only part that should be configure-able is the initial state of the puzzle, since I bet people are going to go to a puzzle, attempt it themselves, give up and look at the tool.

Which makes me wonder: Is there a list of all such puzzles somewhere?

[mgatelabs]

On the official map it has every cube puzzle listed. But I already solved them, so I can't play with them again to get the X triggers Y logic and initial diection.

[mgatelabs]

But I could easily change up the code and have it start at a lower max depth, and then on failure, increase it until it works / max.

[stefnotch]

I suppose there are a few reasonable options for getting puzzles:

• Creating a new Genshin account and speedrunning to Inazuma
• Crowdsourcing it. As long as we have one puzzle and a nice UI, it should make for a decent Reddit post. (Karma go brrr.) Or we could ask on a Genshin Discord server.
• Or we could join random people and solve their puzzles
• Or looking up videos of some of the puzzles might also work

Also, how do you feel about turning this into a website? As in, boring old JavaScript, HTML, CSS, a bunch of images and hosting it on Github Pages. Costs nothing, is easy to make, and saves people the trouble of downloading something. Of course, if you want to try out anything something different, I'm up for it. (Like Rust compiled to WebAssembly?)

[mgatelabs]

It would not be that hard to make simple js page version, since it would just be all client side. Use a worker. I thought about making a simple site, but I forgot about github pages, then it could have a crude map of all the puzzles to click to see the root solution and if you messed with it, enter the current facing.

I still have one of my kids accounts that hasn't don't anything yet in inazuma.

[stefnotch]

It would not be that hard to make simple js page version, since it would just be all client side. Use a worker. I thought about making a simple site, but I forgot about github pages, then it could have a crude map of all the puzzles to click to see the root solution and if you messed with it, enter the current facing.

Yep, fully agreed. It's always nice when a web-development project boils down to client side Javascript. No complicated servers involved, haha. And yes, the crude map is definitely a good idea.

I still have one of my kids accounts that hasn't don't anything yet in inazuma.

Sweet! Then that beautifully solves that.

[mgatelabs]

Just need to worry about copyrights, Jenshin Impact is always pretty memeable.

[stefnotch]

Bwahaha yes indeed. I also propose drawing the Inazuma map instead of using the official, probably copyrighted one. Bonus points for drawing it with Microsoft Paint.

[stefnotch]

On the topic of Jenshin Impact, this is what my better Genshin desktop icon looks like.

[mgatelabs]

Bwahaha yes indeed. I also propose drawing the Inazuma map instead of using the official, probably copyrighted one. Bonus points for drawing it with Microsoft Paint.

This is a task I need to give to my oldest kid, they "think they can draw". And they will add in random sea monsters.

[mgatelabs]

Soooooo, think I found how to make a zoomable map that can use a custom image.

https://leafletjs.com/examples/crs-simple/crs-simple.html

[mgatelabs]

Did some cursory research, seems like I could do a angular project, have it build into /docs and it will present. Don't need to go overboard, two views (world map), and puzzle. So there could be links to specific puzzles. I've been stuck in monolithic java 8 world for a while, so new techs are not common for me.

And then all I need is a JSON file with all the puzzles listed with default solution, configurations and connections.

And the puzzle page needs to show:

• Picture from the game
• Pieces laid out (there are only a few different configurations, in a line, box,...)
• Pieces are clickable and rotate / switch lights
• Solve button
• Reset button
• Show a default pre-calculated solution

[stefnotch]

Soooooo, think I found how to make a zoomable map that can use a custom image.

https://leafletjs.com/examples/crs-simple/crs-simple.html

That looks pretty nice!

Did some cursory research, seems like I could do a angular project, have it build into /docs and it will present. Don't need to go overboard, two views (world map), and puzzle. So there could be links to specific puzzles. I've been stuck in monolithic java 8 world for a while, so new techs are not common for me.

And then all I need is a JSON file with all the puzzles listed with default solution, configurations and connections.

And the puzzle page needs to show:

* Picture from the game

* Pieces laid out (there are only a few different configurations, in a line, box,...)

* Pieces are clickable and rotate / switch lights

* Solve button

* Reset button

* Show a default pre-calculated solution

Yeah, Angular or Vue.js is the way to go. Angular is a bit more opinionated and enterprise-y, while Vue.js is a bit more flexible. Both have their upsides and downsides. Like being opinionated is very convenient if you work in a larger team. Vue.js is convenient if you don't want to read through quite as much documentation.

[mgatelabs]

I need to eventually convert the 20 year old monolith to Angular, so seems like it will be Angular. Should have a demo site that does nothing soon.

[stefnotch]

I need to eventually convert the 20 year old monolith to Angular, so seems like it will be Angular. Should have a demo site that does nothing soon.

Then Angular it is! Always nice when a fun project has the side-effect of "learning something useful". I'll look forward to the demo site!

While I'm at it, should I do all my contributions through Github pull requests or would you prefer giving me access to the repository? Either option is equally fine with me.

[mgatelabs]

Ok, the demo should appear here https://mgatelabs.github.io/GenshinSolvers/ It should take a few minutes for it to switch.

The webpage branch is Pages

Pull requests would be the best, I should setup a pages-dev branch for me to work under and pull them in also.

[mgatelabs]

Seems like the demo has an issue, it is trying to pull from the root folder. Found an answer

[stefnotch]

Yeah, base url stuff. By the way, there is a slightly more elegant way of doing the Github pages stuff that doesn't require you to mix auto-generated files with the other files.

Basically

1. Move the stuff from https://github.com/mgatelabs/GenshinSolvers/tree/Pages to the main branch
2. Add the docs or whatever folder to the .gitignore
3. npm install gh-pages
4. Build an Angular project
5. And then use the gh-pages to automatically take everything from the docs folder and force-push it to the gh-pages branch. I got a script for it here
6. Tell Github to use the gh-pages branch

Do you want to try doing that or should I make a pull request with it?

[mgatelabs]

Yes, please, lets give this a go. The demo is now working.

[mgatelabs]

Ok, had to undo and re-do the changes, but it is now doing the magic.

But the Pages branch should be for the Website. The original java app should stay in the master branch.

[stefnotch]

Sounds reasonable :) The easiest way of redoing the changes is to checkout the master branch before the revert. Then select everything except for the .git folder and copy it somewhere else. Then checkout the Pages branch. And replace everything there with what you copied previously. It guarantees zero merge errors, because you're just brutally replacing everything XD

[mgatelabs]

Ok, time to get serious, need to make a development branch where my changes will go, and then start merging them instead of just pushing to Pages.

And probably need to start making issues about the missing things

[stefnotch]

Ok, time to get serious, need to make a development branch where my changes will go, and then start merging them instead of just pushing to Pages.

And probably need to start making issues about the missing things

Awesome! From the quality of life tweaks, could you please add in the "format on save" stuff? And you'll definitely want to add the .nojekyll file, otherwise Github pages occasionally acts up. https://github.com/mgatelabs/GenshinSolvers/pull/6/commits/6c4f39419799f66287d5fadea990059cf72024d7

[mgatelabs]

Ok, copied over

[stefnotch]

Nice, thank you :) As soon as you got issues for the various features in place, feel free to assign me to some. Or I'll simply comment on the ones that I'd like to take care of.

[mgatelabs]

I just noticed, "bread" first search.

[stefnotch]

Nice, spotted the pun. Yes indeed, searching for a nice loaf, preferably a cat loaf should be the first thing any good algorithm does. 😋

[mgatelabs]

The demo has been updated to the latest dev build https://mgatelabs.github.io/GenshinSolvers/

• It has the Inazuma map
• It has teleport, puzzle and seven icons

It does nothing yet

[mgatelabs]

So now, is the hard part, research, need to visit a few of the puzzles, take a screen shot with the camera, remove the character. Save the initial orientations, see what each hit does.

Then need to start building out the puzzle json, the 2nd screen for the puzzle info and solver.

[stefnotch]

I think it might be easier to build a simplistic 2D (isometric?) view of most puzzles. Maybe recreating some in 3D with a library like Three.js could be practical as well.

As for removing the character, the game has a "photo mode" where you can disable the UI and character. Makes for some pretty nice screenshots.

[stefnotch]

As for collecting data, I think the safest option is to record it all. Fire up OBS, start recording and take notes of what each hit does. That way, if you mess up, you still have a screen recording to fall back to.

And about the "getting to the puzzles part", I'd be up anytime to play Genshin.

[mgatelabs]

I'm going to play on my kids account from my mobile, so camera shots would work best.

Still thinking of the presentation. Could place the cubes to click over the image, so you would see a more 1 to 1.

[stefnotch]

Regarding the presentation, one thing that would be useful would be "which direction is the player looking in". As in, the direction the arrow is pointing in on the minimap.

[mgatelabs]

True, which way you are facing is important. All the small details. But if possible we need to face true direction, so all the NESW makes sense. And some of the images may need to be edited, i'm thinking of a few puzzles where some of the cubes are a bit away.

I was thinking about threejs, i've used it in the past. It gets tricky, but could make a 3d model with an arrow facing and place it over the image, it just gets tricky to determine the orientation and position, so it scales well.

And the same for the light up puzzles, just add the right faces and it would work the same, rotate it.

Idea reference https://medium.com/geekculture/hello-cube-your-first-three-js-scene-in-angular-176c44b9c6c0 https://stackoverflow.com/questions/17638933/three-js-clickable-objects https://threejs.org/docs/#api/en/textures/CubeTexture

Installed three into the dev branch, so it is somewhat ready.

But i'm foreseeing dev tools need to be baked in to generate the json without going crazy over 3d stuff.

But we will need the in-game image, the # of cubes, the x,y,z placement of them in the 3d space. Complicated, but makes it easier. Think we could even replay the steps and show hit this one.

Just fixed the 404 issue, so pathing can work. And added a link to GitHub for the source.

And at some point need to add in the translation stuff, but don't even have a solver yet, so it can wait. I don't think this is going to be very "wordy" app.

[mgatelabs]

So thinking, Bootstrap to handle mobile / desktop? Grids, fancy fields.

[stefnotch]

Nice progress!

True, which way you are facing is important. All the small details. But if possible we need to face true direction, so all the NESW makes sense. And some of the images may need to be edited, i'm thinking of a few puzzles where some of the cubes are a bit away.

Yeah, true. There is at least one puzzle where the pieces are separated by an ocean.

I was thinking about threejs, i've used it in the past. It gets tricky, but could make a 3d model with an arrow facing and place it over the image, it just gets tricky to determine the orientation and position, so it scales well.

I was more thinking of recreating the cubes using Three.js. Not sure how practical that would be. One alternative, along those lines, would be using isometric pixel art. Like this

And at some point need to add in the translation stuff, but don't even have a solver yet, so it can wait. I don't think this is going to be very "wordy" app.

Yes, you're definitely right about that. Depending on how things go, we might be able to get away with practically zero text.

So thinking, Bootstrap to handle mobile / desktop? Grids, fancy fields.

Sure, Bootstrap is a solid choice. Probably an overkill for this, but why not.

[mgatelabs]

I like the iso metric art style, kind of feels like minecraft, but I fear there may be a disconnect between the iso view and the real world. Unless we specifically take the images in a certain way. I've written a game in three js before, I can make it do things.

[stefnotch]

I like the iso metric art style, kind of feels like minecraft, but I fear there may be a disconnect between the iso view and the real world. Unless we specifically take the images in a certain way. I've written a game in three js before, I can make it do things.

True, it might make the tool not quite as easy to use as it could be. If we're going with the 3D Three.js approach, I wonder if stitching some Genshin screenshots together to make an environment map would work. Or if that would be too tricky to be worthwhile.

[mgatelabs]

I think fixed 3D, like the old Grim Fandango, place the 3d cubes on top of the image. So the player just needs to stand in a similar spot and shoot arrows at the cubes in the order we present. Otherwise we would need to break out the Nvidia image tech where it makes 360 images in games, but I don't think GI does that. Now we could add in multiple images and allow switching for some of the less simple ones, just adjust the "world" position so it all makes sense.

Guess we could add in an alternative view where it puts a compass under the floor so you could rotate around a white space with the cubes.

But we need an iterative approach, lets get 1 puzzle to work first so we can run later.

[stefnotch]

I agree, this sounds like the best option so far. Let's go with that then.

[stefnotch]

One quick question regarding puzzles: Do they really only ever rotate in one direction/increment the glowing leaves by 1? If yes, then we can use the super simplistic code from https://github.com/mgatelabs/GenshinSolvers/issues/1#issuecomment-1048511959

[mgatelabs]

I'm pretty sure they all turn the same way, and they all move by 1 state, but until it has been evaluated, not 100% sure.

Now for the solved result, I really just need an array of indexes to click. Like [0,1,0,2]. Then on the screen it would be easy to start with the "initial" layout and manually track the states and generate move 1 was (0,0,2,1), move 2 was (1,1,3,0) and highlight the cube that was touched.

And light up puzzles are the same, just need to convert from N to 0 Light, E to 1 Light. I had a bug in my java version, but they both worked the same so it didn't matter.

[stefnotch]

Here is an untested solver, it works just like the simplistic one. The main differences are that it's properly typed, doesn't do useless work and has comments.

Also, I might as well note that this uses numbers and not enums. Typescript enums are a mixed bag. They work for simple stuff, but break down once you start doing more complicated things with them. The Typescript developers themselves also have decided that adding enums was not in line with the Typescript philosophy, hence they don't receive as much attention.

Please do let me know when and where I should integrate it ;)

type PuzzleState = readonly number[];

type Puzzle = {
  /**
   * We represent the state with simple numbers
   */
  initialState: PuzzleState;

  /**
   * What state do we want to reach?
   */
  finalState: PuzzleState;

  /**
   * What's the maximum state (exclusive), before wrapping around.
   * 4 in the case of a rotating cube puzzle.
   */
  maximumNumber: number;

  /**
   * A state transition basically says "if we hit cube X then Y will be affected"
   */
  stateTransitions: number[][];
};

type PuzzleSolveStep = {
  previousStep: PuzzleSolveStep | null;
  touchedCube: number | null;
  state: PuzzleState;
};

/**
 * @param puzzle The puzzle to be solved
 * @returns A solution if one was found, otherwise null
 */
function solvePuzzle(puzzle: Puzzle) {
  // To prevent doing work more often than we have to
  const solvedStates = new Set<string>();

  // Which puzzle states can we reach and have not solved yet.
  const workQueue: PuzzleSolveStep[] = [
    {
      previousStep: null,
      touchedCube: null,
      state: puzzle.initialState.slice(),
    },
  ];

  while (true) {
    // Take from the beginning of the queue
    let unsolved = workQueue.shift();
    if (unsolved === undefined) break;

    // Now apply every possible state transition
    for (let i = 0; i < puzzle.stateTransitions.length; i++) {
      const newState = unsolved.state.slice();

      // Apply the state transition
      puzzle.stateTransitions[i].forEach((affectedCube) => {
        newState[affectedCube] = mod(newState[affectedCube] + 1, puzzle.maximumNumber);
      });

      const newWork: PuzzleSolveStep = {
        previousStep: unsolved,
        touchedCube: i,
        state: newState,
      };

      // Check if it's a solution
      const isFinalState = newState.every((v, i) => puzzle.finalState[i] == v);
      if (isFinalState) {
        return newWork;
      }

      // Otherwise insert the new state as "work to do"
      if (!solvedStates.has(stateToString(newState))) {
        solvedStates.add(stateToString(newState));
        workQueue.push(newWork);
      }
    }
  }

  return null;
}

function stateToString(state: PuzzleState) {
  return state.map((v) => v + "").join(",");
}

/**
 * Proper modulo, always returns a positive number
 */
function mod(a: number, b: number) {
  return ((a % b) + b) % b;
}

Example call

solvePuzzle({
  initialState: [0, 2, 0, 0],
  finalState: [0, 0, 0, 0],
  maximumNumber: 4,
  stateTransitions: [
    [0,1,3],
    [0,1,2],
    [1,2,3],
    [0,2,3],
  ]
});