I’m looking for a way to generate a random path based on midi note onsets (timing points) for a simulation/game.

I will briefly explain how it works for context:

I’m working on a simulation type game where a square bounces around a procedurally generated map based on a given .mid file from which it extracts the note onsets.

Right now the map is being generated as follows using backtracking (simplified example):

• Given a list of note onsets.
• Start with the square at its initial position and direction.
• For each note onset:
  • Move the square until the current time reaches the note onset.
  • Check for collisions with previously visited (bounced off of) checkpoints.
  • Occasionally change the square’s direction by random chance.
  • If a collision is detected or no valid path is found, backtrack:
    • Undo the last moves and try a different direction.
    • If necessary, reverse the direction of the square and try again.
  • If the square reaches the next note onset without collision, continue to the next onset.
• Repeat the above steps recursively, exploring different paths and backtracking when needed.
• Finally, process the path to remove overlaps and merge adjacent areas.

Important:

• The squares only possible directions are diagonally so north-east, south-east, south-west and north-west.
• The square moves at a constant speed.
• The checkpoints are basically just tiny rectangles (see screenshot and sketch).

As you might imagine this is not very fast and/or memory efficient.

I was wondering if there are any better ways of doing this (algorithm wise for example)?

I was personally thinking something using a grid, this would change how things work but I’m fine with that.

NOTE: A random look to the map is important, it cannot just go bouncing on to the right until the last note for example.

screenshot of the simulation/game

sketch of collision happening

I tried implementing other algorithms, but I’m not great at doing so.

I wanted a better solution than backtracking.

Broken code.