Help - Search - Members - Calendar
Full Version: Pathfinder
Braindead's Mordor Site - Return to Mordor: The Depths Of Dejenol > Mordor: The Depths Of Dejenol > Modding And Development
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
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. wallbash.gif blush2.gif

Would it be too much to ask someone to record taking these routes and upload it to youtube?
Mordion
QUOTE (Nudibranch @ Sep 24 2018, 10:36 AM) *
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. wallbash.gif blush2.gif

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. smile.gif

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
QUOTE (Danjen @ Sep 25 2018, 03:55 AM) *
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.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Invision Power Board © 2001-2019 Invision Power Services, Inc.