Lailloken / Lailloken-UI

Path of Exile UI and QoL overlay. Emphasizes ease of use, minimalist design, and seamless integration.
MIT License
594 stars 28 forks source link

Sanctum room planner #438

Closed ValdemarGr closed 2 months ago

ValdemarGr commented 3 months ago

It would be nice if the tool could show the room reachability for any room. It takes a half minute or so to plan out the optimal path when having All Seeing Eye.

For every next room, a room reachability tree could be drawn with distinct colors. I suppose on hover could also be a implemented, but from my observations it seems that the hover effect ingame might overlay some of the sanctum map in a way that makes image analysis hard.

Furthermore, counting the number of unknown rooms for a given reachability tree would also be a very nice feature.

Lailloken commented 3 months ago

Thanks for your suggestion. This was also suggested during Sanctum League itself. Back then, I wasn't really confident that I could get it working consistently, but I guess I could look into it and actually play around with it this time. But that'll have to wait until dust settles a bit: I'm still waiting for concrete recombination information to update my simulator, and I want to play more of the league of course.

Lailloken commented 3 months ago

I'm in between builds right now and can't get the Sanctum thing out of my head, so I started playing around with the idea.

detecting rooms detecting connections
image image

As a second step, I need to figure out how to abstract that into actual pathing/connections.


I don't really interact with sanctums, so I have a few questions on the basics (just to make sure I got them right):

ValdemarGr commented 3 months ago

I did a bit of playing around and ended with this algorithm, which only uses the paths:

image

I use DBSCAN to cluster the pixels for the paths and intersections of regressions over the path.

The trick is to dilate the paths such that I can de-noise since only highly connected clusters can be paths.

The least squares term in the regression ensures that it should follow the trend of the path very well.

This collection of constants is what I am using currently: image

I end up with this as the output: image

8 rooms and 3 on non-start floor.

Lailloken commented 3 months ago

That looks crazy, nice job. I was going to try something different:

Lailloken commented 3 months ago

I actually got it to work. It spits out a JSON-string, representing columns and the contained rooms. For each room, it lists x and y-coordinates for the overlay I'm going to implement, as well as entrances and exits (all this might change depending on how well the overlay works and whether I need anything else).

I changed my plan and took inspiration from slime molds (of all things):

show JSON-string ``` [ [ { "connections": { "enter": {}, "exit": { "2_1": "1", "2_2": "1" } }, "x": "0", "y": "208" }, { "connections": { "enter": {}, "exit": { "2_2": "1", "2_3": "1" } }, "x": "0", "y": "344" }, { "connections": { "enter": {}, "exit": { "2_3": "1" } }, "x": "0", "y": "480" } ], [ { "connections": { "enter": { "1_1": "1" }, "exit": { "3_1": "1", "3_2": "1" } }, "x": "152", "y": "208" }, { "connections": { "enter": { "1_1": "1", "1_2": "1" }, "exit": { "3_2": "1", "3_3": "1" } }, "x": "152", "y": "344" }, { "connections": { "enter": { "1_2": "1", "1_3": "1" }, "exit": { "3_3": "1", "3_4": "1", "3_5": "1" } }, "x": "152", "y": "480" } ], [ { "connections": { "enter": { "2_1": "1" }, "exit": { "4_1": "1", "4_2": "1" } }, "x": "312", "y": "72" }, { "connections": { "enter": { "2_1": "1", "2_2": "1" }, "exit": { "4_2": "1" } }, "x": "312", "y": "208" }, { "connections": { "enter": { "2_2": "1", "2_3": "1" }, "exit": { "4_2": "1" } }, "x": "312", "y": "344" }, { "connections": { "enter": { "2_3": "1" }, "exit": { "4_2": "1" } }, "x": "312", "y": "480" }, { "connections": { "enter": { "2_3": "1" }, "exit": { "4_2": "1", "4_3": "1" } }, "x": "312", "y": "624" } ], [ { "connections": { "enter": { "3_1": "1" }, "exit": { "5_1": "1", "5_2": "1" } }, "x": "464", "y": "208" }, { "connections": { "enter": { "3_1": "1", "3_2": "1", "3_3": "1", "3_4": "1", "3_5": "1" }, "exit": { "5_2": "1", "5_3": "1" } }, "x": "464", "y": "344" }, { "connections": { "enter": { "3_5": "1" }, "exit": { "5_3": "1", "5_4": "1" } }, "x": "464", "y": "480" } ], [ { "connections": { "enter": { "4_1": "1" }, "exit": { "6_1": "1" } }, "x": "608", "y": "140" }, { "connections": { "enter": { "4_1": "1", "4_2": "1" }, "exit": { "6_1": "1", "6_2": "1", "6_3": "1" } }, "x": "608", "y": "280" }, { "connections": { "enter": { "4_2": "1", "4_3": "1" }, "exit": { "6_3": "1", "6_4": "1", "6_5": "1" } }, "x": "608", "y": "416" }, { "connections": { "enter": { "4_3": "1" }, "exit": { "6_5": "1" } }, "x": "608", "y": "552" } ], [ { "connections": { "enter": { "5_1": "1", "5_2": "1" }, "exit": { "7_1": "1", "7_2": "1" } }, "x": "760", "y": "72" }, { "connections": { "enter": { "5_2": "1" }, "exit": { "7_2": "1", "7_3": "1" } }, "x": "760", "y": "208" }, { "connections": { "enter": { "5_2": "1", "5_3": "1" }, "exit": { "7_3": "1" } }, "x": "760", "y": "344" }, { "connections": { "enter": { "5_3": "1" }, "exit": { "7_3": "1" } }, "x": "760", "y": "480" }, { "connections": { "enter": { "5_3": "1", "5_4": "1" }, "exit": { "7_3": "1", "7_4": "1" } }, "x": "760", "y": "624" } ], [ { "connections": { "enter": { "6_1": "1" }, "exit": { "8_1": "1" } }, "x": "920", "y": "140" }, { "connections": { "enter": { "6_1": "1", "6_2": "1" }, "exit": { "8_1": "1" } }, "x": "920", "y": "280" }, { "connections": { "enter": { "6_2": "1", "6_3": "1", "6_4": "1", "6_5": "1" }, "exit": { "8_1": "1" } }, "x": "920", "y": "416" }, { "connections": { "enter": { "6_5": "1" }, "exit": { "8_1": "1" } }, "x": "920", "y": "552" } ], [ { "connections": { "enter": { "7_1": "1", "7_2": "1", "7_3": "1", "7_4": "1" } }, "x": "1072", "y": "344" } ] ] ```

image

ValdemarGr commented 3 months ago

Mine does 1 second at 3440x1440, but it runs in Scala. It is probably significantly faster than AHK because of the runtime.

I have a bunch of optimizations I can do, so I think I can get it down to less than 200 ms, since my clustering currently is very naive ($$O(n^2)$$).

I think the algorithms for path clustering we use are equivalent (slime mold discovery and DBSCAN with optimizations).

If the tracing is what takes long you can consider doing a (simple) linear regression after the first bunch of pixels since that should point to the room in the same direction.

$$\hat{\alpha} = \bar{y} - (\hat{\beta} \bar{x})$$

$$\hat{\beta} = \frac{\sum_{i=1}^{n}(x_i - \bar{x})(yi - \bar{y})}{\sum{i=1}^{n}(x_i - \bar{x})^2}$$

$$\textit{room} = \textit{min}_{r \in R_x} \hat{\alpha} + \hat{\beta} x$$

The paths can overlap with the rooms, so you have to account for that. An early linear regression avoids this issue since it only needs to be confident in the direction to terminate. Here is an example: src

Lailloken commented 3 months ago

Thanks a lot for your inputs and your worst-case example, much appreciated. I have to admit that stuff goes waaaay over my head. As for the example: I managed to use your screenshot for calibration and testing, and my prototype connected that busy area in the center correctly.

image

I had already implemented some leeway to make it "jump" to distant markers. I just need to tweak it so that the leeway is smaller on the x-axis in order to prevent the tracing from jumping onto a different path altogether. The top-most path to room 5_2 almost connected to the one underneath towards the end because the corner occluded so many pixels. (I just realized that it wouldn't make a difference in this specific situation since both paths lead to the same room.)

I tried making it faster by means of "sparseness" (i.e. only scanning every nth line) but refrained from it for the sake of accuracy/consistency. I can still trim the areas that are scanned because they still have rather large buffer zones, but that's something for later stages.

Lailloken commented 3 months ago

I got some initial UI/UX testing done today and could need some feedback (colors, transparency levels, and other stylistic considerations are all subject to change):

ValdemarGr commented 3 months ago

Hey. Thats pretty cool!

Do you think it could be a good addition to not count rooms that had been banned (purple)? Does the path to node feature exclude banned rooms?

The "show path to node" seems very useful for reveal type strategies.

I think I personally would like the reachability paths of a room drawn, since this is probably the most universally useful thing. You usually always want to take the path that allows you to see as many rooms as possible, but sometimes the "best" path is blocked by a bad affliction, or maybe a good room is on an non-optimal path.

For optimal route planning (given you have the full room revealed), you'd probably want to with a something like a weighted sum. For example:

coins = 0.7
shop = 1.5
shrine = 0
pact = 0.9

Now there are numerous ways to compute this weighted sum, it could be forall rooms, compute the sum of the room types multiplied with the weight, say for coins -> coins -> shop -> shrine:

(coins + coins + shop + shrine)/4 = (0.7  + 0.7 + 1.5 + 0)/4 = 0.725

But there are also other considerations, such as, do I have enough coins for the shop and so on. It gets pretty gnarly and user-specific.

Room types don't matter for most players after the first couple of sanctums.

image

In this picture I take blue path since it has same room number as green (R: 12), because it has a tainted pact (the hands) since those can contain divines on floor 4. My point is that selecting the best route for every circumstance is a huge undertaking so making it easier for the user to plan the path might be the best for version 1 of the tool; give the tools and numbers for planning, but not necessarily do the plan.

Lailloken commented 3 months ago

Do you think it could be a good addition to not count rooms that had been banned (purple)? Does the path to node feature exclude banned rooms?

Yes that makes sense, good idea. Counting the connecting rooms was the last thing I implemented yesterday, so it doesn't interact with anything else yet. For simple testing, both markers and their paths use the same logic (with purple taking precedence), so purple paths simply overlap a green path. But it'll be easy to make a purple path completely cut it off instead, which would be the next step.


I think I personally would like the reachability paths of a room drawn, since this is probably the most universally useful thing. You usually always want to take the path that allows you to see as many rooms as possible, but sometimes the "best" path is blocked by a bad affliction, or maybe a good room is on an non-optimal path.

Drawing the paths has a nice ring to it, but I'd have to figure out how to do that efficiently in AHK (probably draw a transparent bitmap and overlay that) and it would also probably become quite "busy" on lower resolutions (I have to keep everything resolution agnostic). I therefore chose the number-tags as a possible alternative.

I photo "chopped" your screenshot to show what I currently have in mind, what it would look like, and how it could be used: image

Lailloken commented 3 months ago

A few small updates:

image

Lailloken commented 3 months ago

There's light at the end of the tunnel. If I find enough time tomorrow, I might be able to release an initial testing version. I have added another little option to manipulate the overlay: you can middle-click rooms to mark the room you're currently in, and the overlay will cull unnecessary information:

https://github.com/user-attachments/assets/2c3d63ed-96ae-4cfe-93db-15d79454e5ac

You can also hold middle-click and hover back and forth between multiple rooms to show and compare their respective reachability paths. I'm still hesistant to implement the full reachability tree, so I guess this could be another possible alternative to that.


At this point I would ask "is there anything else you'd want it to do?", but you've shown that you actually already have access to more elaborate techniques and possibilities. So instead: "Is there anything else I could implement that's useful to the average Sanctum runner?"

ValdemarGr commented 3 months ago

I think the features for an initial version are there. More elaborate or specific features will probably become apparent from "daily" usage of the tool; adding too many features to the initial version might be an instance of premature (feature) optimization.

Lailloken commented 3 months ago

v1.55.0 is now live. I had to delay it for a day because there were some unforeseen issues at lower resolutions that needed some ironing out.

I had to go into more detail than usual in the release notes because this feature can only perform well if the user sets it up correctly, which I feel is almost never the case.

You can give it a whirl if you like.

knot2006 commented 3 months ago

v1.55.0 is now live. I had to delay it for a day because there were some unforeseen issues at lower resolutions that needed some ironing out.

I had to go into more detail than usual in the release notes because this feature can only perform well if the user sets it up correctly, which I feel is almost never the case.

You can give it a whirl if you like.

Been trying to calibrate as best as I could but it still fails the scan on last row of rooms: sanctum scan sanctum scan

Lailloken commented 3 months ago

@knot2006 The issue is the icon of dark pact rooms. During calibration, you must have caught some pixel-colors that are also present in that icon:

image

The teal cross signals that the tool recognized a "loose end" there and cannot complete this specific path. You have to reset the pathing calibration by long-right-clicking the calibrate paths button, then redo it.