0
$\begingroup$

I hope this is the correct subpage of SE, if not please direct me to the more appropriate place.

Imagine the following scenario:

You are put into a random but known position inside a given maze. The maze contains, in addition to walls (█) and pathways (.), the following things:

  • R - A refresh point which is single use but when used refreshes the amount of steps you can take.
  • S - A save point which is multi use and gives you a known position you can start from (instead of a random position) but does not refresh your steps while inside the maze. If used to re-enter it grants you a full set of steps. Only relevant if algorithm can account for multiple re-entries (see optional optimizations below).
  • T - A treasure chest, which gives you some form of reward (the reward itself is irrelevant for the pathing algorithm)
  • M - A monster which you will need to fight if you encounter it. It will drop some treasure if defeated, but any damage it does to you will need to be regenerated (so a time penalty) or, if it defeats you, you get kicked out of the maze and need to re-enter it (either randomly or through a previously passed save point).

Used / looted / defeated status of a tile preserve between runs.

You have a maximum of 30 steps you can take before you get kicked out of the maze from exhaustion, unless refreshed at a refresh point.

Mazes are always square, with a side length of 160 tiles.

Example part of a maze:

█ █ █ . █ █ █ █ █
. . . . █ . . M █
█ █ █ █ █ . █ . █
M . █ . . R █ . █
█ R █ . █ █ █ . █
█ M . . █ . █ . █
█ █ █ M █ S █ . █
█ . █ . T . . . █
█ . █ . █ █ █ R █

Example visualization of a full maze. Blue drops are refresh points, fires are save points, ghosts are monsters and gifts are treasures. Everything else is irrelevant

What is a good way, given the mentioned restrictions, to find the path, starting from your current position, that passes by the most treasures (and monsters) before you're kicked out of the maze of exhaustion?

What I tried

I tried creating a graph of nodes based on the refresh points as the nodes and the paths between them as the connections, giving a higher value to more points of interest between nodes. I then used a modified Dijkstra algorithm to find the path with the highest value.
Unfortunately, while it works somewhat, it doesn't take into account what treasures/monsters have already been visited, often leading to high density areas of the map being covered many times over, requiring human intervention for improvement of said path (which more often than not has caused user error and a miscount, leading to a failed run).

I'm thankful for any ideas and suggestions as to how to tackle this.

Optional optimizations / extensions:

  • allow backtracking where it makes sense
  • use save points strategically to come back to and cover more area, spanning multiple runs.
  • allow the use of different weights to prioritize/avoid treasures/monsters by user preference
  • there is a single boss inside this maze, which is the ultimate "goal" of it. Make the path end there, while still picking up as many treasures on the way as possible.
  • whatever else you can think of
$\endgroup$
5
  • $\begingroup$ Where did you encounter this? Can you credit the source where you saw it, or the motivation? $\endgroup$
    – D.W.
    May 20, 2023 at 20:55
  • $\begingroup$ Save points and re-entering seem irrelevant for the purposes of the question, since it appears the question is about a single path (from when you enter until you succeed or die) -- is that correct? Can you edit the question to clarify this, either clarifying why this is not correct, or removing the irrelevant details? $\endgroup$
    – D.W.
    May 20, 2023 at 20:57
  • $\begingroup$ @D.W. I'm playing a game where you can do one of these "maze runs" to gain valuable loot. However, the task of plotting a path by hand (with these limitations especially) is super tedious so I'm trying to automate this. And the detail of the save point is relevant for the "optional optimizations" part, as you can probably cover a lot more ground that you otherwise wouldn't reach if you utilize said save points. Either to use it as a "refresh point" with extra steps or to return to a fork in the path. $\endgroup$
    – Plagiatus
    May 21, 2023 at 7:34
  • $\begingroup$ I think you need to explain more precisely how you measure how good a path is. Does each treasure/defeated monster have a particular value (some number of points), and the total value of a path is the sum of those encountered/defeated along the way? The details will matter. $\endgroup$
    – D.W.
    May 21, 2023 at 21:12
  • $\begingroup$ Yes, precisely that. The best possible path (without optimizations) passes by as many treasures and monsters as possible. If to be able to achieve this I need to assign some form of value to these to find the path with the highest value, that's possible (and is what I'm using in the described dijkstra right now, too). $\endgroup$
    – Plagiatus
    May 22, 2023 at 6:09

1 Answer 1

1
$\begingroup$

Basic approach

I suggest you reduce this to a longest path problem in a directed graph. In particular, conceptually we imagine the entire state space, and build a graph with one vertex per possible state in the state space, with edges representing moves you can make in a single step.

More specifically, we have one vertex in the graph for each pair $\langle \ell,s\rangle$, corresponding to starting at location $\ell$ with $s$ steps remaining. Add edges $\langle \ell,s \rangle \to \langle \ell',s-1 \rangle$ if you can go from location $\ell$ to location $\ell'$ in a single step. The weight on this edge is the value incurred in taking that step (e.g., if you visited a treasure, add the value of that treasure; if you defeated a monster, add the value of that monster).

Now find the longest path in this graph. You can find a longest path by negating all edge weights, and then finding a shortest path using the Bellman-Ford algorithm.

I am assuming you can assign a value to any particular path (e.g., that each treasure has a value and defeating each monster has a value, and the total value is the sum of those values acquiring along the way, and you can collect a treasure multiple times).

Save points

When we have save points, we need to keep track of the most recent save point, so let's revise our approach. Create one vertex per triple $\langle \ell,s,p \rangle$, corresponding to starting at location $\ell$ with $s$ steps remaining, and where the most recent save point is $p$. Now we can create edges corresponding to the different ways we can take a single step from this location.

Then, find a longest path in this graph, as before.

Single-use locations

This assumes you can collect a treasure multiple times, defeat a monster multiple times, and use a refresh point multiple times. I suspect in practice you can't. To take this into account, the state needs to keep track of which treasures have already been collected and which monsters have already been defeated and which refresh points have already been used. Taking this into account, each vertex of the graph might correspond to a tuple $\langle \ell, s, p, T \rangle$, where $\ell,s,p$ are as before and $T$ denotes the set of treasures collected and monsters defeated and refresh points used.

This blows up the size of the state space by a factor that is exponential in the number of treasures/monsters/refreshes, so applying Bellman-Ford naively might become intractable. Instead, you could try using heuristics, like A* search or some other method.

$\endgroup$
5
  • $\begingroup$ we're looking at >13k paths with an average of 2 edges, each one of which able to be reached with multiple step amounts left, bringing my estimate to an easy 100k vertices. With backtracking this number absolutely explodes even more, possibly to the unsuitability of this approach. I will give it a try anyways and see how much calculation time is affected, thank you for your suggestion. $\endgroup$
    – Plagiatus
    May 22, 2023 at 6:10
  • $\begingroup$ @Plagiatus, I don't understand why the number of paths is relevant here. What matters is the number of tuples (e.g., number of locations, etc.). I didn't propose backtracking so I don't see how that is relevant. $\endgroup$
    – D.W.
    May 22, 2023 at 6:17
  • $\begingroup$ ah yeah, path is the wrong word, I meant locations. There are 13k locations in the maze (aka path, treasure, fountain, etc tiles), each of which has on average about 2 neighboring locations, so we'd end up with 26k edges. Add to that all the different ways you can reach and move from said locations (aka different s) and you can probably x5 that number, ending up with 100k+ tuples. Or am I misunderstanding how to construct the vertices & edges? $\endgroup$
    – Plagiatus
    May 22, 2023 at 6:40
  • $\begingroup$ Here is an image of what I'm trying to say: imgur.com/TtYwmu2. starting from the fountain, resetting the steps, depending on if you go clockwise or counterclockwise you end up with different tuples (just <l,s> for demonstration) and edges. Now imagine you can also change direction (because you might want to be able to include these) and you have a massive amount of vertices and edges. $\endgroup$
    – Plagiatus
    May 22, 2023 at 7:08
  • 1
    $\begingroup$ @Plagiatus, That makes sense. It might require some careful engineering to handle all of the cases you want to handle. I would suggest you try to implement first a version with no save points, as then the graph can be put into topological order, and then you can find shortest paths in linear time. $\endgroup$
    – D.W.
    May 22, 2023 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.