Pathfinder Options

[Mordion]

I just wrote a program that will find the shortest path from A to B in the dungeon. Are there any routes you'd like to see? Here's the fastest route to 15

CODE

9,11,1
9,12,1
8,12,1
7,12,1
7,11,1
7,10,1
7,9,1
7,8,1
8,8,1
9,8,1
10,8,1
10,7,1
10,6,1
9,6,1
8,6,1
7,6,1
7,6,2
7,7,2
8,7,2
8,6,2
9,6,2
10,6,2
10,7,2
10,8,2
10,9,2
10,10,2
9,10,2
9,11,2
9,12,2
9,13,2
10,13,2
11,13,2
11,14,2
12,14,2
13,14,2
13,15,2
14,15,2
15,15,2
16,15,2
16,14,2
17,14,2
17,13,2
17,13,3
17,14,3
17,15,3
17,16,3
18,16,3
19,16,3
20,16,3
20,17,3
20,18,3
20,19,3
21,19,3
22,19,3
22,20,3
21,20,3
21,20,4
20,20,4
20,20,5
21,20,5
21,20,6
21,21,6
21,22,6
21,23,6
21,24,6
21,25,6
21,26,6
20,26,6
19,26,6
18,26,6
17,26,6
16,26,6
16,27,6
16,28,6
16,29,6
15,29,6
14,29,6
14,28,6
13,28,6
12,28,6
11,28,6
11,29,6
11,29,7
11,30,7
10,30,7
10,30,10
11,30,10
11,29,10
12,29,10
13,29,10
13,30,10
14,30,10
15,30,10
15,29,10
16,29,10
17,29,10
17,30,10
18,30,10
19,30,10
20,30,10
20,30,13
20,29,13
21,29,13
22,29,13
23,29,13
23,28,13
24,28,13
24,27,13
24,26,13
24,25,13
24,24,13
24,23,13
24,22,13
23,22,13
23,21,13
23,20,13
23,19,13
23,18,13
23,17,13
23,16,13
22,16,13
21,16,13
21,15,13
21,14,13
20,14,13
20,13,13
20,12,13
21,12,13
22,12,13
22,13,13
22,14,13
23,14,13
23,13,13
23,13,14
24,13,14
24,12,14
24,11,14
24,10,14
23,10,14
22,10,14
21,10,14
20,10,14
19,10,14
18,10,14
17,10,14
16,10,14
15,10,14
14,10,14
14,9,14
14,8,14
14,7,14
15,7,14
16,7,14
17,7,14
17,6,14
17,5,14
17,4,14
17,3,14
16,3,14
15,3,14
15,2,14
14,2,14
13,2,14
13,3,14
13,4,14
13,4,15

and back

CODE

13,4,15
13,3,15
13,3,14
13,2,14
14,2,14
15,2,14
15,3,14
16,3,14
17,3,14
17,4,14
17,5,14
17,6,14
17,7,14
16,7,14
15,7,14
14,7,14
14,8,14
14,9,14
14,10,14
15,10,14
16,10,14
17,10,14
18,10,14
19,10,14
20,10,14
20,11,14
20,12,14
21,12,14
22,12,14
23,12,14
24,12,14
24,13,14
23,13,14
23,13,13
23,14,13
22,14,13
22,13,13
22,12,13
21,12,13
20,12,13
20,13,13
20,14,13
19,14,13
19,13,13
19,12,13
18,12,13
17,12,13
16,12,13
15,12,13
14,12,13
14,11,13
13,11,13
12,11,13
12,10,13
11,10,13
10,10,13
10,9,13
9,9,13
8,9,13
7,9,13
6,9,13
5,9,13
4,9,13
4,8,13
4,7,13
3,7,13
2,7,13
2,6,13
1,6,13
1,6,12
1,7,12
1,8,12
1,9,12
1,10,12
1,11,12
1,12,12
1,13,12
2,13,12
2,14,12
2,15,12
2,16,12
1,16,12
1,17,12
1,18,12
1,19,12
2,19,12
3,19,12
4,19,12
4,20,12
4,21,12
5,21,12
6,21,12
7,21,12
7,20,12
7,19,12
8,19,12
8,19,11
8,20,11
8,21,11
9,21,11
10,21,11
11,21,11
11,22,11
11,22,10
11,21,10
11,20,10
11,19,10
11,18,10
11,17,10
11,16,10
11,15,10
11,14,10
11,13,10
11,12,10
12,12,10
13,12,10
13,11,10
12,11,10
11,11,10
10,11,10
10,12,10
9,12,10
8,12,10
8,11,10
7,11,10
6,11,10
5,11,10
4,11,10
4,12,10
4,13,10
3,13,10
3,14,10
3,15,10
4,15,10
4,16,10
4,17,10
3,17,10
2,17,10
1,17,10
1,18,10
2,18,10
3,18,10
3,18,9
3,17,9
3,16,9
3,15,9
4,15,9
4,14,9
4,13,9
4,12,9
3,12,9
2,12,9
2,13,9
2,14,9
2,15,9
2,16,9
1,16,9
1,17,9
1,18,9
2,18,9
2,19,9
2,20,9
3,20,9
3,21,9
3,22,9
3,23,9
3,24,9
4,24,9
4,25,9
4,26,9
3,26,9
3,27,9
4,27,9
3,2,8
3,3,8
2,3,8
2,4,8
2,5,8
2,6,8
2,7,8
2,8,8
2,9,8
2,10,8
2,11,8
1,11,8
1,12,8
1,13,8
1,14,8
2,14,8
3,14,8
3,15,8
2,15,8
1,15,8
1,16,8
1,17,8
1,18,8
1,19,8
1,20,8
2,20,8
2,20,7
2,21,7
3,21,7
3,22,7
3,23,7
3,24,7
3,25,7
3,26,7
4,26,7
5,26,7
5,27,7
5,28,7
6,28,7
7,28,7
8,28,7
8,27,7
8,26,7
8,25,7
9,25,7
10,25,7
11,25,7
12,25,7
13,25,7
14,25,7
15,25,7
16,25,7
17,25,7
17,26,7
16,26,7
15,26,7
15,27,7
15,28,7
14,28,7
13,28,7
13,27,7
12,27,7
12,28,7
12,29,7
11,29,7
11,29,6
11,28,6
12,28,6
13,28,6
13,29,6
14,29,6
15,29,6
16,29,6
16,28,6
16,27,6
16,26,6
16,25,6
16,24,6
16,23,6
17,23,6
18,23,6
19,23,6
20,23,6
21,23,6
21,22,6
21,21,6
21,20,6
21,20,5
22,20,5
23,20,5
23,20,4
24,20,4
25,20,4
25,21,4
25,22,4
25,23,4
24,23,4
23,23,4
23,24,4
22,24,4
22,25,4
21,25,4
21,24,4
21,23,4
21,22,4
21,21,4
21,20,4
21,20,3
22,20,3
22,19,3
22,18,3
21,18,3
20,18,3
20,17,3
20,16,3
19,16,3
18,16,3
17,16,3
17,15,3
17,14,3
17,13,3
17,12,3
18,12,3
18,11,3
18,10,3
17,10,3
16,10,3
15,10,3
14,10,3
13,10,3
12,10,3
12,11,3
12,12,3
12,13,3
12,13,2
11,13,2
10,13,2
9,13,2
9,12,2
9,11,2
9,10,2
10,10,2
10,9,2
10,8,2
10,7,2
10,6,2
9,6,2
9,7,2
8,7,2
7,7,2
7,6,2
7,6,1
8,6,1
9,6,1
10,6,1
10,7,1
10,8,1
9,8,1
8,8,1
7,8,1
7,9,1
7,10,1
7,11,1
7,12,1
8,12,1
9,12,1
9,11,1

[Mordion]

I tweaked it to give it one use of Ethereal portal and it shaved off 15 steps. All of these paths surprise me. I guess I'm just old fashioned for taking the stairs.

CODE

9,11,1
9,12,1
8,12,1
7,12,1
7,11,1
7,10,1
7,9,1
7,8,1
8,8,1
9,8,1
10,8,1
10,7,1
10,6,1
9,6,1
8,6,1
7,6,1
7,6,2
7,5,2
6,5,2
5,5,2
5,6,2
5,7,2
4,7,2
3,7,2
3,8,2
3,8,3
2,8,3
2,9,3
3,9,3
3,10,3
3,11,3
3,12,3
3,13,3
3,14,3
3,15,3
3,16,3
2,16,3
1,16,3
1,17,3
22,20,3
21,20,3
21,20,4
20,20,4
20,20,5
21,20,5
21,20,6
21,21,6
21,22,6
21,23,6
20,23,6
19,23,6
18,23,6
17,23,6
16,23,6
16,24,6
16,25,6
16,26,6
16,27,6
16,28,6
16,29,6
15,29,6
14,29,6
13,29,6
13,28,6
12,28,6
11,28,6
11,29,6
11,29,7
11,30,7
10,30,7
10,30,10
11,30,10
12,30,10
12,29,10
13,29,10
14,29,10
14,30,10
15,30,10
15,29,10
16,29,10
17,29,10
18,29,10
18,30,10
19,30,10
20,30,10
20,30,13
20,29,13
21,29,13
22,29,13
23,29,13
24,29,13
24,28,13
24,27,13
24,26,13
24,25,13
24,24,13
24,23,13
24,22,13
23,22,13
23,21,13
23,20,13
23,19,13
23,18,13
22,18,13
22,17,13
22,16,13
21,16,13
21,15,13
20,15,13
20,14,13
20,13,13
20,12,13
21,12,13
22,12,13
22,13,13
22,14,13
23,14,13
23,13,13
23,13,14
24,13,14
24,12,14
23,12,14
22,12,14
21,12,14
20,12,14
20,11,14
20,10,14
19,10,14
18,10,14
17,10,14
16,10,14
15,10,14
14,10,14
14,9,14
14,8,14
14,7,14
15,7,14
16,7,14
17,7,14
17,6,14
17,5,14
17,4,14
17,3,14
16,3,14
15,3,14
15,2,14
14,2,14
13,2,14
13,3,14
13,4,14
13,4,15

This post has been edited by Mordion: Sep 22 2018, 05:58 PM

[Roland]

I usually start by teleporting from the city stairs to 21,20,4. From there, I follow your path to the chute from level 7 to level 10. I didn't know about the chute from 10 to 13 - I'll have to try that. Thanks!

[korexus]

Nice, but the real problem here will be overcoming the muscle memory my fingers have for navigating! It might be fewer steps, but it would be months before a new route took less time for me to follow...

[Nudibranch]

After years of walking down to 15, I starting using my giant to cast Teleport, which is definitely the fastest way down. Biggest drawback is that if you get careless, it is occasionally the fastest way to 16.

Would it be too much to ask someone to record taking these routes and upload it to youtube?

[Mordion]

After years of walking down to 15, I starting using my giant to cast Teleport, which is definitely the fastest way down. Biggest drawback is that if you get careless, it is occasionally the fastest way to 16.

Would it be too much to ask someone to record taking these routes and upload it to youtube?

I would but I can't make it to 15 yet.

[Danjen]

How did you get the data for the routes? Like did you manually plug the numbers into an array, or did you read the files from the game directly?

[Mordion]

How did you get the data for the routes? Like did you manually plug the numbers into an array, or did you read the files from the game directly?

I loaded the map data from mdata11. The specs are on the wiki. Then I wrote a search algorithm to find a path. I cut some corners by assuming everything costs one step. I’d like to do one with varying costs so that I could find paths that use ethereal portal but only if it saves more than X steps.

One quirk of the algorithm is that it finds the shortest path to every square of the dungeon from a single start point. Or, with the reverse path function, the path from every square of the dungeon to a specific point. By generating both I could then search the dungeon for two squares on opposite sides of a wall with a big gap in cost and cut it out. But this doesn’t generalize to multiple shortcuts.

I’ll see about uploading a binary but right now it’s Mac only.